"difflib" --- 差分の計算の補助
******************************

**ソースコード:** Lib/difflib.py

======================================================================

このモジュールはシーケンスを比較するクラスと関数を提供します。 その多
くは、テキスト行のシーケンス (文字列のリストや *ファイルオブジェクト*
など) を比較し、相違点を報告する *差分 (diff)* を生成します。 HTML の
ほか、*diff* や *git diff* などのツールが生成するコンテキスト形式やユ
ニファイド形式など、さまざまな形式の差分を生成できます。

比較には "SequenceMatcher" に実装されたマッチングアルゴリズムを使いま
す。 この柔軟なクラスは、要素が *hashable* であれば、テキストに限らず
任意の型のシーケンスのペアを比較できます。


junk ヒューリスティック
=======================

"difflib" は *junk* ヒューリスティックを使います。 一部の要素を *junk*
とみなし、共通部分を探す際に無視します。 理想的には、空行や空白など、
重要でない要素や頻出する要素がこれに当たります。

このヒューリスティックは、組み合わせの候補を減らすためアルゴリズムを高
速化でき、人間に理解しやすい結果を生成することもあります (通常は空白で
区切ります)。 ただし、次のような不都合が起きる場合もあります:

* junk とする要素を不適切に選ぶと、正しいものの予想外に **大きな** 差
  分になる場合があります。

* デフォルトのヒューリスティックは **非対称** です。 junk とみなす要素
  を決めるときは、2 つ目のシーケンスだけを調べます。 そのため、A を B
  と比較した結果と、B を A と比較した結果を反転したものが異なる場合が
  あります。

By default, if the second input sequence is at least 200 items long,
items that account for more than 1% it are considered *junk*.

データによっては、このヒューリスティックを無効にする
("SequenceMatcher" の *autojunk* 引数を "False" にする) か、*isjunk*
引数で調整することを検討してください。 *isjunk* には 定義済みの関数 の
いずれかを指定することもできます。


"difflib" のアルゴリズム
========================

"SequenceMatcher" のアルゴリズムは、Ratcliff と Obershelp が 1980 年代
後半に「ゲシュタルトパターンマッチング」という大げさな名前で発表したア
ルゴリズムよりも古く、少し高度なものです。 両方の入力に共通する最長の
連続部分シーケンスを見つけ、その左右に残ったシーケンスを再帰的に処理す
るという考え方です。

参考:

  Pattern Matching: The Gestalt Approach
     John W. Ratcliff と D. E. Metzener による、類似のアルゴリズムの解
     説です。 1988 年 7 月の Dr. Dobb's Journal に掲載されました。

Ratcliff と Obershelp のアルゴリズムを拡張し、"difflib" は *junk を含
まない* 最長の連続部分シーケンスを探します。 詳しくは junk ヒューリス
ティック 節を参照してください。

時間計算量

基本的な Ratcliff-Obershelp アルゴリズムの時間計算量は、最悪の場合は 3
次、期待される場合は 2 次です。 "difflib" のアルゴリズムは最悪の場合が
2 次で、期待される場合の振る舞いは、シーケンスの共通要素数に複雑に依存
します。 最良の場合の時間計算量は線形です。


差分の生成
==========

