Ускорение levenshtein/Similar_text в PHP

Question

В настоящее время я использую similar_text, чтобы сравнить строку с списком ~ 50 000, который работает, хотя из-за количества сравнений он очень медленный. Для сравнения ~ 500 уникальных строк требуется около 11 минут.

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

Я уверен, что использование levenshtein будет немного быстрее, и функция LevenshteinDistance, опубликованная в руководстве, выглядит интересной. Я пропустил что-то, что могло бы сделать это значительно быстрее?

Answer 1

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

В качестве эксперимента я портировал часть кода на C#, чтобы увидеть, насколько быстрее он будет переполненным кодом. Он работал примерно через 3 минуты с одним и тем же набором данных.

Далее я добавил дополнительное поле в таблицу и использовал расширение двойного метафона PECL для генерации ключей для каждой строки. Результаты были хорошими, хотя, поскольку некоторые включенные числа вызвали дубликаты. Наверное, я мог бы запустить каждый из этих функций, но решил не делать этого.

В итоге я выбрал простейший подход, полный текст MySQL, который работал очень хорошо. Иногда бывают ошибки, хотя их легко обнаружить и исправить. Также он работает очень быстро, примерно через 3-4 секунды.

Answer 2

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

Как отметил Джейсон, алгоритм O (N^3) никогда не будет хорошим выбором.

Answer 3

При использовании Левенштейн автомат (автомат, который соответствует строке с расстоянием k), вы можете сделать проверку для согласования в O(n), где n является длина строки, которую вы проверяете. Построение автомата займет O(kn), где k - максимальное расстояние и n длина базовой строки.