algorithm - 文字列のリストの繰り返しをどのように検出しますか?

Question

ループを検出するために使用したい一連のSQL呼び出しがあります（したがって、不要な重複SQL呼び出し）が、このより一般的な問題について考えさせられました。

リストが与えられた場合、 [a,b,c,b,c,a,b,c,b,c,a,b,b]

私はそれをに変えることができるいくつかの方法はありますか a,[[b,c]*2,a]*2,b*2

また、[a,[b,c]*2]*2,a,b*2

つまり、繰り返し (おそらくネストされたもの) を検出します。

Answer 1

Lempel-Ziv-Welsh 圧縮アルゴリズムを調べてください。これは、文字列の繰り返しを検出し、それらを圧縮に利用することに基づいています。Trieを使用できると思います 。

Answer 2

最初に並べ替えることができれば、もう一度実行して重複した実行を簡単に見つけることができます。もちろん、SQL クエリのように自由形式で並べ替えを行うのは、少し恐ろしく聞こえます。

Answer 3

私はその分野の専門家ではありませんが、いくつかの圧縮アルゴリズムを調べてみてください。

Answer 4

文字列が十分に大きい場合、圧縮ツール (gzip、bzip、7zip など) を実行するのが興味深い方法です。これらのツールは、(さまざまなレベルで) 繰り返しを見つけて、テキスト (または辞書) の最初のインスタンスへのポインターで置き換えることによって機能します。達成する圧縮は、繰り返しの尺度です。ファイルをダンプすると (これを行うにはコードを作成する必要があります)、コンテンツが繰り返されます。