5

私はPythonに比較的慣れておらず、接尾辞木を使い始めています。それらを構築することはできますが、文字列が大きくなるとメモリの問題が発生します。サイズが4^10または4^12のDNAストリングを処理するために使用できることは知っていますが、メソッドを実装しようとすると、メモリの問題が発生します。

文字列と接尾辞木を生成するための私のコードは次のとおりです。

import random

def get_string(length):
    string=""
    for i in range(length):
        string += random.choice("ATGC")
    return string

word=get_string(4**4)+"$"

def suffixtree(string):
    for i in xrange(len(string)):
        if tree.has_key(string[i]):
            tree[string[i]].append([string[i+1:]][0])
        else:
            tree[string[i]]=[string[i+1:]]
    return tree

tree={}
suffixtree(word)

4 ** 8前後になると、深刻なメモリの問題が発生します。私はこれにかなり慣れていないので、これらのものを保存することで何かが欠けていると確信しています。アドバイスをいただければ幸いです。

注：非常に大きな文字列で一致する文字列を探すために文字列検索を実行したいと思います。検索文字列の一致サイズは16です。したがって、これは大きな文字列内でサイズ16の文字列を検索し、次の文字列に移動して別の検索を実行します。非常に多くの検索を行うので、接尾辞木が提案されました。

どうもありがとう

4

4 に答える 4

4

これは私には木のようには見えません。可能なすべてのサフィックスを生成し、それらをハッシュテーブルに保存しているようです。

実際のツリーを使用すると、メモリパフォーマンスが大幅に低下する可能性があります。ライブラリの実装を使用することをお勧めします。

于 2012-04-10T11:00:12.917 に答える
3

他の人がすでに言ったように、構築しているデータ構造は接尾辞ツリーではありません。ただし、メモリの問題は主に、データ構造に明示的な文字列のコピーが多数含まれているという事実に起因しています。こんな電話

string[i+1:]

で始まる部分文字列の実際の (深い) コピーを作成しi+1ます。

元のデータ構造を構築することにまだ関心がある場合 (その用途が何であれ)、良い解決策は、文字列のコピーの代わりにバッファーを使用することです。アルゴリズムは次のようになります。

def suffixtree(string):
    N = len(string)
    for i in xrange(N):
        if tree.has_key(string[i]):
            tree[string[i]].append(buffer(string,i+1,N))
        else:
            tree[string[i]]=[buffer(string,i+1,N)]
    return tree

これをコードの残りの部分に埋め込んでみましたが、合計長が 8^11 文字であっても、必要なメイン メモリは 1 GB より大幅に少ないことが確認されました。

実際の接尾辞ツリーに切り替えた場合でも、これはおそらく関連することに注意してください。正しいサフィックス ツリーの実装では、ツリー エッジにコピー (バッファーでさえも) は格納されません。ただし、ツリーの構築中に、文字列の一時的なコピーが多数必要になる場合があります。これらに型を使用するbufferことは、不要な明示的な文字列のすべてのコピーのためにガベージ コレクターに大きな負担をかけないようにするための非常に良い考えです。

于 2012-04-12T02:34:59.147 に答える
2

メモリの問題がサフィックス ツリーの作成にある場合、サフィックス ツリーが必要ですか? 次のように、単一の文字列ですべての一致を見つけることができます。

word=get_string(4**12)+"$"

def matcher(word, match_string):
    positions = [-1]
    while 1:
        positions.append(word.find(match_string, positions[-1] + 1))
        if positions[-1] == -1:
            return positions[1:-1]

print matcher(word,'AAAAAAAAAAAA')
[13331731, 13331732, 13331733]
print matcher('AACTATAAATTTACCA','AT')
[4, 8]

私のマシンはかなり古いもので、4^12 文字列で実行に 30 秒かかりました。12 桁のターゲットを使用したので、一致するものもいくつかあります。また、このソリューションは重複する結果を見つけます-ある場合。

次のようなサフィックス ツリー モジュールを試すことができます。

import suffixtree
stree = suffixtree.SuffixTree(word)
print stree.find_substring("AAAAAAAAAAAA")

残念ながら、私のマシンは遅すぎて、長い文字列でこれを適切にテストできません。しかし、おそらくサフィックスツリーが構築されると、検索は非常に高速になるため、大量の検索の場合は適切な呼び出しになるはずです。さらにfind_substring、最初の一致のみを返します（これが問題かどうかはわかりませんが、簡単に適応できると確信しています）。

更新: 文字列を小さなサフィックス ツリーに分割して、メモリの問題を回避します。

したがって、長さ 4^12 の文字列で 1000 万回の検索を行う必要がある場合、9.5 年も待ちたくないことは明らかです (私の遅いマシンでは、標準的な単純な検索を最初に提案しました...)。ただし、サフィックス ツリーを引き続き使用することができ (したがって、はるかに高速になります)、メモリの問題を回避できます。大きな文字列を扱いやすいチャンクに分割し (マシンのメモリが処理できることがわかっています)、チャンクをサフィックス ツリーに変換し、1000 万回検索してから、そのチャンクを破棄して次のチャンクに移動します。また、各チャンク間のオーバーラップを検索することも忘れないでください。これを行うためのコードをいくつか書きました (検索される大きな文字列wordは、管理可能な最大文字列長の倍数であると想定してmax_lengthいます。場合）：

def split_find(word,search_words,max_length):
    number_sub_trees = len(word)/max_length
    matches = {}
    for i in xrange(0,number_sub_trees):
        stree = suffixtree.SuffixTree(word[max_length*i:max_length*(i+1)])
        for search in search_words:
            if search not in matches:
                match = stree.find_substring(search)
                if match > -1:
                    matches[search] = match + max_length*i,i
            if i < number_sub_trees:
                match = word[max_length*(i+1) - len(search):max_length*(i+1) + len(search)].find(search)
                if match > -1:
                    matches[search] = match + max_length*i,i
    return matches

word=get_string(4**12)
search_words = ['AAAAAAAAAAAAAAAA'] #list of all words to find matches for
max_length = 4**10 #as large as your machine can cope with (multiple of word)
print split_find(word,search_words,max_length)

この例では、サフィックス ツリーの最大長を 4^10 に制限しており、これには約 700MB が必要です。このコードを使用すると、1 つの 4^12 の長さの文字列に対して、1,000 万件の検索に約 13 時間かかります (完全な検索で、一致するものがないため、一致する場合はより速くなります)。ただし、その一環として、100 個のサフィックス ツリーを構築する必要があり、約 100*41 秒 = 1 時間かかります。

したがって、合計実行時間は約 14 時間で、メモリの問題はありません... 9.5 年から大幅に改善されました。私はこれを 1GB の RAM を搭載した 1.6GHz の CPU で実行していることに注意してください。

于 2012-04-10T11:38:54.213 に答える
2

'banana'メモリの問題が発生する理由は、入力に対して{'b': ['anana$'], 'a': ['nana$', 'na$', '$'], 'n': ['ana$', 'a$']}. それはツリー構造ではありません。リストの1つに作成および保存された入力のすべての可能なサフィックスがあります。これには O(n^2) のストレージ スペースが必要です。また、サフィックス ツリーが適切に機能するためには、リーフ ノードがインデックス位置を提供する必要があります。

取得したい結果はです{'banana$': 0, 'a': {'$': 5, 'na': {'$': 3, 'na$': 1}}, 'na': {'$': 4, 'na$': 2}}。(これは最適化された表現です。より単純なアプローチでは、1 文字のラベルに限定されます。)

于 2012-04-10T13:07:56.267 に答える