3

メイン文字列 (すべての長さ) 内のサブ文字列のすべての出現を見つけようとしています。私の関数は 1 つの文字列を取り、すべての部分文字列 (もちろん複数回発生します) の辞書と、それが何回発生するか (辞書の形式: {substring: # of occurrences, ...}) を返します。私はcollections.Counter(s)それを手伝うために使用しています。

これが私の機能です：

from collections import Counter

def patternFind(s):
    patterns = {}
    for index in range(1, len(s)+1)[::-1]:
        d = nChunks(s, step=index)
        parts = dict(Counter(d))
        patterns.update({elem: parts[elem] for elem in parts.keys() if parts[elem] > 1})
    return patterns

def nChunks(iterable, start=0, step=1):
    return [iterable[i:i+step] for i in range(start, len(iterable), step)]

data約 2500 のランダムな文字 (ランダムな順序)の文字列があります。ただし、2 つの文字列が挿入されています (ランダム ポイント)。この文字列が「TEST」であるとします。data.count('TEST')2 を返しpatternFind(data)['TEST']ますKeyError。したがって、私のプログラムはその中の 2 つの文字列を検出しません。

私は何を間違えましたか？ありがとう！

編集: テストインスタンスを作成する私の方法:

def createNewTest():
    n = randint(500, 2500)
    x, y = randint(500, n), randint(500, n)
    s = ''
    for i in range(n):
        s += choice(uppercase)
        if i == x or i == y: s += "TEST"
    return s
4

4 に答える 4

3

jurgenreza はあなたのプログラムが動かなかった理由を説明しましたが、解決策はまだかなり遅いです。s繰り返されることがわかっている部分文字列のみを調べるs[:-1]と、はるかに高速なソリューションが得られます (通常は 100 倍以上高速です)。

from collections import defaultdict

def pfind(prefix, sequences):
    collector = defaultdict(list)
    for sequence in sequences:
        collector[sequence[0]].append(sequence)
    for item, matching_sequences in collector.items():
        if len(matching_sequences) >= 2:
            new_prefix = prefix + item
            yield (new_prefix, len(matching_sequences))
            for r in pfind(new_prefix, [sequence[1:] for sequence in matching_sequences]):
                yield r

def find_repeated_substrings(s):
    s0 = s + " "
    return pfind("", [s0[i:] for i in range(len(s))])

dict が必要な場合は、次のように呼び出します。

result = dict(find_repeated_substrings(s))

私のマシンでは、2247 要素の実行で 0.02 秒かかりましたが、元の (修正された) ソリューションでは 12.72 秒かかりました。

(これはかなり単純な実装であることに注意してください。部分文字列の代わりにインデックスを使用すると、さらに高速になるはずです。)

編集:次のバリアントは、(文字列だけでなく) 他のシーケンス タイプでも機能します。また、センチネル要素は必要ありません。

from collections import defaultdict

def pfind(s, length, ends):
    collector = defaultdict(list)
    if ends[-1] >= len(s):
        del ends[-1]
    for end in ends:
        if end < len(s):
            collector[s[end]].append(end)
    for key, matching_ends in collector.items():
        if len(matching_ends) >= 2:
            end = matching_ends[0]
            yield (s[end - length: end + 1], len(matching_ends))
            for r in pfind(s, length + 1, [end + 1 for end in matching_ends if end < len(s)]):
                yield r


def find_repeated_substrings(s):
    return pfind(s, 0, list(range(len(s))))

これには、非常に長い部分文字列が再帰の深さを超えるという問題がまだあります。例外をキャッチしたい場合があります。

于 2013-04-11T11:53:01.843 に答える
2

問題はあなたのnChunks機能にあります。必要なすべてのチャンクが得られるわけではありません。

テスト文字列を考えてみましょう:

s='1test2345test'

サイズ 4 のチャンクの場合、nChunks関数は次の出力を返します。

>>>nChunks(s, step=4)
['1tes', 't234', '5tes', 't']

しかし、あなたが本当に欲しいのは：

>>>def nChunks(iterable, start=0, step=1):
    return [iterable[i:i+step] for i in range(len(iterable)-step+1)]
>>>nChunks(s, step=4)
['1tes', 'test', 'est2', 'st23', 't234', '2345', '345t', '45te', '5tes', 'test']

このように 2 つの'test'チャンクがありpatternFind(s)、魅力的に機能することがわかります。

>>> patternFind(s)
{'tes': 2, 'st': 2, 'te': 2, 'e': 2, 't': 4, 'es': 2, 'est': 2, 'test': 2, 's': 2}
于 2013-04-06T03:54:40.443 に答える