想要街道名稱的壓縮算法

我有一個數以百萬計的街道名稱列表，並希望使用壓縮算法對它們進行壓縮。我不確定哪種算法最適合。大多數街道名稱都有共同的子字符串，例如「街道」，「方式」，...想要街道名稱的壓縮算法

所有街道名稱的集合是固定的，不會動態變化。

起初我一直在想哈夫曼編碼，但是它只編碼單個字母，所以它不會給出很好的性能。所以我想到了生成一個trie並計算最常見的子串。然後，我可以通過某種代碼來遍歷這個trie，以便獲取這個單詞，並使用像huffman編碼這樣的代碼來壓縮這些代碼。我不確定這是不是比它需要更復雜。

有誰知道在我的情況下有意義的壓縮技術？

EDIT 1

我的用例是這樣的：我有有限的存儲尺寸的電話設備。這部手機需要保存特定國家所有街道的所有街道名稱。現在，每個街道對象都有一些值，其中街道的名稱爲字符串。這佔用了大部分空間，我想盡量減少它。由於名稱非常相似，即以「......街道」或「......方式」最後結尾，我認爲可能值得實施針對此場景的特定壓縮算法。

一個簡單的gzip壓縮了約50％。我認爲應該有可能從中獲得更多。

EDIT 2

Ebbe M.佩德森的解決方案實際上是給很好的表現效果。下面是一些代碼（用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％的總壓縮

非常感謝您的答案發送它

來源

2013-03-26 Christian

你打算如何使用你的壓縮數據？ – Serg 2013-03-26 19:32:51

你需要自己實現嗎？我只是測試一些壓縮庫，並使用最好的。我想[LZMA]（http://en.wikipedia.org/wiki/Lempel-Ziv-Markov_chain_algorithm）會很好。 – Blorgbeard 2013-03-26 19:33:22

不確定你的用例是什麼，但gzip/bzip是否足夠？ – mon4goos 2013-03-26 19:32:58

根據您的數據集，您可以先訂購街道名稱，然後將每個街道名稱表示爲前一個街道名稱+「不同部分」的子字符串。

有一些相似的街道名稱的例子：

 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-28 13:35:45

這實際上是一個非常好的主意。到目前爲止，我一直在尋找所有名字中名稱中最長的常見子串。運行時間相當長，但我有大約1000臺電腦並行運行。所以這是可能的。使用該算法，我發現了諸如「街道」，「方式」等模式。它本身可以提供約50％的壓縮率，但與您的想法相結合可能會非常有趣！ – Christian 2013-03-28 14:26:11

不要使用霍夫曼，LZ算法最適合這個。

我建議你把所有的街道名稱合併成一個文本文件（只有街道名稱）。每個街道名稱應該是NULL終止，這將有助於拉出單個字符串。壓縮此文件。不過，你必須弄清楚如何在移動設備的有限內存中管理它。

而且，看看SMAZ

來源

2013-03-27 09:15:10

hm，SMAZ面向英文字母，因此壓縮像「the」這樣的單詞成爲一個位。對於我的特殊情況，它不會給出如此好的壓縮。特別是因爲我需要單獨壓縮單個名稱，而不是一個大文本。 – Christian 2013-03-28 14:24:15

使用靜態辭典編碼算法驗證效果會更好。你可以試試我的玩具壓縮util：http://code.google.com/p/comprox。（comprop組件）

但是，最好的方法是在將數據傳遞到通用壓縮程序之前對數據進行無損轉換，因爲您對數據有更好的理解。

來源

2013-03-28 12:49:35 richselian

想要街道名稱的壓縮算法

回答

相關問題