class difflib.Differ

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

   "Differ" クラスによる差分の各行は、2文字のコードで始まります:

   +------------+---------------------------------------------+
   | コード     | 意味                                        |
   |============|=============================================|
   | "'- '"     | 行はシーケンス1にのみ存在する               |
   +------------+---------------------------------------------+
   | "'+ '"     | 行はシーケンス2にのみ存在する               |
   +------------+---------------------------------------------+
   | "'  '"     | 行は両方のシーケンスで同一                  |
   +------------+---------------------------------------------+
   | "'? '"     | 行は入力シーケンスのどちらにも存在しない    |
   +------------+---------------------------------------------+

   '"?"' で始まる行は、行内の相違点を見つけやすくするためのもので、ど
   ちらの入力シーケンスにも存在しません。 シーケンスにスペース、タブ、
   改行などの空白文字が含まれる場合、これらの行は分かりにくくなること
   があります。

   "Differ" が生成する差分は、**最小** の差分であることを保証しません
   。 むしろ最小の差分は、100 ページ離れた偶然の一致など、対応付けられ
   るところをすべて対応付けるため、人間の直感に反することがよくありま
   す。 対応付ける箇所を連続する一致部分に限ると、差分が長くなる場合は
   ありますが、位置的な近さをある程度保てます。

   "Differ" は、以下のようなコンストラクタを持ちます:

   __init__(linejunk=None, charjunk=None)

      オプションのキーワードパラメータ *linejunk* と *charjunk* は、フ
      ィルタ関数を渡します (使わないときは "None"):

      *linejunk*: ひとつの文字列引数を受け取る関数です。文字列が junk
      のときに真を返します。デフォルトでは、"None" であり、どんな行で
      あっても junk とは見なされません。

      *charjunk*: この関数は文字(長さ1の文字列)を引数として受け取り、
      文字が junk であるときに真を返します。デフォルトは "None" であり
      、どんな文字も junk とは見なされません。

      これらの junk フィルター関数は、相違点を探すマッチングを高速化し
      ますが、相違のある行や文字そのものを無視するわけではありません。
      詳しくは "find_longest_match()" メソッドの *isjunk* パラメーター
      の説明を参照してください。

   "Differ" オブジェクトは、以下の1つのメソッドを通して利用されます。
   （差分を生成します）:

   compare(a, b)

      文字列からなる2つのシーケンスを比較し、差分（を表す文字列からな
      るシーケンス）を生成します。

      各シーケンスは、末尾に改行のある 1 行ずつの文字列で構成されてい
      なければなりません。 このようなシーケンスは、ファイル類似オブジ
      ェクトの "readlines()" メソッドで取得できます。 生成される差分も
      末尾に改行のある文字列で構成され、ファイル類似オブジェクトの
      "writelines()" メソッドでそのまま出力できます。

class difflib.HtmlDiff

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

   警告:

     差分の計算前に末尾の改行を取り除くため、結果が不完全になる場合が
     あります。 詳しくは gh-71896 を参照してください。

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

   __init__(tabsize=8, wrapcolumn=None, linejunk=None, charjunk=IS_CHARACTER_JUNK)

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

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

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

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

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

   make_file(fromlines, tolines, fromdesc='', todesc='', context=False, numlines=5, *, charset='utf-8')

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

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

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

      注釈:

        *fromdesc* と *todesc* はエスケープされていないHTMLとして解釈
        されます。信頼できないソースからの入力を受け取る際には適切にエ
        スケープされるべきです。

      バージョン 3.5 で変更: *charset* キーワード専用引数が追加されま
      した。HTML 文書のデフォルトの文字集合が "'ISO-8859-1'" から
      "'utf-8'" に変更されました。

   make_table(fromlines, tolines, fromdesc='', todesc='', context=False, numlines=5)

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

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

