Commentz-Walter algorithm
In computer science, the Commentz-Walter algorithm is a string searching algorithm invented by Beate Commentz-Walter.[1] Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the Boyer–Moore string search algorithm. For a text of length n and maximum pattern length of m, its worst-case running time is O(mn), though the average case is often much better.[2]
GNU grep implements a string matching algorithm very similar to Commentz-Walter.[3]
References
- Commentz-Walter, Beate (1979). A String Matching Algorithm Fast on the Average (PDF). International Colloquium on Automata, Languages and Programming. LNCS. Vol. 71. Graz, Austria: Springer. pp. 118–132. doi:10.1007/3-540-09510-1_10. ISBN 3-540-09510-1. Archived from the original (PDF) on 2017-10-10.
- Watson, Bruce William (1995-09-15). Taxonomies and toolkits of regular language algorithms. Eindhoven University of Technology. doi:10.6100/IR444299. ISBN 90-386-0396-7.
- "src/kwset.c: search for any of a set of keywords". GNU grep. August 1989. Retrieved 2020-07-14.
External links
- Sheshasaayee, Ananthi; Thailambal, G. (March 2017). "Performance of Multiple String Matching Algorithms in Text Mining". Proceedings of the 5th International Conference on Frontiers in Intelligent Computing: Theory and Applications. Advances in Intelligent Systems and Computing. Vol. 516. pp. 671–681. doi:10.1007/978-981-10-3156-4_71. ISBN 978-981-10-3155-7.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.