论文部分内容阅读
正则表达式匹配在计算机科学中有着广泛的应用。非确定性有限状态自动机(NFA)是实现正则表达式匹配的重要方法,主流的非确定性有限状态自动机一般分为两类,一类为Thompson架构,由K.Thompson于上世纪60年代提出,Thompson架构思路简洁,但是存在大量冗余状态,与空状态转换(e-transiton),典型的Thompson架构存在大约2m个状态(其中m为正则表达式长度);还有一类为Glushkov架构,相比之下,Glushkov架构具有两大优点:其一没有空状态转换;其二Glushkov自动机状态数等于正则表达式长度加1。没有空转换使得Glushkov架构转换数目较Thompson架构要少,状态数等于正则表达式长度加一,使得自动机的状态与正则表达式的位置能方便的建立起对应关系,因此Glushkov自动机又叫位置自动机,并可以采用比特并行的方式实现活跃状态集转换。此外,与Glushkov类似的Follow自动机也没有空转换,Follow自动机根据状态的Follow集元素分类,将Glushkov自动机的部分状态合并,拥有更少的状态数,从而在理论上拥有较Glushkov自动机更好的性能。本文主要工作是研究了位置自动机的高效比特并行实现方法并进行了实验验证。一方面研究了改进Glushkov自动机的比特并行匹配方法。由Glushkov状态的性质,通过自动机状态分类处理,对Glushkov自动机的Navarro-Raffinot方法(NR方法)进行了改进。本文研究了“扩散函数与提取函数”、“位扩展”等方法实现进一步的空间压缩。对于特殊的位置无冲突集合,应用扩散与提取函数能在单位时间内完成一个字长的匹配工作,应用位扩展方法对于一般的位置冲突向量也能在单位时间实现比特并行匹配;另一方面比较了Glushkov及Follow两类自动机性能。对于某些特例,Follow自动机具有好于Glushkov自动机的性能,而从总体上来看,在正则表达式子串数目较少时,Follow自动机的状态数均值上界小于Glushkov自动机,此时Follow自动机平均性能优于Glushkov自动机,随着正则表达式子串数目逐渐增大,Follow自动机的状态数均值上界与Glushkov自动机状态数均值上界基本一致,这意味着两类自动机平均性能是相同的。