編集距離アルゴリズムを使って文字列を変換する

2つのドキュメントや文字列を比較して変更箇所を調べる方法

　リスト1に示すのは、StringEditDistanceプログラムで編集グラフの構築とノードの距離計算に使われているMakeEditGraph関数です。この関数はグラフの配列を作成し、左端の列と最上部の行を初期化します。次に、配列内を左から右に移動しながら他のノードの距離を記録します。

　リスト2に示すのは、結果の表示に使われているDisplayResultsルーチンです。このルーチンは、終了ノードから開始ノードに向かって編集グラフの最良の経路を逆方向にたどります。経由する各ノードで、ルーチンはそのノードに到達するときに行われた変更の種類（削除、挿入、または文字の維持）をチェックし、出力の先頭に適切な文字を追加します。図2を見ると分かるように、削除された文字は打ち消し線付きの赤色、挿入された文字は下線付きの青色、両方の文字列で共通する文字は黒色で表示されます。

リスト1　2つの文字列の編集グラフを記録する

<pre><code>
// Fill in the edit graph for two strings.
private Node[,] MakeEditGraph(string string1, string string2)
{
    // Make the edit graph array.
    int num_cols = string1.Length + 1;
    int num_rows = string2.Length + 1;
    Node[,] nodes = new Node[num_rows, num_cols];

    // Initialize the leftmost column.
    for (int r = 0; r < num_rows; r++)
    {
        nodes[r, 0].distance = r;
        nodes[r, 0].direction = Direction.FromAbove;
    }

    // Initialize the top row.
    for (int c = 0; c < num_cols; c++)
    {
        nodes[0, c].distance = c;
        nodes[0, c].direction = Direction.FromLeft;
    }

    // Fill in the rest of the array.
    char[] chars1 = string1.ToCharArray();
    char[] chars2 = string2.ToCharArray();
    for (int c = 1; c < num_cols; c++)
    {
        // Fill in column c.
        for (int r = 1; r < num_rows; r++)
        {
            // Fill in entry [r, c].
            // Check the three possible paths to here.
            int distance1 = nodes[r - 1, c].distance + 1;
            int distance2 = nodes[r, c - 1].distance + 1;
            int distance3 = int.MaxValue;
            if (chars1[c - 1] == chars2[r - 1])
            {
                // There is a diagonal link.
                distance3 = nodes[r - 1, c - 1].distance;
            }

            // See which is cheapest.
            if ((distance1 <= distance2) && (distance1 <= distance3))
            {
                // Come from above.
                nodes[r, c].distance = distance1;
                nodes[r, c].direction = Direction.FromAbove;
            }
            else if (distance2 <= distance3)
            {
                // Come from the left.
                nodes[r, c].distance = distance2;
                nodes[r, c].direction = Direction.FromLeft;
            }
            else
            {
                // Come from the diagonal.
                nodes[r, c].distance = distance3;
                nodes[r, c].direction = Direction.FromDiagonal;
            }
        }
    }
    
    // Display the graph's nodes (for debugging).
    //DumpArray(nodes);

    return nodes;
}
</pre></code>

リスト2　変更箇所を表示する

<pre><code>
// Display the changes.
private void DisplayResults(string string1, string string2, Node[,] nodes, RichTextBox rch)
{
    // Build a list of the moves from finish to start.
    int num_rows = nodes.GetUpperBound(0) + 1;
    int num_cols = nodes.GetUpperBound(1) + 1;
    int r = num_rows - 1;
    int c = num_cols - 1;

    // Make some fonts.
    Font normal_font = rch.Font;
    Font insert_font = new Font(rch.Font, FontStyle.Underline);
    Font delete_font = new Font(rch.Font, FontStyle.Strikeout);

    // Continue until we reach the upper left corner.
    rch.Clear();
    while ((r > 0) || (c > 0))
    {
        switch (nodes[r, c].direction)
        {
            case Direction.FromAbove:
                rch.Select(0, 0);
                rch.SelectedText = string2.Substring(r - 1, 1);
                rch.Select(0, 1);
                rch.SelectionFont = insert_font;
                rch.SelectionColor = Color.Blue;
                r--;
                break;
            case Direction.FromLeft:
                rch.Select(0, 0);
                rch.SelectedText = string1.Substring(c - 1, 1);
                rch.Select(0, 1);
                rch.SelectionFont = delete_font;
                rch.SelectionColor = Color.Red;
                c--;
                break;
            case Direction.FromDiagonal:
                rch.Select(0, 0);
                rch.SelectedText = string2.Substring(r - 1, 1);
                rch.Select(0, 1);
                rch.SelectionFont = normal_font;
                rch.SelectionColor = Color.Black;
                r--;
                c--;
                break;
        }
    }

    // Dispose of the fonts we created.
    insert_font.Dispose();
    delete_font.Dispose();
}
</pre></code>