difflib.context_diff(a, b, fromfile='', tofile='', fromfiledate='', tofiledate='', n=3, lineterm='\n')

   *a* と *b* (文字列のリスト) を比較し、差分 (差分形式の行を生成する
   *ジェネレータ*) を、 context diff のフォーマット(以下「コンテキスト
   形式」)で返します。

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

   デフォルトで、 diff 制御行 ("***" や "---" を含む行) は改行付きで生
   成されます。 "io.IOBase.readlines()" で作られた入力が
   "io.IOBase.writelines()" で扱うのに適した diff になるので (なぜなら
   入力と出力の両方が改行付きのため) 、これは有用です。

   行末に改行文字を持たない入力に対しては、出力でも改行文字を付加しな
   いように *lineterm* 引数に """" を渡してください。

   コンテキスト形式は、通常、ヘッダにファイル名と変更時刻を持っていま
   す。この情報は、文字列 *fromfile*, *tofile*, *fromfiledate*,
   *tofiledate* で指定できます。変更時刻の書式は、通常、ISO 8601 フォ
   ーマットで表されます。指定しなかった場合のデフォルト値は、空文字列
   です。

   >>> import sys
   >>> from difflib import *
   >>> s1 = ['bacon\n', 'eggs\n', 'ham\n', 'guido\n']
   >>> s2 = ['python\n', 'eggy\n', 'hamster\n', 'guido\n']
   >>> sys.stdout.writelines(context_diff(s1, s2, fromfile='before.py',
   ...                        tofile='after.py'))
   *** before.py
   --- after.py
   ***************
   *** 1,4 ****
   ! bacon
   ! eggs
   ! ham
     guido
   --- 1,4 ----
   ! python
   ! eggy
   ! hamster
     guido

   より詳細な例は、 difflib のコマンドラインインターフェース を参照し
   てください。

difflib.get_close_matches(word, possibilities, n=3, cutoff=0.6)

   「十分」なマッチの上位のリストを返します。*word* はマッチさせたいシ
   ーケンス (大概は文字列) です。*possibilities* は *word* にマッチさ
   せるシーケンスのリスト (大概は文字列のリスト) です。

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

   オプションの引数 *cutoff* (デフォルトでは "0.6")は、区間 [0, 1] に
   入る小数の値です。*word* との一致率がそれ未満の *possibilities* の
   要素は無視されます。

   *possibilities* の要素でマッチした上位(多くても *n* 個)は、類似度の
   スコアに応じて(一番似たものを先頭に)ソートされたリストとして返され
   ます。

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

difflib.ndiff(a, b, linejunk=None, charjunk=IS_CHARACTER_JUNK)

   *a* と *b* (文字列のリスト) を比較し、差分 (差分形式の行を生成する
   *ジェネレータ*) を、 "Differ" のスタイルで返します。

   オプションのキーワード引数 *linejunk* と *charjunk* には、フィルタ
   関数 (または "None") を渡します。

   *linejunk*: 文字列を 1 つ受け取り、その文字列が junk なら真、それ以
   外なら偽を返す関数です。 デフォルトは "None" です。 モジュールレベ
   ルの "IS_LINE_JUNK()" 関数もあり、最大 1 つのハッシュ文字 ("'#'")
   を除いて可視文字のない行を除外します。 ただし、内部で使う
   "SequenceMatcher" クラスは、どの行がノイズとなるほど頻出するかを動
   的に分析するため、通常はこの関数を使うよりよい結果が得られます。

   *charjunk*: 文字 (長さ1の文字列) を受け取る関数です。文字列が junk
   の場合は真を、そうでない場合は偽を返します。デフォルトでは、モジュ
   ールレべルの関数 "IS_CHARACTER_JUNK()" であり、これは空白文字類 (空
   白またはタブ、改行文字をこれに含めてはいけません) をフィルタして排
   除します。

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

difflib.restore(sequence, which)

   差分を生成した元の二つのシーケンスのうち一つを返します。

   "Differ.compare()" または "ndiff()" によって生成された *sequence*
   を与えられると、行頭のプレフィクスを取りのぞいてファイル 1 または 2
   (引数 *which* で指定される) に由来する行を復元します。

   例:

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

difflib.unified_diff(a, b, fromfile='', tofile='', fromfiledate='', tofiledate='', n=3, lineterm='\n', *, color=False)

   *a* と *b* (文字列のリスト) を比較し、差分 (差分形式の行を生成する
   *ジェネレータ*) を、 unified diff フォーマット(以下「ユニファイド形
   式」)で返します。

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

   デフォルトで、 diff 制御行 ("---", "+++", "@@" を含む行) は改行付き
   で生成されます。 "io.IOBase.readlines()" で作られた入力が
   "io.IOBase.writelines()" で扱うのに適した diff になるので (なぜなら
   入力と出力の両方が改行付きのため) 、これは有用です。

   行末に改行文字を持たない入力に対しては、出力でも改行文字を付加しな
   いように *lineterm* 引数に """" を渡してください。

   *color* を "True" にすると、**git diff --color** と同様に色付きで出
   力します。 有効にしても 環境変数で制御できます。

   ユニファイド形式の差分は、通常、ファイル名と更新日時のヘッダーを持
   ちます。 これらは *fromfile*、*tofile*、*fromfiledate*、
   *tofiledate* に文字列を渡して、必要なものだけでもすべてでも指定でき
   ます。 更新日時は通常 ISO 8601 形式で表します。 指定しない場合は空
   文字列になります。

   >>> s1 = ['bacon\n', 'eggs\n', 'ham\n', 'guido\n']
   >>> s2 = ['python\n', 'eggy\n', 'hamster\n', 'guido\n']
   >>> sys.stdout.writelines(unified_diff(s1, s2, fromfile='before.py', tofile='after.py'))
   --- before.py
   +++ after.py
   @@ -1,4 +1,4 @@
   -bacon
   -eggs
   -ham
   +python
   +eggy
   +hamster
    guido

   より詳細な例は、 difflib のコマンドラインインターフェース を参照し
   てください。

   バージョン 3.15 で変更: *color* パラメーターを追加しました。

