[devel] base2 <-> base62

[Alexey Tourbin]

On Thu, Aug 05, 2010 at 04:07:00PM +0300, Alexander Bokovoy wrote:
> 2010/8/5 Alexey Tourbin <at на altlinux.ru>:
> > Ломал голову несколько часов.  Кто знает тому пряник.
> >
> > Есть слово в алфавите {0,1} - т.е. последовательность нулей и единиц.
> > Хочется представить это слово в алфавите {0..9,a..z,A..Z} (base62)
> > для экономии битов.  То есть получить более короткое представление
> > этой последовательности в виде букв и цифр.  И нужно уметь
> > конвертировать назад.
> >
> > Понятно, что если из последовательности сделать просто число, то задача
> > сводится к представлению числа в различных системах счисления.  Но
> > последовательность слишком длинная, в машинное число она не поместится,
> > а связываться с GPM неохота.
> В оригинальной задаче наличие всех первоначальных битов обязательно
> или можно обойтись хэшем?

Обязательно.  В двух словах, происходит следующее.
Нам надо представить набор строк в виде их хешей.
Строки хешируются и урезаются по длине хеша (e.g. 20 битов).
1) Массив хешей сортируется.
2) Идет дельта кодирование, то есть хранится разница между соседними
значениями.
2) Применяется golomb coding, на этих данных он дает оптимальный
результат (как хаффман), т.к. если хеш дает равномерное распределение,
то после сортировки и дельта кодирования получается геометрическое распределение.

Недавно вычитал в статье
http://algo2.iti.kit.edu/singler/publications/cacheefficientbloomfilters-wea2007.pdf
Куда раньше смотрел не понятно.-(

> Если нельзя, то какой длины последовательность? Хорошо ли сжимается?
> Может быть имеет смысл сжимать (хаффманом или еще чем), а потом
> полученный результат паковать в base64 и заменять "неправильные"
> символы на "правильные" с однозначным обратным восстановлением при
> распаковке с последующим unbase64.

Соответственно у меня проблема уже на последней стадии: golomb encoder
выдает поток нулей и единиц, надо их представить в окончательном виде,
пригодном для зависимостей.

Длина большая, представь себе что в библиотеке 1024 символа, и
изначально хеш 20 битов на символ.  После ужатия получается примерно
12 битов на символ.  Поэтому и есть интерес сделать эту строку как можно
короче, за счет base62.  А если бы она был не такой длинной, то сгодился
бы hex обычный.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : отсутствует
Тип     : application/pgp-signature
Размер  : 198 байтов
Описание: отсутствует
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20100805/b0793497/attachment-0001.bin>