2

何百万もの通りの名前のリストがあり、圧縮アルゴリズムを使用してそれらを圧縮したいと思います。どのアルゴリズムが最適かわかりません。ほとんどのストリート名には、「street」、「way」、...などの一般的なサブストリングが含まれています。

すべてのストリート名のセットは固定されており、動的に変更されることはありません。

最初はハフマン符号化を考えていましたが、それは一文字しか符号化しないので、あまり性能が出ません。そこで、トライを生成して、最も一般的な部分文字列を数えることを考えました。次に、単語を取り戻すためにこのトライをトラバースするためのある種のコードを作成し、ハフマンコーディングなどを使用してこれらのコードを圧縮することができます。これが必要以上に複雑になっていないかどうかはわかりません。

私の場合に意味のある圧縮技術を知っている人はいますか？

編集1

したがって、私の使用例は次のとおりです。ストレージサイズが制限された電話デバイスがあります。この電話は、特定の国のすべての道路のすべての道路名を保持する必要があります。これで、すべてのストリートオブジェクトにいくつかの値があり、その中には文字列としてのストリートの名前があります。それはほとんどのスペースを占めるので、最小限に抑えたいと思います。名前は非常に似ているため、つまりほとんどが「...street」または「...way」で終わるため、このシナリオに合わせた特定の圧縮アルゴリズムを実装する価値があると思いました。

単純なgzipにより、約50％の圧縮が実現しました。私はそれからより多くを得ることが可能であるはずだと思います。

編集2

Ebbe M. Pedersenのソリューションは、実際には非常に優れたパフォーマンス結果をもたらしています。ここにいくつかのコードがあります（C＃で書かれています）：

    private IndexedItem[] _items;

    public void CompressStrings(string[] strings)
    {
        Array.Sort(strings);
        _items = new IndexedItem[strings.Length];

        string lastString = string.Empty;

        for (int i = 0; i < strings.Length; i++)
        {
            byte j = 0;
            while (lastString.Length > j && lastString[j] == strings[i][j])
            {
                j++;
            }

            _items[i] = new IndexedItem() { Prefix = j, Suffix = strings[i].Substring(j) };

            lastString = strings[i];
        }
    }

    private struct IndexedItem
    {
        public byte Prefix;
        public string Suffix;
    }

圧縮後、DeflateStreamを介して送信します。これにより、合計で約30％の圧縮が行われます。

答えてくれてありがとう

4

3 に答える 3

2

データセットに応じて、ストリート名を並べ替えることから始めて、すべてのストリート名を前のストリート名のサブストリング+「別の部分」として表すことができます。

似たような通りの名前の例：

      How much to copy from previous street name in Hex 
                         | The rest of the street name
Original                 V   V V V            Orig size  New size
Broadwalk                0 Broadwalk             9         10
Broadwater               7 ter                   8          4
Broadwater Access        A  Access              17          8
Broadwater Bluff         B Bluff                16          6
Broadwater Branch        C ranch                17          6
Broadwater Bridge        D idge                 17          5
Broadwater Cemetary      B Cemetary             19          9
Broadwater Creek         C reek                 16          5
Broadwater Point         B Point                16          6
Broadwater Pvt           C vt                   14          3
Broadwaters              A s                    11          2
Broadway                 7 y                     8          2
Broadway And Union       8  And Union           18         11
Broadway Apartments      9 partments            19         10
Broadway Avenue          9 venue                15          6
                                               ---        ---
                                               220         93

実際の名前に到達できるようにするには、さまざまな名前を処理する必要がありますが、nレコードごとに完全にスペルアウトする規則を作成すると、ニーズに合わせて名前を最適化できます。

これを1文字あたり5〜6ビットのみを使用して組み合わせ、おそらくいくつかの一般的な部分文字列の置換を行うと、bzipで表示される50％をビートできるはずです。

于 2013-03-28T13:35:45.457 に答える
1

静的辞書コーディングでアルゴリズムを使用する方が良いでしょう。私のおもちゃの圧縮ユーティリティを試してみることができます：http ：//code.google.com/p/comprox 。（compropコンポーネント）

ただし、データをよりよく理解しているため、データを汎用圧縮プログラムに渡す前に、データに可逆変換を行うのが最善の方法です。

于 2013-03-28T12:49:35.920 に答える
0

ハフマンは使用しないでください。これにはLZアルゴリズムが最適です。

すべてのストリート名を1つのテキストファイル（ストリート名のみ）に結合することをお勧めします。NULL個々の文字列を引き出すのに役立つ各通りの名前を終了する必要があります。このファイルを圧縮します。それでも、おそらくモバイルデバイスの限られたメモリでそれを管理する方法を理解する必要があります。

また、SMAZを見てください

于 2013-03-27T09:15:10.387 に答える