asciiでエンコードされたビットの文字列で繰り返される部分文字列を検出するGNU拡張正規表現を考え出そうとしています。私はうまくいく表現を持っています - ある種。問題は、多くの解を持つ可能性のある文字列を指定すると、実行が非常に遅くなることです
表現
([01]+)(\1)+
コンパイルは高速ですが、文字列に対する実行には約 1 分かかります
1010101010101010101010101010101010101010101010101010101010
glibc 2.5-49 の正規表現実装を使用しています (CentOS 5.5 に付属しています)。
FWIW、pcre ライブラリは、gregexp や perl のように、すばやく実行されます。したがって、明らかな、しかし間違った答えは「libpcreを使用する」です。プロジェクトに新しい依存関係を簡単に導入できません。CentOS/RHEL に付属する std C ライブラリ内で作業する必要があります。
If the input string can be of any considerable length, or if performance is at all a concern, then one of the better ways to solve this problem is not with regex, but with a more sophisticated string data structure that facilitates these kinds of queries much more efficiently.
このようなデータ構造が接尾辞ツリーです。string が与えられた場合S、そのサフィックス ツリーは基本的に、すべてのサフィックスのパトリシア トライです。複雑に見えますが、線形時間で構築できます。
接尾辞ツリー
"BANANA"(ウィキペディア提供)
接尾辞ツリーを使用すると、多くの種類のクエリを非常に効率的に実行できます。たとえば、部分文字列のすべての出現、少なくとも 2 回出現する最長の部分文字列などを見つけることができます。求めている文字列の種類は、タンデム リピートと呼ばれます。このクエリを容易にするには、接尾辞ツリーを線形時間で前処理する必要があるため、最小共通祖先クエリを一定時間で実行できます。
この問題は計算生物学では非常に一般的であり、DNAはACGT. したがって、パフォーマンスと効率が最も重要であり、これらの非常に洗練されたアルゴリズムと技術が考案されました。
これらの手法をバイナリ シーケンスに最初から実装するか、バイナリ シーケンスを「偽の」DNA 文字列にマッピングしてから、遺伝子研究に利用できる多くのツールの 1 つを使用する方が簡単な方法を検討する必要があります。