Hatena::ブログ(Diary)

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

2008/3/25 (火)

[][] 類似文字列を求める処理を改良  類似文字列を求める処理を改良 - 当面C#と.NETな記録 を含むブックマーク  類似文字列を求める処理を改良 - 当面C#と.NETな記録 のブックマークコメント

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

2008/3/24 (月)

[][] 類似文字列を求める処理  類似文字列を求める処理 - 当面C#と.NETな記録 を含むブックマーク  類似文字列を求める処理 - 当面C#と.NETな記録 のブックマークコメント

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

書いてみましたと言っても、以前書いた 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 ソースコード大変参考になりました。

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

2007/3/15 (木)

siokoshou2007-03-15

[][][] .NET diff class  .NET diff class - 当面C#と.NETな記録 を含むブックマーク  .NET diff class - 当面C#と.NETな記録 のブックマークコメント

.NET 高速 diff classを公開します。2つの文字列のdiffを取ります。行単位のdiff(UNIXのdiffコマンドのような)と、文字単位のdiffを取れます。

"An O(NP) Sequence Comparison Algorithm"(PDF), Sun Wu, Udi Manber, Gene Myers, (1989) のアルゴリズムを使用したC#によるdiffクラスです。非常に賢い処理を作り上げた著者らに感謝いたします。

自由に使用してください。ただし、内容のいかなる保障もしません。バグを見つけたらコメントで教えてください。

テストはしていますが、仕事に使うのであれば再テストをしてから使用してください。

API

  • 行単位diff
    • public static DiffResult[] Diff( string textA, string textB )
    • public static DiffResult[] Diff( string textA, string textB, DiffOption option )
  • 文字単位diff
    • public static DiffResult[] DiffChar( string textA, string textB )
    • public static DiffResult[] DiffChar( string textA, string textB, DiffOption option )

DiffOption は TrimSpace, IgnoreSpace, IgnoreCase があります。詳しくはソースコードを参照してください。

結果は DiffResult 型の配列です。1つ目の文字列をオリジナル、2つ目の文字列を変更後の文字列とすると、両者の共通部分と異なる部分のレポートが結果として返ってきます。こちらも詳しくはソースコードを参照してください。

