2

リストには 300K の文字列が保存されており、各文字列の長さは 10 ～ 400 です。他の文字列の部分文字列である文字列を削除したい (長さが短い文字列ほど、他の文字列の部分文字列である可能性が高くなります)。

現在、最初にこれらの 300K 文字列を長さに基づいて並べ替えてから、以下の方法を使用します。

sorted_string = sorted(string_list, key=length, reverse=True)
for item in sorted_string
    for next_item in sorted_string[sorted_string.index(item)+1:]
        if next_item in item:
            del sorted_string[sorted_string.index(next_item)]

このメソッドの実行時間は O(n^2) です。私は 300K 文字列を持っているので、この方法では満足できません。

これらのソートされた文字列を異なるチャンクに分割し、マルチプロセッシングを使用して各チャンクを計算しようとしました。私が最初に考えたのは、最初の 10K を最初のチャンクに、次の 10K を 2 番目のチャンクに、というように配置することでした。しかし、この方法では、各チャンクの文字列は同様の長さになり、同じチャンク内の他の文字列の部分文字列にならない場合があります。したがって、これは良い分割戦略ではありません。

良いアイデアはありますか？

編集: これらの文字列は DNA 配列を表し、「g」、「c」、「t」、および「a」のみを含みます

更新：

https://github.com/kvh/Python-Suffix-Treeのコードを使用してサフィックス ツリーを構築しようとしました。このプログラムは、ウッコネンのアルゴリズムに基づいてサフィックス ツリーを構築します。

連結された文字列の合計の長さは約 90,000,000 です。それは大きな数です。プログラムは 30 分間実行されており、処理される文字はわずか 3,000,000 (1/30) です。私はこのプログラムに満足していません。

この大きな文字列を処理できる他のサフィックス ツリー構築アルゴリズムはありますか?

4

2 に答える 2

2

サフィックスツリーを使用できます。O(mn) になります。ここで、m は文字列の長さです。それはまだ二次ですが、あなたの場合は m << n であるため、顕著な改善が得られます。

これらのレクチャー ノートでは、サフィックス ツリーを使用して部分文字列を検索する方法を視覚的にわかりやすく説明しています。

于 2013-08-08T22:32:02.407 に答える
0

これは非常にクールで非常に興味深い問題です。私はサブセット シード アルゴリズムを研究してきましたが、すでにかなりの数のアルゴリズムが公開されています。

BLAST アルゴリズムについて聞いたことがありますか? http://blastalgorithm.com/ GUI: http://blast.ncbi.nlm.nih.gov/

于 2013-08-08T23:55:54.410 に答える