##
4.4.1 SequenceMatcherオブジェクト

The `SequenceMatcher` クラスには、以下のようなコンストラクタがあります。:

class `SequenceMatcher`( | [isjunk[, a[, b]]])

  オプションの引数 isjunk は、（デフォルトの） `None` またはsequenceエレメントが与えられた場合にtrueを返し、エレメントが ``junk''の場合に限り無視される、ひとつの引数をもった関数である 必要があります。 b に `None` が渡されるのは、`lambda x: 0`; が渡されるのと同じことです。言い換えると、どんな要素も無視されません。 例えば以下のような引数を渡すことで、空白とタブ文字を無視して キャラクタの列を比較します。

      lambda x: x in " \t"

  オプションの引数 a と b は、比較される文字列です。 デフォルトで、それらは空の文字列で、文字列の要素はハッシュ化できます。

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

`set_seqs`( | a, b)

  比較される2つの文字列を設定します。

`SequenceMatcher` オブジェクトは2つ目の文字列についての詳細な情報を 算定し、保管します。そのため、ひとつの文字列をいくつもの文字列と比較する場合、 まず `set_seq2()` を使って文字列を設定しておき、別の文字列をひとつづつ 比較するために、繰り返し `set_seq()` を呼び出します。

`set_seq1`( | a)

  比較を行うひとつ目の文字列を設定します。比較される2つ目の文字列は 変更されません。

`set_seq2`( | b)

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

`find_longest_match`( | alo, ahi, blo, bhi)

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

  isjunkが省略されたか`None`の時、`get_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内で最初に 始まるものを返します。そしてそのa内で最初のマッチ列すべての うちb内で最初に始まるものを返します。

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

  引数isjunkが与えられている場合、上記の通り、はじめに再長の マッチ列を判定します。ブロック内に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)
      (1, 0, 4)

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

`get_matching_blocks`( | )

  マッチしたシーケンス中で個別にマッチしたシーケンスをあらわす、 3つの値のリストを返します。それぞれの値は`(i, j, n)`という形式であらわされ、`a[i:i+n] == b[j:j+n]`いう関係を意味します。3つの値は iとjの間で単調に増加します。

  最後のタプルはダミーで、`(len(a), len(b), 0)`という 値を持ちます。これは`n==0`である唯一のタプルです。

      >>> s = SequenceMatcher(None, "abxcd", "abcd")
      >>> s.get_matching_blocks()
      [(0, 0, 2), (3, 2, 2), (5, 4, 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 ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
      ...           (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
       delete a[0:1] (q) b[0:0] ()
        equal a[1:3] (ab) b[0:2] (ab)
      replace a[3:4] (x) b[2:3] (y)
        equal a[4:6] (cd) b[3:5] (cd)
       insert a[6:6] () b[5:6] (f)

`get_grouped_opcodes`( | [n])

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

  このメソッドは、`get_opcodes()` で返されるグループの中から、似 たような差異のかたまりに分け、間に挟まっている変更の無い部分を省きます。

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

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

`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()`で測定する同一性をより素早く、限定された形で測ります。

  このメソッドは`ratio()`より限定されており、これを超えるとは 見なされませんが、高速に実行します。

`real_quick_ratio`( | )

  ratio()で測定する同一性を非常に素早く測ります。

  このメソッドは`ratio()`より限定されており、これを 超えるとは見なされませんが、`ratio()`や`quick_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