2

我有数百万个街道名称的列表，并希望使用压缩算法对其进行压缩。我不确定哪种算法最适合。大多数街道名称中都有共同的子字符串，例如“street”、“way”、...

所有街道名称的集合是固定的，不会动态变化。

起初我在考虑霍夫曼编码，但它只编码单个字母，所以它不会提供很好的性能。所以我想生成一个 trie 并计算最常见的子字符串。然后我可以有某种代码来遍历这个 trie 以取回单词，并使用诸如霍夫曼编码之类的东西压缩这些代码。我不确定这是否不会使它变得比需要的更复杂。

有谁知道在我的情况下有意义的压缩技术？

编辑 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 记录的约定，您可以根据您的需要对其进行优化。

将其与每个字母仅使用 5-6 位相结合，并且可能进行一些常见的子字符串替换，您应该能够使用 bzip 获得 50% 的甜菜。

于 2013-03-28T13:35:45.457 回答
1

使用带有静态字典编码的算法会更好。你可以试试我的玩具压缩工具：http ://code.google.com/p/comprox 。（压缩组件）

但最好的方法是在将数据传递给通用压缩程序之前对数据进行无损转换，因为您对数据有更好的理解。

于 2013-03-28T12:49:35.920 回答
0

不要使用 Huffman，LZ 算法最适合这个。

我建议您将所有街道名称合并到一个文本文件中（仅街道名称）。每个街道名称都应该NULL终止，这将有助于拉出单个字符串。压缩这个文件。然而，您将不得不弄清楚如何在移动设备的有限内存中管理它。

另外，看看SMAZ

于 2013-03-27T09:15:10.387 回答