アルゴリズム
編集距離(レーベンシュタイン距離)とは、２つの文字列の類似度を示す距離です。文字に対して３つの操作
- 挿入
- 削除
- 置換
をそれぞれ距離１として、１つの文字列をもう１つの文字列に変えるためには、操作を何ステップ必要とするかを計算します。計算のアルゴリズムの説明は省略しますが、動的計画法を用いて計算します。
実装
class Levenshtein:
def __init__(self, str1, str2):
self.str1 = str1
self.str2 = str2
self.len1 = len(str1) + 1
self.len2 = len(str2) + 1
self.calcurated = False
self.saving_memory = True
# 計算用Arrayの初期化
def init_array(self):
arr = np.zeros((self.len1, self.len2), dtype=int)
for i in range(self.len1):
arr[i, 0] = i
for i in range(self.len2):
arr[0, i] = i
self.array = arr
# 文字列の比較
def is_same(self, i, j):
if self.str1[i - 1] is self.str2[j - 1]:
return True
else:
return False
# フルのArrayで距離計算
def calcurate_full_array(self):
self.init_array() #フルArrayの初期化
arr = self.array
for i in range(1, self.len1):
for j in range(1, self.len2):
naname = arr[i-1, j-1] # 左上の値
if not self.is_same(i, j): # 文字が一致しなければ、+1
naname += 1
# 左、左上、上の3つの中で最も小さいもの
mini = np.min([naname, arr[i-1, j] + 1, arr[i, j-1] + 1])
arr[i, j] = mini
# Arrayの右下が求める距離
self.distance = arr[self.len1 - 1, self.len2 - 1]
# Arrayを節約
def calcurate_saving_memory(self):
# 文字列の長さに応じて、交換
if self.len1 < self.len2:
tmp = self.str1
self.str1 = self.str2
self.str2 = tmp
tmp = self.len1
self.len1 = self.len2
self.len2 = tmp
# Init arrays
arr1 = np.zeros((self.len2), dtype=int)
arr2 = np.zeros((self.len2), dtype=int)
for i in range(self.len2):
arr1[i] = i
for i in range(1, self.len1):
arr2[0] = i
for j in range(1, self.len2):
naname = arr1[j-1]
if not self.is_same(i, j):
naname += 1
mini = np.min([naname, arr1[j] + 1, arr2[j-1] + 1])
arr2[j] = mini
arr1 = arr2.copy()
self.distance = arr2[self.len2 - 1]
def calcurate(self, saving_memory=True):
if saving_memory:
self.calcurate_saving_memory()
else:
self.calcurate_full_array()
self.saving_memory = False
self.calcurated = True
def print_array(self):
if self.calcurated and (not self.saving_memory):
list_print = []
line = [' ', ' ']
line.extend([s for s in self.str2])
list_print.append(line)
tmp = [' ']
tmp.extend(self.str1)
for i, s in enumerate(tmp):
line = [s]
line.extend(self.array[i,:].astype(str).tolist())
list_print.append(line)
for l in list_print:
print(l)
else:
print('Array is NOT exist. Use calcurate(saving_memory=False).')
def main():
str1 = 'cafe'
str2 = 'coffee'
leven = Levenshtein(str1, str2)
leven.calcurate()
print(leven.distance)
if __name__ == '__main__':
計算後にアルゴリズムを可視化する
上記の実装は、アルゴリズムに用いる2次元配列を使ったものと、2次元配列を用いずにメモリを節約したものを使えるようにしています。（上記プログラムを実行すると、メモリを節約して計算します）
2次元配列を使って計算した後に、計算後のアルゴリズムを可視化することもできます。
leven.calcurate(saving_memory=False) # フルのArrayで計算
leven.print_array() #アルゴリズムを可視化
結果
[' ', ' ', 'c', 'o', 'f', 'f', 'e', 'e']
[' ', '0', '1', '2', '3', '4', '5', '6']
['c', '1', '0', '1', '2', '3', '4', '5']
['a', '2', '1', '1', '2', '3', '4', '5']
['f', '3', '2', '2', '1', '2', '3', '4']
['e', '4', '3', '3', '2', '2', '2', '3']
参考サイト
編集距離についての説明及びPythonでの実装