Hatena::ブログ(Diary)

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

2007/3/15 (木)

siokoshou2007-03-15

[][][] .NET diff class  .NET diff classを含むブックマーク  .NET diff classのブックマークコメント

.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さん、こんにちは。
それがいいですね。最長一致とか呼ぶのでしょうか?
ぜひそのようなアルゴリズムを探すか作るかしてみてください。

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 |