WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2872
Volume 22, 2023
String Matching Algorithm Using Multi-Characters Inverted Lists
Author:
Abstract: This research article introduces a new string-matching algorithm that utilizes the multi-character inverted lists structure, implemented using a perfect hashing method. The new solution processes the pattern input string in a single pass. In the searching phase, the algorithm takes a linear time complexity. This approach demonstrates efficient and rapid performance in practical experiments when a binary character set is used. It also handles fewer characters and shorter lengths, even when the pattern length is increased. In some cases, this algorithm exhibits superior text search performance compared to other algorithms. It has been observed that this superiority is particularly evident when searching for smaller amounts of text. This algorithm can be explored more quickly, especially when the search factor is between 0.25 to 0.75 times the length of the pattern, approaching the performance of the traditional algorithm.
Search Articles
Keywords: String Matching Algorithm, Inverted Lists, Inverted Index, Pattern Matching, Exact String Matching
Pages: 151-158
DOI: 10.37394/23205.2023.22.18