2010-09-10T02:16:00の更新内容

programming/tips/compute_levenshtein_distance/index.wiki.txt

current previous
1,134 0,0
+
${smdncms:title,Levenshtein距離(編集距離)を求める}
+
${smdncms:keywords,C#,編集距離,レーベンシュタイン距離,Levenshtein Distance}
+
${smdncms:tags,api/.net,lang/c#,lang/vb.net}
+

          
+
-参考
+
--[[Levenshtein distance - Wikipedia, the free encyclopedia:http://en.wikipedia.org/wiki/Levenshtein_distance]]
+
--[[レーベンシュタイン距離 - Wikipedia:http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2]]
+

          
+
#prompt(実行例){{
+
kitten => sitting : 3
+
Saturday => Sunday : 3
+
 => foo : 3
+
にほんご => にっぽんご : 2
+
}}
+

          
+
以下、C#とVBでの実装。 最適化はしていない。
+

          
+
#code(cs,C#での実装){{
+
using System;
+

          
+
class Sample {
+
  private static int Min(int x, int y, int z)
+
  {
+
    return Math.Min(Math.Min(x, y), z);
+
  }
+

          
+
  private static int ComputeLevenshteinDistance(string strX, string strY)
+
  {
+
    if (strX == null)
+
      throw new ArgumentNullException("strX");
+
    if (strY == null)
+
      throw new ArgumentNullException("strY");
+

          
+
    if (strX.Length == 0)
+
      return strY.Length;
+
    if (strY.Length == 0)
+
      return strX.Length;
+

          
+
    var d = new int[strX.Length + 1, strY.Length + 1];
+

          
+
    for (var i = 0; i <= strX.Length; i++) {
+
      d[i, 0] = i;
+
    }
+

          
+
    for (var j = 0; j <= strY.Length; j++) {
+
      d[0, j] = j;
+
    }
+

          
+
    for (var j = 1; j <= strY.Length; j++) {
+
      for (var i = 1; i <= strX.Length; i++) {
+
        if (strX[i - 1] == strY[j - 1])
+
          d[i, j] = d[i - 1, j - 1];
+
        else
+
          d[i, j] = Min(d[i - 1, j] + 1,
+
                        d[i, j - 1] + 1,
+
                        d[i - 1, j - 1] + 1);
+
      }
+
    }
+

          
+
    return d[strX.Length, strY.Length];
+
  }
+

          
+
  public static void Main()
+
  {
+
    foreach (var texts in new[] {
+
      new[] {"kitten", "sitting"},
+
      new[] {"Saturday", "Sunday"},
+
      new[] {"", "foo"},
+
      new[] {"にほんご", "にっぽんご"},
+
    }) {
+
      Console.WriteLine("{0} => {1} : {2}",
+
                        texts[0],
+
                        texts[1],
+
                        ComputeLevenshteinDistance(texts[0], texts[1]));
+
    }
+
  }
+
}
+
}}
+

          
+
#code(vb,VBでの実装){{
+
Imports System
+

          
+
Class Sample
+
  Private Shared Function Min(ByVal x As Integer, ByVal y As Integer, ByVal z As Integer) As Integer
+
    Return Math.Min(Math.Min(x, y), z)
+
  End Function
+

          
+
  Private Shared Function ComputeLevenshteinDistance(ByVal strX As String, ByVal strY As String) As Integer
+
    If strX Is Nothing Then Throw New ArgumentNullException("strX")
+
    If strY Is Nothing Then Throw New ArgumentNullException("strY")
+

          
+
    If strX.Length = 0 Then Return strY.Length
+
    If strY.Length = 0 Then Return strX.Length
+

          
+
    Dim d(strX.Length + 1, strY.Length + 1) As Integer
+

          
+
    For i As Integer = 0 To strX.Length
+
      d(i, 0) = i
+
    Next
+

          
+
    For j As Integer = 0 To strY.Length
+
      d(0, j) = j
+
    Next
+

          
+
    For j As Integer = 1 To strY.Length
+
      For i As Integer = 1 To strX.Length
+
        If strX(i - 1) = strY(j - 1) Then
+
          d(i, j) = d(i - 1, j - 1)
+
        Else
+
          d(i, j) = Min(d(i - 1, j) + 1, d(i, j - 1) + 1, d(i - 1, j - 1) + 1)
+
        End If
+
      Next
+
    Next
+

          
+
    Return d(strX.Length, strY.Length)
+
  End Function
+

          
+
  Public Shared Sub Main()
+
    For Each texts As String() In New String()() { _
+
      New String() {"kitten", "sitting"}, _
+
      New String() {"Saturday", "Sunday"}, _
+
      New String() {"", "foo"}, _
+
      New String() {"にほんご", "にっぽんご"} _
+
    }
+
      Console.WriteLine("{0} => {1} : {2}", _
+
                        texts(0), _
+
                        texts(1), _
+
                        ComputeLevenshteinDistance(texts(0), texts(1)))
+
    Next
+
  End Sub
+
End Class
+
}}
+

          
+