レーベンシュタイン距離とは
レーベンシュタイン距離とは比較的歴史のある、文字列間の類似度を求めるためのアルゴリズムです。
特定の言語に依存しているわけではないため、様々な言語で解く方法が紹介されています。
以下記事などで詳しく紹介されており、アルゴリズムを理解するためには一度目を通した方が良いです。
[PHP][マルチバイト対応]レーベンシュタイン距離を求める(解説つき)
レーベンシュタイン距離の編集操作を統合してグラフ化する
文字列間の距離を測るレーベンシュタイン距離がシンプルで美しかった
『レーベンシュタイン距離』で2つの文字列の類似度を計算してみた
レーベンシュタイン距離の簡単な説明
既に有識者によるレーベンシュタイン距離の説明は出ていますので、詳細は説明は省きますが
以下のような文章があった場合、
-
今日の天気は何ですか？ -
明日の天気は何ですか？
先頭の一文字、で 今 と 明 のような異なる文字を確認して、一致させるためにはどの程度の計算量が必要になるかを数えて、どれぐらいこの数字が少ないかを考える手法です。
※変更・追加・削除
しかし、このレーベンシュタイン距離の算出は正確すぎるがゆえに、剽窃チェックで用いた場合、課題になると思いました。
今回は解く方法ではなく、この課題に関して記したいと思います。
レーベンシュタイン距離をコピペチェックで用いた場合の課題について
今回、コピペチェッカーを開発したのですが、実装した上でレーベンシュタイン距離を求めた場合、何点か課題がありました
高精度・正確すぎる剽窃チェックになってしまう。
一見良い話にしか聞こえませんが、日本語及び、日本語と同じ文字体系の例えば韓国語などでは、これは問題になるのではないかと思います。
英語などであればよいかもしれませんが、正確すぎると時に、困ったことになる場合もあります。
冒頭の以下の例のように１文字違う場合は良いかもしれません。
-
今日の天気は何ですか？ -
明日の天気は何ですか？
しかし、以下のような例だとどうでしょうか
-
今日の天気は何ですか？ -
冬山の寒さで凍えてしまう。
【の】 の、一文字が一致しますね。
なので、二つの文書間でこの一文字のせいで似ていることになります。
人間の目で見れば一目瞭然で、この二つの文章は似ていませんが、プログラムはそのような人間側の事情などお構いなしでうごいてくれますので、これほど全く異なる文章であっても、たったの一文字の為、とっても距離が離れた状態で似ているといった判断1をしてしまいます。
違和感しかないかもしれませんし、レーベンシュタイン距離の問題ではないかもしれませんが、プログラムで見たときはこの一文字は一致している文字扱いになります。
すべて異なる文字であれば、全く似ていないとNG判定を出せますが、n文字（例の場合は1文字）一致して残り▼▼離れていると判断しなければなりません。
遅すぎる
これは、アルゴリズム的に致し方なしという判断をせざるをえない観点ですし、そもそも速さを求めるものではないので、構わない話です。
レーベンシュタイン距離の算出は非常にシンプルなアルゴリズムで、コードは非常に短いです。
上記の参考記事でプログラムを紹介してもらっていますが、ほんの数十行レベルの内容になっています。
しかし、その中で for分の二重ループになっています。
マトリックスで説明できる話は、おおよそ、for分の二重ループが解く方法になる場合がありますが、時間がかかります。
とはいっても、プログラムでやれば一瞬ですので、30文字と30文字の文章間で用いる場合は気にならないでしょう。
しかし、これが剽窃チェックといった1000文字と1000文字といった分量になると話は変わってきます。
さすがに時間がかかりますね。
不得意な場合
- レモン
- 神奈川
この二つは誰がどう見ても似ていないです。
しかし、レーベンシュタイン距離を求めると３文字異なるという点が評価されるので、計算距離が短くなります。
このような短い文字列で剽窃を確認するのはそもそもが不適切ですが、ロジック的には共通にしなければならないため、
例外処理を盛り込む必要が出てきます。
100点を目指さない剽窃を確認するためのコピペチェッカー
開発したコピペチェッカーでは今回レーベンシュタイン距離を求めることはしませんでした。
途中まで実装しているため、コメントアウトして残っているのですが、有効化する事は無いでしょう。
正確すぎる点は、そのあとのロジックで何とでもなる問題ですが、計算量が多すぎて時間がかかる問題は対応が難しいからです。
計算機側のスペックを上げることにより解決はできますが、コストが増大してしまいます。
100点を目指す場合、レーベンシュタイン距離算出は活用すべき機能ですが、バーターで必要となる計算時間の問題は許容できないレベルです。
90点の精度になり、実装したアルゴリズムでは判定が難しい文字列比較のパターンが発生してしまう事にはなるのですが、
今回作成したコピペチェッカーでは、その分、高速での文字列比較を実現しています。
レーベンシュタイン距離の考え方は自然言語処理の分野では非常に有効・重要なテーマにはなるでしょうが、上記の通り取り扱いに注意が必要な場合もあります。※まぁなんでも一緒だと思いますが、使いようってやつですね。
-
実際には距離が5以上は慣れていれば、似ていないといったロジックを組み入れればよいだけですので問題にはなりません。 ↩