3

この問題の名前は本当にわかりませんが、非可逆圧縮のようなもので、英語が下手ですが、できる限り説明しようと思います。

不明なソースからのソートされていない一意の番号のリストがあるとします。長さは通常 255 から 512 で、範囲は 0 から 512
です。データを読み取り、シード番号のようなものを返す何らかのアルゴリズムがあるのではないかと思います。を使用して、元のリストにある程度近いリストを生成できますが、ある程度のエラーがあります。

例えば

  • オリジナルリスト

    {5, 13, 25, 33, 3, 10}

  • 再生成されたリスト

    {4, 10, 30, 30, 5, 5} or {8, 20, 20, 35, 5, 9} //and so on

この問題には名前がありますか? また、今説明したことを実行できるアルゴリズムはありますか? 私の理解ではそうではないので、 モンテカルロ法
と同じですか。

非可逆圧縮で使用されるいくつかの手法を使用して、この種の近似値を取得することは可能ですか?

この問題を解決するために私が試みたのは、単純な 16 ビット RNG を使用して、考えられるすべての値を元のリストと比較し、差が最小のものを選択することですが、この方法はかなり馬鹿げていて非効率的だと思います。 .

4

1 に答える 1

2

これは確かに非可逆圧縮です。

リスト内の値の範囲を教えてくれません。提供されたサンプルから、それぞれ少なくとも 6 ビット (0 から 63) をカウントしていると推測できます。合計で、圧縮するビット数は 0 ～ 3072 です。

これらのシーケンスに特別な特性がなく、ランダムに見える場合、大幅な圧縮を実現する方法はないと思います。任意のシーケンスが 32 ビットのシードから一致する確率は 2^32.2^(-3072)=7.10^(-916)、つまり無限小より小さいと考えてください。すべての値に 10% の誤差を許容すると、一致する確率は 2^32.0.1^512=4.10^(-503) になります。

12.5% の精度で圧縮する簡単な方法は、各値の 3 つの LSB を取り除くことで、50% の節約 (1536 ビット) につながりますが、これがあなたが探しているものであるとは思えません。

シーケンスのエントロピーhttp://en.wikipedia.org/wiki/Entropy_(information_theory)および/または値間の可能な相関を測定するのに役立ちます。これは、すべての (V, Vi+1) ペア、または (Vi, Vi+1, Vi+2) トリプルをプロットしてパターンを探すことで実行できます。

于 2014-05-10T10:47:19.703 に答える