71

1 ～ 100、110 ～ 160 など、ほぼ連続する整数の範囲を含む大きな配列があります。すべての整数は正です。これを圧縮するのに最適なアルゴリズムは何でしょうか?

deflate アルゴリズムを試しましたが、圧縮率は 50% しかありません。このアルゴリズムは不可逆であってはならないことに注意してください。

すべての数値は一意であり、徐々に増加しています。

また、そのようなアルゴリズムのJava実装を教えていただければ、それは素晴らしいことです。

4

15 に答える 15

38

まず、各値と前の値の差をとって、値のリストを前処理します (最初の値については、前の値がゼロであると仮定します)。これは、ほとんどの場合、ほとんどの圧縮アルゴリズムではるかに簡単に圧縮できる一連のシーケンスを提供するはずです。

これは、PNG 形式が圧縮を改善する方法です (gzip で使用されるのと同じ圧縮アルゴリズムが続くいくつかの異なる方法の 1 つを実行します)。

于 2008-11-12T10:57:11.330 に答える
18

まあ、私はより賢い方法に投票しています。この場合、格納する必要があるのは [int:startnumber][int/byte/whatever:number of iterations] だけです。例の配列を 4xInt 値に変換します。その後、必要に応じて圧縮できます:)

于 2008-11-12T08:35:34.673 に答える
17

データ ストリームに固有のカスタム アルゴリズムを設計することもできますが、市販のエンコード アルゴリズムを使用する方がおそらく簡単です。Java で利用可能な圧縮アルゴリズムのいくつかのテストを実行したところ、100 万個の連続する整数のシーケンスに対して次の圧縮率が見つかりました。

None        1.0
Deflate     0.50
Filtered    0.34
BZip2       0.11
Lzma        0.06
于 2009-07-04T07:52:47.647 に答える
12

数字のサイズは？他の回答に加えて、基数128のバリアント長エンコーディングを検討することもできます。これにより、小さい数値を1バイトに格納しながら、大きい数値を許可できます。MSBは、「別のバイトがある」という意味です。これについては、ここで説明します。

これを他の手法と組み合わせて、「スキップサイズ」、「テイクサイズ」、「スキップサイズ」、「テイクサイズ」を保存します。ただし、「スキップ」も「テイク」もゼロにならないことに注意してください。それぞれから1を引きます（これにより、少数の値のために余分なバイトを節約できます）

それで：

1-100, 110-160

「スキップ1」（物事を簡単にするためにゼロから開始すると仮定）、「テイク100」、「スキップ9」、「テイク51」です。それぞれから1を引き、（小数として）与えます

0,99,8,50

これは（16進数）としてエンコードされます：

00 63 08 32

より大きな数をスキップ/取得したい場合-たとえば、300; 1を引くと299になりますが、これは7ビットを超えます。リトルエンドから始めて、継続を示すために7ビットのブロックとMSBをエンコードします。

299 = 100101100 = (in blocks of 7): 0000010 0101100

だから、小さな終わりから始めます：

1 0101100 (leading one since continuation)
0 0000010 (leading zero as no more)

与える：

AC 02

したがって、大きな数値を簡単にエンコードできますが、小さな数値（スキップ/テイクでは一般的に聞こえます）はスペースを取りません。

これを「deflate」で実行してみることができますが、それ以上の効果はないかもしれません...

面倒なエンコーディングの問題を自分で処理したくない場合は...値の整数配列（0,99,8,60）を作成できる場合は、uint32/を繰り返しパックしたプロトコルバッファを使用できます。 uint64-そしてそれはあなたのためにすべての仕事をします;-p

