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

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

论文摘要

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

论文目录

  • 摘要
  • Abstract
  • 第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 工作展望
  • 参考文献
  • 致谢
  • 攻硕期间参加的项目及发表的论文
  • 相关论文文献

    • [1].用JS与正则表达式验证表单数据格式的方法[J]. 知识文库 2016(14)
    • [2].一种新型动态可重构的正则表达式匹配引擎设计[J]. 复旦学报(自然科学版) 2019(06)
    • [3].请个伙伴,助你成长为正则表达式高手[J]. 电脑爱好者 2008(23)
    • [4].正则表达式方程组的最小解[J]. 电脑与信息技术 2011(05)
    • [5].正则表达式随笔[J]. 程序员 2008(03)
    • [6].正则表达式快速入门[J]. 电脑知识与技术 2019(29)
    • [7].基于正则表达式构建学习的网页信息抽取方法[J]. 计算机应用与软件 2017(02)
    • [8].浅谈正则表达式在方正书版中的应用[J]. 广东印刷 2015(01)
    • [9].基于预定义类的紧凑型正则表达式匹配算法[J]. 计算机应用 2017(02)
    • [10].一种正则表达式匹配的存储空间优化技术[J]. 现代计算机(专业版) 2017(20)
    • [11].支持多正则表达式匹配的硬件结构[J]. 清华大学学报(自然科学版) 2009(10)
    • [12].利用正则表达式进行查找/替换[J]. 中国科技期刊研究 2009(01)
    • [13].正则表达式随笔(续)[J]. 程序员 2008(09)
    • [14].一种支持多正则表达式匹配的硬件结构[J]. 清华大学学报(自然科学版)网络.预览 2009(10)
    • [15].正则表达式及其应用[J]. 电脑编程技巧与维护 2012(04)
    • [16].基于变长切换的多数据流正则表达式匹配[J]. 计算机工程与设计 2013(11)
    • [17].浅析正则表达式[J]. 科技资讯 2010(04)
    • [18].基于正则表达式度量算法的智能评分设计[J]. 电脑知识与技术 2016(35)
    • [19].试议VB.NET中查找替换中正则表达式的使用[J]. 电脑编程技巧与维护 2015(08)
    • [20].正则表达式的实现[J]. 科技创新导报 2010(20)
    • [21].正则表达式在python爬虫中的应用[J]. 电脑知识与技术 2019(25)
    • [22].巧用替换 成批“标题”自动加——也谈“正则表达式”替换实用案例[J]. 电脑爱好者 2011(06)
    • [23].JavaScript技术利用正则表达式验证表单的探讨[J]. 电脑知识与技术 2019(24)
    • [24].基于正则表达式的图像目标特征提取方法研究[J]. 计算机应用与软件 2018(04)
    • [25].面向高效深度包检测的启发式正则表达式分组算法[J]. 计算机应用研究 2018(07)
    • [26].正则表达式优化算法研究[J]. 电脑知识与技术 2012(05)
    • [27].基于正则表达式的客户端数据校验方法研究[J]. 网络与信息 2010(04)
    • [28].基于正则表达式的限制性路径规划[J]. 华东师范大学学报(自然科学版) 2017(05)
    • [29].基于嵌套正则表达式的RDF图数据属性路径查询及推理[J]. 小型微型计算机系统 2015(08)
    • [30].基于正则表达式的结构化修复改进算法[J]. 电子测量与仪器学报 2017(12)

    标签:;  ;  ;  ;  ;  ;  

    基于自动机的正则表达式匹配算法
    下载Doc文档

    猜你喜欢