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

Authors

DOI:

https://doi.org/10.15587/2706-5448.2023.286382

Keywords:

fuzzy search, Levenshtein automaton, Damerau-Levenshtein distance, editing distance, finite state machines

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.

Author Biographies

Kyrylo Kleshch, National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

Assistant, Postgraduate Student

Department of System Design

Volodymyr Shablii, National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

Department of System Design

References

  1. Navarro, G. (2001). A guided tour to approximate string matching. ACM Computing Surveys, 33 (1), 31–88. doi: https://doi.org/10.1145/375360.375365
  2. Schulz, K. U., Mihov, S. (2002). Fast string correction with Levenshtein automata. International Journal on Document Analysis and Recognition, 5 (1), 67–85. doi: https://doi.org/10.1007/s10032-002-0082-8
  3. Boytsov, L. (2011). Indexing methods for approximate dictionary searching. ACM Journal of Experimental Algorithmics, 16. doi: https://doi.org/10.1145/1963190.1963191
  4. Damerau–Levenshtein distance. Available at: https://www.geeksforgeeks.org/damerau-levenshtein-distance/
  5. Snášel, V., Keprt, A., Abraham, A., Hassanien, A. E. (2009). Approximate String Matching by Fuzzy Automata. Man-Machine Interactions. Berlin, Heidelberg: Springer, 281–290. doi: https://doi.org/10.1007/978-3-642-00563-3_29
  6. Baeza-Yates, R., Navarro, G.; Hirschberg, D., Myers, G. (Eds.) (1996). A faster algorithm for approximate string matching. Combinatorial Pattern Matching. CPM 1996. Lecture Notes in Computer Science. Vol 1075. Berlin, Heidelberg: Springer. doi: https://doi.org/10.1007/3-540-61258-0_1
  7. Girijamma, H. A., Ramaswamy, H. A. V. (2009). An extension of Myhill Nerode Theorem for Fuzzy Automata. Advances in Fuzzy Mathematics, 4 (1), 41–47.
  8. Ramon Garitagoitia, J., Gonzalez de Mendivil, J. R., Echanobe, J., Javier Astrain, J., Farina, F. (2003). Deformed fuzzy automata for correcting imperfect strings of fuzzy symbols. IEEE Transactions on Fuzzy Systems, 11 (3), 299–310. doi: https://doi.org/10.1109/tfuzz.2003.812682
  9. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2022). Introduction to Algorithms. MIT Press, 1312.
  10. Mihov, S., Schulz, K. U. (2004). Fast Approximate Search in Large Dictionaries. Computational Linguistics, 30 (4), 451–477. doi: https://doi.org/10.1162/0891201042544938
Comparison of fuzzy search algorithms based on Damerau-Levenshtein automata on large data

Downloads

Published

2023-08-28

How to Cite

Kleshch, K., & Shablii, V. (2023). Comparison of fuzzy search algorithms based on Damerau-Levenshtein automata on large data. Technology Audit and Production Reserves, 4(2(72), 27–32. https://doi.org/10.15587/2706-5448.2023.286382

Issue

Vol. 4 No. 2(72) (2023): Information and control systems

Section

Information Technologies

License

Copyright (c) 2023 Kyrylo Kleshch, Volodymyr Shablii

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.