私はJavaを「実行」しませんが、これが完全なC＃実装です（私のprotobuf-netプロジェクトからエンコードビットの一部を借用しています）。

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
static class Program
{
    static void Main()
    {
        var data = new List<int>();
        data.AddRange(Enumerable.Range(1, 100));
        data.AddRange(Enumerable.Range(110, 51));
        int[] arr = data.ToArray(), arr2;

        using (MemoryStream ms = new MemoryStream())
        {
            Encode(ms, arr);
            ShowRaw(ms.GetBuffer(), (int)ms.Length);
            ms.Position = 0; // rewind to read it...
            arr2 = Decode(ms);
        }
    }
    static void ShowRaw(byte[] buffer, int len)
    {
        for (int i = 0; i < len; i++)
        {
            Console.Write(buffer[i].ToString("X2"));
        }
        Console.WriteLine();
    }
    static int[] Decode(Stream stream)
    {
        var list = new List<int>();
        uint skip, take;
        int last = 0;
        while (TryDecodeUInt32(stream, out skip)
            && TryDecodeUInt32(stream, out take))
        {
            last += (int)skip+1;
            for(uint i = 0 ; i <= take ; i++) {
                list.Add(last++);
            }
        }
        return list.ToArray();
    }
    static int Encode(Stream stream, int[] data)
    {
        if (data.Length == 0) return 0;
        byte[] buffer = new byte[10];
        int last = -1, len = 0;
        for (int i = 0; i < data.Length; )
        {
            int gap = data[i] - 2 - last, size = 0;
            while (++i < data.Length && data[i] == data[i - 1] + 1) size++;
            last = data[i - 1];
            len += EncodeUInt32((uint)gap, buffer, stream)
                + EncodeUInt32((uint)size, buffer, stream);
        }
        return len;
    }
    public static int EncodeUInt32(uint value, byte[] buffer, Stream stream)
    {
        int count = 0, index = 0;
        do
        {
            buffer[index++] = (byte)((value & 0x7F) | 0x80);
            value >>= 7;
            count++;
        } while (value != 0);
        buffer[index - 1] &= 0x7F;
        stream.Write(buffer, 0, count);
        return count;
    }
    public static bool TryDecodeUInt32(Stream source, out uint value)
    {
        int b = source.ReadByte();
        if (b < 0)
        {
            value = 0;
            return false;
        }

        if ((b & 0x80) == 0)
        {
            // single-byte
            value = (uint)b;
            return true;
        }

        int shift = 7;

        value = (uint)(b & 0x7F);
        bool keepGoing;
        int i = 0;
        do
        {
            b = source.ReadByte();
            if (b < 0) throw new EndOfStreamException();
            i++;
            keepGoing = (b & 0x80) != 0;
            value |= ((uint)(b & 0x7F)) << shift;
            shift += 7;
        } while (keepGoing && i < 4);
        if (keepGoing && i == 4)
        {
            throw new OverflowException();
        }
        return true;
    }
}
于 2009-07-04T08:06:35.593 に答える
5

TurboPFor: 最速の整数圧縮

  • Java Critical Natives/JNI インターフェイスを含む C/C++ 用
  • SIMD アクセラレーションによる整数圧縮
  • ソートされた/ソートされていない整数リストのスカラー + 統合 (SIMD) 差分/ジグザグ エンコーディング/デコーディング
  • 全範囲 8/16/32/64 ビット整数リスト
  • 直接アクセス
  • ベンチマークアプリ
于 2016-07-08T16:07:47.483 に答える
3

他のソリューションに加えて：

「密集した」領域を見つけて、ビットマップを使用してそれらを保存することができます。

したがって、たとえば：

1000〜3000の400の範囲に1000の数値がある場合、1つのビットを使用して数値の存在を示し、2つのintを使用して範囲を示すことができます。この範囲の合計ストレージは2000ビット+2インチであるため、その情報を254バイトで保存できます。これは、短い整数でもそれぞれ2バイトを使用するため、非常に優れています。この例では、7倍の節約になります。

領域が密集しているほど、このアルゴリズムのパフォーマンスは向上しますが、ある時点で、開始と終了を保存するだけの方が安くなります。

于 2009-07-04T08:34:29.357 に答える
3

CesarB と Fernando Miguelez の回答を組み合わせます。

まず、各値と前の値の差を保存します。CesarB が指摘したように、これにより、ほとんどが 1 のシーケンスが得られます。

次に、このシーケンスでランレングス エンコーディング圧縮アルゴリズムを使用します。繰り返される値が多数あるため、非常にうまく圧縮されます。

