Ускорение levenshtein / similar_text в PHP
Если шаблон использования выравнивает по ширине его, почему нет? В то время как Ваша команда не распознает оператор сразу же, со временем они могли. Люди изучают новые слова все время. Почему не в программировании?
единственная осторожность, которую я мог бы заявить, состоит в том, что "^" не имеет семантики короткого замыкания Вашей второй булевой проверки. Если Вам действительно нужна семантика короткого замыкания, то статический util метод работает также.
public static boolean xor(boolean a, boolean b) {
return (a && !b) || (b && !a);
}
3 ответа
В конце концов, и levenshtein , и Similar_text были слишком медленными с количеством строк, которые они должны были пройти, даже при большом количестве проверок и использовании только одной из них в качестве последней курорт.
В качестве эксперимента я перенес часть кода на C #, чтобы посмотреть, насколько он будет быстрее взаимодействовать с кодом. Он работал примерно за 3 минуты с тем же набором данных.
Затем я добавил дополнительное поле в таблицу и использовал двойное расширение метафона PECL для генерации ключей для каждой строки. Результаты были хорошими, хотя некоторые из них включали числа, это приводило к дублированию. Полагаю, я мог бы запустить каждую из перечисленных выше функций, но решил не делать этого.
В конце концов, я выбрал самый простой подход, Полный текст MySQL, который работал очень хорошо. Иногда случаются ошибки, хотя их легко обнаружить и исправить. Также он работает очень быстро, примерно за 3-4 секунды.
Возможно, вы могли бы «сократить» некоторые проверки, сначала сравнив вашу строку на точное совпадение (и сначала сравнив, если длина идентична), а если она будет пропущена, более дорогостоящие Подобный вызов .
Как заметил @jason, алгоритм O (N ^ 3) никогда не будет хорошим выбором.
При использовании автомата Левенштейна (автомата, который соответствует строке с расстоянием k ), вы можете выполнить проверку соответствия в O (n) , где n - длина проверяемой строки. Построение автомата займет O (kn) , где k - максимальное расстояние, а n длина базовой строки.