Фибоначчи в народном хозяйстве

[thedeemon]

Всякий знает, что вычисление чисел Фибоначчи - важнейшая задача программирования, поэтому именно с нее нередко начинают обучение. Некоторые языки программирования, похоже, были созданы специально для решения этой задачи (prooflink). Однако не все еще нашли применение этим чудесным числам в быту.

Понадобилось мне тут недавно уметь компактно представить набор целых чисел: при проверке на наличие новых версий а также при деинсталляции программа передает на сервер номер своей версии, а заодно кое-какую статистику, вроде числа запусков, количества дней с момента установки и т.п. Передавать нужно GET'ом, ибо при деинсталляции это делает не сама программа, а скрипт установщика, к тому же хочется сразу иметь эти данные в логах апача. Чисел получилось много, в явном виде запрос получился бы сильно длинным и некрасивым. Решил применить какое-нибудь простое сжатие.

Числа все неотрицательные, сверху не ограниченные, и вероятность встречи числа быстро уменьшается с ростом самого числа. Для таких данных есть семейство кодов переменной длины, называемое универсальными кодами. Большинство из них сначала кодируют некоторым образом число битов (например, унарно), а затем сами биты кодируемого числа. Но длина таких кодов растет довольно быстро. Зато есть более интересный и для нужных мне значений более эффективный способ представления - коды Фибоначчи. Они основаны на теореме одного зубного врача из бельгийской армии, которая говорит, что всякое натуральное число можно уникальным образом представить в виде суммы чисел Фибоначчи, причем в такой сумме никогда не будет двух последовательных членов ряда. Ряд начинается так: 1, 2, 3, 5, 8, 13, 21... Тогда 6 = 1+5, 15 = 2+13, 31 = 2+8+21. Чтобы закодировать число последовательностью битов, достаточно пройтись по ряду Фибоначчи до требуемого числа и проставить единицы напротив входящих в сумму членов и нули напротив невходящих. Поскольку по построению у нас не может быть подряд двух единиц, этот факт используется для маркировки конца числа: после последней единицы ставим еще одну и код готов, длину числа хранить нигде не надо. Примеры:

Fib: 1 2 3 5 8 13 21 34  | Code
  1: *                   | 11
  2:   *                 | 011
  3:     *               | 0011
  4: *   *               | 1011
 10:   *     *           | 010011
 16:     *      *        | 0010011
 42:         *        *  | 000010011

В итоге у меня требуемый набор чисел превращается в такую битовую последовательность, которая затем кодируется по пять цифрами и буквами в Base32. Получается обычно по 12-15 символов на 24 исходных инта.

А вот и сам автор теоремы - полковник Эдуард Цекендорф:

Comments

[xeno-by.livejournal.com]

Помню, когда мы в лицее увлекались архивацией, в книжке Ватолина и компании я также видел описание гамма-, дельта- и других кодов Элиаса (http://ru.wikipedia.org/wiki/Гамма-код_Элиаса и дальше по линкам). Вы про эти коды, наверняка, знаете (я вас видел на компрешн.ру =)), а вот читателям бложека, может быть, будет интересна релевантная информация.

Когда мы делали BWT-компрессор, то на одном из этапов остановились именно на DC + Фибоначчи. Вот только запамятовал почему - то ли потому, что арифметик тогда было писать непонятно как, то ли за перфомансом гнались... В общем, интересно все это. Спасибо за воспоминания =)

[thedeemon.livejournal.com]

Да, коды Элиаса к тому же семейству универсальных относятся, для чисел до 10^4 Фибоначчи эффективнее.

[xeno-by.livejournal.com]

Там, вроде бы, от распределения вероятностей зависело?

[xeno-by.livejournal.com]

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

[thedeemon.livejournal.com]

Верно, осталось найти этому факту применение. ;)

[thedeemon.livejournal.com]

Картинка в тему:
http://en.wikipedia.org/wiki/File:Fibonacci,_Elias_Gamma,_and_Elias_Delta_encoding_schemes.GIF

[109.livejournal.com]

число битов, необходимое для кодирования длины числа в битах растёт как log(log), а разница между fibonacci и direct binary растёт как просто log. таким образом, чем больше число, тем менее выгодно кодировать его fibonacci. что интересно, маленькие числа кодировать fibonacci тоже невыгодно, поскольку их всё равно надо в конечном итоге (чтобы передать) запихивать во что-то стандартное, типа int. таким образом, использовать fibonacci не имеет смысла никогда.

[thedeemon.livejournal.com]

>чем больше число, тем менее выгодно кодировать его fibonacci

Верно. Невыгодность начинается где-то с 10^4, а ожидаемое распределение таково, что 99,9% чисел будут в пределах тысячи, а 90% в пределах сотни. На таких порядках варианты с длинами проигрывают, что и показано на картинке.

>что интересно, маленькие числа кодировать fibonacci тоже невыгодно, поскольку их всё равно надо в конечном итоге (чтобы передать) запихивать во что-то стандартное, типа int

