2

Webアプリケーションは、正の整数のセットのペアを比較します。各セットには、210 000 000（28ビットに収まる）以下の一意の値のみがあります。各セットで最大5000000の値。

セットAとBを比較するには、「Aに固有」、「Bに固有」、「AとBに共通」の3つの結果セットが必要です。特定のタスクは、「セットSに番号Nが存在するか」という質問に答えることです。

これまでのところ、プロジェクトはLAMPスタックの下で共有ホスティングの限られたリソースで実行されています。私が思いついた手っ取り早い解決策は、より多くのリソースを持っているホスティングのMySQLに仕事をアウトソーシングすることでした。各セットの一時テーブル。番号の付いた列はプライマリインデックスのみです。まれに、セットがengine = Memoryに収まるほど小さいため、高速です。動作しますが、遅すぎます。

このようなセットをメモリ内に保持する方法を探しています。これは、内部の特定の番号を検索するタスクに効果的です。メモリフットプリントを可能な限り低く保つ。

各セットを2^28ビット（32 Mb）のビットマスクとしてコーディングするというアイデアを思いつきました。セットに存在する数=1ビットセット。5百万の数字=210百万から設定された5百万ビット。多くのゼロ==効果的に圧縮できますか？

自転車を発明しているようです。バイナリ圧縮のこの特定のケースに対する「よく知られた」解決策を教えてください。私はハフマン符号化について読みましたが、その焦点はサイズの縮小であるため、適切な解決策ではないようですが、私のタスクでは圧縮されたセットに対して多くの検索が必要です。

更新 ゴロムコーディングに関する記事と、ランレングスエンコーディングへのそのアプリケーションの例を見つけました。

4

1 に答える 1

3

範囲内の表現された大きな整数のセットに使用できる標準の圧縮手法があります。これにより、効率的な反復が可能になります（したがって、交差、和集合、集合の差などを簡単に実行できます）が、ランダムアクセスは許可されません（したがって、 「SのNです」）。この特定の問題では、データセットがそれぞれ約7ビットに削減されます。これは、サイズ5,000,000のセットの場合は約8MBになります。役に立つ場合は、以下で説明します。

サイズが210,000,000ビット（それぞれ約26MB）のビットベクトルは、「is N in S」クエリへの回答とビット単位の演算の両方で計算効率が高く、最新のプロセッサでベクトル化された命令を使用して迅速に実行できます。おそらく、5,000,000要素の交差計算で得られるのと同じくらい高速です。大量のメモリを消費しますが、それだけのメモリがある場合は、それを選択してください。

セットが指定されたサイズの一様分布のランダムサンプルである場合に単純でほぼ最適な圧縮手法は、次のとおりです。

  1. セットを並べ替えます（または並べ替えられていることを確認します）。

  2. 「現在の値」を0に設定します。

  3. セット内の各要素について、順番に：

    a。要素から「現在の値」を引きます。

    b。その差が少なくとも32である間、11ビットを出力し、差から32を引きます。

    c。1ビットを出力し0、その後に5ビットでエンコードされた差を出力します。

    d。「現在の値」を要素より1つ多く設定します

圧縮によって要素あたり約7ビットになるという私の主張を正当化するには、次のようにします。

0すべての要素が6ビット（および5ビットのデルタ）を占めることは明らかです。1さらに、ステップ3bのビットを考慮する必要があります。ただし、すべてのデルタの合計はセット内で正確に最大の要素であり、210,000,000を超えることはできないため、ステップ3bを210,000,000/32回を超えて実行することはできません。したがって、ステップ3b。ステップ3cは6*5,000,000ビット、合計3,700万、つまり要素あたり7.4ビットを占めます（実際には、通常はこれより少し少なくなります）。

于 2013-02-28T01:39:46.160 に答える