|Table of Contents|

Improved Multi-keyword Matching Algorithm

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

Issue:
2005年06期
Page:
735-739
Research Field:
Publishing date:

Info

Title:
Improved Multi-keyword Matching Algorithm
Author(s):
DAI Liu-ling~
1,2),WANG Shu-mei~1,HUANG He-yan~2,CHEN Zhaoxiong~2
Keywords:
mult-i keyword matching BM algorithm QS algorithm Sun Wu algorithm
PACS:
TP301.6
DOI:
-
Abstract:
An improved algorithm for matching multiple strings is suggested. The new algorithm, named QMS (Quick Mult-i pattern Searching) , is based on the analysis of Sun Wu algorithm and the idea of QS algorithm. QMS uses hashing and PREFIX table to decrease the number of comparisons. During the computation of the shift distance, the character closely after the current window is considered. Thus shift distances are computed with more accurate technique, and larger average shift distance is acquired. The scanning efficiency and the space utility are improved in result. Series of tests on an actual corpus show that QMS algorithm is much more efficient than Sun Wu algorithm under usual circumstances.

References:

[ 1] Boyer R S, Moore J S. A fast string searching algorithm[ J] . Communications of the ACM, 1977, 20: 762- 772.
[ 2] Sunday DM. A very fast substring search algorithm[ J] . Communications of the ACM, 1990, 33( 8) : 132- 142.
[ 3] Lecroq T. Experimental results on string matching algorithms [ J] . Software- Practice & Exper ience 1995, 25 ( 7) : 727 - 765.
[ 4] Wu S, Manber U. A Fast Algorithm for Mult-i pattern Searching[ R] . Arigona: Computer Science Department, University of Arizona, 1994.
[ 5] David L. The Reuters- 21578 text categorization test collection. http: / /www. research. att. com/- lewis/ reuters 21578. html. 1998- 05- 11.

Memo

Memo:
-
Last Update: 2013-03-03