DiffアルゴリズムをC#でてきとうに実装した

C#

本日のあらすじ

Diff アルゴリズムを C# でてきとうに実装しました（タイトルそのままです）。

ちなみに 2 年半ほど前にも Java で似たようなことをしていましたが、当時はスクリーンショットだけ載せてはいおしまいでした。今回はせっかくなので超カオスなC#のソースも載せておこうと思います。tercel-tech.hatenablog.com

Diffって？

Diffディフとは異なるデータの差分を検出する処理のことで、業界の符丁では「Diffを取る」などと言ったりします。例として、2つのテキストのDiffを取ってみましょう。ちなみに例文はアンサイクロペディアからパクりました。

テキスト1:

個のよ鵜な返還ミスノお御杉る分掌はな２がなん打か輪からないの出、中石て乳緑し魔性。

テキスト2:

このような変換ミスの多すぎる文章はなにがなんだか分からないので、注意して入力しましょう。

テキスト1とテキスト2のDiffを取った結果:

こ╋個━のよう╋鵜━な変╋換╋返━還━ミスの╋多╋す╋ノ━ぎ╋お━御━杉━る文╋章╋分━掌━はなに╋２━がなんだ╋打━か分╋輪━からないので╋出━、 注╋意╋し╋中━石━て入╋力╋乳━緑━しま╋し╋魔━ょ╋性━う╋。

本日の成果物

リハビリも兼ねてDiff情報を求めるための拡張メソッドを作りました。

以下の使用例のように、stringオブジェクトに対して直接Diffメソッドを呼べるようになります。

使用例:

// 「おっぱい」と「いっぱい」のDiffを取る
var result = "おっぱい".Diff("いっぱい");

// 結果を出力する
foreach (var item in result)
{
    Console.WriteLine("{0} {1}", item.Key, item.Value);
}

実行結果:

い +
お -
っ =
ぱ =
い =

これを見た人は、「あぁ、『おっぱい』を『いっぱい』に書き換えるためには、1文字目に『い』を追加して、代わりに『お』を削除すればいいんだね。『っぱい』は共通要素だからそのままでいいんだね」とたちどころに理解できます。よかった。めでたい。

なお、出力の見た目をもう少しマシにする方法をこの記事の最後に載せておきました。

てきとうソース

Diffメソッドと愉快な仲間たちを実装しているクラスです。LINQを悪用してできるだけ可読性の低い仕上がりにしました。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Drawing;
using Path = System.Collections.Generic.IEnumerable<System.Drawing.Point>;

namespace Sample20151024
{
    public static class DiffExtention
    {
        private const char Minus = '-';
        private const char Plus  = '+';
        private const char Equal = '=';
        private static readonly Point ZeroPoint = new Point(x: 0, y: 0);

        public static IList<KeyValuePair<T, char>> Diff<T>(this IEnumerable<T> a, 
                                                           IEnumerable<T> b)
        {
            bool swap        = a.Skip(b.Count()).Any();
            IEnumerable<T> A = !swap ? a : b, B = swap ? a : b;

            int offset = A.Count() + 1;
            int delta  = B.Skip(A.Count()).Count();
            int size   = A.Concat(B).Count() + 3;

            int[] fp   = Enumerable.Repeat<int>(-1, size).ToArray();
            var paths  = Enumerable.Empty<Path>().ToList();

            for (var p = 0; fp[delta + offset] != B.Count(); ++p)
                paths.AddRange(Enumerable.Range(-p, delta + p)
                    .Concat(Enumerable.Range(delta + 1, p).Reverse())
                        .Select(k => Snake(A, B, ref fp, k, offset)).ToList()
                        .Concat(new[] { Snake(A, B, ref fp, delta, offset) }));
    
            return paths.MakeResultData(A, B, swap);
        }

