類似文字列を求める処理

C# diff

類似文字列を求める処理を書いてみました。文字列を与えると、候補文字列の配列中から近いもの順に返してくる関数です。あいまい検索などに応用できます。
書いてみましたと言っても、以前書いた Diff クラスの使い方の一例だったりします。これ書いてて思い出したけど、Diff 結果の読み取り方を書こうと思ってたのに忘れてた…。まあまたいつかそのうち…(^^;

この処理は２つの文字列の編集距離を求めて、近いもの順に並べる処理を行っています。編集距離とは、挿入・削除・置換によって一方の文字列をもう一方の文字列にするのに何回操作が必要かという回数です。ただし、置換を含めるよりも挿入と削除だけの操作の距離を使ったほうが精度がよいので、ここで紹介するものは置換を数えません。つまり、一文字の置換は挿入と削除の距離２とします。コメントアウトしてある部分を生かして前の行をコメントアウトすると置換を一回と数えます(精度は落ちます)。

StringEditDistance.cs

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

namespace StringEditDistance
{
  public static class StringEditDistance
  {
    /// <summary>候補文字列配列を与えられた文字列の編集距離が近い順にソートします</summary>
    /// <param name="org">基準となる文字列</param>
    /// <param name="array">候補文字列の配列</param>
    /// <returns>候補文字列の結果シーケンス</returns>
    public static IEnumerable<string> SortByDistance( this string org, string[] array )
    {
      if ( array == null )
        throw new ArgumentNullException( "array" );
      if ( org == null )
        org = "";

      Func<string, int> func = s => FastDiff.DiffChar( org, s )
        .Where( r => r.Modified )
        .Sum( r => r.OriginalLength + r.ModifiedLength ); // 置換を含まず、挿入と削除の距離を求める
      //.Sum( r => Math.Max( r.OriginalLength, r.ModifiedLength ) ); // 置換を含む(精度は悪くなる)

      var q = from s in array
              select new { Word = s, Length = func( s ) } into e
              orderby e.Length
              select e.Word;

      return q;
    }
  }
}

横に長くてスミマセン。配列中のすべての候補との距離を調べるので処理時間はそれなりに食います。
FastDiff は http://d.hatena.ne.jp/siokoshou/20070315 にあります。
では、使ってみます。

Program.cs

using System;
using System.Linq;

namespace StringEditDistance
{
  class Program
  {
    static void Main()
    {
      string[] candidates = { "クラス", "イベント", "デリゲート", "ジェネリクス", "集合", };
      var s = "ジェネリック".SortByDistance( candidates ).First();
      Console.WriteLine( s ); // ジェネリクス が表示される
      Console.ReadKey();
    }
  }
}

単純なカラクリだけにできることには限界があるけど、使い方によってはなかなか便利です。煮るなり焼くなりなんなりとどうぞ。
# SortByDistance() の名前からすると、引数が逆のほうがいいかなぁ…。でも気持ちはこの順なんだよなぁ。良イ名前求ム。

とここまで書いてから Wikipedia に C# の編集距離を求めるコードへのリンクがあるのに気づいた…。試してみたら凄い速かった…。↑のコードを非 LINQ で書くとだいたい半分程度まで高速化できたけど、それでもリンク先の VectorLevenshtein の倍程度遅いです。GNULevenshtein コードのバグありバージョンはさらにその倍弱速いので後でバグってないバージョンも試してみます。O(NP) のアルゴリズムは比較する文字列が長いときに有利なので、まぁしょうがないか。Diff のための処理も入ってるんでかなうはずもないし。
というわけで、http://corsis.blogspot.com/search/label/levenshtein のコードは速いというお話でした(^^;


参考: