&laquo;Расстояние Левенштейна&raquo;, поясните чуть-чуть&#133

← →
Kolan © (2007-03-26 22:40) [0]

Здравствуйте,
Алгоритм довольно простой и понятный,
d[i, j] := минимум( # стирание d[i-1, j] + 1, # вставка d[i, j-1] + 1, # замена d[i-1, j-1] + цена );
Не пой му только почему d[i-1, j] + 1 обозначает стирание, а d[i, j-1] + 1  вставку и т.д.

← →
Alx2 © (2007-03-26 23:06) [1]

>Kolan © (26.03.07 22:40)

Пусть индекс i для первой строки, j - для второй.
Тогда одновременное изменение идексов на 1 дает эффект перемещения по двум строкам одновременно. То есть, в этом случае просто делаем тот символ одинаковым, и все => замена.
Если уменьшаем индекс для первой строки => игнорируем символ (удаляем). В этом случае ее длина как-бы "уменьшается" относительно второй. Если для второй строки уменьшаем индекс, то это дает эффект "роста" первой относительно второй. То есть вставка.

← →
Kolan © (2007-03-26 23:10) [2]

> [1] Alx2 © (26.03.07 23:06)

Доступно, я понял, благодарю :)

← →
Petr V. Abramov © (2007-03-26 23:34) [3]

> Расстояние Левенштейна
off
это когда шпалы кончатся или придет Левенштейн :)

← →
Kolan © (2007-03-27 18:29) [4]

А есть что-нибудь(другой алгоритм) более продвинутое? И где взять описание(не ш=готовый код а описание)&#133

← →
oldman © (2007-03-27 18:38) [5]

А причем тут работа с массивом и "расстояние кокого-там ученого, пусть даже и еврея"???

Я просто не все читал, проясните, пожалуйста, что такое "Расстояние Левенштейна" и при чем тут работа со строками массива.

Заранее благодарю за развернутый и аргументированный ответ :)

> Я просто не все читал, проясните, пожалуйста, что такое
> «Расстояние Левенштейна» и при чем тут работа со строками
> массива.

Это связано с «fuzzy search»:
http://www.dialog-21.ru/dialog2006/materials/html/Berzin.htm

Стирание в одной последовательности - это ровно тоже самое, что и вставка в другой.

&amp;laquo;Расстояние Левенштейна&amp;raquo;, поясните чуть-чуть&amp;#133 Найти похожие ветки

«Расстояние Левенштейна», поясните чуть-чуть&#133 Найти похожие ветки