рядків В«CONNECTВ» і В«CONEHEADВ» можна побудувати наступну таблицю перетворень:
MMMRRRRI
Знайти тільки відстань Левенштейна - більш просте завдання, ніж знайти ще й редакційне припис.
Недоліки
З точки зору додатків визначення відстані між словами або текстовими полями по Левенштейн володіє наступними недоліками:
. При перестановці місцями слів або частин слів виходять порівняно великі відстані;
. Відстані між абсолютно різними короткими словами виявляються невеликими, в той час як відстані між дуже схожими довгими словами виявляються значними.
Узагальнення
Різні ціни операцій
Ціни операцій можуть залежати від виду операції (вставка, видалення, заміна) та/або від беруть участь в ній символів, відображаючи різну ймовірність мутацій в біології, різну ймовірність різних помилок при введенні тексту і т. д. У загальному випадку: (a, b) - ціна заміни символу a на символ b
w (?, b) - ціна вставки символу b
w (a,?) - ціна видалення символу a
Формула
Тут і далі вважається, що елементи рядків нумеруються з першого, як прийнято в математиці. Нехай S1 і S2 - два рядки (довжиною M і N відповідно) над деякими алфавітом, тоді редакційне відстань d (S1, S2) можна підрахувати за такою рекуррентной формулою
В В
де m (a, b) дорівнює нулю, якщо a = b і одиниці в іншому випадку; min (a, b, c) повертає найменший з аргументів.
Алгоритм Вагнера - Фішера
Як окремий випадок, так і завдання для довільних w, вирішує алгоритм Вагнера - Фішера, наведений нижче. Тут і нижче ми вважаємо, що всі w невід'ємні, і діє правило трикутника: якщо дві послідовні операції можна замінити однією, це не погіршує загальну ціну (наприклад, замінити символ x на y, а потім з y на z не краще, ніж відразу x на z).
Для знаходження найкоротшого відстані необхідно обчислити матрицю D, використовуючи вищенаведену формулу. Її можна обчислювати як по рядках, так і по стовпцях. Псевдокод алгоритму:
для всіх i від 0 до M
для всіх j від 0 до N
обчислити D (i, j)
повернути D (M, N)
Або в більш розгорнутому вигляді, і при довільних цінах замін, вставок і вилучень: (0,0) = 0
для всіх j від 1 до N (0, j) = D (0, j-1) + ціна вставки символу S2 [j]
для всіх i від 1 до M (i, 0) = D (i-1, 0) + ціна вида...
