【Excel】一致率の可視化(レーベンシュタイン距離)

CATツールで一致率とかマッチ率とか、普段何気なく呼んでいるこの数字。

どうやって計算されているのか、気になりませんか?

弊社の開発しているCATOVISでは「レーベンシュタイン距離」というものを使っています。
(おそらく他のCATツールでも、ほとんど同じではないかと思いますが……)

今回はこのレーベンシュタイン距離の計算方法と、そのプロセスの可視化を目指します。


レーベンシュタイン距離ってなに?

レーベンシュタインさんが考案した、2つの文字列の違いを示す指標のことです。

Wikipedia レーベンシュタイン距離

例えば次の2つの文を見てください。

S1 これが原文1です。

S2 それは訳文ではない

上の文(S1)を下の文(S2)に一致させるには、挿入/削除/置換を何回すればよいでしょうか。

  1. 「こ」を「そ」に置換
  2. 「原」を「訳」に置換
  3. 「が」を「は」に置換
  4. 「1」を削除
  5. 「す」を「は」に置換
  6. 「。」を「な」に置換
  7. 「い」を挿入

の合計7回の操作が必要です。この編集コスト 7 がレーベンシュタイン距離となります。

この計算をプログラムするのですが、Wikipediaのアルゴリズムを見てもチンプンカンプンだったので、Excelで可視化してみました。

Excelにいれてみる

まずはS1を行方向に、S2を列方向に1文字ずつ入れていきます。

次に「文字なし」状態からの編集距離として、行方向・列方向ともに1ずつ増やした数字を記入します。

ここでまずC3から列単位で見てみましょう。
S1の「こ」を「そ」にするには 1回の置換が必要です。
S1の「こ」を「それ」にするには 1回の置換と1回の挿入が必要です。
S1の「こ」を「それは」にするには 1回の置換と2回の挿入が必要です
……

と見ていくと、「こ」をS2に一致させるための操作回数が計算できました。

次に行単位です。といっても、さっきと同じこと。
S2の「そ」を「こ」にするには 1回の置換が必要です。
S2の「そ」を「これ」にするには 1回の置換と1回の挿入が必要です。
S2の「そ」を「これが」にするには 1回の置換と2回の挿入が必要です
……

同様に1行目も埋めることができました。

計算をはじめる

次に2列目・2行目のD4を見てみます。
ここは「これ」を「それ」に変えるための操作回数を表しています。

「これ」と「それ」の2文字目は「れ」で一致しているため、新たな操作は発生しません。
そのため、このセルに入れるべき操作回数は、(C3、D3、C4)のうちの最小の数、つまり「1」となります。

次に見るのはセルD5。
「これ」を「それは」に変えるには、ここまでの最小操作回数+1回の挿入が必要になります。
ですので、D5には(C4、D4、C5)のうちの最小数に1を足した数が入ります。

ここまでをまとめると次のように表すことができます。

S1のn文字目までをS2のm文字目までのテキストに変換するには、

S1のn文字目と、S2のm文字目が一致している場合、
(n-1文字目,m-1文字目)(n-1文字目,m文字目)(n文字目,m-1文字目)までの編集距離のうちの最小値が引き継がれる

S1のn文字目と、S2のm文字目が一致していない場合、
(n-1文字目,m-1文字目)(n-1文字目,m文字目)(n文字目,m-1文字目)までの編集距離のうちの最小値+1が必要になる

これをExcelの関数に落とし込みます。

=IF(D$1=$A4,MIN(C4,D4,C5),MIN(C4,D4,C5)+1)

あとはこれを縦横斜めに繰り返すだけ。上記の関数をK11まで貼り付けてしまいましょう。

これで無事に 「7」 という操作回数にたどり着くことができました。

しかしこのレーベンシュタイン距離(操作回数)は、このままでは使いにくい数字です。

今回のように9文字の文に対して7回操作するのと、100文字の文に7回操作するのは全く意味が異なります。
前者は全く異なる文、後者はかなり似ている文と言えますね。

そのため最後に、S1とS2のうち文字数の多い方から操作回数を引き、文字数で割ることで標準化をします。

Excelでは
=(MAX(COUNTA(B1:K1),COUNTA(A2:A11))-K11)/MAX(COUNTA(B1:K1),COUNTA(A2:A11))
ですね。

これで無事、一致率の計算過程がExcelで見られるようになりました。

……でも何百、何千と原文やメモリがあるときに、一つずつExcelで表をつくるのは非現実的です。

こんな面倒な計算ですが、Pythonには標準ライブラリ(difflib.SequenceMatcher)に組み込まれていますし、
pipにあるeditdistanceを使って求めることもできます。
さすがですね!

2021/1/28 追記

この表と同じ計算をして、ワークシートに表示するためのコードをVBAで実装してみました。

詳しくはこちらの記事で!

CATOVIS LS

MS Office Wordと接続。軽量型でWYSIWYGを実現