我正在尝试让我的Levenshtein编辑距离算法工作,但由于某种原因,编辑次数不正确。我看不出我的错误在哪里,我想知道是否有人看到我做错了什么。
输入
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);
}
更新股线
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);
}
}
编辑距离的问题出在您的updateStrands
中。它将对角线移动计为 1,而实际上对角线移动的距离可以是 1(替换)或 0(匹配)。您可以在 updateStrands
中解决此问题,但是当数字已经在table
的右下角时,实际上根本不需要在那里进行计算。
如果你想要正确的"股"(例如"ATCGTT--"和"A--GTTAC"),你将不得不在updateStrands
(你改变你应该插入的字符串元素),getDistance
(你从错误的地方开始)和findEditDistance
(当你stringLength
设置为i
时,你忽略了沿上边缘和左边缘为direction
分配值)。