Быстрый динамический нечеткий поиск по 100 000+ строк в C #

Question

Допустим, они являются предварительно загруженными символами акций, напечатанными в текстовом поле.Я ищу код, который я могу скопировать, а не библиотеку для установки.

Этот вопрос был вдохновлен этим вопросом:

Существуют ли библиотеки Fuzzy Search или String Similarity Functions, написанные дляC #?

Кажется, что алгоритм расстояния Левенштейна хорошо работает, но для его вычисления требуется время.Существуют ли какие-либо оптимизации в отношении того факта, что запрос необходимо будет повторно выполнить, когда пользователь вводит дополнительную букву?Я заинтересован в показе не более 10 лучших совпадений для каждого ввода.

Answer 1

Вам необходимо определить правила соответствия для ваших строк.Что определяет «похожую строку»

• количество совпадающих символов
• количество несовпадающих символов
• аналогичная длина
• опечатки или фонетические ошибки
• бизнес-аббревиатуры
• должен начинаться с одной и той же подстроки
• должен заканчиваться той же подстрокой

Я сделал довольно многоЯ работаю с алгоритмами сопоставления строк, и мне еще предстоит найти любую существующую библиотеку или код, который отвечает моим конкретным требованиям.Просмотрите их, позаимствуйте идеи у них, но вам непременно придется настраивать и писать свой собственный код.

Алгоритм Левенштейна хорош, но немного медленен.Я имел некоторый успех с обоими алгоритмами Смита-Уотермана и Джаро-Винклера, но лучшее, что я нашел для своих целей, - это Монж (по памяти).Однако стоит прочитать оригинальное исследование и определить, почему они написали свои алгоритмы и целевой набор данных.

Если вы не определите, что вы хотите сопоставить и измерить, то вы найдете высокие оценки нанеожиданные совпадения и низкие оценки ожидаемых совпадений.Соответствие строки очень зависит от домена.Если вы не правильно определите свой домен, то вы как рыбак без понятия, разбрасывая крючки и надеясь на лучшее.

Answer 2

Этот пост в блоге описывает некоторые работы, которые были сделаны в Lucene в этой области Они смогли реализовать нечеткое сопоставление расстояний Левенштейна с использованием конечного преобразователя состояний (автомата) достаточно эффективно для расстояния редактирования до 2. Хотя весь код написан на Java и немного сложен, хотя и с открытым исходным кодом.

Но основная идея достаточно проста: думайте о своем словаре как о гигантском дереве буквенных состояний. В состоянии 0 у вас нет писем. В state1 вы допускаете любую букву, которая может быть первой буквой слова. Состояние2 обусловлено состоянием1; если первая буква была «х», то следующее состояние допускает только те буквы, которые могут следовать за х (в позиции 2). и т.д.

Теперь для сопоставления Левенштейна вы пересекаете дерево букв, допуская некоторые ошибки: удаления, вставки (подстановочный знак из одной буквы) и, возможно, транспонирование (хорошим расширением Левенштейна является рассмотрение транспонирования как одного редактирования, а не 2). , Вы должны поддерживать состояние, чтобы отслеживать, сколько изменений было разрешено. Это может быть сделано очень эффективно - конечно, достаточно быстро для интерактивного подсказчика правописания «пока вы печатаете».