Comparison of fuzzy search algorithms based on Damerau-Levenshtein automata on large data

Kyrylo Kleshch () and Volodymyr Shablii
Additional contact information
Kyrylo Kleshch: National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»
Volodymyr Shablii: National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

Technology audit and production reserves, 2023, vol. 4, issue 2(72), 27-32

Abstract: The object of research is fuzzy search algorithms based on Damerau-Levenshtein automata and Levenshtein automata. The paper examines and compares solutions based on finite state machines for efficient and fast finding of words and lines with a given editing distance in large text data using the concept of fuzzy search.Fuzzy search algorithms allow finding significantly more relevant results than standard explicit search algorithms. However, such algorithms usually have a higher asymptotic complexity and, accordingly, work much longer.Fuzzy text search using Damerau-Levenshtein distance allows taking into account common errors that the user may have made in the search term, namely: character substitution, extra character, missing character, and reordering of characters. To use a finite automaton, it is necessary to first construct it for a specific input word and edit distance, and then perform a search on that automaton, discarding words that the automaton will not accept. Therefore, when choosing an algorithm, both phases should be taken into account. This is because building a machine can take a long time. To speed up one of the machines, SIMD instructions were used, which gave a speedup of 1-10% depending on the number of search words, the length of the search word and the editing distance.The obtained results can be useful for use in various industries where it is necessary to quickly and efficiently perform fuzzy search in large volumes of data, for example, in search engines or in autocorrection of errors.

Keywords: fuzzy search; Levenshtein automaton; Damerau-Levenshtein distance; editing distance; finite state machines (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.uran.ua/tarp/article/download/286382/280636 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:baq:taprar:v:4:y:2023:i:2:p:27-32

DOI: 10.15587/2706-5448.2023.286382

Access Statistics for this article

More articles in Technology audit and production reserves from PC TECHNOLOGY CENTER
Bibliographic data for series maintained by Iryna Prudius ().