Я видел эту формулу Левенштейна в Википедии:
Я реализовал этот алгоритм рекурсивным способом (я знаю, что это неэффективный способ реализовать его таким образом, но я хотел посмотреть, насколько он неэффективен), вот код (на PHP):
function lev($str1, $str2, $i, $j) {
if (min($i, $j) == 0) {
return max($i, $j);
}
else {
$m = ($str1[$i-1] == $str2[$j-1]) ? 0 : 1;
return min(lev($str1, $str2, $i, $j - 1) + 1,
lev($str1, $str2, $i - 1, $j) + 1,
lev($str1, $str2, $i - 1, $j - 1) + $m);
}
}
$str1 = "long long text";
$str2 ="absolute";
echo lev($str1, $str2, strlen($str1),strlen($str2));
Когда я проверяю это, как я делал для этих двух строк (даже если «длинный длинный текст» не такой длинный), я получаю «Максимальное время выполнения 30 секунд» …, но функция, кажется, работает со строками, где Левенштейн небольшое расстояние (например, $ str1 = «word», $ str2 = «corw»)
Превышение 30 секунд для завершения этого сценария слишком много, поэтому, возможно, я ввел что-то неправильно в реализации (но когда я смотрю на реализацию, я не вижу ошибок, мне кажется, что я написал правильный алгоритм, если он основан на формула вики)
Эта реализация слишком медленная или я где-то ошибаюсь в коде?
Спасибо за внимание!
Вы не используете памятку в своем коде, поэтому она имеет экспоненциальную временную сложность. Вот почему это так медленно. Вы можете добавить памятку, чтобы избежать вычисления значения функции более одного раза для одного и того же i
а также j
достигать O(N * M)
сложность времени.
Других решений пока нет …