difflib.diff_bytes(dfunc, a, b, fromfile=b'', tofile=b'', fromfiledate=b'', tofiledate=b'', n=3, lineterm=b'\n')

   *dfunc* を使用して *a* と *b* (bytes オブジェクトのリスト) を比較し
   て、差分形式の行 (これも bytes オブジェクトです) を*dfunc* の戻り値
   の形式で返します。*dfunc* は、呼び出し可能である必要があります。一
   般に、これは "unified_diff()" または "context_diff()" です。

   未知のエンコーディングまたは一貫性のないエンコーディングのデータ同
   士を比較できます。*n* 以外のすべての入力は、bytes オブジェクトであ
   る必要があります。*n* 以外のすべての入力を損失なく str に変換して、
   "dfunc(a, b, fromfile, tofile, fromfiledate, tofiledate, n,
   lineterm)" を呼び出すことにより動作します。*dfunc* の出力は、bytes
   型に変換されます。これにより、受け取る差分形式の行のエンコーディン
   グは、*a* と *b* の未知または一貫性のないエンコーディングと同一にな
   ります。

   Added in version 3.5.


junk を定義する関数
===================

difflib.IS_LINE_JUNK(line)

   無視できる行のとき "True" を返します。行 *line* は空白、または
   "'#'" ひとつのときに無視できます。それ以外のときには無視できません
   。古いバージョンでは "ndiff()" の引数 *linejunk* にデフォルトで使用
   されました。

difflib.IS_CHARACTER_JUNK(ch)

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


SequenceMatcher オブジェクト
============================

