doi: 10.7763/IJCTE.2010.V2.166
Inverted Lists String Matching Algorithms
Chouvalit Khancome1
,
Veera Boonjing2
- 1King Mongkut’s Institute of Technology Ladkrabang, Thailand.
- 2King Mongkut’s Institute of Technology Ladkrabang, Thailand. Also.
Abstract
This research article presents two algorithms of string pattern matching. These algorithms employ a new data structure called inverted lists structure which is inherited from the inverted index to accommodate a string pattern to be searched. The first solution scans the given text in a single pass for all occurrences of string pattern. The second solution, which improves the first one, takes the comparison times equal to the length of pattern plus the numbers of comparison that lead to be mismatched. For experimental results, these algorithms are efficient in the case of small alphabet sizes.
Keywords
- string pattern matching
- inverted lists (IVL)
- inverted index
- string algorithm
How to Cite
Chouvalit Khancome and Veera Boonjing, "Inverted Lists String Matching Algorithms," International Journal of Computer Theory and Engineering, vol. 2, no. 3, pp. 352-357, 2010. https://doi.org/10.7763/IJCTE.2010.V2.166
Copyright & License
Copyright © 2010 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).