文章を書くということは、頭に浮かんだ考えやアイディアに基づく創造的なプロセスである。文章の書き方は、私たちの個性を反映し、その時の気分や思考の整理の仕方、テーマそのもの、そして読者という宛先の人々にも大きく影響されるのです。
かつては、2人以上の著者が同じアイデアを持ち、別々に書き留めて、それぞれの名前で出版し、非常によく似たものを作っていました。電子出版が普及する以前は、彼らのアイデアが流通するのに時間がかかったため、本当の発明者は誰か、誰がその発明を称えるべきかという争いに発展しました。
現在では、すべての記事がデジタル形式ですぐにオンラインで入手できる。オンライン論文は正しくインデックス化され、他の文書とリンクされているので、すぐに見つけることができる。一方では、このような仕事のやり方は、アイデアの交換やトピックに関する研究を簡素化しますが、他方では、アクセスが容易なために、他人の仕事を許可なくコピー＆ペーストするだけで、盗用と呼ばれるドアを開くことになります。
このとき、異なるテキストの類似性に対処する方法が登場します。これは、2つのテキスト（またはデータセット全般）が完全に、あるいは少なくとも部分的に類似しているかどうか、同じトピックについて互いに関連しているかどうか、あるテキストを別のテキストに変換するためにどれだけの編集が必要かという質問に答えられるようにすることが主な目的である。
一例として、情報検索システム、検索エンジン、自動インデックス作成システム、テキスト要約システム、カテゴリ分類システム、剽窃チェックシステム、音声認識、評価システム、DNA解析、プロファイリングアルゴリズム（人と人の行動を自動的にデータとして結びつけるIR/AIプログラム）などで利用されている。
検索・比較方法
私たちは皆、指定された単語や文字列（パターン）に対してテキストを検索することに慣れ親しんでいる。その目的は、正確に発生するもの（マッチ）を見つけるか、正規表現やファジーロジックなどの特別な意味を持つ文字を使って、正確にマッチするものを見つけることである。たいていは、別の文字と類似している文字の並びである。
さらに、言葉の響きによって類似性を測ることもできる–響きは似ているが書き方が違う？あるアルファベットから別のアルファベットへの翻訳では、言語によって複数の結果が得られることが多いため、苗字や名前の綴りの違いから親戚を探すためにSoundexアルゴリズムが作られ、現在でも最も人気があり普及しているものの一つである。
最後になりましたが、ある単語から別の単語への変更（編集）は何回必要でしょうか？編集が少なければ少ないほど、類似度は高くなる。この比較のカテゴリーには、以下で詳しく取り上げるレーベンシュタイン距離も含まれる。
表1は、テキストデータの検索と比較の方法の一部を取り上げたものである。表の右の列は、これらのタスクを達成するために対応するPythonモジュールの選択を含んでいます。
| カテゴリ｜メソッドまたはアルゴリズム｜Pythonパッケージ｜—｜Pythonモジュール
| — | — | — |
| 厳密探索｜Boyer-Moore文字列探索、Rabin-Karp文字列探索、Knuth-Morris-Pratt (KMP)、正規表現｜string、re、Advas |。
| 非正確検索｜ビッグラム検索、トリグラム検索、ファジー論理｜Fuzzy｜。
| 音素解析アルゴリズム｜Soundex, Metaphone, Double Metaphone, Caverphone, NYIIS, Kölner Phonetik, Match Rating codex｜ Advas, Fuzzy, jellyfish, phonetics, kph｜…．
| 変更・編集｜レーベンシュタイン距離、ハミング距離、ジャロ距離、ジャロ・ウィンクラー距離｜editdistance、python-レーベンシュタイン、クラゲ｜。
表1
レーベンシュタイン距離
1965年にロシアの数学者Vladimir Levenshtein（1935-2017）により考案された手法である。距離の値は、ある文字列（ソース）を別の文字列（ターゲット）に変換するために必要な、削除、挿入、置換の最小数を表している。ハミング距離とは異なり、レーベンシュタイン距離は長さが均等でない文字列に対して有効である。
レーベンシュタイン距離が大きいほど、文字列間の差は大きくなります。例えば、”test “から “test “までは、ソースとターゲットの文字列が同じなので、レーベンシュタイン距離は0である。変換の必要はない。一方、”test “から “team “はレーベンシュタイン距離が2であり、“test “から “team “に変換するために2つの置換が必要であることがわかります。
このアルゴリズムがどのように機能するかを説明した素晴らしいビデオがあります。
Python によるレーベンシュタイン距離の実装
Pythonでは、様々なPythonパッケージからだけでなく、オンライン[9,10]でもかなりの数の異なる実装が利用できます（上の表参照）。これには、ベクトル化されたバージョンだけでなく、ダイナミックプログラミングの概念に従ったバージョンも含まれます。ここで紹介するのは、NumPyパッケージと1つの行列を使って計算を行う反復バージョンです。例として、”test “と “text “の編集距離を求めたいと思います。
文字列の長さと同じ大きさの空の行列から始めます。最初の行と列は、0から始まり、どんどんインデックスがつけられていきます。
t e s t
[[ 0. 1. 2. 3. 4.]
t [ 1. 0. 0. 0. 0.]
e [ 2. 0. 0. 0. 0.]
x [ 3. 0. 0. 0. 0.]
t [ 4. 0. 0. 0. 0.]]
次に、2つのループが文字列を1文字ずつ比較するために続きます。2つの文字が等しい場合、位置 [x, y] における新しい値は、位置 [x-1, y] + 1, 位置 [x-1, y-1], および位置 [x, y-1] + 1 の値の間の最小値となる。
[+0.] [+1.]
[+1.] [ ]
それ以外の場合は、位置 [x-1, y] + 1, 位置 [x-1, y-1] + 1, および位置 [x, y-1] + 1 の値の間の最小値である。これも2×2の部分行列として可視化することができ、以下のように右下の位置の欠損値を計算することになります。
[+1.] [+1.]
[+1.] [ ]
2つの文字が異なる場合、挿入、削除、置換の3種類の変更が可能であることに注意してください。最後に、行列は次のようになります。
t e s t
[[ 0. 1. 2. 3. 4.]
t [ 1. 0. 1. 2. 3.]
e [ 2. 1. 0. 1. 2.]
x [ 3. 2. 1. 1. 2.]
t [ 4. 3. 2. 1. 1.]]
編集距離は位置 [4, 4] – 右下隅 – の値であり、実際には1です。この実装は、NとMが2つの文字列の長さである場合、 O(N*M) 時間で実行されることに注意してください。他の実装では、もっと短い時間で実行できるかもしれませんが、理解するにはもっと野心的です。
以下は、先ほど説明したレーベンシュタイン距離アルゴリズムに対応するコードです。
import numpy as np
def levenshtein(seq1, seq2):
size_x = len(seq1) + 1
size_y = len(seq2) + 1
matrix = np.zeros ((size_x, size_y))
for x in xrange(size_x):
matrix [x, 0] = x
for y in xrange(size_y):
matrix [0, y] = y
for x in xrange(1, size_x):
for y in xrange(1, size_y):
if seq1[x-1] == seq2[y-1]:
matrix [x,y] = min(
matrix[x-1, y] + 1,
matrix[x-1, y-1],
matrix[x, y-1] + 1
)
else:
matrix [x,y] = min(
matrix[x-1,y] + 1,
matrix[x-1,y-1] + 1,
matrix[x,y-1] + 1
)
print (matrix)
return (matrix[size_x - 1, size_y - 1])
参考文献
- [1] Python re モジュール
- 2] Python Levenshtein モジュール
- [3] Python editdistance モジュール
- [4] Python advas モジュール
- [5] Python fuzzy モジュール
- [6] Python くらげモジュール
- [7] Python phonetics モジュール
- [8] Python kph モジュール
- [9] https://www.python-course.eu/levenshtein_distance.php
- [10] https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python
謝辞
著者は以下の方々に感謝します。
Axel Beckert, Mandy Neumeyer, Gerold Rupprecht, Zoleka Hatitongweの各氏には、本論文の作成にあたり、ご支援をいただいた。