Быстрый динамический нечеткий поиск по 100 000+ строк в C#
Допустим, они являются предварительно загруженными символами, напечатанными в текстовом поле. Я ищу код, который я могу скопировать, а не библиотеку для установки.
Это было вдохновлено этим вопросом:
Существуют ли библиотеки для нечеткого поиска или функции схожести строк, написанные для C#?
Кажется, что алгоритм расстояния Левенштейна работает хорошо, но для его вычисления требуется время. Существуют ли какие-либо оптимизации в отношении того факта, что запрос необходимо будет повторно выполнить, когда пользователь вводит дополнительную букву? Я заинтересован в том, чтобы показать максимум 10 совпадений для каждого входа.
2 ответа
Вы должны определить правила соответствия вокруг ваших строк. Что определяет "похожую строку"
- количество совпадающих символов
- количество несовпадающих символов
- аналогичная длина
- опечатки или фонетические ошибки
- специфичные для бизнеса сокращения
- должен начинаться с той же подстроки
- должен заканчиваться одной и той же подстрокой
Я проделал довольно большую работу с алгоритмами сопоставления строк, и мне еще предстоит найти какую-либо существующую библиотеку или код, отвечающий моим конкретным требованиям. Просмотрите их, позаимствуйте идеи у них, но вам непременно придется настраивать и писать свой собственный код.
Алгоритм Левенштейна хорош, но немного медленен. У меня был некоторый успех с обоими алгоритмами Смита-Уотермана и Джаро-Винклера, но лучшее, что я нашел для своих целей, это Монж (по памяти). Однако стоит прочитать оригинальное исследование и определить, почему они написали свои алгоритмы и целевой набор данных.
Если вы не правильно определите, что вы хотите сопоставить и измерить, то вы найдете высокие оценки в неожиданных матчах и низкие оценки в ожидаемых матчах. Соответствие строк очень зависит от домена. Если вы не правильно определите свой домен, то вы как рыбак без понятия, разбрасывая крючки и надеясь на лучшее.
Этот пост описывает некоторые работы, которые были сделаны в Lucene в этой области. Они смогли реализовать нечеткое сопоставление расстояний Левенштейна с использованием конечного преобразователя состояний (автомата) достаточно эффективно для расстояния редактирования до 2. Хотя весь код написан на Java и немного сложен, хотя и с открытым исходным кодом.
Но основная идея достаточно проста: думайте о своем словаре как о гигантском дереве буквенных состояний. На state0 у вас нет букв. На state1 вы допускаете любую букву, которая может быть первой буквой слова. Состояние2 обусловлено состоянием1; если первая буква была "х", то следующее состояние допускает только те буквы, которые могут следовать за х (в позиции 2). и т.п.
Теперь для сопоставления Левенштейна вы пересекаете дерево букв, допуская некоторые ошибки: удаления, вставки (подстановочный знак из одной буквы) и, возможно, транспонирование (хорошим расширением Левенштейна является рассмотрение транспонирования как одного редактирования, а не 2). Вы должны поддерживать состояние, чтобы отслеживать, сколько изменений было разрешено. Это может быть сделано очень эффективно - конечно, достаточно быстро для интерактивного подсказчика правописания "пока вы печатаете".