想要的街道名称的压缩算法

Question

我有一个包含数百万个街道名称的列表，想使用压缩算法压缩它们。我不确定哪种算法最适合。大多数街道名称中都有共同的子字符串，例如“街道”、“路”……

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

起初我在考虑霍夫曼编码，但它只编码单个字母，所以它不会提供很好的性能。所以我想到了生成一个 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%

非常感谢您的回答

Answer 1

根据您的数据集，您可以先对街道名称进行排序，然后将每条街道名称表示为前一个街道名称的子字符串+“不同部分”。

具有一些相似街道名称的示例:

      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% 的值。