Какой алгоритм нечеткого поиска лучше для 10 тысяч строк из 50 символов?

#javascript #алгоритм #нечеткий_поиск

Есть массив из 10000 строк. Средняя длина строки 50 символов.

Символы в строках: a-я0-9'"%+!& .,;\-()/

Поиск осуществляется на клиенте при помощи JavaScript. Сейчас использую простой поиск
по точному совпадению при помощи метода indexOf. Какой алгоритм будет оптимальнее?
    

Ответы

Ответ 1

Из комментария пользователя @PinkTux:

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

Можно почитать статью «Нечёткий поиск в тексте и словаре».


Ответ 2

Тут проблема в том, что для каждой ошибки нужен свой алгоритм. Опечатка - наиболее
сложный вариант.
С раскладкой могу посоветовать сразу при наборе каждую букву переводить в другую
раскладку и сразу осуществлять 2 поиска - на той раскладке что вводят и на изменённой.
Если один из вариантов пуст а другой уже нашёл что-то после 3 букв например то можно
показывать на экране.


Ответ 3

Попробуйте Bitap. Реализации на JS у меня нет, но с C# он списывается почти один
в один :)
Вот реализация: Fuzzy Bitap Algorithm