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

[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]

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

[thedeemon.livejournal.com]

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

[alll]

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

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

[109.livejournal.com]

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

[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]

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

[thedeemon.livejournal.com]

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

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

[thedeemon.livejournal.com]

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

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

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

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

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

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

[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'ом

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

[soonts.livejournal.com]

OK, если для тебя фан, тогда конечно.
Лично меня бы заебало это программировать только ради фана.

Формула Бине какая-то сука сложная.
Забил в Maple, он тоже не смог её обратить.
Значит скорее всего "быстрого" решения не существует.

Тогда насколько я понимаю, для кодирования надо одновременно искать по двум фибоначчи-рядам (сначала по одному вверх до упора, потом по нему вниз и одновременно по второму вверх).

Подобные алгоритмы обычно занимают как минимум полтора экрана плохо поддерживаемого кода.

И потом ещё надо клеить биты: или склеивать строчки из '0' и '1' (очень неэффективно), или ебаццо самому с битовыми операциями (снова трудно поддерживаемый код: в первой реализации шансы где-нить перепутать >> с << стремятся к 100%).

Причом судя по тому что ты живёшь не в мире Windows (где было бы достаточно один раз закодить на C# сразу для всех платформ, включая xbox, zune и телефоны), тебе это нужно делать минимум два раза: в windows приложении, и для твоего оп.сорсного apache.

P.S. Конечно, я и не такие извращения придумывал и успешно реализовывал, но как минимум в половине случаев это было оправдано экономией ценных ресурсов :-)

[thedeemon.livejournal.com]

Не, че-то ты усложняешь. Одновременно по двум точно не надо. Обычно достаточно одного прохода сверху вниз.

bool started = false;
res.push_front(1);
for(std::vector::reverse_iterator it = fibs.rbegin(); it != fibs.rend(); it++) {
  if (*it <= x) {
    res.push_front(1);
    x -= *it;
    started = true;
  } else {
    if (started) res.push_front(0);
  }
}
return res;

Перед этим проверяется, достаточно ли у нас посчитанных членов ряда в fibs, если нет - досчитываются недостающие.

Эффективность в этой задаче на стороне клиента вообще не требуется, ибо кодируются числа один-два раза за сессию работы с программой. Поэтому вместо возни с битами можно использовать списки интов. Упаковка в строку:

int tn = digits.size() % 5;
if (tn > 0)
  digits.insert(digits.end(), 5-tn, 0);
CString out;
for(int dn = 0; dn < digits.size()/5; dn++) {
  int v = digits[dn*5]*16 + digits[dn*5+1]*8 + digits[dn*5+2]*4 + digits[dn*5+3]*2 + digits[dn*5+4];
  out += enc[v];
}

Причом судя по тому что ты живёшь не в мире Windows (где было бы достаточно один раз закодить на C# сразу для всех платформ, включая xbox, zune и телефоны), тебе это нужно делать минимум два раза: в windows приложении, и для твоего оп.сорсного apache.

Данный продукт как раз чисто виндовый, а вот на хостинге у меня действительно линукс. Использовать C# тут нельзя, ибо а) это shareware-утилита для широкого круга пользователей, не у всех был .net framework нужной версии, когда она начиналась, и б) там жосткий number crunching - обработка видео между отнюдь не managed кодеками.

[thedeemon.livejournal.com]

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

[109.livejournal.com]

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

[thedeemon.livejournal.com]

Слово могу забрать, если угодно, т.к. ошибку свою вы осознали, я думаю.

В чем именно пари? Фибоначчи vs. коды с указанием длины (Элиас/Райс/Голомб/другое)? Или Фибоначчи vs. заранее неизвестный метод для конкретной задачи? Если второе, то я пас. Если первое, то вот, например, типичный код:
D77KMB0F31JRPPVCV1HQB
т.е. в пределах 101-105 бит (здесь base32).
Это такая последовательность чисел:
1 9 5 0 30 10 20 0 4 7 2 0 1 0 2 5 0 0 1 2 0 13 4 50

[109.livejournal.com]

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

не хотите принимать пари - ваше дело. но тогда я напишу у себя соответствующий пост.

[soonts.livejournal.com]

Точно, про кодирование я чо-то проебал.
Я думал теорема про "сумму одного или двух чисел" - три взятых наугад числа, и твои примеры этому не противеречили.
Не мог что ли 41 вместо 42 написать? :-)))

>на хостинге у меня действительно линукс
Бросай ты эти open source поделки, и переходи на Windows Server 2008 - не пожалеешь.
godaddy.com: неограниченный трафик, medium trust level, $50 в год - там web site шо я сделал для своего клиента.
aspdiscount.net: 80 GB/month, full trust = можно звать unmanaged API, $120 в год - там const.me.

[thedeemon.livejournal.com]

Хорошо, можете предложить свой более эффективный метод. С удовольствием о нем напишу, если он себя оправдает.