＜面白い技術＞文章がどれだけ似ているかを確認するための概念｜社員ブログ｜アベールソリューションズ株式会社

ご挨拶

こんにちは、インフラ事業のグループリーダーをしている、伊藤です。
今回のブログでは、よくある文字列の差分チェッカー等にも使われる「レーベンシュタイン距離」というものを題材にしてみようと思います。

「レーベンシュタイン距離」という言葉を聞いたことがありますか？
これを使うと、二つの文字列がどれくらい似ているかを数値で示すことができるというものです。

 

1.レーベンシュタイン距離の概要

レーベンシュタイン距離は、二つの文字列を同じにするための最小の操作回数を表します。
具体的には、文字の挿入（追加）、削除、置換の3つの操作をどれだけ行えば、文字列Aを文字列Bに変えられるか。そのコストを示す数値です。

3つの操作とは

1. 文字の追加

文字列に新しい文字を追加する操作です。
例として、「たき」から「たぬき」を作る場合、「た」と「き」の間に「ぬ」を追加すればいいので、この操作が1回必要です。

2. 文字の削除

文字列から文字を取り除く操作です。
例として、「たいこ」から「たこ」を作る場合、真ん中の「い」を削除すればいいので、この操作も1回必要です。

3. 文字の置換

文字列の中のある文字を別の文字に変える操作です。
例として、「たいこ」と「たらこ」の場合、真ん中の「い」を「ら」に置換すれば二つの文字列が同じになるので、この操作も1回必要です。

これらの操作を組み合わせて使うことで、どんな二つの文字列も同じにすることができます。
そして、それを最小回数で行うことが、レーベンシュタイン距離の目的となります。

例えば、「おとぎばなし（おとぎ話）」を「とぎいし（研ぎ石）」にするためのレーベンシュタイン距離は、削除が2回と置換が1回必要になるため、コストは3となります。

 

これをもとに戻す際にも、挿入が2回と置換が1回必要なので同じくコストは3となります。

 

2.どうやって計算するのか

簡単な例では手計算も可能ですが、長い文章の場合はプログラムを使用すると便利です。
多くのプログラミング言語には、この距離を計算するライブラリが存在しています。

もちろん、お手製でVBAマクロ等に組み込んで自作する事も可能です。
例えばExcelにVBAを使用してレーベンシュタイン距離を計算する関数を追加する場合、コアな処理として簡単なものでは以下コードで実装できます。

◆———–

Function Levenshtein(ByVal str1 As String, ByVal str2 As String) As Integer
Dim strLen1, strLen2, d(), cost As Integer
Dim min1, min2, min3 As Integer

strLen1 = Len(str1)
strLen2 = Len(str2)
ReDim d(strLen1, strLen2)

For i = 0 To strLen1
d(i, 0) = i
Next

For j = 0 To strLen2
d(0, j) = j
Next

For i = 1 To strLen1
For j = 1 To strLen2
If Mid(str1, i, 1) = Mid(str2, j, 1) Then
cost = 0
Else
cost = 1
End If

min1 = d(i – 1, j) + 1
min2 = d(i, j – 1) + 1
min3 = d(i – 1, j – 1) + cost

d(i, j) = Application.WorksheetFunction.Min(min1, min2, min3)
Next
Next

Levenshtein = d(strLen1, strLen2)
End Function

———–◆

※実際に使う際には、文字列の正規化や単語分割などの処理を加えていく事になります。

 

3.レーベンシュタイン距離をExcel関数化してできる事

上のコードでExcelに関数を追加すると、『= Levenshtein(セルA,セルB)』という関数が使えるようになります。
作成した関数で試しに「18才と81才の違い」を比較してみるとこんな感じになります。

 

類似度は、以下のような計算を使って求めます。

レーベンシュタイン距離（コスト）を比較した二つの文字列の長い方の文字数で割って乖離率を求めて、その数字を1から引く事で類似率が求められます。
この計算では、2つの文字列が完全に一致する場合に類似度が1（100%）、完全に異なる場合には類似度が0（0%）となります。

 

4.レーベンシュタイン距離の応用

レーベンシュタイン距離は、基本的に「2つの文字列がどれだけ異なるか」を数字で示す方法です。
この考え方を日常の例に当てはめてみるとこんな事に利用できます。

1. スペルチェック

想像してみてください。
友人にメールを書くとき、誤って「hello」を「helo」と打ってしまったとします。
レーベンシュタイン距離を使えば、この「helo」が「hello」にどれだけ近いかを計算でき、スペルの提案を受け取ることができます。
この応用で住所等の打ち間違いを検知して一番近い住所を推測させるプログラムにする事も可能です。

2. 書類の比較

例えば、2つの文章を比較して、どれくらい内容が異なるかを知りたい場合。
レーベンシュタイン距離を使用することで、文章の類似度を数値化できます。

3.新旧対照表の作成

セル毎に比較した結果から、操作を行った箇所を赤字にしたり下線を付ける処理を加える事で、例えば規程やマニュアル等の改訂で変更された箇所を可視化して新旧対照表を作る事も可能です。

 

4. DNAの比較

私たちの遺伝情報は、文字列のようなものとして保存されています。
科学者は、レーベンシュタイン距離を使って、2つの生物のDNAがどれくらい異なるかを計算しているそうです。

5.学生が提出したレポートの複製をチェック

最近ではレポートの提出等をデジタルで行う高校や大学も増えているとの事ですが、そこで横行しているのが、WEBや学生同士でのレポート複製、そして、”てにおは” だけを変えたレポートだそうです。
この類似度をチェックする事で、複製など不正が行われていないかチェックができます。

6.バイナリ情報の比較

バイナリ情報から文字列データを抽出してテキストファイルを生成すればその比較も可能です。

おわりに

以上。今回は、私が文字列比較ソフト等を自由に導入できない環境に居た時に、文字列の変更箇所を探すための手段として面白い概念を知り、こんなものがあるのかと感心したものを紹介させていただきました。

ここまでお読みいただき、ありがとうございました。
次回のブログでまたお会いしましょう！