        // ------------------------------------------------------------------------
        // 最小編集距離を求めつつ、ついでに経路情報を記録するよ∩( ・ω・)∩
        // 昔のアルゴリズムって一つの関数に複数の目的を詰め込んだ処理が多い気がする
        private static IEnumerable<Point> Snake<T>(IEnumerable<T> a, 
                                                   IEnumerable<T> b, 
                                                   ref int[] fp, 
                                                   int k, 
                                                   int offset)
        {
            var index = k + offset;
            var snake = Snake(a, b, k, Math.Max(fp[index - 1] + 1, fp[index + 1]));

            fp[index] = snake.Last().Y;
            return snake;
        }

        private static IEnumerable<Point> Snake<T>(IEnumerable<T> a, 
                                                   IEnumerable<T> b, 
                                                   int k, int y)
        {
            int x = y - k;
            return new[] { new Point(x, y) }
                .Concat(PointSequence(x, y)
                .TakeWhile(p => a.Skip(p.X - 1).Any() && b.Skip(p.Y - 1).Any() &&
                    a.ElementAt(p.X - 1).Equals(b.ElementAt(p.Y - 1)))).ToList();
        }

        private static IEnumerable<Point> PointSequence(int x, int y)
        {
            for (int _x = x, _y = y; ;) yield return new Point(++_x, ++_y);
        }
        
        private static Point OffsetX(this Point point, int offset = 1)
        {
            return new Point(x: point.X + offset, y: point.Y);
        }

        private static Point OffsetY(this Point point, int offset = 1)
        {
            return new Point(x: point.X, y: point.Y + offset);
        }
        
        // ---------------------------------
        // 結果データを作ります∩( ・ω・)∩
        private static IList<KeyValuePair<T, char>> MakeResultData<T>(this List<Path> paths, 
                                                                      IEnumerable<T> a, 
                                                                      IEnumerable<T> b,
                                                                      bool swap)
        {
            var prunedPaths = paths.Prune(swap);
            var ret         = Enumerable.Empty<KeyValuePair<T, char>>().ToList();
            for(var path = prunedPaths.FirstOrDefault(); path != null;)
            {
                var tail = path.BuildCommonElementData(a, ref ret).Last();
                path     = prunedPaths.BuildAddedElementData(tail, b, swap, ref ret) ??
                           prunedPaths.BuildDeletedElementData(tail, a, swap, ref ret);
            }
            return ret;
        }

        private static Path BuildAddedElementData<T>(this List<Path> paths, 
                                                     Point tail, 
                                                     IEnumerable<T> sequence, 
                                                     bool swap, 
                                                     ref List<KeyValuePair<T, char>> resultSequence)
        {
            return paths.BuildChangedElementData(tail, sequence, swap, ref resultSequence, 
                                                 isAdded: true);
        }

        private static Path BuildDeletedElementData<T>(this List<Path> paths, 
                                                       Point tail, IEnumerable<T> sequence, 
                                                       bool swap, 
                                                       ref List<KeyValuePair<T, char>> resultSequence)
        {
            return paths.BuildChangedElementData(tail, sequence, swap, ref resultSequence, 
                                                 isAdded: false);
        }

        private static Path BuildChangedElementData<T>(this List<Path> paths, 
                                                       Point tail, 
                                                       IEnumerable<T> sequence, 
                                                       bool swap, 
                                                       ref List<KeyValuePair<T, char>> resultSequence, 
                                                       bool isAdded)
        {
            var nextStartPoint = isAdded ? tail.OffsetY() : tail.OffsetX();
            var query          = paths.Where(x => x.First().Equals(nextStartPoint));
            if (!query.Any()) return null;

            var ret   = query.First();
            var index = (isAdded ? ret.First().Y : ret.First().X) - 1;
            resultSequence.Add(new KeyValuePair<T, char>
                (sequence.ElementAt(index), (isAdded ^ swap) ? Plus : Minus));
            return ret;
        }
        
        private static Path BuildCommonElementData<T>(this Path path, 
                                                      IEnumerable<T> sequence, 
                                                      ref List<KeyValuePair<T, char>> resultSequence)
        {
            int start = path.First().X;
            int count = path.Last().X - start;

            resultSequence.AddRange(Enumerable.Range(start, count)
                .Select(x => new KeyValuePair<T, char>(sequence.ElementAt(x), Equal)));

            return path;
        }

