Approximate String Matching Algorithm Using Multiple-Character Inverted Lists
Soontaree Thumsuwan, Nuanprang Sangurai, Chouvalit Khancome · 2024
Approximate string matching algorithms, which permit mismatched characters, are extensively employed in software featuring search tools, database management systems, and various applications and online services. Consequently, the development of new algorithms to facilitate faster and more accurate searches continues to pose a significant challenge for researchers. This research article introduces a novel approximate string matching algorithm, designated as m-IVLASM, derived from the Multiple-Character Inverted Lists data structure traditionally utilized for single pattern string matching. The proposed algorithm exhibits flexibility by allowing adjustable search parameters for each query, thereby enhancing search speed and efficiency compared to conventional methods. Operating in linear time, the algorithm demonstrates superior performance. Experimental results, derived from both random data and real-world datasets, provide compelling evidence that the new method significantly surpasses previous approaches in terms of effectiveness. The optimal efficiency for character length factor splitting was identified at values of 0.5 and 0.8.