「2つのテキストが一致していること」を判定しようとすると結構苦労することがあります。 "わかりやすく", "微妙に"違ってる、くらいだと良いんですが、現実の問題を考えるとそんなわかりやすい状況のほうが珍しいということに気が付きます。
今回はそんな意外と大変なテキスト間の一致度を評価する方法についてあれこれ考えてみたのでそのメモです。
やりたいこと
やりたいことのイメージとしてはこんな感じです。
上記のように分割の単位が異なり、それぞれのテキスト領域が分けられた状況で左右のテキストがどの程度マッチングしているかを判定したいです。
- 2つのテキストがあるとする
- 両方は同じデータを基にしているが、必ずしも同じではないので異なる箇所がある可能性がある
- 両者のテキストの分割単位は必ずしも同じではない
- 片方は行単位、他方は段落単位、のように微妙に粒度が異なる
このように、
- そもそもどのテキストの箱とどのテキストの箱を比較すればよいのかわからない
- どのペアを比較すべきかわかったとして、テキストのどこからどこまで比較すればよいのかわからない
といった状況で、左右のテキストがどの程度異なっているか測定することを考えていきたいと思います。
テキストの一致度
最初に、テキストの一致度合いを比較する際にどんな指標を使うか考えます。 一般論としては、
- ハミング距離
- レーベンシュタイン距離
など、色々あります。
方針
測定するにあたって、方針としては今回こんな感じにしてみようと思います。
- どのブロックとどのブロックを突き合わせるかを特定する
- ブロック内のどこからどこまでを突き合わせるかを特定する
- 距離を測定する
一点注意点があるとすれば、片方に含まれるテキストがもう一方のテキストに含まれない場合、おそらく変なことになるのでその点はご注意ください。 そこも気にする場合、マッチングに使用したペアは両者から他の評価から除外していくなどが必要かもしれませんが、今回は省略しようと思います。
どのブロックとどのブロックを突き合わせるかを特定する
まず初めにどのブロックとどのブロックが比較対象になるかを考えます。
片方のドキュメントに含まれるテキストをクエリとし、もう一方に対して全文検索を行えば良さそうです。 合致・含有しているブロックであればスコアは高くなるはずなので、最もスコアが高いブロックを採用すれば突き合わせるブロックのペアは決めることができそうです。
もっと簡易にやるなら、ブロック内のテキストをすべて走査し、テキストの一致率が最も高い部分テキストを持つブロックを突き合わせをするブロックとしても良いでしょう。
ブロック内のどこからどこまでを突き合わせるかを特定する
ブロック内のテキストについて、どこからどこまで採用して距離を測定するのが良さそうか判断したい。
- クエリ側の先頭から走査して最大ヒット数で最も短い部分テキストを特定する
- 最大ヒット数が多い領域を特定する
- それを検索対象側の該当テキストとする
距離を測定する
ハミング距離だと不必要な文字が入ってしまうと距離が過剰に大きく算出されてしまうので、レーベンシュタイン距離を用いて距離を算出することにします。
やってみる
こんな感じに書いてみました。大方こんな感じで行けるはず…
感想
あんまりこういうテクニックに詳しくないので、もし詳しい方いらっしゃいましたらぜひ正しいやり方教えて下さい…
