Розробка методу нечіткого пошуку для створення системи ефективного пошуку інформації в текстових даних

Автор(и)

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

DOI:

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

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

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

Анотація

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

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

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

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

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

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

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

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

Посилання

  1. Boytsov, L. (2011). Indexing methods for approximate dictionary searching. ACM Journal of Experimental Algorithmics, 16. doi: https://doi.org/10.1145/1963190.1963191
  2. Carvalho, J. P., Coheur, L. (2013). Introducing UWS – A fuzzy based word similarity function with good discrimination capability: Preliminary results. 2013 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). Hyderabad. doi: https://doi.org/10.1109/fuzz-ieee.2013.6622494
  3. Yu, M., Li, G., Deng, D., Feng, J. (2015). String similarity search and join: a survey. Frontiers of Computer Science, 10 (3), 399–417. doi: https://doi.org/10.1007/s11704-015-5900-5
  4. 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
  5. Fancy Letters. Available at: https://symbl.cc/en/collections/fancy-letters/
  6. Snášel, V., Keprt, A., Abraham, A., Hassanien, A. E. (2009). Approximate String Matching by Fuzzy Automata. Advances in Soft Computing. Berlin Heidelberg: Springer, 281–290. doi: https://doi.org/10.1007/978-3-642-00563-3_29
  7. 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. doi: https://doi.org/10.15587/2706-5448.2023.286382
  8. Kleshch, K. O., Tsarov, M. O. (2023). Modification of the fuzzy search algorithms to use a symbols similarity table. Таuridа Scientific Herald. Series: Technical Sciences, 3, 21–28. doi: https://doi.org/10.32782/tnv-tech.2023.3.3
  9. 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
  10. Wang, J., Li, G., Fe, J. (2011). Fast-join: An efficient method for fuzzy token matching based string similarity join. 2011 IEEE 27th International Conference on Data Engineering. Hannover, 458–469. doi: https://doi.org/10.1109/icde.2011.5767865
Development of fuzzy search method for creating an efficient information search system in text data

##submission.downloads##

Опубліковано

2024-02-13

Як цитувати

Клещ, К. О. (2024). Розробка методу нечіткого пошуку для створення системи ефективного пошуку інформації в текстових даних. Technology Audit and Production Reserves, 1(2(75), 20–24. https://doi.org/10.15587/2706-5448.2024.298425

Номер

Том 1 № 2(75) (2024): Інформаційно-керуючі системи

Розділ

Інформаційні технології

Ліцензія

Авторське право (c) 2024 Kyrylo Kleshch

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.