一种快速字串交叉模式匹配算法.pdf

37 3 上 海 交 通 大 学 学 报 Vol. 37 No. 3 2003 3 JOURNAL OF SHANGHAI JIAOT ONG UNIVERSIT Y Mar. 2003 : 1006-2467( 2003) 03-0420-04 鲍峥嵘, 　王永成, 　刘功申, 　韩客松 ( , 200030) : 介绍了一种基于高频字串 取的快速字串交叉模式匹配算法, 同已有的KMP、BM 等单 模式匹配算法和有限自动机等多模式匹配算法相比, 在字符集 较大且字串 个数远大于字串最大 2 长度的情况下, 该算法具有较低的时间复杂度和空间复杂度, 并适用于字符集较大, 词长较短的文 本处理. : 模式匹配; 高频字串; 算法 : T P301. 6: A A Fast Algorit hm on St ring Cross Pattern Matching BA O Zheng-rong , WA N G Yong-cheng , L I U Gong-shen, H A N K e-song ( . . , . , 200030, ) Dept of Computer Science Eng Shanghai Jiaotong Univ Shanghai China Abstract: This paper presented a fast string pattern matching algorithm based on extracting high frequency strings. Compared w ith the existing algorithms including single-pattern algorithms, such as KMP and BM , - , , algorithm and multi pattern matching algorithms such as DFA this algorithm has both lower time and space complexity w hen the size of 2 is large and the number of strings is far more than the max length of string in set U. As Chinese character set is large and the average length of Chinese w ords is much short, this algorithm is more suitable to process Chinese text. : ; ; Key words pattern matching high frequency string algorithm , , GOTO [ 1] [ 2] , , 2 . , . HASH [ 6] 2