可能であれば効率的な方法で、複数回出現する文字列の部分文字列を識別し、その部分文字列のすべての出現箇所をトークンに置き換える、ある種の「検索と置換」アルゴリズムを実行したいと思います。
たとえば、文字列「AbcAdAefgAbijkAblmnAbAb」が与えられた場合、「A」が繰り返されることに注意してください。そのため、パス 1 を「#1bc#1d#1efg#1bijk#1blmn#1b#1b」に減らします。ここで、#_ はインデックス付きパターンです (インデックス付きテーブルのパターン)、「#1b」が繰り返されることに注意してください。したがって、「#2c#1d#1efg#2ijk#2lmn#2#2」に縮小されます。文字列にこれ以上パターンが発生しないので、完了です。
「最長の共通サブシーケンス」と圧縮アルゴリズムに関する情報をいくつか見つけましたが、これを行うと思われるものは何もありません。これらは、2 つの文字列を比較するため、または何らかの種類のストレージに最適な結果を取得するためのものです。
一方、私の目的は、ゲノムを「文字」ではなく「言葉」に還元することです。つまり、gatcatcgatc の代わりに 2c1c2c を見たいのです。後で正規表現を実行して、「#42*#42」のようなものを見つけることができます。DNA に括弧が繰り返されるのを見るのはクールだろう。
オンラインでそれを見つけることができれば、自分でそれを行うことをスキップしますが、明らかにすることができたという点で、この質問に対する答えは以前には見られませんでした. 私を正しい方向に向けることができる人に感謝します。