5

この問題を解決するための最もメモリ効率の良い方法を探しています。

文の部分的な文字列の一致を表すタプルのリストがあります。

[(0, 2), (1, 2), (0, 4), (2,6), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]

各タプルの最初の値はマッチの開始位置で、2 番目の値は長さです。

アイデアは、リストを折りたたんで、最長の継続文字列の一致のみが報告されるようにすることです。この場合、次のようになります。

[(0,4), (2,6), (22,6)]

最長の重複しないシーケンスを見つけるアルゴリズムのように、最長の範囲だけは必要ありませんが、すべての範囲を最長のもので折りたたむ必要があります。

ご参考までに、私は Aho-Corasick の純粋な Python 実装を使用して、静的辞書内の用語を特定のテキスト スニペットに一致させています。

編集: これらのタプル リストの性質上、重複しているが自己完結型ではない範囲は個別に出力する必要があります。たとえば、betazandという単語zetaが辞書にある場合、 の一致betazetaは[(0,5),(4,8)]です。これらの範囲は重複していますが、他の範囲には何も含まれていないため、答えは になります[(0,5),(4,8)]。このケースがカバーされるように、上記の入力データセットも変更しました。

ありがとう！

4

3 に答える 3

4 
import operator
lst = [(0, 2), (1, 2), (0, 4), (2,6), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]
lst.sort(key=operator.itemgetter(1))
for i in reversed(xrange(len(lst)-1)):
    start, length = lst[i]
    for j in xrange(i+1, len(lst)):
        lstart, llength = lst[j]
        if start >= lstart and start + length <= lstart + llength:
            del lst[i]
            break
print lst
#[(0, 4), (2, 6), (22, 6)]
于 2012-05-29T08:54:56.417 に答える
-1

したがって、あなたの主な関心はスペース効率であるというあなたの言葉に基づいて、あなたが望むことを行う1つの方法を次に示します。

lst = [(0, 2), (1, 2), (0, 4), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]
lst.sort()
start, length = lst.pop(0)
i = 0
while i < len(lst):
    x, l = lst[i]
    if start + length < x:
        lst[i] = (start, length)
        i += 1
        start, length = x, l
    else:
        length = max(length, x + l - start)
        lst.pop(i)
lst.append((start, length))

これにより、リストが所定の位置に変更され、リストが長くなることはなく、少数の変数のみを使用して状態を維持し、リストを 1 回通過するだけで済みます。

リストをその場で変更したくない場合は、はるかに高速なアルゴリズムが可能です。特にリストが長い場合、リストの途中からアイテムをポップすると遅くなる可能性があります。

合理的な最適化の 1 つは、削除するインデックスのリストを保持し、2 回目のパスで戻ってリストを再構築することです。これにより、リスト全体を一度に再構築し、popオーバーヘッドを回避できます。しかし、それはより多くのメモリを使用します!

于 2012-05-28T23:06:01.723 に答える