class difflib.SequenceMatcher(isjunk=None, a='', b='', autojunk=True)

   オプションの引数 *isjunk* は、"None" (デフォルトの値です) にするか
   、単一の引数をとる関数でなければなりません。後者の場合、関数はシー
   ケンスの要素を受け取り、要素が junk であり、無視すべきである場合に
   限り真を返すようにしなければなりません。*isjunk* に "None" を渡すと
   、"lambda x: False" を渡したのと同じになります; すなわち、いかなる
   要素も無視しなくなります。例えば以下のような引数を渡すと:

      lambda x: x in " \t"

   これは、行を文字のシーケンスとして比較する際に、空白やタブ文字を対
   応付けの基点にしたくない場合の例です。

   省略可能な引数 *a* と *b* は比較するシーケンスで、どちらもデフォル
   トは空文字列です。 両方のシーケンスの要素は *ハッシュ可能* でなけれ
   ばなりません。

   オプションの引数 *autojunk* は、自動 junk ヒューリスティックを無効
   にするために使えます。

   バージョン 3.2 で変更: *autojunk* パラメーターを追加しました。

   SequenceMatcher オブジェクトは3つのデータ属性を持っています:
   *bjunk* は、 *isjunk* が "True" であるような *b* の要素の集合です;
   *bpopular* は、 (無効でなければ) ヒューリスティックによって popular
   であると考えられる非ジャンク要素の集合です; *b2j* は、 *b* の残りの
   要素をそれらが生じる位置のリストに写像する dict です。この 3 つは
   "set_seqs()" または "set_seq2()" で *b* がリセットされる場合は常に
   リセットされます。

   Added in version 3.2: *bjunk* および *bpopular* 属性。

   "SequenceMatcher" オブジェクトは以下のメソッドを持ちます:

   set_seqs(a, b)

      比較する 2 つのシーケンスを設定します。

   "SequenceMatcher" は 2 つ目のシーケンスの詳細な情報を計算してキャッ
   シュします。 1 つのシーケンスを多数のシーケンスと比較するには、
   "set_seq2()" で共通のシーケンスを一度設定し、比較相手のシーケンスご
   とに "set_seq1()" を呼び出します。

   set_seq1(a)

      比較を行う1つ目のシーケンスを設定します。比較される2つ目のシーケ
      ンスは変更されません。

   set_seq2(b)

      比較を行う2つ目のシーケンスを設定します。比較される1つ目のシーケ
      ンスは変更されません。

   find_longest_match(alo=0, ahi=None, blo=0, bhi=None)

      "a[alo:ahi]" と "b[blo:bhi]" の中から、最長のマッチ列を探します
      。

      *isjunk* が省略されたか "None" の場合、"find_longest_match()" は
      "a[i:i+k]" が "b[j:j+k]" に等しくなる "(i, j, k)" を返します。
      ここで "alo <= i <= i+k <= ahi" かつ "blo <= j <= j+k <= bhi" で
      す。 これらの条件を満たす任意の "(i', j', k')" に対して、さらに
      "k >= k'"、"i <= i'"、および "i == i'" ならば "j <= j'" という条
      件も満たします。 つまり、最長の一致ブロックのうち *a* 内で最も早
      く始まるものを返します。 そのようなブロックが複数あれば、*b* 内
      で最も早く始まるものを返します。

      >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
      >>> s.find_longest_match(0, 5, 0, 9)
      Match(a=0, b=4, size=5)

      引数 *isjunk* が与えられている場合、まず上記のように最長のマッチ
      列を判定しますが、列に junk 要素を含めないという制約が加わります
      。 次に、その列の両側にある junk 要素だけをマッチさせて、列をで
      きる限り広げます。 したがって、junk 以外の要素のマッチ列に同一の
      junk 要素が隣接している場合を除き、結果の列で junk 要素がマッチ
      することはありません。

      以下は前と同じサンプルですが、空白を junk とみなしています。これ
      は "' abcd'" が2つ目の列の末尾にある "' abcd'" にマッチしないよ
      うにしています。代わりに "'abcd'" にはマッチします。そして 2つ目
      の文字列中、一番左の "'abcd'" にマッチします:

      >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
      >>> s.find_longest_match(0, 5, 0, 9)
      Match(a=1, b=0, size=4)

      どんな列にもマッチしない時は、"(alo, blo, 0)" を返します。

      このメソッドは *named tuple* "Match(a, b, size)" を返します。

      バージョン 3.9 で変更: デフォルト引数が追加されました。

   get_matching_blocks()

      重複しない一致部分シーケンスを表す 3 要素タプルのリストを返しま
      す。 各タプルは "(i, j, n)" の形式で、"a[i:i+n] == b[j:j+n]" を
      意味します。 タプルの並びでは *i* と *j* がそれぞれ単調に増加し
      ます。

      最後の3つ組はダミーで、"(len(a), len(b), 0)" という値を持ちます
      。これは "n == 0" である唯一のタプルです。もし "(i, j, n)" と
      "(i', j', n')" がリストで並んでいる3つ組で、2つ目が最後の3つ組で
      なければ、"i+n < i'" または "j+n < j'" です。言い換えると並んで
      いる3つ組は常に隣接していない同じブロックを表しています。

         >>> s = SequenceMatcher(None, "abxcd", "abcd")
         >>> s.get_matching_blocks()
         [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]

   get_opcodes()

      *a* を *b* にするための方法を記述する、5 要素のタプルのリストを
      返します。 それぞれのタプルは "(tag, i1, i2, j1, j2)" という形式
      です。 最初のタプルでは "i1 == j1 == 0" であり、残りのタプルでは
      *i1* が直前のタプルの *i2* と同じ値になります。 同様に、*j1* は
      直前のタプルの *j2* と同じ値になります。

      *tag* の値は文字列であり、次のような意味です:

      +-----------------+-----------------------------------------------+
      | 値              | 意味                                          |
      |=================|===============================================|
      | "'replace'"     | "a[i1:i2]" は "b[j1:j2]" に置き換えられる。   |
      +-----------------+-----------------------------------------------+
      | "'delete'"      | "a[i1:i2]" は削除される。この時、"j1 == j2"   |
      |                 | である。                                      |
      +-----------------+-----------------------------------------------+
      | "'insert'"      | "b[j1:j2]" が "a[i1:i1]" に挿入される。この時 |
      |                 | "i1 == i2" である 。                          |
      +-----------------+-----------------------------------------------+
      | "'equal'"       | "a[i1:i2] == b[j1:j2]" (サブシーケンスは等し  |
      |                 | い).                                          |
      +-----------------+-----------------------------------------------+

      例えば:

         >>> a = "qabxcd"
         >>> b = "abycdf"
         >>> s = SequenceMatcher(None, a, b)
         >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
         ...     print('{:7}   a[{}:{}] --> b[{}:{}] {!r:>8} --> {!r}'.format(
         ...         tag, i1, i2, j1, j2, a[i1:i2], b[j1:j2]))
         delete    a[0:1] --> b[0:0]      'q' --> ''
         equal     a[1:3] --> b[0:2]     'ab' --> 'ab'
         replace   a[3:4] --> b[2:3]      'x' --> 'y'
         equal     a[4:6] --> b[3:5]     'cd' --> 'cd'
         insert    a[6:6] --> b[5:6]       '' --> 'f'

   get_grouped_opcodes(n=3)

      最大 *n* 行までのコンテキストを含むグループを生成するような、 *
      ジェネレータ* を返します。

      "get_opcodes()" が返すグループをもとに、変更箇所をより小さなまと
      まりに分割し、間に挟まる変更のない範囲を除きます。

      グループは "get_opcodes()" と同じ書式で返されます。

   ratio()

      [0, 1] の範囲の浮動小数点数で、シーケンスの類似度を測る値を返し
      ます。

      T が2つのシーケンスの要素数の総計だと仮定し、M をマッチした数と
      すると、この値は 2.0*M / T であらわされます。もしシーケンスがま
      ったく同じ場合、値は "1.0" となり、まったく異なる場合には "0.0"
      となります。

      このメソッドは "get_matching_blocks()" または "get_opcodes()" が
      まだ呼び出されていない場合には非常にコストが高いです。この場合、
      上限を素早く計算するために、 "quick_ratio()" もしくは
      "real_quick_ratio()" を最初に試してみる方がいいかもしれません。

   quick_ratio()

      "ratio()" の上界を、より高速に計算します。

   real_quick_ratio()

      "ratio()" の上界を、非常に高速に計算します。

