Pythonのサフィックスツリーでの作業

Question

私は比較的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の文字列が検索され、次の文字列に移動して別の検索を実行します。私は非常に多くの検索をしているので、接尾辞ツリーが提案されました。

多くのありがとう

Answer 1

他の人が既に述べたように、構築しているデータ構造は接尾辞ツリーではありません。しかし、のメモリの問題は、データ構造に明示的な文字列コピーがたくさん含まれていることが主な原因です。この

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型を使用することは、不要な明示的な文字列コピーのすべてに対してガベージコレクタに負担をかけることを避けるための非常に良い考えです。

Answer 2

これは私にとってはツリーのようではありません。可能なすべての接尾辞を生成し、ハッシュテーブルに格納するようです。

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

Answer 3

メモリの問題がサフィックスツリーの作成にある場合は、必要がありますか？

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桁のターゲットを使用したので、いくつかのマッチがあります。また、この解決法は重複した結果を見つけるでしょう。

Hereは、あなたが試みることができる接尾辞木のモジュールで、次のように：Unfortunetly

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

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

更新：あなたは4^12の長さの文字列に千万検索を行う必要がある場合、我々は明らかに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個の接尾辞ツリーを構築する必要があります.1000 * 41秒= 1時間です。

したがって、実行に要する時間は約14時間で、メモリの問題はありません... 9.5年の大きな改善。 私は1.6GHzのCPUと1GBのRAMを搭載しているので、これ以上の性能を発揮できるはずです。

Answer 4

メモリの問題が発生する理由は、入力が'banana'の場合、{'b': ['anana$'], 'a': ['nana$', 'na$', '$'], 'n': ['ana$', 'a$']}を生成しているためです。それは木構造ではありません。入力のすべての可能な接尾辞を作成し、リストの1つに格納します。それはO（n^2）の記憶スペースを必要とする。また、サフィックスツリーが正しく機能するようにするには、リーフノードでインデックスの位置を指定する必要があります。

result you want to getは、{'banana$': 0, 'a': {'$': 5, 'na': {'$': 3, 'na$': 1}}, 'na': {'$': 4, 'na$': 2}}です。 （これは最適化された表現であり、より簡単なアプローチにより、1文字のラベルに制限されます）。