Levenshtein Редактировать Расстояние не вычисляется Расстояние редактирования

Question

Я пытаюсь запустить мой алгоритм редактирования Levenshtein Edit, но по некоторым причинам количество исправлений выходит неверно. Я не вижу, где моя ошибка, и мне было интересно, если кто-то увидит, что я делаю неправильно.

Входной

5 
ATCGTT 
AGTTAC 
ACGAAT 
CCGTAAAT 
TTACGACCAGT 

ожидается выход

Strand A: ATCGTT-- 
Strand B: A--GTTAC 
Edit Distance: 4 

Strand A: ATCG-TT 
Strand B: A-CGAAT 
Edit Distance: 3 

Strand A: ATCGT---T 
Strand B: -CCGTAAAT 
Edit Distance: 5 

Strand A: AT-CG----TT 
Strand B: TTACGACCAGT 
Edit Distance: 7 

Strand A: AGTTAC 
Strand B: ACGAAT 
Edit Distance: 4 

Strand A: -AGT-TAC 
Strand B: CCGTAAAT 
Edit Distance: 5 

Strand A: --A-G-TTA-C 
Strand B: TTACGACCAGT 
Edit Distance: 8 

Strand A: ACG--AAT 
Strand B: CCGTAAAT 
Edit Distance: 3 

Strand A: --ACGA--A-T 
Strand B: TTACGACCAGT 
Edit Distance: 5 

Strand A: --CCG-TAAAT 
Strand B: TTACGACCAGT 
Edit Distance: 7 

мой выход

Strand A: ATCGT- 
Strand B: AGTTAC 
Edit Distance: 5 

Strand A: ATC-T- 
Strand B: ACGAAT 
Edit Distance: 5 

Strand A: ATC-T- 
Strand B: CCGTAAAT 
Edit Distance: 5 

Strand A: A-C-T- 
Strand B: TTACGACCAGT 
Edit Distance: 10 

Strand A: AGTTAC 
Strand B: ACGAAT 
Edit Distance: 5 

Strand A: AG-TAC 
Strand B: CCGTAAAT 
Edit Distance: 6 

Strand A: A--T-C 
Strand B: TTACGACCAGT 
Edit Distance: 7 

Strand A: AC-AAT 
Strand B: CCGTAAAT 
Edit Distance: 7 

Strand A: AC---T 
Strand B: TTACGACCAGT 
Edit Distance: 8 

Strand A: CC-TAAAT 
Strand B: TTACGACCAGT 
Edit Distance: 8 

findEditDistance

void EditDistance::findEditDistance() 
{ 
    int upperValue, leftValue, diagonalValue; 

    for (int i = 0; i < mLengthX; ++i) 
    { 
     table[i][0].stringLength = i; 
    } 

    for (int i = 0; i < mLengthY; ++i) 
    { 
     table[0][i].stringLength = i; 
    } 

    for (int i = 1; i < mLengthX; ++i) 
    { 
     for (int j = 1; j < mLengthY; ++j) 
     { 
      if (mStringX[i] == mStringY[j]) 
      { 
       table[i][j].direction = DIAGONAL; 
       table[i][j].stringLength = table[i - 1][j -1].stringLength; 
      } 
      else 
      { 
       upperValue = table[i - 1][j].stringLength; 
       leftValue = table[i][j - 1].stringLength; 
       diagonalValue = table[i - 1][j - 1].stringLength; 

       if (upperValue < leftValue) 
       { 
        if (upperValue < diagonalValue) 
        { 
         //upper is the lowest 
         table[i][j].stringLength = table[i - 1][j].stringLength + 1; 
         table[i][j].direction = UP; 
        } 
        else 
        { 
         //diagonal is lowest 
         table[i][j].stringLength = table[i - 1][j -1].stringLength + 1; 
         table[i][j].direction = DIAGONAL; 
        } 
       } 
       else if (leftValue < diagonalValue) 
       { 
        //left is lowest 
        table[i][j].stringLength = table[i][j - 1].stringLength + 1; 
        table[i][j].direction = LEFT; 
       } 
       else 
       { 
        //diagonal is lowest 
        table[i][j].stringLength = table[i - 1][j -1].stringLength + 1; 
        table[i][j].direction = DIAGONAL; 
       } 
      } 
     } 
    } 
} 

GetDistance

void EditDistance::getDistance() 
{ 
    int i = mStringX.length() - 1; 
    int j = mStringY.length() - 1; 

    numEdits = 0; 

    updateStrands (i, j); 
} 

updateStrands

void EditDistance::updateStrands (int i, int j) 
{ 
    if (i == 0 || j == 0) 
    { 
     return; 
    } 

    if (table[i][j].direction == DIAGONAL) 
    { 
     ++numEdits; 
     updateStrands (i - 1, j - 1); 
    } 
    else if (table[i][j].direction == UP) 
    { 
     mStringY[j] = '-'; 
     ++numEdits; 
     updateStrands (i - 1, j); 
    } 
    else 
    { 
     mStringX[i] = '-'; 
     ++numEdits; 
     updateStrands (i, j - 1); 
    } 
} 

Answer 1

Проблема с расстоянием редактирования находится в вашем updateStrands. Он считает диагональные движения равными 1, когда на самом деле диагональное перемещение может иметь расстояние 1 (подстановка) или 0 (совпадение). Вы можете исправить это в updateStrands, но там действительно не нужно делать расчет там, когда номер уже находится в нижнем правом углу table.

Если вы хотите правильную «нить» (например, «ATCGTT--» и «A - GTTAC»), вам придется внести исправления в updateStrands (вы изменить элементов строк, где вы должны вставок), getDistance (вы начинаете не в том месте) и findEditDistance (вы не учитываете присвоение значений direction вдоль верхнего и левого краев при установке stringLength на i).