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

Question

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

Answer 1

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

http://sift.codeplex.com

Answer 2

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

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

Answer 3

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

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

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