Определяне на последователност от редакции, която произвежда разстоянието на Левенщайн

Върша малко работа, използвайки Levenshtein (редактиране) разстояние, използвайки динамично програмиране. Мисля, че разбирам алгоритъма на Вагнер-Фишер, за да направя това ефективно. Не изглежда обаче, че алгоритъмът е конструктивен. Ако изчисля, че разстоянието за редактиране между два низа е, например, 10, тогава бих искал също така да определя конкретна последователност от 10 редакции, която превръща една в друга. Може ли и това да се направи ефективно? Ако е така, как?


dynamic-programming edit-distance levenshtein-distance
person dextrous    schedule 10.08.2014    source източник

Отговори (2)


arrow_upward
2
arrow_downward

Много е градивно. С получената матрица е възможно да се намерят всички различни последователности от редакции, които произвеждат минимално разстояние.

За да намерите редакции, трябва да прехвърлите получената матрица в 'назад'. Започнете от клетка с резултати, (m,n).

  • Ако стойността на клетка (m-1, n-1) е същата, знаците на тези места са еднакви и не е необходима редакция.
  • Ако стойността на клетка (m-1, n-1) е по-малка, намерете клетка(и) от {(m-1, n-1), (m-1, n), (m, n-1)} с най-малката стойност. Позицията на клетка(и) с най-малка стойност определя дали се извършва заместване, изтриване или вмъкване. Ако има повече клетки с най-малка стойност, повече последователности от редакции могат да произведат минимално разстояние. Ако имате нужда само от една последователност, изберете която и да е от тях.

Направете същата проверка, докато пътят достигне клетка (0,0).

Пътят на проверките определя редакциите, извършени в обратен ред.

person Ante    schedule 11.08.2014

arrow_upward
5
arrow_downward

Докато се опитвах да внедря алгоритъма на Анте, получих грешни резултати, което означава, че или е грешен, или съм го внедрил по грешен начин. Във всеки случай успях да проработя и ето моят по-подробен алгоритъм. Вижте алгоритъм на Wagner-Fischer за описание на d.

  1. Започнете от клетка d(m, n)
  2. Check cells d(m - 1, n - 1), d(m - 1, n) and d(m, n - 1) and determine which one contains the smallest value.
    • If it's d(m - 1, n - 1) (prefer this if it's a tie) then you have either
      • a substitution if d(m - 1, n - 1) < d(m, n). Decrement m and n by one.
      • няма операция, ако d(m - 1, n - 1) == d(m, n). Намали m и n с едно.
    • Ако е d(m - 1, n), тогава имате изтриване. Намали m с едно.
    • Ако е d(m, n - 1), тогава имате вмъкване. Намали n с едно.

Ако някое търсене в клетка би причинило отрицателни индекси, просто ги пропуснете. Ако стигнете до клетка (0, 0), сте готови. Ще изготвите списъка с редакции в обратен ред.

Написах имплементация в Python, която извежда точните инструкции, включително знаците и отместванията, включени във всяка операция . Той също така включва някои тестове за валидиране на изхода и които също демонстрират формата на изхода.

person jlh    schedule 20.08.2018
comment
Това е същият алгоритъм, както е описан от Ante, но с повече подробности за това как да се реши точният тип редакция. - person Reuben Morais; 19.02.2020
comment
Възможно е просто да съм се объркал, докато съм го прилагал и отговорът на Анте също да е правилен. Твърде отдавна е, за да си спомня наистина какъв беше проблемът. Във всеки случай актуализирах отговора с още повече подробности и написах реализация в Python. - person jlh; 19.02.2020