4.4.1 SequenceMatcherオブジェクト

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

クラス SequenceMatcher( [isjunk[, a[, b]]])
オプションの引数 isjunk は、None (デフォルトの値です) にするか、単一の引数をとる関数にせねばなりません。後者の場合、関数は シーケンスの要素を受け取り、要素が ``junk'' であり、無視すべきである場合に 限り真をかえすようにせねばなりません。 isjunkNone を渡すと、lambda x: 0 を渡したのと 同じになります; すなわち、いかなる要素も無視しなくなります。 例えば以下のような引数を渡すと、空白とタブ文字を無視して文字のシーケンスを 比較します。

lambda x: x in " \t"

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

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つの値は ijの間で単調に増加します。

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

もし (i, j, n)(i', j', n') がリストで並んでいる3つ組で、 2つ目が最後の3つ組でなければ、 i+n != i' または j+n != j' です。言い換えると並んでいる3つ組 は常に隣接していない同じブロックを表しています。 バージョン 2.5 で 変更 された仕様: 隣接する3つ組は常に隣接しないブロックを表すと保証するようになりました

>>> 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

ご意見やご指摘をお寄せになりたい方は、 このドキュメントについて... をご覧ください。