Заранее извиняюсь за длинный пост.
С 1999 года все мечтал написать себе архиватор с собственным методом сжатия. Первые "алгоритмы" я уже не помню. До сих пор меня эта мысль мучает. Постоянно пробую написать свой метод сжатия, но никак не могу. Постоянно начинаю, но либо получаю отрицательные результаты (в результате сжатия файл становится больше), либо бросаю реализацию. Через полгода опять приходит эта мысль и все по-новому.
Одним из первых алгоритмов был: берем первый символ, и сравниваем следующие n байт с этим символом. = устанавливаем n бит 1, иначе 0. После этого эти байты удалялись, и весь массив сдвигался, заполняя свободное место. В большинстве случаев, после "архивации" файл получался большего размера чем был. Приходила идея сравнивать не 1 байт, а блоками. Т.е. бьем файл на блоки до тех пор, пока не появятся 2 одинаковых. Записываем вышеописанным методом. Блоки, соответственно, "архивируются" таким же способом. Данный метод не реализовывал.
Следующий алгоритм мне пришел в голову, когда мне надо было отправить много однотипных файлов. Один из файлов выбирался в качестве "шаблона". Хранился без сжатия. По нему сверялись все остальные. Если n байт файла-шаблона=n байту архивируемого файла, то n бит=1, иначе 0. То, что не совпало, дописывалось в без архивации. Следующий файл сверялся как с первым, так и со вторым файлом этим же способом. Выбирался наилучший вариант и сохранялся... Написание этого варианта забросил (недописал). Результат неизвестен.
Вчера опять пришли мысли о новом алгоритме. Вернее даже 2. Находим (не обязательно в одном файле) 2 одинаковых блока и записываем их в словарь, а в файле ставил ссылку на него (1 байт:0-неархивированный блок+8байт его размер;>0-архивированный блок+4/8байт номер блока). Или без словаря: 0-тоже, >0-размер блока (мин.размер блока+этот байт*const)+адрес в файле, откуда читать. Т.е. как бы частичные link. (почему-то ни один мной испытанный архиватор не поддерживает link'и. WinRAR честно архивирует файл 2 раза)
Каждый раз меня мучает сомнение в целесообразности/эффективности данного алгоритма. Хочется узнать мнение других, в частности — специалистов по алгоритмам сжатия, чтобы не мучатся и окончательно забросить эту идею (или может развивать ее дальше), т.к. свободного времени для этого не очень много. Да и реализовывать его лучше на C++, который я не очень хорошо знаю.
Модераторам: если написанное мною является бредом, удалить этот пост, или перенесите в соответствующий раздел.

Думаю, лучшего качества сжатия можно добиться, если слить все файлы в одну кучу, а потом неким волшебным образом оптимально разрезать на куски (n >= 0) и сжимать эти куски отдельно. Причем файлы нужно расположить в той последовательности, в которой оптимальное разбиение будет опять же оптимально
Только вот не стоит оно того...

ViRUS_1 wrote:

> Одним из первых алгоритмов был: берем первый символ, и сравниваем
> следующие n байт с этим символом. = устанавливаем n бит 1, иначе 0.
> После этого эти байты удалялись, и весь массив сдвигался, заполняя
> свободное место. В большинстве случаев, после "архивации" файл получался
> большего размера чем был. Приходила идея сравнивать не 1 байт, а
> блоками. Т.е. бьем файл на блоки до тех пор, пока не появятся 2
> одинаковых. Записываем вышеописанным методом. Блоки, соответственно,
> "архивируются" таким же способом. Данный метод не реализовывал.
RLE?
> Следующий алгоритм мне пришел в голову, когда мне надо было отправить
> много однотипных файлов. Один из файлов выбирался в качестве "шаблона".
> Хранился без сжатия. По нему сверялись все остальные. Если n байт
> файла-шаблона=n байту архивируемого файла, то n бит=1, иначе 0. То, что
> не совпало, дописывалось в без архивации. Следующий файл сверялся как с
> первым, так и со вторым файлом этим же способом. Выбирался наилучший
> вариант и сохранялся... Написание этого варианта забросил (недописал).
> Результат неизвестен.
Посмотреть на результат можно, добыв утилиту diff/bsdiff/xdelta (?). тут
недалеко в ветке про эти программы говорили. Так распространяют версии
исходников: дают базовые версии и списки изменений между промежуточными.
> Вчера опять пришли мысли о новом алгоритме. Вернее даже 2. Находим (не
> обязательно в одном файле) 2 одинаковых блока и записываем их в словарь,
> а в файле ставил ссылку на него (1 байт:0-неархивированный блок+8байт
> его размер;>0-архивированный блок+4/8байт номер блока). Или без словаря:
> 0-тоже, >0-размер блока (мин.размер блока+этот байт*const)+адрес в
> файле, откуда читать. Т.е. как бы частичные link. (почему-то ни один
> мной испытанный архиватор не поддерживает link'и. WinRAR честно
> архивирует файл 2 раза)
Если файлы маленькие — склейте их. Или скажите создать непрерывный
архив. Просто WinRAR a) не делает дальних ссылок (это невыгодно, сам
убедился, когда писал архиватор. Он сжимал HTML, меняя регистр тегов и
заменяя их по словарю, а остальное — LZ (поиск повторов)+ Huffman). б)
стремится спасти файлы (все без одного) при повреждении архива
дискеткой. Ваш алгоритм похож на имеющиеся, просто Вы ещё не выбрали
параметры (в чём отдельное искусство).
> Каждый раз меня мучает сомнение в целесообразности/эффективности данного
> алгоритма. Хочется узнать мнение других, в частности — специалистов по
> алгоритмам сжатия, чтобы не мучатся и окончательно забросить эту идею
> (или может развивать ее дальше), т.к. свободного времени для этого не
> очень много.
Не то, что я специалист, но опыт подсказывает, что указанные Вами
алгоритмы (кроме первого, который, впрочем, похож на RLE) близки самым
используемым. Надо только угадать константы.
> Да и реализовывать его лучше на C++, который я не очень
> хорошо знаю.
Чем плох Паскаль? Когда писал архиватор, мороки было много. Но уж точно
не из-за языка/компилятора. Free Pascal Compiler позволил создать массив
нужного размера, а Borland Pascal — нет (стар он), и это определило выбор.
> Модераторам: если написанное мною является бредом, удалить этот пост,
> или перенесите в соответствующий раздел.
Про моё это тоже верно..

