Скачать: CL | DM;

«Расстояние Левенштейна», поясните чуть-чуть&#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]

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

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

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

---

← →
Kolan ©   (2007-03-27 19:04) [6]

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

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

---

← →
TUser ©   (2007-03-28 00:26) [7]

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.031 c