алгоритм сжатия данных , на основе теории вероятностей

Хочу знать, есть ли здесь кто, кто интересуется данным или схожим вопросом?

Как мне известно, существует уйма упаковщиков. Одни сжимают лучше один тип файлов, другие другой.
Взять например арифметическое кодирование. Если взять любой файл, и перемешать в нем символы - лучше него никакой упаковщик не сожмет.
НО!
В описании этого алгоритма, педлагается , что нулевые частоты всех символов - равны 1. Что поему теперешнему мнению не есть правильно.
В принципе чисто для арифметического кодера это не имеет значения, но когда учитывать контекстную зависимость - эти лишние биты растут с гигантской скоростью.
Да и прочитал описание PPM алгоритма, и про его клонов. По моему мнению там все наобум берется!

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

А если для начала сократить повторяемость символов в файле (аля PCX компрессией), а потом происпользовать тот самый алгоритм

ЗЫ: где-т я уже такое слышал...

Цитата Shaman @ 31.01.04, 02:01

А если для начала сократить повторяемость символов в файле (аля PCX компрессией), а потом происпользовать тот самый алгоритм

ЗЫ: где-т я уже такое слышал...

По моему товарищ предлагает азбуку Морзе делать .Шифр без избыточного кодирования или как там... Уж и не помню-алгоритм давно описан (его в школе, т.е в институте проходят)
Смысл простой- при таком подходе делается выборка частот всех единиц информации (далее символов).
Эта выборка делится пополам (чтоб частота появления символов в двух половинах была равна).
Соответственно правой половине присваиваем бит 1, а левой 0.
Эти половины снова делим и т.д. В результате запись наиболее частых символов будет короткой (типа 01),а редких- длинной (например 100101).Все это уже доказано-в кодировании информации трудно сказать новое слово.
Что ни говори, а минимальный носитель информации-один бит и можно, конечно, оперировать природой информации и возможностью ее незначительного искажения, но один бит это один бит.Частотный анализ и все такое-да может, быть, но зачем все это?Глобыльных выигрышей по сравнению с существующими системами это не даст ни по скорости работы ни по результату сжатия.

PS Мда-никого не хотел обидеть-раньше и сам грезил сломать этот паршивый бит об колено

MajorMilizii, это, случаем, не архивирование по Хаффмену? Если да, то перед этим прогоняем Лемпель-Зиффом и получаем классический архиватор по Лемпель-Зифф-Хаффмен (LZH)!

Цитата tserega,6.02.04, 10:47

MajorMilizii, это, случаем, не архивирование по Хаффмену? Если да, то перед этим прогоняем Лемпель-Зиффом и получаем классический архиватор по Лемпель-Зифф-Хаффмен (LZH)!

Да, по моему, но точно не поню-давно это было-в голове только идея осталась .

Я бы не стал утверждать, что в PPM всё наобум берётся. Есть люди, которые этим делом занимаются годами и пишут диссертации (я так думаю ©). А если делается какое-либо допущение, то стараются сделать так, чтобы выходные данные были как можно меньше. Вообще говоря, PPM - это не самый лучший вариант для сжатия произвольных данных. Взять, например, RAR, который работает на основе LZ77 (тормознутость распаковки из-за кучи фильтров) или UPX (который сжимает хоть и медленнее, но даже лучше, а распаковщик вообще мизерный). PPM хорош для текста, ну, ты должен сам знать.
Я предлагаю начать с UPX'а . Где брать описание алгоритма - х/з, а исходники библиотеки, кажется, платные (халявные исходники - это не то, там коэффициент сжатия ниже и при компиляции ты не получишь копии оригинального UPX'а). Да и копаться в чужом исходнике...

Добавлено в 17.02.04, 20:13:
Кстати, о себе: вопросом сжатия интересуюсь, но не особо активно. Есть книга "методы сжатия данных" (подробнее здесь), но я её ещё до конца так и не дочитал (забросил на середине, наверное, уже год назад). Реализацией алгоритмов не занимался, если не считать алгоритм Хаффмана (студенту на заказ) и попытки изобрести свои методы (ещё когда я вообще ничего не знал по вопросу и изобрёл что-то нечто LZ77, только безо всяких хэшей и прочей оптимизаций по скорости... и работал он у меня очень тормозно, а результирующий файл получался в 2 раза больше rar'овского ).

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

Цитата Izya,9.03.04, 09:22

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

неважно новый ли алгоритм или старый.

важна теорема, что не существует программы которая способна хоть чуть чуть сжать ЛЮБОЙ ФАЙЛ.

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

Цитата

неважно новый ли алгоритм или старый.

важна теорема, что не существует программы которая способна хоть чуть чуть сжать ЛЮБОЙ ФАЙЛ.

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

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

а кстате, про

Цитата

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

зря не задумались ребятки, тут не слабые перспективы.....

Цитата T1000_RUS @ 16.03.04, 21:49

Цитата

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

зря не задумались ребятки, тут не слабые перспективы.....

а по моему персектив тут почти нет. такая функция должна сжимать только какой-то пределенный тип файлов.
--------
Я уже реализовал алгоритм контекстно зависимого моделирования. Мне он так нравился, думал он заткнет за пояс ZIP и RAR, но... ZIP сделал, а вот до RAR-а немного недотянулся. Вот теперь занимаюсь кристаллизацией файлов, т.е. пытаюсь придумать принцип по которому файл делится на элементарные кристаллики. Если кто сталкивался с информацией на эту тему, буду рад любой помощи.