Levenshtein Edit Distance 不计算编辑距离

Question

我正在尝试让我的 Levenshtein 编辑距离算法正常工作，但出于某种原因，编辑的数量不正确。我看不出我的错误在哪里，我想知道是否有人看到我做错了什么。

Input

5
ATCGTT
AGTTAC
ACGAAT
CCGTAAAT
TTACGACCAGT

expected output

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

my output

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.

的右下角时，根本不需要在那里进行计算

如果您想要正确的 "strands"（例如 "ATCGTT--" 和 "A--GTTAC"），您必须在 updateStrands 中进行更正（您更改字符串的元素，您应该插入 )、getDistance（您从错误的位置开始）和 findEditDistance（您忽略了赋值当您将 stringLength 设置为 i 时，沿左上边缘到 direction。

Levenshtein Edit Distance 不计算编辑距离

Levenshtein Edit Distance is not calculating edit distance

c++

algorithm

edit-distance

levenshtein-distance