一致した文字数の総文字数に対する比率を返す 3 つのメソッドは、近似の程
度が異なるため、結果も異なる場合があります。 ただし "quick_ratio()" と
"real_quick_ratio()" の結果は、常に "ratio()" 以上です:

>>> s = SequenceMatcher(None, "abcd", "bcde")
>>> s.ratio()
0.75
>>> s.quick_ratio()
0.75
>>> s.real_quick_ratio()
1.0


使用例
======


SequenceMatcher の例
--------------------

この例は2つの文字列を比較します。空白を "junk" とします:

>>> s = SequenceMatcher(lambda x: x == " ",
...                     "private Thread currentThread;",
...                     "private volatile Thread currentThread;")

"ratio()" は [0, 1] の範囲の浮動小数点数を返し、シーケンスの類似度を示
します。 目安として、"ratio()" の値が 0.6 を超えていれば、シーケンスは
よく似ています:

>>> print(round(s.ratio(), 3))
0.866

シーケンスのどこが一致するかだけを知りたい場合は、
"get_matching_blocks()" が便利です:

>>> for block in s.get_matching_blocks():
...     print("a[%d] and b[%d] match for %d elements" % block)
a[0] and b[0] match for 8 elements
a[8] and b[17] match for 21 elements
a[29] and b[38] match for 0 elements

"get_matching_blocks()" が返す最後のタプルは、常にダミーの "(len(a),
len(b), 0)" です。 タプルの最後の要素 (一致した要素数) が "0" になるの
は、このタプルだけです。

