Pythonで編集距離(レーベンシュタイン距離)を実装する

アルゴリズム
--
編集距離(レーベンシュタイン距離)とは、２つの文字列の類似度を示す距離です。文字に対して３つの操作

* 挿入
* 削除
* 置換

をそれぞれ距離１として、１つの文字列をもう１つの文字列に変えるためには、操作を何ステップ必要とするかを計算します。計算のアルゴリズムの説明は省略しますが、動的計画法を用いて計算します。

実装
--


```python
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次元配列を使って計算した後に、計算後のアルゴリズムを可視化することもできます。

```python
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での実装

>https://qiita.com/tenten1010/items/e5fef7bc32605738f126