Алгоритм циклического сжатия без потерь.Нужен совет.

[О_С_Е_Н_Ь]

Разрабатываю алгоритм циклического сжатия без потерь любых типов данных. Столкнулся с некоторыми трудностями, которые вроде решил. Сам любитель, основная профессия не соответствует,это хобби. Програмлю на Дэльфи. Есть рабочий прототип программы, но смущает вероятность ошибок в последующих этапах сжатия( пока научился крутить один цикл, были проблемы с файловыми системами)..Так как времени хронически не хватает, хочу узнать, может кто занимался подобными вопросами и есть ли вероятность что такое возможно? Сразу оговорюсь, сжатие не бесконечно - каждый цикл оставляет после себя след, который переноситься в конечный сжатый файл. Теоретически, можно циклически жать кругов под 500 а то и больше. Сам процесс сжатия очень требователен к ресурсам, а вот распаковка идет моментально. Еще рас повторюсь ,если кто занимался, подскажите! Может я просто в тупиковой ветке ?

[Duncon]

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

[somewhere]

Долгой запаковки и моментальной распаковки - такого не бывает..

Еще как бывает. Это, можно сказать, нормальная ситуация. Дело в том, что основные методы и алгоритмы сжатия основаны на составлении словаря и поиска некоторых цепочек исходных данных в этом словаре с последующей заменой на (код команды + смещение в словаре). Поиск в словаре - наиболее затратная по времени процедура. Время зависит от размера словаря, при этом достигаемая скорость сжатия очень редко превышает 1 мегабайт в секунду, а если установлена максимальная степень сжатия, когда алгоритм пытается сэкономить каждый бит - то и вовсе 50-70 кбайт в сек. Алгоритм поиска обычно пишут на асме с применением всевозможных SIMD-инструкций.
А вот процедура распаковки сводится к прямому копированию из словаря цепочек байт по заданным смещениям в выходной буфер. По скорости это не сильно отличается от операции перемещения блоков, измеряется сотнями и тысячами мегабайт в секунду.

Касательно темы, я немного не понял вопроса: занимался ли кто нибудь подобным? Да, занимался конечно, но разве только это интересно?
В тупиковой ли ветке на основании каких данных? какого факта? То, что сжатие идет долго - это норм. Ошибки появляются? - ну так это у всех, никто не совершенен.

[Duncon]

Будь реалистом, каждый из нас пользовался архиваторами, да распаковка происходит быстрее, но не так чтоб моментально, может 1 к 2, 1 к 3.. И не всегда и не обязательно архивация на словарях основывается..

[О_С_Е_Н_Ь]

Касательно темы, я немного не понял вопроса: занимался ли кто нибудь подобным? Да, занимался конечно, но разве только это интересно?
В тупиковой ли ветке на основании каких данных? какого факта? То, что сжатие идет долго - это норм. Ошибки появляются? - ну так это у всех, никто не совершенен.

Вечер добрый. Суть сомнений в том, что фактически можно запаковать 1Гб в 10Мб (возможно и меньше),но возможно ли такое, просчитывалось ли? Ведь вероятность такого решения практически меняет концепцию сжатия. К сожалению, я могу пока сжимать в один проход без потери данных с постоянным коэффициентом только небольшие файлы ( и то не все, так как на некоторых программа "спотыкается" и не находит возможных решений) поскольку очень емкий процесс задействован и моих 4-ёх ядер явно недостаточно . Для сравнения - файл объемом 1 Мб жмется примерно 30-40 сек. Мне кажется, что при последующих циклах я могу натолкнуться на такие же проблемы,т.е. невозможность найти решение для уже сжатого объема для последующего цикла..

[somewhere]

Суть сомнений в том, что фактически можно запаковать 1Гб в 10Мб (возможно и меньше),но возможно ли такое, просчитывалось ли?

Ну, в принципе, 1Гб можно и в 5 байт запаковать. Тут уже зависит от информационной емкости. Если там будет серия одинаковых байт, то вообще нет проблем.

поскольку очень емкий процесс задействован и моих 4-ёх ядер явно недостаточно

Ассемблер в помощь. Держу пари, я могу без труда ускорить текущую реализацию на языке высокого уровня, скажем... в 10 раз. То есть проблема в скорости? Это сущий пустяк. Если она жмет хотя бы примерно как LZMA или пусть даже в раза хуже, то это решаемая проблема.

( и то не все, так как на некоторых программа "спотыкается" и не находит возможных решений)

Это норма. Энтропия в некоторых файлах предельно высока, поэтому не все файлы сжимаются

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

Информационная емкость файла (или энтропия) - это постоянная величина. Она тоже выражается в байтах, только это минимальное количество байт, которыми можно представить информацию.
Например если взять 9 байт (72 бита): '114829306' - то их информационная емкость всего 27 бит (степень сжатия 62.5%). Меньше 27 бит никаким алгоритмом вы не представите натуральные числа от 0 до 2^27.
Тоже самое с файлами - у них тоже есть свой предел, к которому стремятся все архиваторы, сжимающие без потерь.

[О_С_Е_Н_Ь]

Информационная емкость файла (или энтропия) - это постоянная величина. Она тоже выражается в байтах, только это минимальное количество байт, которыми можно представить информацию.
Например если взять 9 байт (72 бита): '114829306' - то их информационная емкость всего 27 бит (степень сжатия 62.5%). Меньше 27 бит никаким алгоритмом вы не представите натуральные числа от 0 до 2^27.
Тоже самое с файлами - у них тоже есть свой предел, к которому стремятся все архиваторы, сжимающие без потерь.

Большое спасибо за ответ и разъяснения. Хочу ещё немного пояснить мои сомнения. Способ, который я так сказать "мучаю", берёт любые 10 байт и жмет их независимо от информационной составляющей с постоянным коэффициентом. Т.е. это может быть и уже упакованный архив,картинка или мр3 , и все они сжимаются с одним коэффициентом, пусть и небольшим.Т.е. запустив цикличную процедуру,теоретически, можно сократить объем информации в достаточно значительной мере. Отсюда количество вариантов просто космическое - 256^10. Исследовав достаточно много файлов на сжатие обнаружил много таких, которые без проблем проходят эту процедуру.Но были и такие , которые выдавали порции невозможности сжать до 25% файла по этому методу. А 75% соответственно могла сократиться.. (например 1Кб=100 блоков по 10 байт . 90 блоков проходят сжатие, а - 10 нет). Отсюда и сомнения. Получается, что если это возможно, то тот же фильм в HD можно закинуть на старый 3'5 диск. Если же это исключения, то почему такой ненормально высокий процент? Заранее спасибо за ответ.Просто иногда посещает мысль ,что я ерундой занимаюсь, хоть это и не в тягость..

[stanislav1955]

давай свяжемся engels64.64@ya.ru

[stanislav1955]

работал над тем - же думаю возможно хотел бы связаться с единомышленниками моя почта engels64.64@ya.ru

[stanislav1955]

это возможно как связаться с вами