最初のシーケンスを 2 つ目に変える方法を知るには、"get_opcodes()" を使
います:

>>> for opcode in s.get_opcodes():
...     print("%6s a[%d:%d] b[%d:%d]" % opcode)
 equal a[0:8] b[0:8]
insert a[8:8] b[8:17]
 equal a[8:29] b[17:38]

参考:

  * "SequenceMatcher" を使った、シンプルで使えるコードを知るには、この
    モジュールの関数 "get_close_matches()" を参照してください。

  * "SequenceMatcher" で作った小さなアプリケーションについては、簡単な
    バージョン管理のレシピ を参照してください。


Differ の例
-----------

この例では 2 つのテキストを比較します。 まず、末尾に改行のある 1 行ず
つの文字列のシーケンスとしてテキストを用意します (ファイル類似オブジェ
クトの "readlines()" メソッドでも取得できます):

>>> text1 = '''  1. Beautiful is better than ugly.
...   2. Explicit is better than implicit.
...   3. Simple is better than complex.
...   4. Complex is better than complicated.
... '''.splitlines(keepends=True)
>>> len(text1)
4
>>> text1[0][-1]
'\n'
>>> text2 = '''  1. Beautiful is better than ugly.
...   3.   Simple is better than complex.
...   4. Complicated is better than complex.
...   5. Flat is better than nested.
... '''.splitlines(keepends=True)

次に Differ オブジェクトをインスタンス化します:

>>> d = Differ()

注意:  "Differ" オブジェクトをインスタンス化するとき、行 junk と文字
junk をフィルタリングする関数を渡すことができます。詳細は "Differ()"
コンストラクタを参照してください。

最後に、2つを比較します:

>>> result = list(d.compare(text1, text2))

"result" は文字列のリストなので、pretty-printしてみましょう:

>>> from pprint import pprint
>>> pprint(result)
['    1. Beautiful is better than ugly.\n',
 '-   2. Explicit is better than implicit.\n',
 '-   3. Simple is better than complex.\n',
 '+   3.   Simple is better than complex.\n',
 '?     ++\n',
 '-   4. Complex is better than complicated.\n',
 '?            ^                     ---- ^\n',
 '+   4. Complicated is better than complex.\n',
 '?           ++++ ^                      ^\n',
 '+   5. Flat is better than nested.\n']

これは、複数行の文字列として、次のように出力されます:

>>> import sys
>>> sys.stdout.writelines(result)
    1. Beautiful is better than ugly.
-   2. Explicit is better than implicit.
-   3. Simple is better than complex.
+   3.   Simple is better than complex.
?     ++
-   4. Complex is better than complicated.
?            ^                     ---- ^
+   4. Complicated is better than complex.
?           ++++ ^                      ^
+   5. Flat is better than nested.


difflib のコマンドラインインターフェース
----------------------------------------

この例では、difflib を使って "diff" のようなユーティリティを作る方法を
示します。

   """ 4 つの形式の差分を提供する difflib.py のコマンドラインインターフェース:

   * ndiff:    全行を列挙し、行間の変更を強調表示します。
   * context:  まとまった変更を変更前/変更後の形式で強調表示します。
   * unified:  まとまった変更をインライン形式で強調表示します。
   * html:     左右に並べた比較を生成し、変更点を強調表示します。

   """

   import sys, os, difflib, argparse
   import datetime as dt

   def file_mtime(path):
       t = dt.datetime.fromtimestamp(os.stat(path).st_mtime,
                                     dt.timezone.utc)
       return t.astimezone().isoformat()

   def main():

       parser = argparse.ArgumentParser()
       parser.add_argument('-c', action='store_true', default=False,
                           help='Produce a context format diff (default)')
       parser.add_argument('-u', action='store_true', default=False,
                           help='Produce a unified format diff')
       parser.add_argument('-m', action='store_true', default=False,
                           help='Produce HTML side by side diff '
                                '(can use -c and -l in conjunction)')
       parser.add_argument('-n', action='store_true', default=False,
                           help='Produce a ndiff format diff')
       parser.add_argument('-l', '--lines', type=int, default=3,
                           help='Set number of context lines (default 3)')
       parser.add_argument('fromfile')
       parser.add_argument('tofile')
       options = parser.parse_args()

       n = options.lines
       fromfile = options.fromfile
       tofile = options.tofile

       fromdate = file_mtime(fromfile)
       todate = file_mtime(tofile)
       with open(fromfile) as ff:
           fromlines = ff.readlines()
       with open(tofile) as tf:
           tolines = tf.readlines()

       if options.u:
           diff = difflib.unified_diff(fromlines, tolines, fromfile, tofile, fromdate, todate, n=n)
       elif options.n:
           diff = difflib.ndiff(fromlines, tolines)
       elif options.m:
           diff = difflib.HtmlDiff().make_file(fromlines,tolines,fromfile,tofile,context=options.c,numlines=n)
       else:
           diff = difflib.context_diff(fromlines, tolines, fromfile, tofile, fromdate, todate, n=n)

       sys.stdout.writelines(diff)

   if __name__ == '__main__':
       main()