Здравствуйте, raskin, Вы писали:

R>Если файлы маленькие — склейте их. Или скажите создать непрерывный
R>архив. Просто WinRAR a) не делает дальних ссылок (это невыгодно, сам
R>убедился, когда писал архиватор. Он сжимал HTML, меняя регистр тегов и
R>заменяя их по словарю, а остальное — LZ (поиск повторов)+ Huffman). б)
R>стремится спасти файлы (все без одного) при повреждении архива
R>дискеткой. Ваш алгоритм похож на имеющиеся, просто Вы ещё не выбрали
R>параметры (в чём отдельное искусство).
Испытывал: есть файл 1.avi. Shift+F5 в FAR ->2.avi. Архивирую rar. Размер 1.avi+2.avi-несколько килобайт.
R>Не то, что я специалист, но опыт подсказывает, что указанные Вами
R>алгоритмы (кроме первого, который, впрочем, похож на RLE) близки самым
R>используемым. Надо только угадать константы.
Ясно, велосипед изобрел.
R>Чем плох Паскаль? Когда писал архиватор, мороки было много. Но уж точно
R>не из-за языка/компилятора. Free Pascal Compiler позволил создать массив
R>нужного размера, а Borland Pascal — нет (стар он), и это определило выбор.
На нем и реализовывал. Просто на C++ скорость повыше, скорее всего, будет.

Здравствуйте, ViRUS_1, Вы писали:

VRU>Каждый раз меня мучает сомнение в целесообразности/эффективности данного алгоритма. Хочется узнать мнение других, в частности — специалистов по алгоритмам сжатия, чтобы не мучатся и окончательно забросить эту идею (или может развивать ее дальше), т.к. свободного времени для этого не очень много.

http://forum.compression.ru:8080/

ViRUS_1 wrote:
> Здравствуйте, raskin, Вы писали:
>
> R>Если файлы маленькие — склейте их. Или скажите создать непрерывный
> R>архив. Просто WinRAR a) не делает дальних ссылок (это невыгодно, сам
> R>убедился, когда писал архиватор. Он сжимал HTML, меняя регистр тегов и
> R>заменяя их по словарю, а остальное — LZ (поиск повторов)+ Huffman). б)
> R>стремится спасти файлы (все без одного) при повреждении архива
> R>дискеткой. Ваш алгоритм похож на имеющиеся, просто Вы ещё не выбрали
> R>параметры (в чём отдельное искусство).
> Испытывал: есть файл 1.avi. Shift+F5 в FAR ->2.avi. Архивирую rar.
> Размер 1.avi+2.avi-несколько килобайт.
Тогда непрерывный архив надо. Впрочем, несколько килобайт тоже не мало.
> R>Не то, что я специалист, но опыт подсказывает, что указанные Вами
> R>алгоритмы (кроме первого, который, впрочем, похож на RLE) близки самым
> R>используемым. Надо только угадать константы.
> Ясно, велосипед изобрел.
> R>Чем плох Паскаль? Когда писал архиватор, мороки было много. Но уж точно
> R>не из-за языка/компилятора. Free Pascal Compiler позволил создать массив
> R>нужного размера, а Borland Pascal — нет (стар он), и это определило выбор.
> На нем и реализовывал. Просто на C++ скорость повыше, скорее всего, будет.
Мистика. Не намного и не всегда. Особенно для этого алгоритма (главное —
аккуратно буферизовать файл (без шуток)).