        // -------------------------------------------
        // 経路情報から余分な枝を刈ります∩( ・ω・)∩
        private static List<Path> Prune(this IEnumerable<Path> paths,
                                        bool swap)
        {
            return paths.Prune(paths.Last(), swap).ToList();
        }

        private static IEnumerable<Path> Prune(this IEnumerable<Path> paths,
                                               Path last,
                                               bool swap)
        {
            var startPoint = last.First();
            var sequence   = new[] { last };

            if (startPoint.Equals(ZeroPoint)) return sequence;
            var path = paths
                .Where(p => startPoint.AdjacentPoints(swap).Contains(p.Last()))
                .Select(p => paths.Prune(p, swap))
                .Where(result => result != null)
                .FirstOrDefault();

            return path != null ? path.Concat(sequence) : null;
        }

        private static IEnumerable<Point> AdjacentPoints(this Point point, bool swap)
        {
            var x = new[] { point.OffsetX(-1), point.OffsetY(-1) };
            return !swap ? x : x.Reverse();
        }
    }
}

てきとう仕様

今回のDiffは、IEnumerable<T>の拡張メソッドとして実装されています。

引数には、呼び出し元と同型のオブジェクトを指定します。

戻り値はList<KeyValuePair<TKey, charValue>>です。Listには、以下に示すキーと値のペアが格納されます。

  • Key … 結果要素: 入力a, bの要素。
  • Value… 差分情報: '+', '-', '='いずれか。
    • '+' … 変更（追加）: Keyがbで追加された要素のとき。
    • '-' … 変更（削除）: Keyがaから削除された要素のとき。
    • '=' … 変更なし: Keyがa, bで共通の要素のとき。

Diffを求めるアルゴリズムには、Wuの方法を使用しました。「diffの動作原理を知る～どのようにして差分を導き出すのか｜gihyo.jp … 技術評論社」にくわしい解説があります。

注意点

このプログラムは、結合文字やサロゲートペアに関する考慮は一切行っていません。また、パフォーマンスの最適化（要素のハッシュ化、探索の打ち切りなど）を行っていないため、大規模なデータに対してDiffを取ろうとするとパフォーマンスが低下します。

おまけ

さっきの使用例ではおもしろくない！ もっとこう処理結果をビジュアル的にしたい！ という人向け。

static void Main(string[] args)
{
    string str1 = "いっぱい。";
    string str2 = "おっぱい。";

    for (var diff = str1.Diff(str2); diff.Any();)
    {
        var type      = diff.First().Value;
        var color     = type == '+' ? "red"     : type == '-' ? "blue"    : "black";
        var backColor = type == '+' ? "#FFD5EC" : type == '-' ? "#D9E5FF" : "white";

        Console.Write("<span style='color: {0}; background-color: {1};'>", color, backColor);
        diff.TakeWhile(x => x.Value == type)
            .Select(x => "<ruby>" + x.Key + "<rt>" + x.Value + "</rt></ruby>")
            .ToList().ForEach(Console.Write);
        Console.WriteLine("</span>");

        diff = diff.SkipWhile(x => x.Value == type).ToList();
    }
}

これを実行すると、以下のようなHTMLが出力されます（見やすくするために改行やインデントを勝手に入れました）。
実行結果1:

<span style='color: red; background-color: #FFD5EC;'>
    <ruby>お<rt>+</rt></ruby>
</span>
<span style='color: blue; background-color: #D9E5FF;'>
    <ruby>い<rt>-</rt></ruby>
</span>
<span style='color: black; background-color: white;'>
    <ruby>っ<rt>=</rt></ruby>
    <ruby>ぱ<rt>=</rt></ruby>
    <ruby>い<rt>=</rt></ruby>
    <ruby>。<rt>=</rt></ruby>
</span>

ブラウザで見るとアラ不思議！ なんか無駄にデコレーションが。
実行結果2:

お+い-っ=ぱ=い=。=

いじょ。

Copyright (c) 2012 @tercel_s, @iTercel, @pi_cro_s.