1

我已经在 c# 中实现了 LevenshteinDistance 算法，如下所示。这段代码运行良好。但出于调试目的，我想打印矩阵但无法决定应该在哪里放置 Print 语句。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _Levenshtein_
{
    class Program
    {
        public static void Print(int[,] data)
        {
            for (int i = 0; i < data.GetUpperBound(0); i++)
            {
                for (int j = 0; j < data.GetUpperBound(1); j++)
                {
                    Console.Write(data[i, j] + " ");
                }
            }
            Console.WriteLine();
        }
        public static int LevenshteinDistance(string source, string target)
        {
            if (String.IsNullOrEmpty(source))
            {
                if (String.IsNullOrEmpty(target)) return 0;
                {

                    return target.Length;
                }
            }
            if (String.IsNullOrEmpty(target)) return source.Length;

            if (source.Length > target.Length)
            {
                var temp = target;
                target = source;
                source = temp;
            }

            var m = target.Length;
            var n = source.Length;
            var distance = new int[2, m + 1];
            // Initialize the distance 'matrix'
            for (var j = 1; j <= m; j++) distance[0, j] = j;


                Console.Write(target + " ");

            var currentRow = 0;
            for (var i = 1; i <= n; ++i)
            {
                currentRow = i & 1;
                distance[currentRow, 0] = i;
                var previousRow = currentRow ^ 1;
                Console.WriteLine(source[i-1] + " " );
                for (var j = 1; j <= m; j++)
                {
                    var cost = (target[j - 1] == source[i - 1] ? 0 : 1);

                    distance[currentRow, j] = Math.Min(Math.Min(distance[previousRow, j] + 1,distance[currentRow, j - 1] + 1),distance[previousRow, j - 1] + cost);
                    Print(distance);        
                }
                Console.WriteLine();
            }
            return distance[currentRow, m];
        }
        static void Main(string[] args)
        {
            LevenshteinDistance("Sunday", "Saturday");
        }
    }
}
4

1 回答 1

1

我添加了注释以打印距离矩阵。

// `target` string in first ROW, each char in 4 width
// for (var j = 0; j <=target.Length; j++)
//    Console.Write(target[j] + "   ") 
for (var i = 1; i <= n; ++i)
{
    currentRow = i & 1;
    distance[currentRow, 0] = i;
    var previousRow = currentRow ^ 1;
    // print: `source[i]`  ith char only one Console.Write(source[i] + " ")
    // Console.Write(source[i] + " ") 
    for (var j = 1; j <= m; j++)
    {
        var cost = (target[j - 1] == source[i - 1] ? 0 : 1);
        distance[currentRow, j] = Math.M........);
        // write distance in 3 width
           //Console.Write(distance[currentRow, j] + " ")  
    }       

      // Console.Write("\n")
}

编辑：

长度“星期日”= 6
长度“星期六”= 8 

if (source.Length > target.Length){  // target is large .
    // swap means 
}

所以目标是“星期六”字符串。（水平字符串）
和“星期日”是垂直的

您将获得如下图所示的输出：
在此处输入图像描述

在Codepade上是我的工作 C 代码，可以打印编辑距离矩阵，如：

      S  a  t  u  r  d  a  y  

S     0  1  2  3  4  5  6  7
u     1  1  2  2  3  4  5  6
n     2  2  2  3  3  4  5  6
d     3  3  3  3  4  3  4  5
a     4  3  4  4  4  4  3  4
y     5  4  4  5  5  5  4  3
于 2013-03-30T19:24:32.013 回答