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__':

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']