A practical method for implementing string pattern matching machines
A practical method for implementing string pattern matching machines
复制标题
一种实现字符串模式匹配机的实用方法
DOI：
10.1016/0020-0255(92)90113-m
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
J. Aoe
中科院分区：
文献类型：
--
作者：
J. Aoe
本文提出了一种紧凑、快速的数据结构来实现字符串模式匹配机的静态转换表，该转换表可以定位文本字符串中有限个关键字的所有出现。该方法涉及到一种用于实现有限状态机转换表的三数组结构，并且该结构已被许多用户用作UNIX系统中的编译器-编译器LEX和YACC。通过将有限状态机的转换表限制为字符串模式匹配机的转换表，可以将三数组结构减少为两个数组的结构。匹配算法可以通过一个有限的无循环的直接程序来加速。理论和实验结果表明，采用该结构的模式匹配机比采用三重阵列的模式匹配机体积小33%，速度快1.3倍。
A compact and fast data structure is presented to implement the static transition table of a string pattern matching machine that locates all occurrences of a finite number of keywords in a text string. The approach is related to a triple-array structure for implementing the transition table of a finite state machine, and the structure has been utilized by many users as compiler-compilers LEX and YACC in UNIX systems. By restricting the transition table of the finite state machine to that of the string pattern matching machine, the triple-array structure can be reduced to a structure of two arrays. The matching algorithm can be speeded up by a finite straight program without loops. It is shown by theoretical and empirical observations that the pattern matching machine by the presented structure is about 33% smaller and about 1.3 times faster than that by the triple array.