# 4 `difflib` -- 差異の計算を助ける

バージョン 2.1 で 新たに追加 された仕様です。

class `SequenceMatcher`
  柔軟性のあるクラスで、ハッシュ化できる要素の連続であれば、 どんな型のものであっても比較可能です。基礎的なアルゴリズムは 可塑的なものであり、1980年代の後半に発表されたRatcliffとObershelp によるアルゴリズム、大げさに名づけられた``ゲシュタルトパターン マッチング''よりはもう少し良さそうなものです。その考え方は、 ``junk''要素を含まない最も長いマッチ列を探すことです（Ratcliffと Obershelpのアルゴリズムではjunkを示しません）。このアイデアは、 下位のマッチ列から左または右に伸びる列の断片に対して再帰的に あてはまります。これは小さな文字列に対して効率良いものでは ありませんが、人間の目からみて「良く見える」ようにマッチする 傾向があります。

  実行時間: 基本的なRatcliff-Obershelpアルゴリズムは、最 悪の場合3乗、期待値でも2乗となります。`SequenceMatcher` オブジェクトは、最悪のケースで4乗、期待値はシーケンスの 中の要素数に非常にややこしく依存しています。最良の場合 は線形時間になります。

class `Differ`
  テキスト行からなるシーケンスを比較するクラスです。人が読むことの できる差異を作成します。Differクラスは`SequenceMatcher` クラスを利用します。これらは、列からなるシーケンスを比較し、 (ほぼ) 同一の列内の文字を比較します。

  `Differ`クラスによる差異の各行は、2文字のコードではじめられます。

  コード | 意味
  --- | ---
  `'- '` | 列は文字列1にのみ存在する
  `'+ '` | 列は文字列2にのみ存在する
  `' '` | 列は両方の文字列で同一
  `'? '` | 列は入力文字列のどちらにも存在しない

  '? 'で始まる列は線内の差異に注意を向けようとします。その差異は、 入力されたシーケンスのどちらにも存在しません。シーケンスが タブ文字を含むとき、これらのラインは判別しづらいものになる ことがあります。

class `HtmlDiff`

  このクラスは、二つのテキストを左右に並べて比較表示し、行間あるいは行内の 変更点を強調表示するような HTML テーブル (またはテーブルの入った 完全な HTML ファイル) を生成するために使います。テーブルは完全差分モード、 コンテキスト差分モードのいずれでも生成できます。

  このクラスのコンストラクタは以下のようになっています:

  `__init__`( | [tabsize][, wrapcolumn][, linejunk][, charjunk])

    `HtmlDiff` のインスタンスを初期化します。

    tabsize はオプションのキーワード引数で、タブストップ幅を指定 します。デフォルトは `8` です。

    wrapcolumn はオプションのキーワード引数で、テキストを折り返す カラム幅を指定します。デフォルトは `None` で折り返しを行いません。

    linejunk および charjunk はオプションのキーワード引数で、 `ndiff()` (`HtmlDiff` はこの関数を使って左右のテキストの 差分を HTML で生成します) に渡されます。それぞれの引数のデフォルト値 および説明は `ndiff()` のドキュメントを参照してください。

  以下のメソッドが public になっています:

  `make_file`( | fromlines, tolines [, fromdesc][, todesc][, context][, numlines])

    fromlines と tolines (いずれも文字列のリスト) を比較し、 行間または行内の変更点が強調表示された行差分の入った表を持つ完全な HTML ファイルを文字列で返します。

    fromdesc および todesc はオプションのキーワード引数で、 差分表示テーブルにおけるそれぞれ差分元、差分先ファイルのカラムの ヘッダになる文字列を指定します (いずれもデフォルト値は空文字列です)。

    context および numlines はともにオプションのキーワード 引数です。contest を `True` にするとコンテキスト差分を 表示し、デフォルトの `False` にすると完全なファイル差分を 表示します。numlines のデフォルト値は `5` で、 context が `True` の場合、 numlines は強調部分の前後に あるコンテキスト行の数を制御します。context が `False` の場合、numlines は "next" と書かれたハイパーリンクをたどった時に 到達する場所が次の変更部分より何行前にあるかを制御します (値をゼロにした場合、"next" ハイパーリンクを辿ると変更部分の強調表示が ブラウザの最上部に表示されるようになります)。

  `make_table`( | fromlines, tolines [, fromdesc][, todesc][, context][, numlines])

    fromlines と tolines (いずれも文字列のリスト) を比較し、 行間または行内の変更点が強調表示された行差分の入った完全な HTML テーブル を文字列で返します。

    このメソッドの引数は、`make_file()` メソッドの引数と同じです。

  Tools/scripts/diff.py はこのクラスへのコマンドラインフロントエンド で、使い方を学ぶ上で格好の例題が入っています。

  バージョン 2.4 で 新たに追加 された仕様です。

