Алгоритм/формат номера для номеров «меньше хранения»

Question

У меня есть очень серьезная проблема для решения. У меня есть список из 75000 слов. Каждому слову присваивается номер для удобства идентификации. Первому слову присваивается 0, последнее слово - 75000. Теперь у меня есть список предложений. Возьмем 1 пример для примера.

I have big dog 

Когда вы представляете это с присвоенными номерами, он стал 20 123 2332 3434. Это просто означает, что слово Я появился в 20-слово в нашем списке, слово имеют появился как 123 слова в нашем списке, слово большой появился как 2332 слова и так далее.

Как раз это, у меня более 2 миллиардов предложений, и мне нужно сохранить/написать их численное представление. Мы считали, что сохранение длинных номеров, таких как 20 123 2332 3434 за 2 миллиарда записей, займет огромное пространство. Вместо этого, если мы можем представить их с использованием более короткой системы счисления, например F3x G6e rRr, это позволит сэкономить место для хранения.

Как я могу это достичь? Может быть, используются шестнадцатеричные числа? Я использовал this конвертер и, кажется, нет большой разницы, потому что число в шестнадцатеричном 1e240 числа в шестнадцатеричной является 124f8 и так далее; похоже, что количество символов одинаково, поэтому я не уверен, сохранит ли оно какое-либо пространство.

Просьба предоставить вам ваши советы для достижения этой задачи. Я буду писать эту функцию в Java.

Answer 1

Десятичные числа дают вам 10 возможностей на каждый байт. Шестнадцатеричные числа дают вам 16. Если бы вы могли использовать все возможные битовые шаблоны, у вас было бы 256 возможностей на каждый байт, что эквивалентно сохранению двух шестнадцатеричных цифр в пространстве одного. В зависимости от того, как вы храните и извлекаете данные, вы можете обнаружить, что кодирование http://en.wikipedia.org/wiki/Base64 позволяет избежать коррупции, если, например, вы не можете хранить нулевые байты или некоторые другие битовые шаблоны, например битовые шаблоны с высоким набором бит.

Есть возможности для более сложного сжатия. Можно было бы просто использовать стандартный компрессор, такой как тот, который предоставлен в Java пакетом java.util.Zip или эквивалентами на других языках. Другое - если вы знаете, как бывают общие слова, было бы просто отсортировать слова так, чтобы общие слова имели низкие числа и, следовательно, более короткие числа. Вы также можете посмотреть http://en.wikipedia.org/wiki/Huffman_coding. Это позволит вам избежать пробелов между числами, а также дать более короткие слова коротким последовательностям цифр.

Answer 2

Внедрение двоичного представления вашей строки. Первый бит 16/32 представляет длину строки n, затем следуйте n 17-битные целые числа, представляющие индексы в вашем массиве из 75000 слов. Число 17 является примерно логарифм по основанию 2 из 75000. Таким образом, ваш пример будет (при условии, 16 бит для длины слова):

0000 0000 0000 0100 0 0000 0000 0001 0100 0 0000 0000 0111 1011 
|     4 |     20 |     123 | 
         0 0000 1001 0001 1100 0 0000 1101 0110 1010 
        |     2332 |     3434 | 

Затем вы можете преобразовать этот поток битов в/из двоичного файла, используя для Пример: BinaryIn and BinaryOut classes: Роберт Седжуик. Обратите внимание, что в приведенной выше строке требуется всего 21 байт для кодирования.

Вы можете использовать сжатие Хаффмана для сжатия двоичного потока, если вы заранее знали распределение слов. Это может сэкономить много места, если распределение искажено в сторону небольшого подмножества слов.