# 4.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にのみ存在する
  `' '` | 列は両方の文字列で同一
  `'? '` | 列は入力文字列のどちらにも存在しない

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

`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月号掲載。