`context_diff`( | a, b[, fromfile][, tofile][, fromfiledate][, tofiledate][, n][, lineterm])

  a と b (文字列のリスト) を比較し、差異 (差異のある行を生成するジェネレータ) を、diff のコンテクスト形式で返します。

  コンテクスト形式は、変更があった行に前後数行を加えてある、コンパクトな表 現方法です。変更箇所は、変更前/変更後に分けて表します。コンテクスト（変 更箇所前後の行）の行数は n で指定し、デフォルト値は 3 です。

  デフォルトでは、diff の制御行 (`***` や `---` を含む行) の最 後には、改行文字が付加されます。この場合、入出力共、行末に改行文字を持つ ので、`file.readlines()` で得た入力から生成した差異を、 `file.writelines()` に渡す場合に便利です。行末に改行文字を持た ない入力に対しては、出力でも改行文字を付加しないように lineterm 引 数に `""` を渡してください。

  diff コンテクスト形式は、通常、ヘッダにファイル名と変更時刻を持ってい ます。この情報は、文字列 fromfile、tofile、fromfiledate、 tofiledate で指定できます。変更時刻の書式は、通常、 `time.ctime()` の戻り値と同じものを使います。指定しなかった場合 のデフォルト値は、空文字列です。

  Tools/scripts/diff.py は、この関数のコマンドラインのフロントエンド（インターフェイス）になっています。

  バージョン 2.3 で 新たに追加 された仕様です。

`get_close_matches`( | word, possibilities[, n][, cutoff])

  最も「十分」なマッチのリストを返します。wordは、なるべく マッチして欲しい（一般的には文字列の）シーケンスです。 possibilitiesはwordにマッチさせる（一般的には文字列） シーケンスのリストです。

  オプションの引数n（デフォルトでは`3`）はメソッドの返す マッチの最大数です。n は `0` より大きくなければなりません。

  オプションの引数 cutoff （デフォルトでは `0.6`）は、 [0, 1]の間となるfloatの値です。可能性として、少なくとも word が無視されたのと同様の数値にはなりません。

  可能性のある、（少なくとも n に比べて）最もよいマッチはリストに よって返され、同一性を表す数値に応じて最も近いものから順に格納されます。

      >>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
      ['apple', 'ape']
      >>> import keyword
      >>> get_close_matches('wheel', keyword.kwlist)
      ['while']
      >>> get_close_matches('apple', keyword.kwlist)
      []
      >>> get_close_matches('accept', keyword.kwlist)
      ['except']

