2

我试图让我的 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);
    }
}
4

1 回答 1

1

编辑距离的问题在于您的updateStrands. 它将对角线移动计为 1，而实际上对角线移动的距离可以为 1（替换）或 0（匹配）。你可以在 中解决这个问题updateStrands，但是当数字已经在 的右下角时，根本不需要在那里进行计算table。

如果您想要正确的“链”（例如“ATCGTT--”和“A--GTTAC”），则必须进行更正updateStrands（更改应插入的字符串元素），getDistance（您从错误的开始放置）和（当您设置为时，您忽略了沿上边缘和左边缘findEditDistance分配值）。directionstringLengthi

于 2015-04-28T07:36:57.483 回答