Comments 3
Спасибо за наглядный разбор алгоритмов!
В этом случае использование автомата Левенштейна для нечеткого поиска возможно, но нецелесообразно.Более того, применительно к словарям для существующих языков (не абстрактных в лингвистическом смысле) использовать всё вами разобранное в чистом виде не совсем целесообразно.
Поясню мысль, tl;dr ...
Оставим пока за кадром такие вещи как морфология, семантика, фразеологизм, всякие стемеры и иже с ним (хотя на самом деле именно они кстати позволяют часто упростить «нечеткий» поиск даже на гигантских словарях до минимума).
Для примера возьму фонологию, или даже часть оной, описывающую фона слов, а именно часть отвечающую за общность фонем. Строим «фонологический» индекс по словарю и 70-80% всех fuzzy токенов или под-деревьев найдется без длительного поиска используя только автоматы и т.д., даже при больших расстояниях редактирования (причем в некоторых случаях, выражаясь в терминах wildcard, часто даже не важно где стоят
Что такое индекс и хеш-функция на хабре не нужно рассказывать. Фонологически же правильная хеш-функция будет возвращать одинаковое (иногда близкое) хеш-значение для похоже звучащих слов или слогов (зависит от того как организован индекс). Алгоритмов образования таких хеш-значений множество, ну для примера — простейший soundex. Хотя есть и куча модификаций, позволяющие улучшить его например для тех же отклонений типа опечаток. Существуют и другие формы, работающие со слогами, где например «красавчег», «гразовчек» и «красавчик» дают одинаковую группу хешей для всего слова (или для каждого слога). Даже простейший вариант — просто привести к уни-форме, преобразуя каждую гласную и согласную к наименьшей похожей по звучанию, уже упростит поиск по (проиндексированным) словарям.
Используя же еще и другие лингвистические алгоритмы, те же стемеры например (группировка по словам с общим корнем), позволяют организовать кластерный поиск в большинстве случаев много-много быстрее «чистого» нечеткого поиска.
(Звиняюсь если немного оффтоп, и я тормозну пожалуй, а то уже простыня...)
Для примера возьму фонологию, или даже часть оной, описывающую фона слов, а именно часть отвечающую за общность фонем. Строим «фонологический» индекс по словарю и 70-80% всех fuzzy токенов или под-деревьев найдется без длительного поиска используя только автоматы и т.д., даже при больших расстояниях редактирования (причем в некоторых случаях, выражаясь в терминах wildcard, часто даже не важно где стоят
*/?, в конце, в середине и даже в начале).Что такое индекс и хеш-функция на хабре не нужно рассказывать. Фонологически же правильная хеш-функция будет возвращать одинаковое (иногда близкое) хеш-значение для похоже звучащих слов или слогов (зависит от того как организован индекс). Алгоритмов образования таких хеш-значений множество, ну для примера — простейший soundex. Хотя есть и куча модификаций, позволяющие улучшить его например для тех же отклонений типа опечаток. Существуют и другие формы, работающие со слогами, где например «красавчег», «гразовчек» и «красавчик» дают одинаковую группу хешей для всего слова (или для каждого слога). Даже простейший вариант — просто привести к уни-форме, преобразуя каждую гласную и согласную к наименьшей похожей по звучанию, уже упростит поиск по (проиндексированным) словарям.
Используя же еще и другие лингвистические алгоритмы, те же стемеры например (группировка по словам с общим корнем), позволяют организовать кластерный поиск в большинстве случаев много-много быстрее «чистого» нечеткого поиска.
(Звиняюсь если немного оффтоп, и я тормозну пожалуй, а то уже простыня...)
Sign up to leave a comment.
Нечеткий поиск в словаре с универсальным автоматом Левенштейна. Часть 2