各行に 2 つの類似した単語を含む 30 行の小さなテキスト ファイルがあります。各行の 2 つの単語間のレーベンシュタイン距離を計算する必要があります。また、距離の計算中にmemoize関数を使用する必要があります。私は一般的にPythonとアルゴリズムにかなり慣れていないので、これは私にとって非常に難しいことが証明されています. ファイルを開いて読み取っていますが、2 つの単語のそれぞれを変数 'a' と 'b' に割り当てて距離を計算する方法がわかりません。
現在、ドキュメントのみを印刷する現在のスクリプトは次のとおりです。
txt_file = open('wordfile.txt', 'r')
def memoize(f):
cache = {}
def wrapper(*args, **kwargs):
try:
return cache[args]
except KeyError:
result = f(*args, **kwargs)
cache[args] = result
return result
return wrapper
@memoize
def lev(a,b):
if len(a) > len(b):
a,b = b,a
b,a = a,b
current = range(a+1)
for i in range(1,b+1):
previous, current = current, [i]+[0]*n
for j in range(1,a+1):
add, delete = previous[j]+1, current[j-1]+1
change = previous[j-1]
if a[j-1] != b[i-1]:
change = change + 1
current[j] = min(add, delete, change)
return current[b]
if __name__=="__main__":
with txt_file as f:
for line in f:
print line
以下は、テキスト ファイルからいくつかの単語を抜粋したものです。
アーキタイプ、アーキタイプ
独自の、独自の
認識する、認識する
除外する、除外する
竜巻、竜巻
起こった、起こった
空き地、近辺
これはスクリプトの更新版です。まだ機能していませんが、改善されています。
class memoize:
def __init__(self, function):
self.function = function
self.memoized = {}
def __call__(self, *args):
try:
return self.memoized[args]
except KeyError:
self.memoized[args] = self.function(*args)
return self.memoized[args]
@memoize
def lev(a,b):
n, m = len(a), len(b)
if n > m:
a, b = b, a
n, m = m, n
current = range(n + 1)
for i in range(1, m + 1):
previous, current = current, [i] + [0] * n
for j in range(1, n + 1):
add, delete = previous[j] + 1, current[j - 1] + 1
change = previous[j - 1]
if a[j - 1] != b[i - 1]:
change = change + 1
current[j] = min(add, delete, change)
return current[n]
if __name__=="__main__":
for pair in open("wordfile.txt", "r"):
a,b = pair.split()
lev(a, b)