Name
Abstract | ||
|---|---|---|
Based on deep analysis of Boyer-Moore algorithm and Quick Search algorithm, we propose a faster algorithm for single pattern matching by utilizing the continuous skip over the text, this idea enables its high performance because of the large shift on the text, its best time complexity is O(n/(m+1)), which is an inspiring research result. We also discuss the average time complexity of this suggested algorithm, which demonstrates and proves its high efficiency. Our experimental result shows that the algorithm is superior to other algorithms for pattern matching, such as Boyer-Moore algorithm, Quick Search algorithm, Shift Or algorithm, Reverse Factor algorithm, Reverse Colussi algorithm, Improved Apostolico-Giancarlo algorithm and so on. Especially, when the pattern is smaller, our algorithm is more efficient than other algorithms, which is very practical in natural language text retrieval. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1145/355214.355231 | IRAL |
Keywords | Field | DocType |
suggested algorithm,boyer-moore algorithm,factor algorithm,colussi algorithm,pattern matching,natural language text retrieval,faster algorithm,single pattern,improved apostolico-giancarlo algorithm,quick search algorithm,boyer moore algorithm,time complexity | Ramer–Douglas–Peucker algorithm,Search algorithm,Commentz-Walter algorithm,Computer science,In-place algorithm,Algorithm,FSA-Red Algorithm,Rabin–Karp algorithm,Shortest Path Faster Algorithm,Population-based incremental learning | Conference |
ISBN | Citations | PageRank |
1-58113-300-6 | 1 | 0.37 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Han Kesong | 1 | 46 | 3.94 |
| Wang Yongcheng | 2 | 1 | 0.70 |
| Chen Guilin | 3 | 9 | 6.24 |