EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH
EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH
复制标题
DOI：
10.1145/360825.360855
复制
发表时间：
1975-01-01
影响因子：
22.7
通讯作者：
CORASICK, MJ
中科院分区：
文献类型：
--
作者：
AHO, AV;CORASICK, MJ
本文描述了一个简单，有效的算法来定位所有出现的任何一个有限数量的关键字在一个字符串的文本。该算法由关键字构造一个有限状态模式匹配机，然后使用模式匹配机处理文本串在一个单一的通行证。模式匹配机器的构造所花费的时间与关键字的长度之和成比例。模式匹配机在处理文本串时进行的状态转换的数量与关键字的数量无关。该算法已被用来提高图书馆书目检索程序的速度的5至10倍。
This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.