3

私が取り組んでいる圧縮の問題を次のように減らしました。

入力として、浮動小数点値の 2 つの長さ n ベクトルが与えられます。

float64 L1, L2, ..., Ln;
float64 U1, U2, ..., Un;

そのようなすべての私のために

0.0 <= Li <= Ui <= 1.0

(ちなみに n が大きい: ~10^9)

このアルゴリズムは、L と U を入力として受け取り、それらを使用してプログラムを生成します。

生成されたプログラムを実行すると、長さ n のベクトル X が出力されます。

float64 X1, X2, ..., Xn;

そのようなすべての私のために：

L1 <= Xi <= Ui

生成されたプログラムは、これらの境界に適合する任意の X を出力できます。

たとえば、生成されたプログラムは、単純に L を配列として格納し、それを出力することができます。(これには、L を格納するために 64n ビットのスペースが必要であり、プログラムがそれを出力するために少し余分に必要になることに注意してください)

目標は、与えられた L と U で、生成されたプログラム (データを含む) をできるだけ小さくすることです。

たとえば、L のすべての要素が 0.3 未満であり、U のすべての要素が 0.4 より大きい場合、生成されたプログラムは次のようになります。

for i in 1 to n
    output 0.35

これは小さいでしょう。

これに取り組むための戦略、アルゴリズム、またはアーキテクチャを提案できる人はいますか?

4

1 に答える 1

2

この単純なヒューリスティックは非常に高速であり、境界が非常に良好な圧縮を可能にする場合、非常に良好な圧縮を提供するはずです。

すべての候補値に対して任意の (仮想) 二分探索木を準備します。float64s は s とソート順を共有するため、signed int64末尾のゼロが多い値を任意に優先 (ルートに近づける) ことができます。

  • 境界のペアごとに
    • ルートから開始します。
    • 現在のノードが両方の境界よりも大きいか、両方の境界よりも小さい場合、
      • 木を下ります。
    • 現在のノードをベクトルに追加します。

上記のツリーの場合、これは次のことを意味します。

  • 境界のペアごとに
    • 指定された範囲内で有効ビットができるだけ少ない (一意の) 数値を見つけます。つまり、両方の境界が異なる最初のビットを見つけます。それを に設定し、それに1続くすべてのビットを に設定し0ます。に設定されている1ビットが符号ビットの場合は、0代わりに設定します。

次に、これを ing ライブラリにフィードしdeflateて圧縮 (および自己解凍型アーカイブの構築) できます。

データを分析して別の二分探索木を構築すると、より良い圧縮を達成できる可能性があります。データセットは非常に大きく、データのストリームとして到着するため、実行できない可能性がありますが、これはそのようなヒューリスティックの 1 つです。

  • 出力が完全に定義されていない間
    • 最も未定の境界内に収まる値を見つけます。
      • すべての境界を一緒に並べ替えます。
        • より高い値の境界の前に、より低い値の境界を並べ替えます。
        • 下限は、同じ値を持つ上限の前に並べ替えます。
        • 区別できない境界はグループ化されます。
      • 開いている間隔の現在の合計を計算します。
      • 最大の合計を選択します。上限または下限のどちらでもかまいません。最小量の重要なビットで間隔を分割することにより、「賢明な選択」を試みることもできます。
    • この値を使用できるすべての位置の出力として設定します。

並べ替え順序を再計算する代わりに、並べ替え順序をキャッシュしてそこから削除するか、実行中の合計もキャッシュすることもできます (または、実行時に実行中の合計を再計算することから実行中の合計をキャッシュするように切り替えます)。これは結果を変えるものではなく、実行時間を改善するだけです。

于 2012-11-30T08:27:59.630 に答える