МОДИФІКАЦІЯ АЛГОРИТМІВ НЕЧІТКОГО ПОШУКУ ДЛЯ ВИКОРИСТАННЯ ТАБЛИЦІ ПОДІБНОСТІ СИМВОЛІВ
DOI:
https://doi.org/10.32782/tnv-tech.2023.3.3Ключові слова:
нечіткий пошук, таблиця подібності символів, алгоритм Дамерау-Левенштейна, обробка текстових даних, відстань редагування.Анотація
Об’єктом дослідження є алгоритм нечіткого пошуку на основі відстані Дамерау-Левенштейна та таблиця подібності символів. У роботі було досліджено, проаналізовано та надано рекомендації, як саме можна інтегрувати потужності таблиці подібності символів з алгоритмом нечіткого пошуку Дамерау-Левенштейна. Дослідження алгоритмів нечіткого пошуку в тексті є важливою темою в галузі інформаційного пошуку та обробки тексту. Це обумовлено зростаючим обсягом інформації і ймовірністю помилок через вплив людського фактора під час написання тексту. Нечіткий пошук використовує алгоритми для пошуку даних в тексті, які приблизно відповідають шаблону. Це досягається шляхом порівняння та зіставлення рядків або ключових слів, які можуть бути схожими, але не ідентичними. Для нечіткого пошуку можна використати таблицю подібності символів, яка допомагає з'ясувати міру подібності пари символів. Поєднуючи алгоритм нечіткого пошуку з таблицею подібності, можна досягти більш точного та індивідуального доступу до великого обсягу інформації, яка зберігається у текстовому форматі. В роботі було проведено порівняльний аналіз ефективності та коректності результатів алгоритмів нечіткого пошуку з використанням таблиці і без її використання, а також алгоритму точного пошуку. Використання таблиці подібності покращує отримані результати, особливо при використанні мов зі спеціальними символами. Це дозволяє знаходити значно більше релевантних результатів, проте швидкодія алгоритму зменшується. Отримані результати могли б стати важливим внеском у вдосконалення пошукових систем. Це дозволило б користувачам знаходити відповідні документи навіть при наявності орфографічних помилок, синонімів, скорочень або інших форм неточностей у запиті. Підхід з використанням таблиці подібності символів міг би бути використаний у системах для перевірки орфографії та автоматичної корекції, системах автопропозицій та автозавершення, а також у реалізації функцій з виявлення плагіату та дублікатів даних.
Посилання
М. В. Михайлова. Порівняння алгоритмів нечіткого пошуку в текстах українською мовою: Радіоелектроніка, інформатика, управління, 2007, 80 с.
Відстань Дамерау-Левенштейна [Електронний ресурс]. https://www. geeksforgeeks.org/damerau-levenshtein-distance/
Fred J. Damerau. A Technique for Computer Detection and Correction of Spelling Errors : Communications of the ACM, 1964, с. 171 – 176.
Gonzalo N. A guided tour to approximate string matching / Navarro Gonzalo. // Association for Computing Machinery. – 2001.
J. P. Carvalho and L. Coheur, "Introducing UWS – A fuzzy based word similarity function with good discrimination capability: Preliminary results," 2013 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), Hyderabad, India, 2013, pp. 1-8.
H. Ayeldeen, A. E. Hassanien and A. A. Fahmy, "Lexical similarity using fuzzy Euclidean distance," 2014 International Conference on Engineering and Technology (ICET), Cairo, Egypt, 2014, pp. 1-6.
Mihov S. Fast Approximate Search in Large Dictionaries / S. Mihov, K. Schulz. // Computational Linguistics. – 2004.
Yu, M., Li, G., Deng, D. et al. String similarity search and join: a survey. Front. Comput. Sci. 10, 399–417 (2016).
Вступ в алгоритми, 4 видання / [Т. Кормен, Р. Рівест]., 2022. – 1312 с.
Fancy Letters [Електронний ресурс]. https://symbl.cc/en/collections/fancyletters/
Посібник користувача Google Benchmar [Електронний ресурс]. https:// github.com/google/benchmark/blob/main/docs/user_guide.md#runtime-and-reportingconsiderations
