Backward Inverted Lists Approximate String Matching Algorithm
Nuanprang Sangurai, Soontaree Thumsuwan, Chouvalit Khancome · 2024
Approximate String Matching is a principle of data retrieval that allows for typos or misspelled words. It is widely applied in database management systems, search engines, and even in various applications and online services. Therefore, constantly seeking new algorithms to search for data quickly and accurately is a constant challenge for computer science researchers. This research article presents a new Approximate String Matching Algorithm utilizing a novel data structure called Backward Inverted Lists, which is an advancement of the Inverted Lists data structure commonly used for Single pattern String Matching. This new data structure enables the new Approximate String Matching Algorithm proposed in this research to efficiently detect Edit-distance values faster and more efficiently than conventional baseline methods. The newly proposed algorithm demonstrates low computational complexity and time, operating in linear time, making data retrieval faster than commonly used algorithms. Experimental results provide clear evidence that the new method outperforms previous methods significantly in both random data retrieval and real data retrieval from genome and DNA sequences. Additionally, the Backward Inverted Lists data structure exhibits flexibility and can be extended to support the development of various searching and approximate string matching algorithms in the future.