алгоритм сжатия для названий улиц

Question

У меня есть список миллионов имен улиц и вы хотите сжать их с помощью алгоритма сжатия. Я не уверен, какой алгоритм подходит лучше всего. Большинство названий улиц имеют в них общие подстроки, такие как, например, «улица», «путь», ...

Набор всех названий улиц фиксирован и не изменяется динамически.

Сначала я думал о кодировке хаффмана, но это только коды для одиночных букв, поэтому он не даст большой производительности. Поэтому я подумал о создании trie и подсчете наиболее распространенных подстрок. Тогда у меня мог бы быть какой-то код для прохождения этого три, чтобы вернуть слово и сжать эти коды, используя что-то вроде кодирования хаффмана. Я не уверен, что это не делает его более сложным, чем нужно.

Кто-нибудь знает технику сжатия, которая имеет смысл в моем случае?

EDIT 1

Мой UseCase таким образом: у меня есть телефон устройства с ограниченным размером памяти. Этот телефон должен содержать все названия улиц всех улиц в конкретной стране. Теперь каждый уличный объект имеет некоторые значения, а среди них - название улицы в виде строки. Это занимает больше места, и я хотел бы свести его к минимуму. Поскольку имена очень похожи, т. Е. Большинство заканчивается на «... street» или «... way», я подумал, что стоит реализовать конкретный алгоритм сжатия, ориентированный на этот сценарий.

Простой gzip принес сжатие около 50%. Я думаю, что можно было бы получить больше от этого.

РЕДАКТИРОВАТЬ 2

Решение Ebbe М. Педерсен на самом деле дает очень хорошие результаты производительности. Вот код (написанный на 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 

Вам нужно будет обрабатывать диапазон имен, чтобы иметь возможность добраться до реальной, но если вы сделаете условность полностью изложив все п вы можете оптимизировать его для своих нужд.

Объедините это с использованием только 5-6 бит на букву и, возможно, выполните некоторые общие замены подстрок, вы должны иметь возможность свеклу 50%, которую вы видите с помощью bzip.

Answer 2

Не используйте алгоритмы Huffman, LZ, которые лучше всего подходят для этого.

Я предлагаю вам объединить все названия улиц в один текстовый файл (только названия улиц). Каждое название улицы должно быть NULL завершено, что поможет вытащить отдельную строку. Сжатие этого файла. Тем не менее вам придется выяснить, как управлять им, возможно, в ограниченной памяти мобильного устройства.

Кроме того, обратите внимание на SMAZ

Answer 3

Используя алгоритм со статическим словарем кодированием будет лучше. Вы можете попробовать использовать мою компрессию для игрушек: http://code.google.com/p/comprox. (компонент компоновки)

Но лучший способ заключается в том, что вы преобразовываете без потерь в свои данные, прежде чем передавать его в программу сжатия общего назначения, поскольку вы лучше понимаете свои данные.