総当たりレーベンシュタイン距離
複数の文字列データ同士の組み合わせから、総当たりのレーベンシュタイン距離を計算し、
最もレーベンシュタイン距離の小さい組み合わせを探そうとしています。
# levendist.py
import numpy as np
def levenshtein(source, target):
if len(source) < len(target):
return levenshtein(target, source)
# So now we have len(source) >= len(target).
if len(target) == 0:
return len(source)
# We call tuple() to force strings to be used as sequences
# ('c', 'a', 't', 's') - numpy uses them as values by default.
source = np.array(tuple(source))
target = np.array(tuple(target))
# We use a dynamic programming algorithm, but with the
# added optimization that we only need the last two rows
# of the matrix.
previous_row = np.arange(target.size + 1)
for s in source:
# Insertion (target grows longer than source):
current_row = previous_row + 1
# Substitution or matching:
# Target and source items are aligned, and either
# are different (cost of 1), or are the same (cost of 0).
current_row[1:] = np.minimum(
current_row[1:],
np.add(previous_row[:-1], target != s))
# Deletion (target grows shorter than source):
current_row[1:] = np.minimum(
current_row[1:],
current_row[0:-1] + 1)
previous_row = current_row
return previous_row[-1]
上のモジュールでlevenshteinを定義して、
下で2つの文字列配列を総当たりで調べようとしています。
ValueError: could not broadcast input array from shape (2,2) into shape(2)
と出てしまいます。
import numpy as np
import levendist as leven
lst1 = np.array([[1],[2]])
lst2 = np.array([3,4,5,6,7,8,9])
#print(lst1.shape)
#print(lst2.shape)
lst3=leven.levenshtein(lst1,lst2)
print(lst3.shape)
print(lst3)
print(np.max(lst3, axis = 1))
lst4 = np.max(lst3, axis = 1)
print(lst4.shape)
Llevenshteinでsourceとtargetを入れ替えているからかもしれませんが、どのようにかして総当たりのレーベンシュタイン距離を求められないでしょう。