10

Python で文字列からサフィックス配列を作成する非常に簡単な方法を次に示します。

def sort_offsets(a, b):
    return cmp(content[a:], content[b:])

content = "foobar baz foo"
suffix_array.sort(cmp=sort_offsets)
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

ただし、「content[a:]」はコンテンツのコピーを作成するため、コンテンツが大きくなると非常に非効率になります。だから、2つの部分文字列をコピーせずに比較する方法があるのだろうか. buffer-builtin を使用しようとしましたが、うまくいきませんでした。

4

4 に答える 4

5

部分文字列を比較する簡単な方法があるかどうかはわかりませんが、key代わりに を使用すると、コードをはるかに高速 (かつ単純) にすることができcmpます。

suffix_array.sort(key=lambda a: content[a:])

これにより、a の値ごとに 1 回だけ部分文字列が作成されます。

編集: 考えられる欠点は、部分文字列に O(n^2) メモリが必要になることです。

于 2010-02-17T16:52:49.103 に答える
3

非常に興味深い問題で+1！これを直接行う明確な方法はわかりませんが、次の比較関数を代わりに使用することで、大幅な高速化 (100000 文字列の桁数) を得ることができました。

def compare_offsets2(a, b):
    return (cmp(content[a:a+10], content[b:b+10]) or
            cmp(content[a:], content[b:]))

つまり、各サフィックスの最初の 10 文字を比較することから始めます。その比較の結果が 0 で、最初の 10 文字が一致したことを示す場合にのみ、サフィックス全体を比較します。

明らかに、10 は何でもかまいません。実験して最良の値を見つけてください。

この比較関数は、キー関数に簡単に置き換えられないものの良い例でもあります。

于 2010-02-17T18:38:19.397 に答える
0

私が書いたblist 拡張タイプを使用できます。Ablistは組み込みの のように機能しlistますが、(とりわけ) コピー オン ライトを使用するため、スライスを取得するには O(log n) 時間とメモリが必要です。

from blist import blist

content = "foobar baz foo"
content = blist(content)
suffix_array = range(len(content))
suffix_array.sort(key = lambda a: content[a:])
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

ランダムに生成された 100,000 文字の文字列から 5 秒以内に suffix_array を作成できました。これには、文字列の生成も含まれます。

于 2010-03-05T00:04:36.203 に答える