Существует ли более быстрый (менее точный) алгоритм, чем Левенштейн для расстояния между строками?

Question

Я хочу запустить Levenshtein, но ПУТЬ быстрее, потому что я создаю приложение в реальном времени. Это может закончиться, как только расстояние больше 10.

Answer 1

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

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

Answer 2

Судя по комментариям, люди, похоже, очень довольны Sift3.

http://sift.codeplex.com/

Answer 3

Если вы хотите сравнить содержимое UTF-8, используйте sift4:

http://siderite.blogspot.com/2014/11/super-fast-and-accurate-string-distance.html

Также я подготовил jsPerf, который показывает разницу в производительности между этими библиотеками: http://jsperf.com/levenshtein-perf