レーベンシュタイン編集距離アルゴリズムを機能させようとしていますが、何らかの理由で編集数が正しくありません。自分の間違いがどこにあるのかわからず、誰かが私が間違っていることを見ているのではないかと思っていました。
入力
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
検索編集距離
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;
}
}
}
}
}
取得距離
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);
}
}