ISSN 1000-9825, CODEN RUXUEW Journal of Software, Vol.19, No.3, March 2008, pp.674686 DOI: 10.3724/SP.J.1001.2008.00674 2008 by Journal of Software. All rights reserved.
E-mail: jos@iscas.ac.cn http://www.jos.org.cn Tel/Fax: +86-10-62562563
面向中英文混合环境的多模式匹配算法
孙钦东 1,2+, 黄新波 3, 王 倩 1
1 2 3
(西安理工大学 计算机科学与工程学院,陕西 西安 (西安交通大学 电子与信息工程学院,陕西 西安 (西安工程大学 电子信息学院,陕西 西安
710048) 710049)
710048)
Multiple Pattern Matching on Chinese/English Mixed Texts
SUN Qin-Dong1,2+,
1 2 3
HUANG Xin-Bo3,
WANG Qian1
(School of Computer Science and Engineering, Xi'an University of Technology, Xi'an 710048, China) (School of Electronics and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China) (College of Electronics and Information, Xi'an Polytechnic University, Xi'an 710048, China)
+ Corresponding author: Phn: +86-29-82312231, E-mail: sqd@xanet.edu.cn
Sun QD, Huang XB, Wang Q. Multiple pattern matching on Chinese/English mixed texts. Journal of Software, 2008,19(3):674686. http://www.jos.org.cn/1000-9825/19/674.htm Abstract: The characteristics of multiple pattern matching in mixed Chinese and English text and the problem of
the existing multiple pattern matching algorithms used for processing mixed Chinese and English text are analyzed. A theorem of multiple pattern matching in mixed Chinese and English text is discovered and proved. A novel multiple pattern matching algorithm based on the threaded trie tree is proposed, which expands the standard trie structure, constructs the hash trie matching machine with the codes of Chinese and English characters, and threads the trie tree according to the characteristic of patterns set. The proposed algorithm does not need complex hash operation, and the matching pointer does not need backdate during matching. Theoretic analysis and experimental results demonstrate that the proposed algorithm efficiently solves the space expansion problem, and process mixed Chinese and English text correctly and efficiently with lower time and space complexity. Key words: 摘 要: multiple pattern matching; Chinese/English mixed; Hash; Trie

下一页