Ускорение levenshtein / Similar_text в PHP
https://stackoverflow.com/questions/1215720
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В настоящее время я использую Similar_text для сравнения строки с список ~ 50 000, который работает, хотя из-за количества сравнений это очень медленно. Сравнение ~ 500 уникальных строк занимает около 11 минут.
Перед запуском я проверяю базы данных на предмет того, была ли она обработана в прошлом, поэтому каждый раз после начального запуска она близка к мгновенной.
Я уверен, что использование левенштейна будет немного быстрее, и Функция LevenshteinDistance, размещенная кем-то в руководстве, выглядит интересно. Я что-то упустил, что могло бы сделать это значительно быстрее?
Решение
В конце концов, и levenshtein , и Similar_text были слишком медленными из-за количества строк, через которые ему пришлось пройти, даже с большим количеством проверок и с использованием только одной из них в крайнем случае.
В качестве эксперимента я портировал часть кода на C #, чтобы увидеть, насколько быстрее он будет по сравнению с взаимодействующим кодом. Он работал примерно через 3 минуты с тем же набором данных.
Затем я добавил дополнительное поле в таблицу и использовал расширение PECL с двойным метафоном для генерации ключей для каждой строки. Результаты были хорошими, хотя, так как некоторые включали числа, это вызвало дублирование. Полагаю, я мог бы запустить каждую из перечисленных выше функций, но решил не делать этого.
В итоге я выбрал самый простой подход - полный текст MySQL, который работал очень хорошо. Изредка бывают ошибки, хотя их легко обнаружить и исправить. Кроме того, он работает очень быстро, примерно за 3-4 секунды.
Другие советы
Возможно, вы могли бы «замкнуть» некоторые проверки, сначала сравнив вашу строку на предмет точного соответствия (и сначала сравнив, если длина идентична), и если это произойдет, пропустите более дорогой вызов Similar_text .
Как заметил @jason, алгоритм O (N ^ 3) никогда не будет хорошим выбором.
При использовании автомата Левенштейна (автомат, который соответствует строке с расстоянием k ), вы можете проверить соответствие в O (n) , где n - длина проверяемой строки. Для создания автомата потребуется O (kn) , где k - максимальное расстояние, а n - длина базовой строки.