`ndiff`( | a, b[, linejunk[, charjunk]])

  a と b （文字列からなるリスト）を比較し、`Differ` オブジェクト形式の差異（解析器は差異のある列）を返します。

  オプションのパラメータ linejunk と charjunk は、filter 機能のためのキーワードです（使わないときは空にする）。

  linejunk: string型の引数ひとつを受け取る関数で、文字列が junkか否かによってtrueを（違うときにはtrueを）返します。Python 2.3以降、デフォルトでは（`None`）になります。それまでは、 モジュールレべルの関数`IS_LINE_JUNK()`であり、それは 少なくともひとつのシャープ記号（"`#`"）をのぞく、可視の キャラクタを含まない行をフィルタリングします。 Python 2.3では、下位にある`SequenceMatcher`クラスが、 雑音となるくらい頻繁に登場する列であるか否かを、動的に分析します。 これは、バージョン2.3以前でのデフォルト値よりうまく動作します。

  charjunk: 長さ1の文字を受け取る関数です。デフォルトでは、 モジュールレべルの関数 IS_CHARACTER_JUNK()であり、これは空白文字列 （空白またはタブ、注：改行文字をこれに含めるのは悪いアイデア！）を フィルタリングします。

  Tools/scripts/ndiff.py は、この関数のコマンドラインのフロント エンド（インターフェイス）です。

      >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
      ...              'ore\ntree\nemu\n'.splitlines(1))
      >>> print ''.join(diff),
      - one
      ?  ^
      + ore
      ?  ^
      - two
      - three
      ?  -
      + tree
      + emu

`restore`( | sequence, which)

  差異を生成したシーケンスのひとつを返します。

  与えられるsequenceは `Differ.compare()` または `ndiff()`によって生成され、ファイル1または2（引数 whichで指定される）によって元の列に復元され、行頭の プレフィクスが取りのぞかれます。

  例:

      >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
      ...              'ore\ntree\nemu\n'.splitlines(1))
      >>> diff = list(diff) # materialize the generated delta into a list
      >>> print ''.join(restore(diff, 1)),
      one
      two
      three
      >>> print ''.join(restore(diff, 2)),
      ore
      tree
      emu

`unified_diff`( | a, b[, fromfile][, tofile][, fromfiledate][, tofiledate][, n][, lineterm])

  a と b (共に文字列のリスト) を比較し、diff の unified 形式 で、差異 (差分行を生成するジェネレータ) を返します。

  unified 形式は変更があった行に前後数行を加えた、コンパクトな表現方法で す。変更箇所は (変更前/変更後を分離したブロックではなく) インライン・ス タイルで表されます。コンテクスト（変更箇所前後の行）の行数は、n で 指定し、デフォルト値は 3 です。

  デフォルトでは、diff の制御行 (`---`、`+++`、`@@` を含 む行) は行末で改行します。この場合、入出力共、行末に改行文字を持つので、 `file.readlines()` で得た入力を処理して生成した差異を、 `file.writelines()` に渡す場合に便利です。

  行末に改行文字を持たない入力には、出力も同じように改行なしになるように、lineterm 引数を `""` にセットしてください

  diff コンテクスト形式は、通常、ヘッダにファイル名と変更時刻を持ってい ます。 この情報は、文字列 fromfile、tofile、 fromfiledate、tofiledate で指定できます。変更時刻の書式は、 通常、`time.ctime()` の戻り値と同じものを使います。 指定しなかっ た場合のデフォルト値は、空文字列です。

  Tools/scripts/diff.py は、この関数のコマンドラインのフロントエ ンド（インターフェイス）です。

  バージョン 2.3 で 新たに追加 された仕様です。

`IS_LINE_JUNK`( | line)

  無視できる列のときtrueを返します。列 line が空白、または "`#"`" ひとつのときには無視できます。それ以外の時には 無視できません。`ndiff()` の引数linkjunkとして デフォルトで使用されます。 `ndiff()`のlinejunkはPython 2.3以前のものです。

`IS_CHARACTER_JUNK`( | ch)

  無視できる文字のときtrueを返します。文字 ch が空白、または タブ文字のときには無視できます。それ以外の時には無視できません。 `ndiff()` の引数charjunkとしてデフォルトで使用されます。

参考:

Pattern Matching: The Gestalt Approach （パターン マッチング: 全体アプローチ）
  John W. Ratcliff と D. E. Metzener による同一性アルゴリズムに関する議論。 Dr. Dobb's Journal 1988年7月号掲載。