как мне определить вореции распаковки по длине дерева???

[Jura1990]

Сообщение от Человек_Борща

Погуглил, че-то ничего нету на эту тему..

Здесь скачай http://dfiles.eu/files/fs4znav6g
Ты плохо искал вот видео http://m.youtube.com/watch?v=VFHsVXNFaLU
Здесь тест его http://www.youtube.com/watch?v=OovQn5d2H9c
Инструкции там уже. На видео показан как пользоваться

[Utkin]

По сути они всегда выдают одну определенную последовательность, только начальное смещение задается некоторым действительно случайным значением (например, текущим временем). Это смещение всего 32, ну или 64 бита (для новых процессоров). Так вот достаточно знать всего 64 бита, чтобы выдать определенную последовательность чисел любой длины. Остается лишь так подобрать параметры генератора псевдослучайных чисел, чтобы на выходе он выдавал цепочку байт, соответствующих содержимому файла. В итоге файл любого размера сжимается до 64 бит (8 байт). Операция сжатия может быть достаточно сложной (перебор и подбор правильного генератора), но распаковка всегда будет происходить очень быстро.

Я думал над этой темой, но не нашел алгоритма . И во вторых, большинство генераторов суть циклы, то есть через большой промежуток времени рано или поздно последовательность повторяется. Эта проблема для сжатия больших объемов данных, например, образа ДВД. А мегакрутой генератор с большим шагом повторения требует либо большие числа, либо пупец как много параметров. Соответственно сложность алгоритма возрастает.

[waleri]

Можно считать число пи.
Компрессия будет сводится к индексу.

[Utkin]

Можно считать число пи.
Компрессия будет сводится к индексу.

Верно, но только в том случае если число Пи не вырождается на каком-то из этапов. Доказательств тому, что в миллионых или миллиардных разрядах идет какое-нибудь 55555555 нет. Также как не знаю, есть ли доказательство того что число пи не имеет периода и где-то в разрядах не начнется 31415... Плюс нужно обоснование того, что число требующееся на разряд по количеству разрядов не будет превышать объем сжимаемой информации. А эта вероятность может оказаться высокой.

[Аватар]

Хи. По моему есть доказательство не вырождаемости пи. Впрочем не важно. Пусть не вырождается. Предполагается, что для любой ограниченной последовательности цифр (в нашем случае можно ограничится несколькими миллиардами цифр) где-то в недрах пи существует точное соответствие? Скорее всего вероятность этого не нулевая. Но предполагаю её соизмеримость с вероятностью того, что обезьяна долбящая по клаве когда-нибудь точный текст Войны и мира напечатает. Или полную Дюну Герберта

[Utkin]

Предполагается, что для любой ограниченной последовательности цифр (в нашем случае можно ограничится несколькими миллиардами цифр) где-то в недрах пи существует точное соответствие? Скорее всего вероятность этого не нулевая. Но предполагаю её соизмеримость с вероятностью того, что обезьяна долбящая по клаве когда-нибудь точный текст Войны и мира напечатает. Или полную Дюну Герберта

Для этого можно задействовать какой-нибудь проект распределенных вычислений и проверить экспериментально на ограниченном участке числа пи. Имея экспериментальные данные можно будет пытаться получить зависимость и утверждать что для получения нужной позиции требуется гарантированно участок пи размером столько-то. Или что при определенном объеме данных вычислительные возможности не позволяют получить нужные данные.
И потом вообще можно не сжимать всю последовательность сразу, а блочно. Ну допустим взять файл и попилить на блоки 8 байтов. А уже их записать как смещение от начала в числе пи. Ну это к примеру. То есть если получится экспериментально доказать что 8-ми байтовое число можно гарантированно встретить в позиции не превышающем скажем 6 байт, то сжимая многократно можно наверно достигнуть не плохих результатов. Даже если на это уйдут значительные ресурсы, можно жать потихоньку большие объемы данные - энциклопедии, библиотеки, архивы документов. То есть где не требуется оперативность запаковки.

[Аватар]

Можно ли построить цепочку цифр, что бы смещение любого из однобайтных чисел в ней (0-255) было не более чем семибитное (0-127)? если можно, то тогда можно говорить и об 8-байтных числах и меньшем смещении чем 8 байт

[Arigato]

Сообщение от Utkin

Доказательств тому, что в миллионых или миллиардных разрядах идет какое-нибудь 55555555 нет.

Точка Фейнмана.

[waleri]

Сообщение от Аватар

Но предполагаю её соизмеримость с вероятностью того, что обезьяна долбящая по клаве когда-нибудь точный текст Войны и мира напечатает. Или полную Дюну Герберта

Насчет скорости алгоритма речи не было

[Stilet]

Jura1990

Исходники антивиря опубликовать сюда можешь?