6

私の問題は次のとおりです。大量の数列があります。ある時点の後、それが周期的になることを知っています-つまり、シーケンスの最初に k 個の数字があり、シーケンスの残りの部分で繰り返される m 個の数字があります。これをより明確にする例として、シーケンスは次のようになります: [1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3 、...]、ここで、k は 5、m は 4 で、繰り返しブロックは [2, 1, 1, 3] です。この例から明らかなように、大きなブロック内に繰り返しビットを含めることができるため、繰り返しの最初のインスタンスを探すだけでは役に立ちません。

ただし、kまたはmが何であるかはわかりません-私の目標は、シーケンス[a_1、a_2、...、a_n]を入力として受け取り、シーケンス[a_1、...、a_k、[a_(k +1), ... , a_(k+m)]] - 基本的に、その大部分を繰り返しブロックとしてリストすることにより、長いシーケンスを切り捨てます。

この問題を効率的に行う方法はありますか? また、計算上はおそらくより困難ですが、より理想的です-問題のシーケンスを生成するときにこれを実行して、最小限の量を生成する必要がありますか? このサイトで他の同様の質問を見てきましたが、それらはすべて、最初の非反復ビットなしでシーケンスを処理しているように見え、多くの場合、内部反復を心配する必要がありません.

それが役立つ/役立つ場合は、なぜこれを見ているのか、何に使用するのかについても説明できます。

ありがとう！

EDITS：最初に、入力シーケンスが繰り返されるブロックの最後で正確に終了するかどうかわからないことに言及する必要がありました。

私が取り組もうとしている現実世界の問題は、2 次無理数 (実際には負の CFE) の連分数展開 (CFE) の適切な閉じた形式の式を作成することです。これらの CFE の部分商 * を任意の精度で生成するのは非常に簡単ですが、ある時点で、2 次無理数の CFE の末尾が繰り返しブロックになります。この繰り返しブロックの部分商を処理する必要があります。

私の現在の考えは次のとおりです。おそらく、これらのシーケンスのいずれかで動作するように、右から動作するように提案されたアルゴリズムのいくつかを適応させることができます. あるいは、二次無理数が周期的である理由の証明には、なぜそれらが繰り返され始めるのかを理解するのに役立つ何かがあり、簡単な基​​準を確認するのに役立ちます.

*連分数展開を [a_0, a_1, ...] と書いている場合、a_i を部分商と呼びます。

興味のある方のために、いくつかの背景情報をここで見つけることができます: http://en.wikipedia.org/wiki/Periodic_continued_fraction

4

5 に答える 5

7

ローリング ハッシュを使用して、線形時間の複雑さと O(1) 空間の複雑さを実現できます (相互の倍数ではない 2 つの周波数を持つ無限の繰り返しシーケンスを持つことができるとは思わないため、これが当てはまると思います)。 .

アルゴリズム: 次のように展開する 2 つのローリング ハッシュを保持するだけです。

                       _______  _______  _______
                      /       \/       \/       \
...2038975623895769874883301010883301010883301010
                      .        .        .      ||
                      .        .        .    [][]
                      .        .        .  [ ][ ]
                      .        .        .[  ][  ]
                      .        .       [.  ][   ]
                      .        .     [  . ][    ]
                      .        .   [    .][     ]
                      .        . [      ][      ]
                      .        [       ][       ]

シーケンス全体でこれを続けます。最初のパスは、n の値に対して 2*n 回繰り返される繰り返しのみを検出します。ただし、それは私たちの目標ではありません。最初のパスでの目標は、考えられるすべての期間を検出することです。このプロセスを実行するシーケンスに沿って進むにつれて、後で確認する必要があるすべての比較的主要な期間も追跡します。

periods = Set(int)
periodsToFurthestReach = Map(int -> int)

for hash1,hash2 in expandedPairOfRollingHashes(sequence):
    L = hash.length
    if hash1==hash2:
        if L is not a multiple of any period:
            periods.add(L)
            periodsToFurthestReach[L] = 2*L
        else L is a multiple of some periods:
            for all periods P for which L is a multiple:
                periodsToFurthestReach[P] = 2*L

このプロセスの後、すべての期間とそれらが到達した距離のリストが得られます。私たちの答えはおそらく最も到達範囲が広いものですが、他のすべての期間を繰り返しチェックします（チェックしている期間がわかっているため、高速です）。これが計算上難しい場合は、次の周期の繰り返しを予測する優先キューを保持することで、エラトステネスのふるいのように、リストを通過するときに周期 (繰り返しが停止する) を取り除くことで最適化できます。

