Порівняння алгоритмів нечіткого пошуку на основі автомата Дамерау-Левенштейна на великих масивах даних
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
![Comparison of fuzzy search algorithms based on Damerau-Levenshtein automata on large data](https://journals.uran.ua/public/journals/15/submission_286382_324614_coverImage_en_US.png)
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2023 Kyrylo Kleshch, Volodymyr Shablii
![Creative Commons License](http://i.creativecommons.org/l/by/4.0/88x31.png)
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.