python の RapidFuzz で2つの文字列の差分を検出

やりたいこと

2つの文字列を比較し、各文字列のどこが一致しているか、差分となっているかを取得する。

RapidFuzz

RapidFuzz で2つの文字列の差分を計算することができる。

インストール

pip install python-levenshtein

編集距離

2つの文字列の編集距離を取得するだけなら、Levenshtein.distance() で計算できる。

from rapidfuzz.distance import Levenshtein

text1 = "abc"
text2 = "a b c"

distance = Levenshtein.distance(text1, text2)
print(f"distance: {distance}")

実行結果

distance: 2

文字列のマッチ、差分

2つの文字列のマッチしている部分、差分は opcodes = Levenshtein.opcodes(text1, text2) で取得することができる。

opcodes の各要素には以下の情報が格納されている。

• tag: equal/insert/delete/replace のいずれかの操作
• src_start: tag の操作の引数1の文字列の開始インデックス
• src_end: tag の操作の引数1の文字列の終了インデックス(+1)
• dest_start: tag の操作の引数2の文字列の開始インデックス
• dest_end: tag の操作の引数2の文字列の終了インデックス(+1)

src_start と src_end が異なる場合、引数1に対して tag の操作が実行されている。
同様に dest_start と dest_end が異なる場合、引数2に対して tag の操作が実行されている。

from rapidfuzz.distance import Levenshtein

text1 = "abcde"
text2 = "a b C"

opcodes = Levenshtein.opcodes(text1, text2)

matches1 = []
matches2 = []
diffs1 = []
diffs2 = []

for oc in opcodes:
    print(oc)

    # equal: マッチ
    if oc.tag == 'equal':
        m1 = (oc.src_start, oc.src_end, text1[oc.src_start:oc.src_end])
        matches1.append(m1)
        m2 = (oc.dest_start, oc.dest_end, text2[oc.dest_start:oc.dest_end])
        matches2.append(m2)
        continue

    # equal 以外で start != end の場合は差分
    if oc.src_start != oc.src_end:
        d1 = (oc.src_start, oc.src_end, text1[oc.src_start:oc.src_end])
        diffs1.append(d1)

    if oc.dest_start != oc.dest_end:
        d2 = (oc.dest_start, oc.dest_end, text2[oc.dest_start:oc.dest_end])
        diffs2.append(d2)

print(f"matches1: {matches1}")
print(f"matches2: {matches2}")
print(f"diffs1: {diffs1}")
print(f"diffs2: {diffs2}")

tag が equal の場合には、matches1、matches2 にマッチした部分文字列のインデックスとその部分文字列を抽出する。
それ以外の操作の場合には、start と end が異なる場合に、diffs1、diffs2 に部分文字列を差分として抽出する。

実行結果

Opcode(tag='equal', src_start=0, src_end=1, dest_start=0, dest_end=1)
Opcode(tag='insert', src_start=1, src_end=1, dest_start=1, dest_end=2)
Opcode(tag='equal', src_start=1, src_end=2, dest_start=2, dest_end=3)
Opcode(tag='replace', src_start=2, src_end=4, dest_start=3, dest_end=5)
Opcode(tag='delete', src_start=4, src_end=5, dest_start=5, dest_end=5)
matches1: [(0, 1, 'a'), (1, 2, 'b')]
matches2: [(0, 1, 'a'), (2, 3, 'b')]
diffs1: [(2, 4, 'cd'), (4, 5, 'e')]
diffs2: [(1, 2, ' '), (3, 5, ' C')]

"abcde" と "a b C" とでは "a"、"b" がマッチした文字列として抽出されている。
"abcde" のマッチしなかった差分として、"cd"、"e" が抽出され、"a b C" のマッチしなかった部分として " "、" C" が抽出されている。