Я ищу библиотеку JavaScript нечеткого поиска для фильтрации массива. Я пытался использоватьfuzzyset.js а такжеfuse.js, но результаты ужасны (есть демоверсии, которые вы можете попробовать на связанных страницах).

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

Один очевидный недостаток, который зафиксирован в модели Левенштейна-Демерау, заключается в том, что обареветь а такжеболван считаются одинаково похожими наколба (каждая требует двух замен). Понятно, однако, чтоколба больше похоже нареветь чемболван и модель, которую я только что упомянул, признает, что, учитываятранспозиции.

Я хочу использовать это в контексте завершения текста, поэтому, если у меня есть массив['international', 'splint', 'tinder']и мой запросИНТ, Я думаюМеждународный должен занимать более высокое место, чемлубокхотя первый имеет оценку (выше = хуже) 10 против последних 3.

Так что я ищу (и буду создавать, если он не существует), это библиотека, которая делает следующее:

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

Кто-нибудь сталкивался с чем-нибудь подобным? Я понимаю, что StackOverflow - это не то место, где нужно спрашивать рекомендации по программному обеспечению, но подразумевается (не больше!) В приведенном выше: я думаю об этом правильно?

редактировать

Я нашелхорошая статья (pdf) на предмет. Некоторые заметки и выдержки:

Аффинные функции редактирования расстояния назначают относительно более низкую стоимость последовательности вставок или удалений

функция расстояния Монгера-Элкана (Monge & Elkan 1996), которая является аффинным вариантом функции расстояния Смита-Уотермана (Дурбан и др. 1998) с конкретными параметрами стоимости

ДляРасстояние Смит-Уотерман (Википедия)«Вместо рассмотрения общей последовательности алгоритм Смита-Уотермана сравнивает сегменты всех возможных длин и оптимизирует меру подобия». Это n-граммовый подход.

Схожей метрикой, которая не основана на модели расстояния редактирования, является метрика Jaro (Jaro 1995; 1989; Winkler 1999). В литературе о связях записей хорошие результаты были получены с использованием вариантов этого метода, который основан на количестве и порядке общих символов между двумя строками.

Вариант этого из-за Winkler (1999) также использует длину P самого длинного общего префикса

(кажется, предназначен в первую очередь для коротких строк)

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

Заключение:

ранжирование TFIDF показало лучший результат среди нескольких метрик расстояния на основе токенов, а настроенная метрика аффинного промежутка редактирования, предложенная Монге и Элканом, показала наилучший результат среди нескольких метрик расстояния строкового редактирования. Удивительно хорошая метрика расстояния - это быстрая эвристическая схема, предложенная Джаро и позже расширенная Винклером. Это работает почти так же, как схема Монжа-Элкана, но на порядок быстрее. Один простой способ объединить метод TFIDF и Jaro-Winkler - заменить точные совпадения токенов, используемые в TFIDF, на приблизительные совпадения токенов, основанные на схеме Jaro-Winkler. Эта комбинация работает немного лучше, чем Jaro-Winkler или TFIDF в среднем, и иногда работает намного лучше. По производительности он также близок к изученной комбинации нескольких лучших метрик, рассмотренных в этой статье.