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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

Как заметил @jason, алгоритм O (N ^ 3) никогда не будет хорошим выбором.