于 2008-11-12T11:34:12.520 に答える
3

文字列「1-100、110-160」を圧縮するか、文字列をバイナリ表現で保存し、それを解析して配列を復元します

于 2008-11-12T08:31:31.483 に答える
2

算術符号化の特殊なケースであるHuffman Codingを見てみることをお勧めします。どちらの場合も、開始シーケンスを分析して、異なる値の相対頻度を決定します。発生頻度の高い値は、発生頻度の低い値よりも少ないビット数でエンコードされます。

于 2008-11-12T13:08:16.777 に答える
1

あなたのケースは、検索エンジンでのインデックスの圧縮と非常によく似ています。使用される一般的な圧縮アルゴリズムは、PForDeltaアルゴリズムとSimple16アルゴリズムです。圧縮のニーズに合わせてカミカゼライブラリを使用できます。

于 2011-06-23T16:28:47.260 に答える
1

おそらく使用する必要がある基本的な考え方は、連続する整数の範囲 (これらを範囲と呼びます) ごとに、開始番号と範囲のサイズを格納することです。たとえば、1000 個の整数のリストがあり、個別の範囲が 10 個しかない場合、わずか 20 個の整数 (範囲ごとに 1 つの開始番号と 1 つのサイズ) を格納してこのデータを表すことができます。これは 98 の圧縮率になります。 %。幸いなことに、範囲の数が多い場合に役立ついくつかの最適化を行うことができます。

  1. 開始番号自体ではなく、前の開始番号に対する開始番号のオフセットを格納します。ここでの利点は、格納する数値に必要なビット数が一般的に少なくなることです (これは、後の最適化の提案で役立つ場合があります)。さらに、開始番号のみを保存した場合、これらの番号はすべて一意になりますが、オフセットを保存すると、番号が近いか、繰り返される可能性があり、後で別の方法を適用してさらに圧縮することができます。

  2. 可能な限り最小のビット数を使用する両方のタイプの整数。数値を反復処理して、開始整数の最大オフセットと最大範囲のサイズを取得できます。次に、これらの整数を最も効率的に格納するデータ型を使用して、圧縮データの先頭にデータ型またはビット数を指定するだけです。たとえば、開始整数の最大オフセットがわずか 12,000 で、最大範囲の長さが 9,000 の場合、これらすべてに 2 バイトの符号なし整数を使用できます。次に、圧縮データの先頭にペア 2,2 を詰め込んで、両方の整数に 2 バイトが使用されていることを示します。もちろん、少しのビット操作を使用して、この情報を 1 バイトに収めることができます。

これら 2 つの最適化を使用して、いくつかの例を見てみましょう (それぞれが 4,000 バイトです)。

  1. 1,000 個の整数、最大オフセットは 500、10 個の範囲
  2. 1,000 整数、最大オフセットは 100、50 範囲
  3. 1,000 整数、最大オフセットは 50、100 範囲

最適化なし

  1. 20 個の整数、それぞれ 4 バイト = 80 バイト。圧縮 = 98%
  2. 100 個の整数、それぞれ 4 バイト = 400 バイト。圧縮 = 90%
  3. 200 個の整数、それぞれ 4 バイト = 800 バイト。圧縮 = 80%

最適化あり

  1. ヘッダー 1 バイト + 数字 20 個、各 1 バイト = 21 バイト。圧縮 = 99.475%
  2. ヘッダー 1 バイト + 数字 100 個、それぞれ 1 バイト = 101 バイト。圧縮 = 97.475%
  3. 1 バイトのヘッダー + 200 個の数字、それぞれ 1 バイト = 201 バイト。圧縮 = 94.975%
于 2009-07-04T08:49:55.893 に答える
0

一連の繰り返し値がある場合、RLE は実装が最も簡単で、良い結果が得られる可能性があります。それにもかかわらず、LZW などのエントロフィを考慮した他のより高度なアルゴリズムは、現在は特許がなく、通常ははるかに優れた圧縮を実現できます。

これらおよびその他のロスレス アルゴリズムについては、こちらを参照してください。

于 2008-11-12T08:26:52.087 に答える