基于自动机的正则表达式匹配算法

摘要

随着计算机科学的不断发展，信息数据量呈爆炸性增长，给数据处理工作带来了一定的挑战，用户的查询也变的越来越复杂。由于需要处理的数据规模越来越大，进行的搜索也越来越困难，正则表达式作为一种可定义复杂查询的强有力工具为处理文本搜索问题提供了一种灵活而又高效的方法。如今，正则表达式的应用已经涉及到很多领域，为查询处理提供了方便。如何快速高效地响应正则表达式查询也变得至关重要。
　　目前，已提出了很多解决正则表达式匹配的方法。这些方法基本上都是对正则表达式进行在线搜索，即预先没有对要查询的文本做任何处理，根据其匹配的原理大致可分为三种:基于NFA的正则表达式匹配;基于DFA的正则表达式匹配;基于过滤方法的正则表达式匹配。其中，基于过滤方法的正则表达式匹配方法目前使用的比较多，查询性能较高，但是现有的过滤方法只是针对某些结构的正则表达式效果较明显，而正则表达式本身的结构非常复杂，如何选择一种更优的过滤方法来满足正则表达式的查询需求整体提高正则表达式的查询性能是一项很具挑战性的工作。
　　本文根据正则表达式的特点，针对数据文件是否预先被处理这两种情况，提出了相应的正则表达式在线与离线查询处理技术。在未索引数据文件的情况下，从正则表达式中提取出可以很好地代表该表达式的最佳因子集合，然后根据最佳因子的个数来选择使用单字符串查询的BM算法或多字符串查询的CW算法在数据文件中找到包含最佳因子的候选字符串，最后在DFA上对候选字符串进行验证。在索引数据文件的情况下，本文提出了三种索引结构，基于基本后缀树的索引、基于扩展后缀树的索引和基于聚类的索引。基于后缀树索引的方法是在后缀树上查找有最佳因子出现的字符串集合，再对其验证。基于聚类索引的方法是先使用聚类方法对字符串集合进行聚类，从每个类提取出公共子串，根据类中的公共子串是否被DFA所识别来进行过滤。最后，在基于真实与模拟数据集上的大量实验测试结果表明，本文所提出的在线和离线处理技术能够高效地支持正则表达式查询处理。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 本文的研究内容及面临的挑战

1．3 本文的贡献

1．4 本文的组织结构

第2章 相关工作

2．1 子串查询算法

2．1．1 子串查询定义

2．1．2 Boyer-Moore算法

2．1．3 Knuth-Morris-Pratt算法

2．2 正则表达式查询算法

2．2．1 基于NFA的正则表达式匹配

2．2．2 基于DFA的正则表达式匹配

2．2．3 基于过滤方法的正则表达式匹配

2．3 本章小结

第3章 背景知识与问题定义

3．1 后缀树索引

3．2 Commentz-Walter多字符串查询算法

3．3 k-means聚类算法

3．4 问题定义

3．5 本章小结

第4章 在线正则表达式查询处理方法

4．1 基于最佳因子的过滤策略

4．2 最佳因子的提取

4．3 正则表达式在线处理算法

4．4 本章小结

第5章 基于索引的正则表达式查询处理方法

5．1 基于后缀树索引的查询算法

5．1．1 后缀树索引的构建

5．1．2 基本查询算法

5．1．3 优化查询算法

5．2 基于聚类索引的查询算法

5．2．1 聚类索引的构建

5．2．2 查询算法

5．3 本章小结

第6章 实验与分析

6．1 实验设置

6．2 在线正则表达式查询的实验与分析

6．3 离线正则表达式查询的实验与分析

6．3．1 索引构建评估

6．3．2 查询时间评估

6．4 本章小结

第7章 结束语

7．1 本文总结

7．2 工作展望

参考文献

致谢

攻硕期间参加的项目及发表的论文