СБОРНИК
НАУЧНЫХ ТРУДОВ НГТУ

ISSN: 2307-6879
English | Русский

Последний выпуск
№1(94) Январь - Март 2019

Практическое применение алгоритмов нечеткого поиска

Выпуск № 3-4 (93) июль - декабрь 2018
Авторы:

Лещенко Андрей Владимирович
DOI: http://dx.doi.org/10.17212/2307-6879-2018-3-4-59-69
Аннотация

В статье обозреваются некоторые популярные алгоритмы нечеткого поиска(approximate string matching, fuzzy search). Объясняются основные понятия, на которых основаны алгоритмы. С помощью псевдокода и схем отображается их формальная сторона. Рассматривается реализация одного из приведенных алгоритмов для объединенного решения агрегации digital-каналов, маршрутизации клиентов и геймификации рабочего пространства оператора сотовой связи. Программа, которая использует алгоритм нечеткого поиска и организует рабочее пространство оператора, была написана на хакатоне(соревнование по программированию), который состоялся на базе научной библиотеки НГТУ по заказу компании «Мегафон» 5–7 октября 2018 года командой Infinite Capacity. Программа создана на основе обширного стека технологий: вся серверная часть написана на JavaScript, алгоритм нечеткого поиска также представлен фреймворком elasticsearch для JavaScript(NoteJS), базы данных реализованы на PostgreSQL, сообщение с клиентами сотового оператора организовано с использованием ботов для социальных сетей(VK BOT api, TG BOT api). Ссылка на открытый код программы: https://github.com/JackMor/HKTgit. Программа с помощью объединения  каналов связи из социальных сетей предоставляла информацию о клиентах оператору сотовой связи, и на основе имеющейся базы данных ответов для клиента алгоритм(fuzzy search) подбирал наиболее подходящие ответы, из которых оператор выбирал соответствующий его требованиям. Основное внимание статьи уделено алгоритму fuzzy search. Для лучшего понимания алгоритма предоставлены его формальная и схематическаясхемы. Также в литературных источниках можно найти руководство к фреймворку elasticsearch, который основан на исходном алгоритме.


Ключевые слова: расстояние Левенштейна, редакционное расстояние, дистанция редактирования, алгоритм нечеткой логики, алгоритм нечеткого поиска, fuzzy search, алгоритм Нидлмана–Вунша, расстояние Дамерау–Левенштейна, аpproximate string matching

Список литературы

1. Мосалев П.М. Обзор методов нечеткого поиска текстовой информации // Вестник МГУП имени Ивана Федорова. – 2013. – № 2. – С. 87–91.



2. Indexing methods for approximate string matching / G. Navarro, R. Baeza-Yates, E. Sutinen, J. Tarhio // IEEE Data Engineering Bulletin. – 2001. – Vol. 24, N 4. – P. 19–27.



3. Navarro G. A guided tour to approximate string matching // ACM Computing Surveys. – 2001. – Vol. 33, N 1. – P. 31–88.



4. Задача о редакционном расстоянии, алгоритм Вагнера-Фишера [Электронный ресурс]. – URL: http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_редакционном_расстоянии,_алгоритм_Вагнера-Фишера (дата обращения: 13.03.2019).



5. Lowrance  R., Wagner R.A. An extension of the string-to-string correction problem // Journal of the ACM. – 1975. – Vol. 22, N 2. – P. 177–183.



6. Метод динамического программирования Вагнера и Фишера [Электронный ресурс]. – URL: http://algolist.manual.ru/search/lcs/vagner.php (дата обращения: 13.03.2019).



7. Cholakian A. How to use fuzzy searches in elasticsearch [Electronic resource]. – URL: www.elastic.co/blog/found-fuzzy-search (accessed: 13.03.2019).



8. Нечеткий поиск в тексте и словаре [Электронный ресурс]. – URL: https://habr.com/post/114997/ (дата обращения: 13.03.2019).



9. Vernica R., Li C. Efficient top-k algorithms for fuzzy search in string collections // Proceedings of the First International Workshop on keyword search on structured data, 28 June 2009. – New York: ASM, 2009. – P. 9–14.



10. Cholakian A. A human-friendly tutorial for elasticsearch [Electronic resource]. – URL: http://exploringelasticsearch.com (accessed: 13.03.2019).



 

Для цитирования:

Лещенко А.В. Обзор и практическое применение алгоритмов нечеткого поиска // Сборник научных трудов НГТУ. – 2018. – № 3–4 (93). – С. 59–69. – DOI: 10.17212/2307-6879-2018-3-4-59-69.

For citation:

Leshchenko A.V. Obzor i prakticheskoe primenenie algoritmov nechetkogo poiska [Overview and practical implementation of fuzzy search algorithms]. Sbornik nauchnykh trudov Novosibirskogo gosudarstvennogo tekhnicheskogo universitetaTransaction of scientific papers of the Novosibirsk state technical university, 2018, no. 3–4 (93), pp. 59–69. DOI: 10.17212/2307-6879-2018-3-4-59-69.

Просмотров: 244