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

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

О_С_Е_Н_Ь
Сообщения: 4
Зарегистрирован: 22 окт 2015, 22:07

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

Сообщение О_С_Е_Н_Ь » 22 окт 2015, 22:22

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

Аватара пользователя
Duncon
Сообщения: 1974
Зарегистрирован: 10 окт 2004, 13:11
Откуда: Питер
Контактная информация:

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

Сообщение Duncon » 22 окт 2015, 22:31

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

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

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

Сообщение somewhere » 23 окт 2015, 08:12

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

Касательно темы, я немного не понял вопроса: занимался ли кто нибудь подобным? Да, занимался конечно, но разве только это интересно?
В тупиковой ли ветке на основании каких данных? какого факта? То, что сжатие идет долго - это норм. Ошибки появляются? - ну так это у всех, никто не совершенен.
It's a long way to the top if you wanna rock'n'roll

Аватара пользователя
Duncon
Сообщения: 1974
Зарегистрирован: 10 окт 2004, 13:11
Откуда: Питер
Контактная информация:

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

Сообщение Duncon » 23 окт 2015, 10:29

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

О_С_Е_Н_Ь
Сообщения: 4
Зарегистрирован: 22 окт 2015, 22:07

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

Сообщение О_С_Е_Н_Ь » 24 окт 2015, 19:14

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

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

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

Сообщение somewhere » 24 окт 2015, 20:43

Суть сомнений в том, что фактически можно запаковать 1Гб в 10Мб (возможно и меньше),но возможно ли такое, просчитывалось ли?
Ну, в принципе, 1Гб можно и в 5 байт запаковать. Тут уже зависит от информационной емкости. Если там будет серия одинаковых байт, то вообще нет проблем.
поскольку очень емкий процесс задействован и моих 4-ёх ядер явно недостаточно
Ассемблер в помощь. Держу пари, я могу без труда ускорить текущую реализацию на языке высокого уровня, скажем... в 10 раз. То есть проблема в скорости? Это сущий пустяк. Если она жмет хотя бы примерно как LZMA или пусть даже в раза хуже, то это решаемая проблема.
( и то не все, так как на некоторых программа "спотыкается" и не находит возможных решений)
Это норма. Энтропия в некоторых файлах предельно высока, поэтому не все файлы сжимаются
Мне кажется, что при последующих циклах я могу натолкнуться на такие же проблемы,т.е. невозможность найти решение для уже сжатого объема для последующего цикла..
Информационная емкость файла (или энтропия) - это постоянная величина. Она тоже выражается в байтах, только это минимальное количество байт, которыми можно представить информацию.
Например если взять 9 байт (72 бита): '114829306' - то их информационная емкость всего 27 бит (степень сжатия 62.5%). Меньше 27 бит никаким алгоритмом вы не представите натуральные числа от 0 до 2^27.
Тоже самое с файлами - у них тоже есть свой предел, к которому стремятся все архиваторы, сжимающие без потерь.
It's a long way to the top if you wanna rock'n'roll

О_С_Е_Н_Ь
Сообщения: 4
Зарегистрирован: 22 окт 2015, 22:07

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

Сообщение О_С_Е_Н_Ь » 24 окт 2015, 23:33

somewhere писал(а): Информационная емкость файла (или энтропия) - это постоянная величина. Она тоже выражается в байтах, только это минимальное количество байт, которыми можно представить информацию.
Например если взять 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
Сообщения: 4
Зарегистрирован: 23 май 2016, 02:20

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

Сообщение stanislav1955 » 23 май 2016, 03:11

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

stanislav1955
Сообщения: 4
Зарегистрирован: 23 май 2016, 02:20

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

Сообщение stanislav1955 » 23 май 2016, 03:19

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

Ответить