Вариант на алгоритъма за редактиране на разстояние, който проследява само замествания и вмъквания

Някой знае ли за алгоритъм за редактиране на разстояние, който брои само замествания и вмъквания. Така че по същество това ще бъде алгоритъмът за разстояние на Левенщайн без изтривания.


algorithm edit-distance levenshtein-distance
person kchoi    schedule 10.10.2014    source източник
comment
Какъв точно е въпросът ти?   -  person But I'm Not A Wrapper Class    schedule 10.10.2014
comment
Предполагам, че се чудех дали има някакви алгоритми, за които никога не съм чувал, които правят точно това, което обясних по-горе. или ако знаете начин да преброите отделно изтриванията, включени в редактирането в разстоянието на Левенщайн, това също би било полезно.   -  person kchoi    schedule 10.10.2014

Отговори (2)


arrow_upward
0
arrow_downward

Можете да използвате почти същото решение за динамично програмиране, което се използва за изчисляване на нормалното разстояние на Левенщайн, но без преходи, които съответстват на изтривания.

person kraskevich    schedule 10.10.2014
comment
И така, разстоянието на Левенщайн се изчислява от min(Lev[i-1][j], Lev[i][j-1], Lev[i-1][j-1]) + 1 Когато казвате пропускане на прехода, съответстващ на изтриване, казвате ли премахване на Lev[i-1][j] в релацията на повторение, което съответства на изтриване? - person kchoi; 10.10.2014
comment
Зависи от това дали операциите могат да се извършват върху двата низа или само върху първия. В първия случай, да. В последния не трябва да се променя нищо, защото изтриването от един низ е еквивалентно на вмъкване в друг. - person kraskevich; 10.10.2014

arrow_upward
0
arrow_downward

Кажете, че вашият алгоритъм за разстоянието на Левенщайн е следният:

For each i= 1...M
    For each j = 1...N
        //min(deletion, insertion, match/substitution)
        D(i,j) = min(D(i-1,j) + 1, D(i,j-1) + 1, D(i-1,j-1) + (X(i)=Y(j) : 0 ? 2))

Частта, която отчита изтриванията, трябва да бъде премахната. Оставяйки ви с:

For each i= 1...M
    For each j = 1...N
        //min(insertion, match/substitution)
        D(i,j) = min(D(i,j-1) + 1, D(i-1,j-1) + (X(i)=Y(j) : 0 ? 2))

Забележка: Този конкретен алгоритъм оценява заместването с 2 точки, а другите две операции (изтриване, вмъкване) с 1 точка. Има много вариации, които имат различен резултат.

Добър ресурс за PowerPoint тук.

person But I'm Not A Wrapper Class    schedule 10.10.2014