По мотивам Re: придумал принцип архивации, надо осушествить.

Автор:
Дата: 19.10.02

Просматриваем файл. Находим в этом файле простое число>8 байт, которое есть в таблице, и заменяем порядковым номером из таблицы (размером 4^2), где 0 элемент=первое простое число после (>8 байт)^2. Адрес замещаемого элемента записываем в другой файл. Получается (>8 байт)-8 (4 байта индекс в таблица, 4 байта адрес замещаемого элемента) байт экономии.

ViRUS_1 wrote:
> Просматриваем файл. Находим в этом файле простое число>8 байт, которое
> есть в таблице, и заменяем порядковым номером из таблицы (размером 4^2),
> где 0 элемент=первое простое число после (>8 байт)^2. Адрес замещаемого
> элемента записываем в другой файл. Получается (>8 байт)-8 (4 байта
> индекс в таблица, 4 байта адрес замещаемого элемента) байт экономии.
Вы представляете себе степень сжатия? Ради этого никто руки не марает.
Поиск заранее заданных небольших объектов малой Колмогоровской сложности
и замена на описания не эффективен. Скорее стремятся приблизиться к
Колмогоровской сложности целого текста за счёт повторов и т.п.

Здравствуйте, ViRUS_1, Вы писали:

VRU>Заранее извиняюсь за длинный пост.
VRU>С 1999 года все мечтал написать себе архиватор с собственным методом сжатия...

У Стругацких был такой персонаж -- Доморощинер. (Не обижайтесь.)

Ваши алгоритмы кое в чем близки к распространенным методам.

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

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

volk wrote:
>
> По сути вопроса.
> Если Вы обнаружили, что какой-то из архиваторов упускает одну из
> возможностей
> для сжатия, попробуйте написать утилиту, которая эту возможность реализует.
> Предварительно пропущенные через нее файлы попробуйте скормить архиватору.
> Если размер уменьшится, то это уже будет некоторое достижение.

Впрочем, если нет, то это ни о чём не говорит. Поскольку выход
стандартных реализаций LZ хорошо сжимается Huffman, но не наоборот
(после Huffman вообще тяжело работать методам, построенным на байтах, а
LZ сжимает байты в байты, а не байты в биты, как Huffman).

Здравствуйте, raskin, Вы писали:

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

R>Впрочем, если нет, то это ни о чём не говорит. Поскольку выход
R>стандартных реализаций LZ хорошо сжимается Huffman, но не наоборот
R>(после Huffman вообще тяжело работать методам, построенным на байтах, а
R>LZ сжимает байты в байты, а не байты в биты, как Huffman).

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

volk wrote:
> Здравствуйте, raskin, Вы писали:
>
>> > Предварительно пропущенные через нее файлы попробуйте скормить
> архиватору.
>> > Если размер уменьшится, то это уже будет некоторое достижение.
>
> R>Впрочем, если нет, то это ни о чём не говорит. Поскольку выход
> R>стандартных реализаций LZ хорошо сжимается Huffman, но не наоборот
> R>(после Huffman вообще тяжело работать методам, построенным на байтах, а
> R>LZ сжимает байты в байты, а не байты в биты, как Huffman).
>
> Продолжая тему, давайте предложим автору скачать n архиваторов,
> выполнить все n*n последовательными сжатий двумя архиваторами, а затем
> выбрать лучший вариант.

Не получится.. Если просто скачивать, то есть проблема: почти все
архиваторы хотят байтовый вход и почти все выдают битовый выход из-за
комбинаций методов. Скорее, можно попытаться сделать файл, который этим
принципом сожмётся хорошо и посмотреть на файл. Если удастся поверить,
что такой файл возможен естественным путём — уже что-то. Можно поискать
в интернете похожий алгоритм.