類似文字列を求める処理を改良

id:siokoshou:20080324 の類似文字列を求める処理をちょっと改良。かなり使えるかも。一文字も同じ文字がなければ捨てるようにしてみました。編集距離が比較する両方の文字列の長さの合計以上であれば、それは完全に文字列を置き換えたということなので、つまり一文字も一致していないということです。置換を含めた距離の場合は長いほうの文字列長以上なら一文字も一致していないことになります。

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, Distance = func( s ) } into e
              where e.Distance < org.Length + e.Word.Length // new!
              orderby e.Distance
              select e.Word;

      return q;
    }
  }
}

orderby の前に捨てるための where を追加しました。ついでにプロパティ名を Length から Distance にリファクタ。

string[] candidates = { "クラス", "イベント", "デリゲート", "ジェネリクス", "集合", };
var s = "メソッド".SortByDistance( candidates ).FirstOrDefault();
Console.WriteLine( s );

とすると何も表示されません。この例のように、結果が空シーケンスの場合があるので、FirstOrDefault() や Any() での検査が必要になります。