すべての記事

Text Diff:テキストの差分検出アルゴリズムの仕組み

日本語の文には英語のような単語間のスペースがない。「今日は良い天気です」をどこで単語に区切るかは自明ではなく、形態素解析器(MeCabなど)が文脈から推測するしかない — この曖昧さのせいで、日本語テキストの「単語単位のdiff」は英語のそれほど素直には機能せず、文字単位の比較のほうがかえって扱いやすい場面が多い。

最長共通部分列

古典的なdiffの手法は、テキストの2バージョン間で行の最長共通部分列(LCS)を見つけることに基づいています。この部分列に含まれる行は変更なしとみなされ、残りは旧バージョンから削除された、あるいは新バージョンに追加されたとマークされます。この手法は、あり得る組み合わせの中から任意の1つではなく、最小の変更セットを生成します。

結果の読み方

削除された行は-と赤色、追加された行は+と緑色で示されるのが一般的です。「変更された」行は、実は旧バージョンの削除と新バージョンの追加の組み合わせとして表示されます — diffには1行をその場で編集するという独立した概念はありません。

行単位の比較が常に直感的とは限らない理由

テキストの途中に1行挿入すると、行単位の比較では以降のすべての行が「変更された」と表示されることがあります。アルゴリズムは、それが挿入なのか一括置換なのかを常に見分けられるわけではないからです。日本語のテキストでは、スペースがないぶん行内の単語境界も曖昧なので、単語単位でdiffを取ろうとすると形態素解析の精度に結果が左右されるという別の不確実性も加わります。

この機能が必要な理由

  • 設定ファイルやドキュメントの2つのバージョン間で正確に何が変わったかを確認する。
  • 差分検出アルゴリズムのロジックを理解した上でコードレビューを行う。
  • リファクタリング前後のスクリプト出力を比較し、リグレッションがないことを確認する。

行レベルのdiffと文字レベルのdiff

行ごとの比較はコードや設定ファイルには向いていますが、1つの単語だけが変わった文章では、行全体を削除・再追加として表示してしまいます。日本語では単語境界自体が曖昧なため、文字レベルのdiffのほうが単語分割の誤りに影響されず、変化した箇所を素直に示せることが少なくありません。

ツールを試す