ndiff の例
----------

この例では "difflib.ndiff()" の使い方を示します。

   """ndiff [-q] file1 file2
       or
   ndiff (-r1 | -r2) < ndiff_output > file1_or_file2

   Print a human-friendly file difference report to stdout.  Both inter-
   and intra-line differences are noted.  In the second form, recreate file1
   (-r1) or file2 (-r2) on stdout, from an ndiff report on stdin.

   In the first form, if -q ("quiet") is not specified, the first two lines
   of output are

   -: file1
   +: file2

   Each remaining line begins with a two-letter code:

       "- "    line unique to file1
       "+ "    line unique to file2
       "  "    line common to both files
       "? "    line not present in either input file

   Lines beginning with "? " attempt to guide the eye to intraline
   differences, and were not present in either input file.  These lines can be
   confusing if the source files contain tab characters.

   The first file can be recovered by retaining only lines that begin with
   "  " or "- ", and deleting those 2-character prefixes; use ndiff with -r1.

   The second file can be recovered similarly, but by retaining only "  " and
   "+ " lines; use ndiff with -r2; or, on Unix, the second file can be
   recovered by piping the output through

       sed -n '/^[+ ] /s/^..//p'
   """

   __version__ = 1, 7, 0

   import difflib, sys

   def fail(msg):
       out = sys.stderr.write
       out(msg + "\n\n")
       out(__doc__)
       return 0

   # open a file & return the file object; gripe and return 0 if it
   # couldn't be opened
   def fopen(fname):
       try:
           return open(fname)
       except IOError as detail:
           return fail("couldn't open " + fname + ": " + str(detail))

   # open two files & spray the diff to stdout; return false iff a problem
   def fcompare(f1name, f2name):
       f1 = fopen(f1name)
       f2 = fopen(f2name)
       if not f1 or not f2:
           return 0

       a = f1.readlines(); f1.close()
       b = f2.readlines(); f2.close()
       for line in difflib.ndiff(a, b):
           print(line, end=' ')

       return 1

   # crack args (sys.argv[1:] is normal) & compare;
   # return false iff a problem

   def main(args):
       import getopt
       try:
           opts, args = getopt.getopt(args, "qr:")
       except getopt.error as detail:
           return fail(str(detail))
       noisy = 1
       qseen = rseen = 0
       for opt, val in opts:
           if opt == "-q":
               qseen = 1
               noisy = 0
           elif opt == "-r":
               rseen = 1
               whichfile = val
       if qseen and rseen:
           return fail("can't specify both -q and -r")
       if rseen:
           if args:
               return fail("no args allowed with -r option")
           if whichfile in ("1", "2"):
               restore(whichfile)
               return 1
           return fail("-r value must be 1 or 2")
       if len(args) != 2:
           return fail("need 2 filename args")
       f1name, f2name = args
       if noisy:
           print('-:', f1name)
           print('+:', f2name)
       return fcompare(f1name, f2name)

   # read ndiff output from stdin, and print file1 (which=='1') or
   # file2 (which=='2') to stdout

   def restore(which):
       restored = difflib.restore(sys.stdin.readlines(), which)
       sys.stdout.writelines(restored)

   if __name__ == '__main__':
       main(sys.argv[1:])
