Hatena::ブログ(Diary)

当面C#と.NETな記録 このページをアンテナに追加 RSSフィード

2008/3/25 (火)

[][] 類似文字列を求める処理を改良  類似文字列を求める処理を改良を含むブックマーク  類似文字列を求める処理を改良のブックマークコメント

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() での検査が必要になります。

トラックバック - http://d.hatena.ne.jp/siokoshou/20080325

2008/3/24 (月)

[][] 類似文字列を求める処理  類似文字列を求める処理を含むブックマーク  類似文字列を求める処理のブックマークコメント

類似文字列を求める処理を書いてみました。文字列を与えると、候補文字列の配列中から近いもの順に返してくる関数です。あいまい検索などに応用できます。

書いてみましたと言っても、以前書いた Diff クラスの使い方の一例だったりします。これ書いてて思い出したけど、Diff 結果の読み取り方を書こうと思ってたのに忘れてた…。まあまたいつかそのうち…(^^;

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

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() の名前からすると、引数が逆のほうがいいかなぁ…。でも気持ちはこの順なんだよなぁ。良イ名前求ム。

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

というわけで、http://corsis.blogspot.com/search/label/levenshtein のコードは速いというお話でした(^^;


参考:

cetin@sertcom.decetin@sertcom.de 2008/04/02 02:31 Hi Can you please tell me what ”というわけで、http://corsis.blogspot.com/search/label/levenshtein のコードは速いというお話でした(^^;” means?

Cetin Sert ^_^

siokoshousiokoshou 2008/04/03 01:33 Hi cetin.
The short answer is ”My conclusion. http://corsis.blogspot.com/search/label/levenshtein ’s code is fast.” (free translation)
The long answer: First, I wrote a code in search of the Levenshtein distance with the diff class which I ported. But, I noticed a link to your blog entry of wikipedia afterwards. Several times were faster than the code that I wrote when I tried your code. I should have noticed your code earlier!

shimshim 2012/12/01 14:47 ソースコード大変参考になりました。

もし、発表されている論文その他ありましたら、
引用させていただきたいと思います。

2008/3/9 (日)

[] user.config ファイルを探す : または実用的な LINQ サンプル  user.config ファイルを探す : または実用的な LINQ サンプルを含むブックマーク  user.config ファイルを探す : または実用的な LINQ サンプルのブックマークコメント

クライアントで動く .NET アプリのアプリケーション設定で、ユーザースコープなデータを定義すると user.config ファイルに記録されます。この user.config ファイルを探して列挙するコードを書きました。id:siokoshou:20071227#p1 のファイル列挙のサンプルとしてどうぞ。

ApplicationSettingsBase.Upgrade() をオーバーライドするときや、よそのアプリの user.config を見たいときなどに使えます。

user.config の FileInfo を列挙して返します。バージョンが新しいものから古いものへ、同じバージョンがあれば(署名してないと実行ファイルのパスを変えると user.config は異なるディレクトリに記録される)書き込み時刻が新しいものから古いものへ、という順に並べて返します。LINQ でさらに絞り込みも楽々です。

company と product は、対象アプリの AssemblyCompany と AssemblyProduct で指定した文字列を入れてください。

public static IEnumerable<FileInfo>
  SearchUserConfig( string company, string product )
{
  if ( company == null )
    company = "";

  var path = Path.Combine(
    Environment.GetFolderPath( Environment.SpecialFolder.LocalApplicationData ),
    company );
  var dir = new DirectoryInfo( path ).GetDirectories(
    product + "*" );

  var files = from d in dir
    from f in d.EnumFileSystemInfos().OfType<FileInfo>().Where( ff => ff.Name == "user.config" )
    where f.Directory.Name.Count( c => c == '.' ) == 3
    orderby new Version( f.Directory.Name ) descending, f.LastWriteTimeUtc descending
    select f;

  return files;
}

public static IEnumerable<FileSystemInfo>
  EnumFileSystemInfos( this DirectoryInfo dir )
{
  foreach ( var item in dir.GetFileSystemInfos() )
  {
    yield return item;

    var subDir = item as DirectoryInfo;
    if ( subDir != null )
    {
      foreach ( var subItem in subDir.EnumFileSystemInfos() )
      {
        yield return subItem;
      }
    }
  }
}

EnumFileSystemInfos() は nsharp さんのものをちょっと改造したもの。LINQ 登場でなんでも列挙してしまえば楽に扱えるようになりましたね。いろんなものを列挙して LINQ で扱うアイデアがあちこちで出てくることを期待してます。

EnumFileSystemInfos() を使っているので、標準の user.config が作られるディレクトリより深い階層に退避してあるような user.config ファイルも見つけてしまうのでご注意を。メリットでもあると思ったのでそのまま載せましたが、このロジックで困る場合は改造して使ってください。

よそのアプリの user.config を読みたい場合に System.Configuration 名前空間を使う方法もありますが、特にメリットもないので↑のコードでファイルを見つけて LINQ to XML で中身を読むのがおすすめです。苦労して ConfigurationManager.OpenMappedExeConfiguration あたりを調べたのに、面倒なだけで特にメリットがなかった…(T-T)

先週は System.Configuration と格闘してました。ここのドキュメントは酷すぎるので、疲れた…。

追記

LINQ 登場前はこういう新規性も何もないつまらない部分のコーディングって、モチベーションが上がらなくてぐずぐずして取り掛かれなかったんだけど、LINQ 登場でさっと書けるようになったし、LINQ で書くとどうなるかな?って部分が楽しいのでさっさと取り組めるようになりました。LINQ いいよ〜。

  • 2008/3/10 サンプルコードのエラー耐性を強化しました。
  • 2008/3/10 エラー耐性強化が一部まずかったので修正。

nsharpnsharp 2008/03/10 13:05 Treeの取り扱いは一度汎用化してみるとおもしろいですよ。(ちょっと長くなりますが、失礼・・・。)

public class Tree<T> {

  public Tree(T root, IEnumerable<Tree<T>> children) {
    Root = root;
    Children = children;
  }

  public T Root {
    get;
    private set;
  }

  public IEnumerable<Tree<T>> Children {
    get;
    private set;
  }

  public IEnumerable<T> Flatten() {
    yield return Root;
    foreach (var item in Children.SelectMany(x => x.Flatten())) {
      yield return item;
    }
  }

  public static Tree<T> Build(T root, Func<T, IEnumerable<T>> childrenSelector) {
    return new Tree<T>(root, childrenSelector(root).Select(x => Build(x, childrenSelector)));
  }
}

こうすると、EnumFileSystemInfos はメソッド化する必要もなくなります。

  var tree = Tree<FileSystemInfo>.Build(new DirectoryInfo(dirName), fsi =>
    Enumerable.Repeat(fsi as DirectoryInfo, 1).Where(d => d != null).SelectMany(d => d.GetFileSystemInfos())).Flatten();

どうしても横に長くなってしまいますが・・・。(´・ω・`)

siokoshousiokoshou 2008/03/10 14:02 おぉぅ。すばらしいコメントありがとうございます。Flatten きましたね!
そのうち書こうと思って忘れてたメモにリンクに欠けてるものリストがあって、ForEach, Cons, Flatten の3つを挙げてました。ForEach はすぐ書けるからいいとして、Cons は実は欠けてなくて new {} で配列作ればよくて、あと Flatten がいるのかいらないのか長いこと葛藤してました。
EnumFileSystemInfos が Flatten だよねぇというのは実は気づいてて、でも汎用的な Flatten が必要なのかなぁと。ときどき欲しいと思うんだけど、でもいつも SelectMany でなんとかなってしまってやっぱりいらないやと思って。本当に必要なのかどうかそのうちじっくり考えてみようと思ってました。いろんな言語にあるから、やっぱりあったほうがいいんでしょうねぇ。
Build() がすごいコードですね。じっくり読み解いてみます。

siokoshousiokoshou 2008/03/10 15:27 日記の横幅とコメント欄広げました(^^)

トラックバック - http://d.hatena.ne.jp/siokoshou/20080309

2008/3/8 (土)

[] 次期新機能 : 呼び出し階層  次期新機能 : 呼び出し階層を含むブックマーク  次期新機能 : 呼び出し階層のブックマークコメント

MIX08 に心奪われてる間に C# Community PM の Charlie Calvert さんの blog で月一恒例の次の新機能が発表されてました。微妙に月一じゃない気もするけど。

前回の Dynamic Lookup の話が大好評で C# チーム大助かりらしく、これからは Code Gallery に場所を移して正式に話し合いの場としてやっていくことになったようです。Dynamic Lookup のほうは、今見たらものすごい量のコメントがついてました。

そして第二回目のお題は Call Hierarchy。これは VisualStudio で予定している新機能で C# だけじゃなく VB も対象。

コード書いてる最中に、メソッドの呼び出し元ツリーと呼び先ツリーをたどれる機能で、別ウィンドウ表示と DataTip みたいな表示とを考えてるようです。モックアップスクリーンショットを直接見てみてください。

私は VisualStudio の「すべての参照の検索」のヘビーユーザーなので、これは便利そう。一段階だけじゃなく階層をたどれるってのがナイスです。

関連ネタ: Dynamic Loop http://d.hatena.ne.jp/siokoshou/20080127#p1

[] MIX08関連ネタ  MIX08関連ネタを含むブックマーク  MIX08関連ネタのブックマークコメント

MIX08 関連ネタいろいろ。どちらかというとマイナーなあたりのメモ。

一番盛り上がった Deep Zoom (SeaDragon)

Silverlight2 を入れたら見ておけ!なデモ。クリックでどんどんズーム。ズームアウトは左上あたりにマウスを持っていくと「-ボタン」が出てきます(追記:ホイールで OK だった)。スゲー、ナニコレ!どうなってるの?っていう新技術。

その解説など

MIX08サイト

オジーさんとジャグラー・スコットガさん(一番の盛り上がりはこっちかも?)の基調講演 日本語

ガイカワサキさんとバルマーたんの基調講演 日本語

裏MIX? Miguel さんに John Lam さんに Surface

網羅してないのであとはニュースサイトなどでどうぞ。

nsharpnsharp 2008/03/08 23:06 Deep Zoomでしたら、こちらで遊べますよ。
ttp://photozoom.mslivelabs.com/

好きな画像をうpして半日ぐらい待てば、ズーム可能な独自のアルバムのできあがり。

siokoshousiokoshou 2008/03/09 10:14 これはおもしろそうですね!
でも昨日、memorabilia.hardrock.com 見てたら PC が固まったので、ちょっと警戒してしまいます(^^;
うちの PC は WPF でときどき固まるようで…

2008/3/6 (木)

[] Microsoft Silverlight Tools Beta 1 for Visual Studio 2008 のインストール方法  Microsoft Silverlight Tools Beta 1 for Visual Studio 2008 のインストール方法を含むブックマーク  Microsoft Silverlight Tools Beta 1 for Visual Studio 2008 のインストール方法のブックマークコメント

Silverlight2β1 が公開されましたが、VisualStudio 向けのアドオンのインストール方法が罠っぽいのでメモしておきます。

http://www.microsoft.com/downloads/details.aspx?FamilyId=E0BAE58E-9C0B-4090-A1DB-F134D9F095FD&displaylang=en

Silverlight2β1を先にインストールすると、↑のインストールができないようです。いったん、アンインストールして↑から落とした silverlight_chainer.exe を実行するとインストールできます。日本語版には入れれないのかと思った…。なんだかなぁ。

2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 09 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 09 | 10 | 12 |
2009 | 01 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 07 |
2011 | 04 | 07 | 10 |
2012 | 04 | 12 |
2013 | 08 |
2014 | 03 | 08 |
2017 | 09 |