(2009/8/24 追記 行単位 diff のバグを修正。id:SiroKuro さん、ご指摘ありがとうございます。

参考 http://d.hatena.ne.jp/SiroKuro/20090823/1251043905)

以下、ソースコード。

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Diagnostics;

namespace FastDiff
{
  [Serializable]
  public struct DiffOption { public bool TrimSpace, IgnoreSpace, IgnoreCase; }

  [Serializable]
  public class DiffResult
  {
    public bool Modified; // 変更あり?
    public int OriginalStart;
    public int OriginalLength;
    public int ModifiedStart;
    public int ModifiedLength;

    public DiffResult( bool modified, int orgStart, int orgLength, int modStart, int modLength )
    {
      this.Modified = modified;
      this.OriginalStart = orgStart;
      this.OriginalLength = orgLength;
      this.ModifiedStart = modStart;
      this.ModifiedLength = modLength;
    }

    public override string ToString()
    {
      return ( ( this.Modified ) ? "Modified" : "Common" )
        + ", OrgStart:" + this.OriginalStart + ", OrgLen:" + this.OriginalLength
        + ", ModStart:" + this.ModifiedStart + ", ModLen:" + this.ModifiedLength;
    }
  }

  public class FastDiff
  {
    private int[] dataA, dataB;
    private string[] linesA, linesB;
    private bool isSwap;
    private Snake[] fp;

    private delegate bool IsSame( int posA, int posB );
    private IsSame isSame;


    private FastDiff() { }

    /// <summary>複数行の文字列を行単位で比較します</summary>
    /// <param name="textA">元テキスト</param>
    /// <param name="textB">変更テキスト</param>
    /// <returns>比較結果</returns>
    public static DiffResult[] Diff( string textA, string textB )
    {
      DiffOption option = new DiffOption();
      return Diff( textA, textB, option );
    }

    /// <summary>複数行の文字列を行単位で比較します</summary>
    /// <param name="textA">元テキスト</param>
    /// <param name="textB">変更テキスト</param>
    /// <param name="option">オプション指定</param>
    /// <returns>比較結果</returns>
    public static DiffResult[] Diff( string textA, string textB, DiffOption option )
    {
      if ( string.IsNullOrEmpty( textA ) || string.IsNullOrEmpty( textB ) )
        return StringNullOrEmpty( textA, textB );

      FastDiff diff = new FastDiff();
      return diff.DiffCore( textA, textB, option );
    }

    private DiffResult[] DiffCore( string textA, string textB, DiffOption option )
    {
      this.linesA = SplitLine( textA, option );
      this.linesB = SplitLine( textB, option );

      if ( this.linesB.Length < this.linesA.Length )
      {
        this.isSwap = true;

        string[] tmps = this.linesA;
        this.linesA = this.linesB;
        this.linesB = tmps;
      }
      this.dataA = MakeHash( this.linesA );
      this.dataB = MakeHash( this.linesB );

      this.isSame = delegate( int posA, int posB )
      {
        return ( this.dataA[ posA ] == this.dataB[ posB ] ) && ( this.linesA[ posA ] == this.linesB[ posB ] );
      };

      return DetectDiff();
    }

    /// <summary>単一行の各文字を比較します</summary>
    /// <param name="textA">元テキスト</param>
    /// <param name="textB">変更テキスト</param>
    /// <returns>比較結果</returns>
    public static DiffResult[] DiffChar( string textA, string textB )
    {
      DiffOption option = new DiffOption();
      return DiffChar( textA, textB, option );
    }

    /// <summary>単一行の各文字を比較します</summary>
    /// <param name="textA">元テキスト</param>
    /// <param name="textB">変更テキスト</param>
    /// <param name="option">オプション指定</param>
    /// <returns>比較結果</returns>
    public static DiffResult[] DiffChar( string textA, string textB, DiffOption option )
    {
      if ( string.IsNullOrEmpty( textA ) || string.IsNullOrEmpty( textB ) )
        return StringNullOrEmpty( textA, textB );

      FastDiff diff = new FastDiff();
      if ( textA.Length <= textB.Length )
      {
        diff.SplitChar( textA, textB, option );
      }
      else
      {
        diff.isSwap = true;
        diff.SplitChar( textB, textA, option );
      }

      diff.isSame = delegate( int posA, int posB )
      {
        return diff.dataA[ posA ] == diff.dataB[ posB ];
      };

      return diff.DetectDiff();
    }


    private static DiffResult[] StringNullOrEmpty( string textA, string textB )
    {
      int lengthA = ( string.IsNullOrEmpty( textA ) ) ? 0 : textA.Length;
      int lengthB = ( string.IsNullOrEmpty( textB ) ) ? 0 : textB.Length;
      return PresentDiff( new CommonSubsequence( lengthA, lengthB, 0, null ), true );
    }

    private void SplitChar( string textA, string textB, DiffOption option )
    {
      this.dataA = SplitChar( textA, option );
      this.dataB = SplitChar( textB, option );
    }

    private static int[] SplitChar( string text, DiffOption option )
    {
      if ( option.IgnoreCase )
        text = text.ToUpperInvariant();

      // TODO: FIXME! Optimize this
      if ( option.IgnoreSpace )
        text = Regex.Replace( text, @"\s+", " " );

      if ( option.TrimSpace )
        text = text.Trim();

      int[] result = new int[ text.Length ];
      for ( int i = 0; i < text.Length; i++ )
        result[ i ] = text[ i ];
      return result;
    }

    private static string[] SplitLine( string text, DiffOption option )
    {
      if ( option.IgnoreCase )
        text = text.ToUpperInvariant();

      string[] lines = text.Split( new string[] { "\r\n", "\n", "\r" }, StringSplitOptions.None );

      // TODO: FIXME! Optimize this
      if ( option.IgnoreSpace )
        for ( int i = 0; i < lines.Length; ++i )
          lines[ i ] = Regex.Replace( lines[ i ], @"\s+", " " );

      if ( option.TrimSpace )
        for ( int i = 0; i < lines.Length; ++i )
          lines[ i ] = lines[ i ].Trim();

      return lines;
    }

    private static int[] MakeHash( string[] texts )
    {
      int[] hashs = new int[ texts.Length ];

      for ( int i = 0; i < texts.Length; ++i )
        hashs[ i ] = texts[ i ].GetHashCode();

      return hashs;
    }

    private DiffResult[] DetectDiff()
    {
      Debug.Assert( this.dataA.Length <= this.dataB.Length );

      this.fp = new Snake[ this.dataA.Length + this.dataB.Length + 3 ];
      int d = this.dataB.Length - this.dataA.Length;
      int p = 0;
      do
      {
        //Debug.Unindent();
        //Debug.WriteLine( "p:" + p );
        //Debug.Indent();

        for ( int k = -p; k < d; k++ )
          SearchSnake( k );

        for ( int k = d + p; k >= d; k-- )
          SearchSnake( k );

        p++;
      }
      while ( this.fp[ this.dataB.Length + 1 ].posB != ( this.dataB.Length + 1 ) );

      // 末尾検出用のCommonSubsequence
      CommonSubsequence endCS = new CommonSubsequence( this.dataA.Length, this.dataB.Length, 0, this.fp[ this.dataB.Length + 1 ].CS );
      CommonSubsequence result = CommonSubsequence.Reverse( endCS );

      if ( this.isSwap )
        return PresentDiffSwap( result, true );
      else
        return PresentDiff( result, true );
    }

    private void SearchSnake( int k )
    {
      int kk = this.dataA.Length + 1 + k;
      CommonSubsequence previousCS = null;
      int posA = 0, posB = 0;

      int lk = kk - 1;
      int rk = kk + 1;

      // 論文のfp[n]は-1始まりだが、0始まりのほうが初期化の都合がよいため、
      // +1のゲタを履かせる。fpから読む際は-1し、書く際は+1する。
      int lb = this.fp[ lk ].posB;
      int rb = this.fp[ rk ].posB - 1;

      //Debug.Write( "fp[" + string.Format( "{0,2}", k ) + "]=Snake( " + string.Format( "{0,2}", k )
      //    + ", max( fp[" + string.Format( "{0,2}", ( k - 1 ) ) + "]+1= " + string.Format( "{0,2}", lb )
      //    + ", fp[" + string.Format( "{0,2}", ( k + 1 ) ) + "]= " + string.Format( "{0,2}", rb ) + " ))," );

      if ( lb > rb )
      {
        posB = lb;
        previousCS = this.fp[ lk ].CS;
      }
      else
      {
        posB = rb;
        previousCS = this.fp[ rk ].CS;
      }
      posA = posB - k;

      int startA = posA;
      int startB = posB;

      //Debug.Write( "(x: " + string.Format( "{0,2}", startA ) + ", y: " + string.Format( "{0,2}", startB ) + " )" );

      while ( ( posA < this.dataA.Length )
        &&  ( posB < this.dataB.Length )
        &&  this.isSame( posA, posB ) )
      {
        posA++;
        posB++;
      }

      if ( startA != posA )
      {
        this.fp[ kk ].CS = new CommonSubsequence( startA, startB, posA - startA, previousCS );
      }
      else
      {
        this.fp[ kk ].CS = previousCS;
      }
      this.fp[ kk ].posB = posB + 1; // fpへ+1して書く。論文のfpに+1のゲタを履かせる。

      //Debug.WriteLine( "= " + string.Format( "{0,2}", posB ) );
    }

    /// <summary>結果出力</summary>
    private static DiffResult[] PresentDiff( CommonSubsequence cs, bool wantCommon )
    {
      List<DiffResult> list = new List<DiffResult>();
      int originalStart = 0, modifiedStart = 0;

      while ( true )
      {
        if (   originalStart < cs.StartA
          || modifiedStart < cs.StartB )
        {
          DiffResult d = new DiffResult(
            true,
            originalStart, cs.StartA - originalStart,
            modifiedStart, cs.StartB - modifiedStart );
          list.Add( d );
        }

        // 末尾検出
        if ( cs.Length == 0 ) break;

        originalStart = cs.StartA;
        modifiedStart = cs.StartB;

        if ( wantCommon )
        {
          DiffResult d = new DiffResult(
            false,
            originalStart, cs.Length,
            modifiedStart, cs.Length );
          list.Add( d );
        }
        originalStart += cs.Length;
        modifiedStart += cs.Length;

        cs = cs.Next;
      }
      return list.ToArray();
    }

    /// <summary>結果出力</summary>
    private static DiffResult[] PresentDiffSwap( CommonSubsequence cs, bool wantCommon )
    {
      List<DiffResult> list = new List<DiffResult>();
      int originalStart = 0, modifiedStart = 0;

      while ( true )
      {
        if (   originalStart < cs.StartB
          || modifiedStart < cs.StartA )
        {
          DiffResult d = new DiffResult(
            true,
            originalStart, cs.StartB - originalStart,
            modifiedStart, cs.StartA - modifiedStart );
          list.Add( d );
        }

        // 末尾検出
        if ( cs.Length == 0 ) break;

        originalStart = cs.StartB;
        modifiedStart = cs.StartA;

        if ( wantCommon )
        {
          DiffResult d = new DiffResult(
            false,
            originalStart, cs.Length,
            modifiedStart, cs.Length );
          list.Add( d );
        }
        originalStart += cs.Length;
        modifiedStart += cs.Length;

        cs = cs.Next;
      }
      return list.ToArray();
    }

    private struct Snake
    {
      public int posB;
      public CommonSubsequence CS;

      public override string ToString()
      {
        return "posB:" + this.posB + ", CS:" + ( ( this.CS == null ) ? "null" : "exist" );
      }
    }

    private class CommonSubsequence
    {
      private int startA_, startB_;
      private int length_;
      public CommonSubsequence Next;

      public int StartA { get { return this.startA_; } }
      public int StartB { get { return this.startB_; } }
      public int Length { get { return this.length_; } }

      public CommonSubsequence() { }

      public CommonSubsequence( int startA, int startB, int length, CommonSubsequence next )
      {
        this.startA_ = startA;
        this.startB_ = startB;
        this.length_ = length;
        this.Next = next;
      }

      /// <summary>リンクリスト反転</summary>
      public static CommonSubsequence Reverse( CommonSubsequence old )
      {
        CommonSubsequence newTop = null;
        while ( old != null )
        {
          CommonSubsequence next = old.Next;
          old.Next = newTop;
          newTop = old;
          old = next;
        }
        return newTop;
      }

      public override string ToString()
      {
        return "Length:" + this.Length + ", A:" + this.StartA.ToString()
          + ", B:" + this.StartB.ToString() + ", Next:" + ( ( this.Next == null ) ? "null" : "exist" );
      }
    }

  }
}

"An O(ND) Difference Algorithm and Its Variations"(PDF), EUGENE W. MYERS, (1986)、APIやオプションはAn O(ND) Difference Algorithm for C#を、読み取り結果の保存についてはSubversionを参考にしました。感謝します。

subversionにあった番兵は使いませんでした。ハッシュ値と番兵の値が衝突した場合に配列の範囲外にアクセスする可能性がありうるので。subversionがリングリストにしてるのはこの対策かも。衝突するとどうなるのかよくわかりませんが、おそらくセキュリティホールではないと思います。ただ、正常なdiffは出せないような気がする…。

コード中のコメントアウトしてあるDebug.Write等を動かしながら、論文を読むと動きがわかると思います。すんごいよくできた賢いアルゴリズムでした。アルゴリズムの説明はそのうちちょっとだけ書くかもしれないし、面倒だから書かないかもしれないしw

読み取り方は希望があればコードをアップします。

NNNN 2007/03/26 17:14 ども。Diffの話題を漁っていてたどり着きました。
数年前にDiffのロジックに興味を持って、vivi作者の津田氏の「技術文書」で紹介されていた論文を読み、辛うじてO(ND)が理解できたのですが、O(NP)アルゴリズムに関しては解説しているサイトが見あたらず、『O(ND)は読んだしもう良いかなー』という感じで、暫く手を触れていませんでした。

宜しければザックリとでもO(NP)の解説を書いていただけるとありがたいです。

siokoshousiokoshou 2007/03/27 01:46 あまりわかってないけど(^^; さらっと書いてみます。O(ND)との違いは探索を狭い範囲からはじめて徐々に広げていく点です。k=0〜の範囲(中央部分)から探索をはじめ、一致がなくなったところで次のループで両隣のkについて探索し、再び0〜の範囲を見るってことの繰り返しです。これに対してO(ND)はすぐに広い範囲を探し始めるので、O(NP)より無駄が多いです。文章でたくさん説明するより、動きを見ると巧みさがすぐわかりますよ。
C#を動かせる環境があれば、このコードのDebug.Writeをはずして動かすと、探索の軌跡がきれいに表示されます。これと、EditGraphをつき合わせてたどってみると、動きが見えると思います。お試しあれ〜。

JakenJaken 2010/11/21 13:16 こんにちは、はじめまして。古い記事にコメント失礼します(^^;
バイナリDIFF差分がやりたくて調べてたら、ここにたどり着きました。大変参考になります。

早速、プログラムについて質問と改善(改悪?)案です。
PresentDiffとPresentDiffSwapがAとBを反転させるだけの同じ処理をしているように見えます。
「while(true)」のループ内でisSwapを判定してしまえば、一本化できると思うのですが、これを分けた理由は、やっぱりif判定の回数を減らして速度UPしたいからでしょうか。
速度を量っていないので、どれぐらい遅くなるかわかりませんが、こんな方法を思いつきましたので、ご報告です。
PresentDiffにisSwapを引数で渡して、内部の処理をこんな感じにします。
int startA, startB;
Func<CommonSubsequence, int> csStartA = null;
Func<CommonSubsequence, int> csStartB = null;
if (isSwap)
{
csStartA = (CommonSubsequence csf) => { return csf.StartB; };
csStartB = (CommonSubsequence csf) => { return csf.StartA; };
}
else
{
csStartA = (CommonSubsequence csf) => { return csf.StartA; };
csStartB = (CommonSubsequence csf) => { return csf.StartB; };
}

while (true)
{
startA = csStartA(cs);
startB = csStartB(cs);
省略。以後ループ内でstartAとstartBを参照する。
}
毎回ifするよりは速いのではないかと想像してるのですが、実測はしてませんw
メソッドコールが入るので、現状より遅くなるとは思うのですが、許容範囲にならないですかねぇ・・・。
とりあえず、これでメソッドが一本化でき、コードが短くならないでしょうか。

あと、ご存知かもしれませんが、同じO(ND)の実装でgoogleがdiffを公開してました。C#のコードもあるので、ご興味があれば是非比較記事を(笑)
http://code.google.com/p/google-diff-match-patch/

JakenJaken 2010/11/21 13:23 あ。見間違えてました。このロジックはO(NP)だった・・・
googleとは違いましたね;
忘れてくださいorz

KSKKSK 2011/05/12 09:46 はじめまして。
C#のDiffについて参考にさせていただいています。

1点質問なのですが、
コード中にDebug.Assertとありますが、ここでAssertとなった場合(行数は少ないが、文字数が多い文字列と比較した場合?)、その後の処理でどのようなことが起こるのでしょうか?
(処理速度が遅くなる?正常に比較できない?)

古い記事へのコメントですが、宜しければ教えてください。

siokoshousiokoshou 2011/05/16 15:21 KSKさん、こんにちは。
Assertにはなりません。あくまでもデバッグ用です。
AとBの長さには制約があり、逆にすると正常に比較できません。
詳しくは論文を参照願います。

kasuyakasuya 2016/05/18 14:36 いつもお世話になります。
使用してみまして、

string original = "静岡大学大学院";
string dest = "大学院理工学研究科情報専攻";
var DiffResult = FastDiff.DiffChar(original, dest);
を計算すると、
下記のような出力になりますが、
[0] = {Modified, OrgStart:0, OrgLen:2, ModStart:0, ModLen:0}
[1] = {Common, OrgStart:2, OrgLen:2, ModStart:0, ModLen:2}
[2] = {Modified, OrgStart:4, OrgLen:1, ModStart:2, ModLen:3}
[3] = {Common, OrgStart:5, OrgLen:1, ModStart:5, ModLen:1}
[4] = {Modified, OrgStart:6, OrgLen:1, ModStart:6, ModLen:7}

できれば下記のように出たらいいのにと思います。
[0] = {Modified, OrgStart:0, OrgLen:4, ModStart:0, ModLen:0}
[1] = {Common, OrgStart:4, OrgLen:3, ModStart:0, ModLen:3}
[2] = {Modified, OrgStart:7, OrgLen:0, ModStart:3, ModLen:10}

とはいえ、

静岡大学 大学院
大学院理工 学 研究科情報専攻

という対応付けでも

静岡大学大学院
大学院理工学研究科情報専攻

という対応付けでも同じ3文字対応付けられてるし仕方ないなと思ってもやもやしています。

siokoshousiokoshou 2016/05/20 23:13 kasuyaさん、こんにちは。
それがいいですね。最長一致とか呼ぶのでしょうか?
ぜひそのようなアルゴリズムを探すか作るかしてみてください。

2007/3/12 (月)

[][][] diff その3  diff その3 - 当面C#と.NETな記録 を含むブックマーク  diff その3 - 当面C#と.NETな記録 のブックマークコメント

前回は http://www.mathertel.de/Diff/ のコードの Hashtable を削除したら2倍速くなったところまで。今日はその続き。

このコードでは文字列を行ごとにばらしてハッシュ値にする前処理があって、その後にハッシュ値配列のdiffを調べる。この前処理とdiff処理の各時間を計ると、2桁差で圧倒的に前処理に時間が掛かってました。

じゃあってことで、ハッシュ化止めて文字列をそのまま比較してみると、前回のHashtableなし版と同程度の速度でした。これって、オリジナルはハッシュ化で余計遅くなってるってことじゃ…。高速化はまず計測ありきですな。

文字列のインターン化も試してみたけど、Hashtableあり版と同程度の時間でした。内部でHashtable使ってるってリッチャーが書いてるけど、それと一致する速度ですね。

しょうがないんで(なにが?w)、どう見ても手抜きな DiffCodes() を直してみました。Splitしてオプションに従って文字列いじってハッシュ値を求めた後は文字列を捨てるんで、どう見ても無駄です。経験的にSplitは遅い気がするし。LLっぽくてかなり重宝してるけど。

private static int[] DiffCodes( string text, Option option )
{
	if ( option.IgnoreCase )
		text = text.ToUpperInvariant();

	List<int> list = new List<int>();
	const int seed = 5381;
	int h = seed;
	for ( int i = 0; i < text.Length; i++ )
	{
		if ( text[ i ] == '\n' )
		{
			list.Add( h );
			h = seed;
			continue;
		}
		h = ( ( h << 5 ) ^ ( h >> 27 ) ) ^ text[ i ];
	}
	if ( ( h != seed ) || ( text[ text.Length - 1 ] == '\n' ) )
		list.Add( h );

	return list.ToArray();
}

まじめに行末を探しながらハッシュ化してみました。\r削除はいらないような気がしたんで削除。ignoreSpace と trimSpace は面倒なので元のコードを使ってください。ところで ignoreSpace は空白文字の連続を空白1文字にしてるけど、ignoreSpace って響きからすると空白全削除がいいような気がするんだけど、どうなんでしょう。

これで、オリジナルに比べて約6倍も速くなった!シャアより速いw

O(ND)とかO(NP)とか調べて楽しんでるのに、こんなところで高速化してしまうんじゃつまらないw ってわけで、O(NP)にも取り組んで、subversionの移植を捨ててペーパーのコードを持ってきました。subversionの一致部分の保存/読み取りのとこは参考にしつつ。今度こそO(ND)のコードより速くなりました。http://www.mathertel.de/Diff/ のコードと比べると当社比(?)14倍も高速。そのうち公開します。ペーパーではfpが-1ベースなのに対して0ベースに改善した(つもり)。たいていの言語でさらに速くなるハズ。

ところでsubversionのコードでシーケンスをリング状のリンクリストにしてる理由がよくわかんなかった。番兵を追加するときに、巧みに文字列の入れ替えをしてる(O(NP)では文字列長の制約がある。文字列A,BのうちBが長くないといけない)んだけど、そのためだけのような気がした。CとC#の違いも山程あるけど、もしかしたらsubversionも単純なコードにすればもう少し速くなるのかもしれない。あと、Cでは引数の[IN][OUT]くらいはコメントに書けw!

しっかし、アルゴリズムはまだしっかり理解できないな〜。速いアルゴリズムのほうが短くて単純なコードになってるのがおもしろい。以前見たQuickSearchもそうだったけど。比較回数はペーパーでは1/2とあるけど、それどころじゃなく減る場合も普通にあります。なんてかしこいんだろ。

2007/3/9 (金)

[][][] diff その2  diff その2 - 当面C#と.NETな記録 を含むブックマーク  diff その2 - 当面C#と.NETな記録 のブックマークコメント

http://www.mathertel.de/Diff/

ここのO(ND)なコード、「非常に早いコードです。diffのアルゴリズムに詳しくなければこれより早いコードは書けません。」と書いたばかりでなんだけど、ちょっといじったら2倍早くなった。前言撤回(^^;

Hashtableいらなくね?と気づいて、直接stringのGetHashCode()を取るようにしたら、手元のデータでは2倍も早くなってしまった。

ほかのいじったところと一緒に貼っときます。

public struct Option
{
	public bool TrimSpace, IgnoreSpace, IgnoreCase;
}

public static Item[] DiffText( string textA, string textB )
{
	Option option = new Option();
	return DiffText( textA, textB, option );
}

public static Item[] DiffText( string textA, string textB, Option option )
{
	DiffData dataA = new DiffData( DiffCodes( textA, option ) );
	DiffData dataB = new DiffData( DiffCodes( textB, option ) );

	LCS( dataA, 0, dataA.Length, dataB, 0, dataB.Length );
	return CreateDiffs( dataA, dataB );
}

private static int[] DiffCodes( string text, Option option )
{
	// strip off all cr, only use lf as textline separator.
	text = text.Replace( "\r", "" );

	if ( option.IgnoreCase )
		text = text.ToLower();

	string[] lines = text.Split( '\n' );

	if ( option.TrimSpace )
		for ( int i = 0; i < lines.Length; ++i )
			lines[ i ] = lines[ i ].Trim();

	// TODO: optimization: faster blank removal.
	if ( option.IgnoreSpace )
		for ( int i = 0; i < lines.Length; ++i )
			lines[ i ] = Regex.Replace( lines[ i ], "\\s+", " " );

	int[] hashs = new int[ lines.Length ];

	for ( int i = 0; i < lines.Length; ++i )
		hashs[ i ] = lines[ i ].GetHashCode();

	return hashs;
}

ちなみに、この高速化をしたら移植したO(NP)diffより速くなってしまった…。

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 |