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

Кирило Олегович Клещ; Володимир Сергійович Шаблій

doi:10.15587/2706-5448.2023.286382

Автор(и)

Кирило Олегович Клещ Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Україна https://orcid.org/0009-0006-8133-3086
Володимир Сергійович Шаблій Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Україна https://orcid.org/0009-0004-5113-3572

DOI:

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

Ключові слова:

нечіткий пошук, автомат Левенштейна, відстань Дамерау-Левенштейна, відстань редагування, скінчені автомати

Анотація

Об’єктом дослідження є алгоритми нечіткого пошуку на основі автоматів Дамерау-Левенштейна та автоматів Левенштейна. В роботі розглянуто та порівняно між собою рішення на основі скінченних автоматів для ефективного та швидкого знаходження слів та рядків із заданою відстанню редагування у великих текстових даних при використанні концепції нечіткого пошуку.

Алгоритми нечіткого пошуку дозволяють знаходити значно більше релевантних результатів, ніж стандартні алгоритми чіткого пошуку. Проте такі алгоритми зазвичай мають більшу асимптотичну складність і відповідно працюють набагато довше.

Нечіткий пошук в тексті з використанням відстані Дамерау-Левенштейна дозволяє враховувати поширені помилки, які користувач міг допустити в пошуковому слові, а саме: заміна символу, додатковий символ, пропущений символ та змінений порядок символів. Для використання скінченого автомата необхідно спочатку побудувати його для певного вхідного слова та певної відстані редагування, а потім виконати пошук по цьому автомату, відкидаючи слова, які автомат не буде приймати. Тому при виборі алгоритму, слід враховувати обидві фази. Це пояснюється тим, що побудова автомата може займати багато часу. Для пришвидшення одного з автоматів були використані SIMD інструкції, що дало прискорення на 1–10 % в залежності від кількості пошукових слів, довжини пошукового слова та відстані редагування.

Отримані результати можуть бути корисними для використання в різних галузях, де потрібно швидко та ефективно проводити нечіткий пошук у великих обсягах даних, наприклад, в пошукових системах або при автокорекції помилок.

Біографії авторів

Кирило Олегович Клещ, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

Асистент, аспірант

Кафедра системного проєктування

Володимир Сергійович Шаблій, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

Кафедра системного проєктування

Посилання

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
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
Boytsov, L. (2011). Indexing methods for approximate dictionary searching. ACM Journal of Experimental Algorithmics, 16. doi: https://doi.org/10.1145/1963190.1963191
Damerau–Levenshtein distance. Available at: https://www.geeksforgeeks.org/damerau-levenshtein-distance/
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
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
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.
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
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2022). Introduction to Algorithms. MIT Press, 1312.
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