Bitstream уже отменили? По одному их передавать действительно нет смысла, но набор - уже есть.

>таким образом, использовать fibonacci не имеет смысла никогда

Очевидная глупость, ибо применима и к Хаффману и к прочим VLC, используемым повсеместно - mp3, MPEG4, H.264 etc.

[109.livejournal.com]

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

[sassa-nf.livejournal.com]

не смешите мои тапочки.

меньше одного байта не перешлёшь, отсюда и плясать.

например, если речь о 8-битных числах (для простоты):

- числа 0..0x7f пересылаются одним байтом.
- числа 0x80..0x3fff пересылаются двумя байтами, где первый байт сообщения маскированный 0xc0 даёт 0x80. это уже числа до 16К. далее забиваем на выигрыш от уродства кодов переменной длины и кодируем длину сообщения в байтах.

аналогичная схема для base64.

[alll]

> Числа все ... сверху не ограниченные
...
> Большинство из них сначала кодируют некоторым образом число битов

Гм, я правильно понимаю, что если числа неограничены сверху, то возникает задача определения числа битов в числе битов и мы в некотором роде впадаем в рекурсию? :)

[thedeemon.livejournal.com]

Правильно, некоторые универсальные коды так и устроены.

[juan-gandhi.livejournal.com]

Фигасе. Век живи век учись.

[soonts.livejournal.com]

Неочевидный код, пара часов разработки, не human-readable данные в запросах - ради экономии нескольких байт трафика, на операции которую пользователь сделает раз в год?
Обращаю внимание, что типичный HTTP GET заголовок - это уже порядка 300 байт по TCP. То есть экономия с 60 байт до 12 не в 5 раз, а всего на 15%.

Я бы закодировал числа в строчку как-нить так
0-12-F5-AE75-0-0-0-2-0-FFDDEE-0-0-0-0-0-0
(минусы вместо например '|' - шоб разделитель оставался одним символом а не "%A6", помним про URL encoding)
Да, у меня было бы минимум 47 байт в запросе. Однако плюсы в данном случае IMO перевешивают: время разработки минуты а не часы, и human readable формат данных.

P.S. А как ты кодируешь число 0 ?

[thedeemon.livejournal.com]

Дело не в экономии трафика, а в "страшности" URL'a (при деинсталляции там не просто запрос посылается, а открывается браузер с uninstall feedback form, если пользователь согласился на нее пройти, конечно).

Про 0 - кодирую везде N+1.

[thedeemon.livejournal.com]

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

[soonts.livejournal.com]

>открывается браузер с uninstall feedback form
Например пишешь 10 строк C# кода, который, если запрошен файл "Uninstall.aspx?s=...", сохраняет Request.QueryString["s"] в Session["s"], после чего отправляет клиенту HTTP 301 на Uninstall.aspx без параметров.
Все параметры на месте + чистый URL.

>это же представление используется для хранения статистики
А если в след. версии один счотчик исчезнет (причом не последний, а тот шо посередине), и появятся 2 новых?

>не возникнет желания ее выборочно попортить
IMO чувак, который открывает RegEdit и правит непонятные для него значения - весьма редкий use-case.

Когда на сайте support.microsoft.com есть инструкции по правке реестра, они всегда сопровождаются warning "serious problems might occur if you modify the registry incorrectly".
Где-то мне попадался warning даже страшнее, о том шо "вы можете сломать систему так шо потребуется её переустановка".

Несмотря на то что удалив единственный ключ (например из ветки HKCR), можно поиметь очень разнообразные проблемы, Microsoft не делает попыток защититься от таких чуваков.
Точнее, делает только если пиздец: "Restore last known good configuration".

[thedeemon.livejournal.com]

А если в след. версии один счотчик исчезнет (причом не последний, а тот шо посередине), и появятся 2 новых?

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

Я не спорю, можно было сделать и так, как ты говоришь. Но все же мне идея хранения и передачи статистики в явном виде не очень симпатична, а сжатие кодами Фибоначчи это фан. Могу позволись себе совместить приятное с полезным. :)

[nponeccop.livejournal.com]

> Передавать нужно GET'ом

как Вы могли пожертвовать идемпотентностью ради искусства!

[thedeemon.livejournal.com]

Виноват, каюсь! :)

[http://users.livejournal.com/_winnie/]

Получился интересный способ генерирования кодов Хафманна (т.е. без общего префикса) для какого-то фиксированной частоты чисел. Наверное если померять настоящие частоты входящих символов, то можно сделать в среднем короче.
Если их частоты невозможно померять, то такой способ наверное лучший ибо красивый :)

[thedeemon.livejournal.com]

Две трудности - бесконечный алфавит и отсутствие априорной статистики.

[trueview.livejournal.com]

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

Не совсем корректная формулировка. Всякое натуральное число можно представить уникальным образом в виде суммы чисел Фибоначчи, если запретить использование в сумме двух соседних членов последовательности.

[thedeemon.livejournal.com]

Да, можно так сформулировать.

[trueview.livejournal.com]

Нужно. В вашем случае телега впереди кобылы.:)