最後に、結果を再確認して、ハッシュの衝突がなかったことを確認します (ありそうもないことですが、ブラックリストに載せて繰り返します)。

ここで、あなたの目標は非繰り返しの長さを最小限に抑え、さらに因数分解できる繰り返し要素を与えないことだと仮定しました。このアルゴリズムを変更して、存在する場合は他のすべての圧縮を見つけることができます。

于 2012-05-04T04:11:02.293 に答える
2

したがって、ninjagecko は、私が提起した質問に対して有効な回答を提供してくれました。どうもありがとう！しかし、私が見ている特定のケースを行うためのより効率的で数学に基づく方法、つまり、二次無理数の連続分数展開の閉じた形式の式を書き出すことになりました。明らかに、この解決策は、私が尋ねた一般的なケースではなく、この特定のケースでのみ機能しますが、他の人が同様の質問をした場合に備えて、ここに置くと役立つと思いました.

基本的に、二次無理数は、その継続的な分数展開が純粋に周期的である場合にのみ減約されることを思い出しました。つまり、最初から繰り返され、先頭の項はありません。

数値 x の連分数展開を計算するときは、基本的に x_0 を x に設定してから、数列 [a_0; a_1、a_2、a_3、... ] a_n = floor(x_n) および x_(n+1) = 1/(x_n - a_n) を定義することにより。通常は、目的の精度に達するまでこれを続けます。ただし、目的のために、x_k が減数二次無理数になるまでこのメソッドを実行します (これは、1 より大きく、その共役が -1 と 0 の間にある場合に発生します)。これが発生すると、a_k が繰り返しブロックの最初の項であることがわかります。次に、x_(k+m+1) が x_k と等しいことがわかると、a_(k+m) が繰り返しブロックの最後の項であることがわかります。

于 2012-05-04T22:39:11.340 に答える
1

何度も繰り返されたシーケンスを考えてみましょう。たとえば...12341234123412341234で終了します。文字列の繰り返し部分を最後の繰り返しサイクルの直前まで取得し、そのサイクルの長さだけスライドさせると、シーケンスの最後の部分文字列と同じ部分文字列が、その長さに比べて小さい距離を左にスライドしました。

逆に、多数のxに対してa [x] = a [x + k]の文字列がある場合は、a [x] = a [x + k] = a [x + 2k]=aもあります。 [x + 3k] ...したがって、その長さに比べて短い距離をスライドしたときにそれ自体と一致する文字列には、繰り返しが含まれている必要があります。

http://en.wikipedia.org/wiki/Suffix_arrayを見ると、文字列のすべてのサフィックスのリストを、並べ替えられた順序で、線形時間で作成できることがわかります。また、その方法を示す配列も作成できます。各接尾辞には、ソートされた順序で前の接尾辞と共通する多くの文字があります。この値が最大のエントリを探す場合、これは..1234123412341234に進む文字列の候補であり、2つのサフィックスの開始点間の距離から、シーケンスが繰り返される長さがわかります。（しかし実際には、 http：//en.wikipedia.org/wiki/Rabin-Karpのようなある種のローリングハッシュ検索KarkkainenとSandersによる「SimpleLinearWorkSuffix Array Construction」のように、非常にコード化可能な線形時間接尾辞配列アルゴリズムがありますが、より速くて簡単かもしれません。

使用可能な文字数が8、16、32、64、.... 2 ^ nのときにこのアルゴリズムを適用し、最終的に2^pで繰り返しが見つかったとします。初期の段階でどれくらいの時間を無駄にしましたか？2 ^（p-1）+ 2 ^（p-2）+ ...、合計すると約2 ^ pになるため、検索の繰り返しは一定のオーバーヘッドにすぎません。

于 2012-05-04T05:09:25.887 に答える
1

右から検索:

  • a_n == a_n-1
  • (a_n,a_n-1) == (a_n-2,a_n-3) を行います
  • ...

これは明らかに O(m^2) です。利用可能な唯一の境界は m<n/2 のように見えるため、O(n^2) です。

これはあなたのアプリケーションに受け入れられますか? （私たちはあなたのために宿題をしていますか、それとも実際に現実世界の問題がありますか？）

于 2012-05-04T02:06:22.830 に答える
1

このページでは、いくつかの優れたサイクル検出アルゴリズムをリストし、C でのアルゴリズムの実装を示します。

于 2012-05-04T02:46:50.763 に答える