1

アルゴリズムを実装しましたが、他の文字列との編集距離が最も短い文字列の編集距離を見つけたいと思います。

アルゴリズムは次のとおりです。

def lev(s1, s2):
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1)
4

2 に答える 2

5

あなたの「実装」にはいくつかの欠陥があります。

def lev(a, b):(1)ではなく、で始まる必要がありdef lev(s1, s2):ます。(a) 質問する前にコードを実行する、(b) 実際に実行したコードを引用する ((エラーが発生しやすい) 再入力するのではなく、コピー/貼り付けする) という良い習慣を身につけてください。

(2) 終了条件がない。任意の引数について、最終的に評価しようとすることになりlev("", "")、Python 実装の制限がなければ永久にループします: RuntimeError: maximum recursion depth exceeded.

次の 2 行を挿入する必要があります。

if not a: return len(b)
if not b: return len(a)

それを機能させるために。

(3) レーベンシュタイン距離は再帰的に定義されます。「唯一無二の」アルゴリズムなどというものはありません。再帰コードは教室の外ではめったに見られず、「ストローマン」の立場でのみ見られます。

(4) 単純な実装は、時間とメモリに比例して時間がかかりlen(a) * len(b)ます ... 通常、これらの文字列は 4 から 8 よりも少し長くありませんか?

（5）入力のスライスをコピーするため、非常に単純な実装はさらに悪いです。

ウェブ上で動作するあまり単純ではない実装を見つけることができます... google("levenshtein python") ...O(max(len(a), len(b)))追加のメモリを使用する実装を探します。

あなたが求めたもの（「他の弦との編集距離が最も短い弦の編集距離」）は意味がありません...「THE弦」??? 「タンゴには2つかかります」:-)

おそらくあなたが望むこと (最小距離を持つコレクション内の文字列のすべてのペアを見つけること)、またはおそらくその最小距離だけを見つけることは、単純なプログラミング演習です。何を試しましたか？

ちなみに、単純なアルゴリズムでこれらのペアを見つけるには、O(N ** 2) の実行が必要ですlev()。ここで、N はコレクション内の文字列の数です ...これが実際のアプリケーションである場合は、証明された自分で書こうとするのではなく、コードを書いてください。これが宿題なら、そう言うべきです。

于 2010-11-13T17:59:53.867 に答える
0

これはあなたが探しているものですか??

import itertools
import collections

# My Simple implementation of Levenshtein distance
def levenshtein_distance(string1, string2):
    """
    >>> levenshtein_distance('AATZ', 'AAAZ')
    1
    >>> levenshtein_distance('AATZZZ', 'AAAZ')
    3
    """

    distance = 0

    if len(string1) < len(string2):
        string1, string2 = string2, string1

    for i, v in itertools.izip_longest(string1, string2, fillvalue='-'):
        if i != v:
            distance += 1
    return distance

# Find the string with the shortest edit distance.
list_of_string = ['AATC', 'TAGCGATC', 'ATCGAT']

strings_distances = collections.defaultdict(int)

for strings in itertools.combinations(list_of_string, 2):
    strings_distances[strings[0]] += levenshtein_distance(*strings)
    strings_distances[strings[1]] += levenshtein_distance(*strings)

shortest = min(strings_distances.iteritems(), key=lambda x: x[1])
于 2010-11-13T17:22:54.867 に答える