Форум программистов, компьютерный форум, киберфорум
Непризнанные теории, гипотезы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
96 / 23 / 20
Регистрация: 17.09.2014
Сообщений: 1,322
1

Как написать лучший алгоритм сжатия

28.12.2016, 20:36. Просмотров 2090. Ответов 26
Метки нет (Все метки)

Проснулся сегодня в 5 часов утра, приснилось что я алгоритм сжатия данных придумал, да такой, что можно сжать любой размер до 1го байта, о как.
Странно кстати, я вообще сжатием не интересовался до этого ни разу...
Ну врубил комп, давай вспоминать чего там снилось, толком ничего не вспомнил, помню только 2 байта в 1 методом каких-то операций.
Пол утра считал, и так и так, ну никак нельзя 8 нулей||единиц засунуть в 4...

Пробовал в 4 прохода с множителем - нифига.

В итоге наморосил какой-то бред в текстовике:
Кликните здесь для просмотра всего текста
0-255 диапазон

1 200 - два байта для сжатия.

255 почему-то должно присутствовать...

200 - 1 = 199
255 - 199 = 56

255 / 1 = 255

255 / 200 =


11111111 = 256
1111111 = 127
111111 = 64
11111 = 32
1111 = 16

0000 - 0 0 и 0
0001 - 1 0 и 1
0010 - 2 0 и 2
0011 - 3 0 и 3
0100 - 4 1 и 0
0101 - 5 1 и 1
0110 - 6 1 и 2
0111 - 7 1 и 3
1000 - 8 2 и 0
1001 - 9 2 и 1
1010 - 10 2 и 2
1011 - 11 2 и 3
1100 - 12 3 и 0
1101 - 13 3 и 1
1110 - 14 3 и 2
1111 - 15 3 и 3


200 / 2 = 100 / 2 = 50 / 2 = 25 / 5 = 5 / 5 = 1
200 / 3 = 66,66666666666667
200 / 4 = 50 / 4 = 12,5
200 / 5 = 40 / 5 = 8 / 5 = 1,6
200 / 6 = 33,33333333333333
200 / 7 = 28,57142857142857
200 / 8 = 25

200 / 4 = 50
50 / 5 = 10
10 / 2 = 5
5 / 5 = 1

0001 1 * 1
00001 1 * 1
000001 1 * 1
0000001 1 * 1

0010 1 * 2
00010 2 * 1
000010 2 * 1
0000010 2 * 1

0011 1 * 2
00010 2

200 \ 2 = 100


256 - 1 = 254
128 - 254 = -127
64 - -127 = 191
32 - = -159
8
4
2

255
127.5
63,75
31,875
15,9375


11001000 = 200

200 / 255 = 0,7843137254901961 ~ 0.78

1001110 = 78

78 / 127 = 0,6141732283464567 ~ 0.61


Потом загуглил, есть 2 типа сжатия, и все работают на повторении.
1й - когда подряд идут одинаковые байты, 2й - когда в файле встречаются одинаковые байты...

Вот и верь после этого снам...

Добавлено через 6 часов 24 минуты
Да не стоило в отдельную тему, это я как пример ТСу, что не все сны сбываются...Я вообще не интересуюсь такими вещами как сжатие ))
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.12.2016, 20:36
Ответы с готовыми решениями:

У какого архиватора лучший метод сжатия?
Может и тупой вопрос но спрашиваю почему 100мб данных обычный способ сжимает лучше чем...

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

Алгоритм сжатия
целочисленную таблицу из n-элементов переписать так, чтобы вместо одинаковых, идущих подряд...

Алгоритм сжатия LZ
Если у кого есть, поделитесь кодом, пожалуйста:-/

26
es geht mir gut
11208 / 4686 / 1177
Регистрация: 27.07.2011
Сообщений: 11,422
28.12.2016, 21:25 2
В 5 утра женщины должны сниться, а не алгоритмы сжатия
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
28.12.2016, 21:42 3
Общая дискуссия о предельной степени сжатия
"Если нет такого - то что будет если появится?"
Нет и не будет.

Задайтесь простым вопросом - до какого предельного размера можно разжать заданный файл?

Для любого заданного алфавита и набора кодов есть ровно два экстремальных значения длины кодированного текста: минимальная и максимальная. В вырожденном случае (равная кратность всех символов алфавита) эти значения совпадают.

По аналогии - прямоугольный объект можно повернуть длинной стороной, можно - короткой.

Круглый - как ни крути - все того же размера.

Математически, "сжатие" (термин абсолютно неверный, но общепринятый) - это поворот.

Так вот, "круглое" - НЕ сжимается. Как ни крути :-)
0
Миниатюры
Как написать лучший алгоритм сжатия  
390 / 353 / 62
Регистрация: 29.05.2015
Сообщений: 2,161
02.01.2017, 14:03 4
Цитата Сообщение от артист Посмотреть сообщение
Проснулся сегодня в 5 часов утра, приснилось что я алгоритм сжатия данных придумал, да такой, что можно сжать любой размер до 1го байта, о как.
Это и любой сможет. Проблемы начинаются, когда пытаешься распаковать свой сжатый файл.
0
96 / 23 / 20
Регистрация: 17.09.2014
Сообщений: 1,322
03.01.2017, 00:27  [ТС] 5
Да не, таких алгоритмов вообще не существует.
А с потерями - это фигня...

Как пример, запаковать файл винраром по максимуму, далее получившийся архив запаковать - результат будет одинаков.
Потому, что сжимается за счет повторов одинаковых байт, а в архиве их уже нет.
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
03.01.2017, 15:43 6
gazlan
Вообще говоря круг определяется координатами своего центра и
размером радиуса, а также оператором, о котором известно, что
он рисует круг. И все это выглядит примерно так... Круг (x, y), R
Вот это и есть для круга максимальное сжатие...
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
03.01.2017, 16:02 7
Цитата Сообщение от echs Посмотреть сообщение
Вот это и есть для круга максимальное сжатие
В "колмогоровском" смысле - как генератор (пред)фрактала.

В "чистом" же виде, как (пере)кодирование (Ex: Huffman / LZ) - это просто переход к другой системе координат (другой системе счисления).
0
627 / 134 / 46
Регистрация: 22.12.2013
Сообщений: 1,123
Записей в блоге: 19
31.01.2017, 07:52 8
Цитата Сообщение от gazlan Посмотреть сообщение
Так вот, "круглое" - НЕ сжимается. Как ни крути :-)
Вы фигуры не покрутили в третьем измерении. Тогда, если повернуть любую фигуру получится отрезок.
Так что, в случае сжатия по площади фигур, получится максимальное сжатие.

Добавлено через 1 час 19 минут
Цитата Сообщение от gazlan Посмотреть сообщение
Математически, "сжатие" (термин абсолютно неверный, но общепринятый) - это поворот.
Тогда получается лучше вращать в трехмерном пространстве.
В n-мерном пространстве сжатие будет больше. Вопрос выбора следующих измерений.

Добавлено через 9 минут
Можно ли вращать относительно массы? Можно ли вращать относительно времени?
Можно ли вращать относительно скорости? Можно ли вращать относительно ускорения?
Что можно взять за единицу измерения?

Добавлено через 5 минут
Как сжать сферу? Повернуть относительно цвета, массы, скорости, ускорения.

Добавлено через 10 минут
Пусть два 3-х мерных пространства не параллельны, а как-бы перпендикулярны друг другу и пересекаются в одной точке.
Тогда можно поворачивать уже в двух пространствах.

Добавлено через 7 минут
Как сжать сферу? Повернуть относительно цвета, упругости, скорости, ускорения,
длины, массы, времени, электрического тока, термодинамической температуры, количества вещества и силы света
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
31.01.2017, 14:45 9
Цитата Сообщение от vvm28 Посмотреть сообщение
Вы фигуры не покрутили в третьем измерении
Покрутите шар - с любым числом измерений. "Сжать" можно только что-то асимметричное.
0
627 / 134 / 46
Регистрация: 22.12.2013
Сообщений: 1,123
Записей в блоге: 19
31.01.2017, 16:15 10
Цитата Сообщение от gazlan Посмотреть сообщение
Покрутите шар - с любым числом измерений. "Сжать" можно только что-то асимметричное.
Обозначить сферу по другому. Пример: o12 - сфера с радиусом 12 и она уже меньше "места" занимает.

Добавлено через 8 минут
Другой вопрос как расшифровать древнюю надпись, например из раскопок.
И в если в эта надпись на неизвестном языке. Не известен ни один символ языка.
Такое скорее всего невозможно.
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
31.01.2017, 18:24 11
Цитата Сообщение от vvm28 Посмотреть сообщение
Обозначить сферу по другому
Об этом уже говорилось в #7. В теории, вы можете указать генератор фрактала и процедуру его построения. Для алгоримов сжатия с потерями (аппроксимацией) есть успешные примеры - порядка 500:1. Для обратимого (без потерь) процесса работающих методов не найдено.

Что касается языков, в некоторых случаях успехи весьма велики (расшифровка египетских иероглифов), в других - тупик (манускрипт Войнича).
0
96 / 23 / 20
Регистрация: 17.09.2014
Сообщений: 1,322
31.01.2017, 21:30  [ТС] 12
Цитата Сообщение от SoftIce Посмотреть сообщение
В 5 утра женщины должны сниться, а не алгоритмы сжатия
Животные инстинкты только мешают просветлению разума. )

Но с другой стороны - для чего вообще существовать, если ты всё знаешь, не к чему стремиться, нет удовольствия и прочих ощущений...
0
627 / 134 / 46
Регистрация: 22.12.2013
Сообщений: 1,123
Записей в блоге: 19
02.02.2017, 13:43 13
Цитата Сообщение от gazlan Посмотреть сообщение
"Сжать" можно только что-то асимметричное.
Смотря что мы "сжимаем".
Мы работаем не с геометрией, а с числами.
Нулевое измерение 0.
Одномерное измерение константы.
Двумерное измерение - числа по основанию 2
Десяти мерное измерение - числа по основанию 10.

Сферу тоже можно повернуть. Распилить на две части, две эти части сложить в одну. Повернуть и склеить.
Но в четвертом измерении скорее всего сферу можно повернуть без распиливания.
Но в числах нет четверного измерения и даже третьего нет.

Добавлено через 8 минут
Числа с которыми работают в десятичной системе - это не десятичная система.
Это десятичная система + ноль. Даже скорее всего: ноль + конечные константы+ бесконечные константы

Добавлено через 28 минут
Ценность быстрого алгоритма сжатия и передачи данных очень высока.
Если его найти, то можно будет пересмотреть протокол TCP/IP и сделать его быстрее.
Тогда скорость интернета возрастет значительно.

Добавлено через 4 часа 17 минут
И еще : что мешает получить максимально сжатие?
Ноль, это не ноль в микросхеме памяти - это отсутствие напряжения(не всегда так).
Один - это не один в микросхеме памяти - это присутствие напряжения.
Между ноль и один 0.5 - это ноль или один? Ладно пусть более точно 0.4999999999999999999999999999999999999999999
это ноль или один? На обработку такой ошибки программе нужно будет потратить время. То есть время тратится на решение не однозначности. Программа не должна входить в ступор из-за неопределенности.
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
02.02.2017, 17:12 14
Софистика. Вы жонглируете словами, за которыми нет смысла.
  • Число измерений - это вопрос точки зрения (точнее токенизации, лексического разбора). Лексер как угодно может блокировать символы в группы, произвольно меняя число измерений (в пределах реального числа степеней свободы). Причем, блок не обязан иметь фиксированный размер и во многих алгоритмах он выбирается адаптивно.
  • Сферу нет нужды "пилить" - достаточно смять. Речь, разумеется, идет о шаре (в общем случае, о фрактале и достижении предельной плотности - Энтропийный предел).
  • Система счисления, как уже сказано, это вопрос представления. Компрессор строит ее самостоятельно.
  • Скорость работы обменивается на размер памяти - Золотое правило механики. Рычаг Архимеда еще никому обойти не удавалось.
  • О предельном сжатии я уже писал, просто чтобы было под рукой, процитирую еще раз:

Энтропийный предел
Зайду с другой масти.

Оперируя (общепринятым) термином "избыточность", можно сказать, что сжатие -
это устранение избыточности. Условно, - "очистка" продукта от примеси.

Рассмотрим, к примеру, очистку от примесей золота.

Предположим, вы владелец небольшого аффинажного компрессора и принимаете в
переработку файлы с содержанием продукта 37.5% (текстовые) и 58.3% (двоичные),
получая на выходе сжатый продукт - 90.0% чистого вещества - так же, как и
большинство остальных присутствующих на рынке.

Как человека творческого, 90.0% вас не устраивают и вы создаете
суперкомпрессор Миллера, поднимающий степень сжатия с жалких 90.0% до вполне
приемлемых 99.95%.

Так вот, если вам не жалко времени и денег, то, возможно, вы сможете улучшить
степень очистки еше на "пару девяток" - до 99.9995%, но очевидно, что никакими
ухищрениями невозможно добиться более чем 100% содержания продукта.

"Энтропийный предел" - это и есть 100% содержание (эксцентриситет e = 1).
Никакая дальнейшая "очистка" (сжатие) невозможны.
0
627 / 134 / 46
Регистрация: 22.12.2013
Сообщений: 1,123
Записей в блоге: 19
02.02.2017, 19:03 15
Цитата Сообщение от gazlan Посмотреть сообщение
Софистика. Вы жонглируете словами, за которыми нет смысла.
Это не софистика, а попытка взглянуть на проблему с разных сторон. Посмотрев с различных сторон, можно увидеть
ошибки предыдущих взглядов.
Ну например если считать что "сжатие" - это поворот, то поворот прямоугольника в трехмерном пространстве превращает
его в отрезок. На следующем его повороте в трехмерном пространстве мы запоминаем, что это был прямоугольник и поворачивая отрезок превращаем его в точку. Два поворота для плоской фигуры.

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

Добавлено через 9 минут
Мир который мы видим перед собой в видимом спектре диапазона псевдотрехмерен в нашем воображении.
Два глаза человека видят два плоских(полусферических) изображения и проецируют в одно.
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
02.02.2017, 20:33 16
Именно, софистика.

Ваш трехмерный мир - игра в песочнице. Мегабайт текста имеет миллион координатных осей и, в общем случае (литературный текст) порядка 200,000 степеней свободы (независимых обобщенных координат). Задачи компрессора: 1. найти эти оси и 2. "примять углы", так чтобы среднее расстояние от барицентра до вершины для всех осей было примерно одинаково (рассматривайте это как процесс многомерной шлифовки: выступы срываются, впадины засыпаются).

Сдвиг и Поворот - это упрощенная двумерная аналогия, речь идет о многомерной деформации, инвариант которой - энтропия фрактала.

Представьте, например, конденсацию пара в жидкость - тот несжимаемый объем, в который, в конечном итоге, превратится паровой фрактал, и есть энтропия.
0
96 / 23 / 20
Регистрация: 17.09.2014
Сообщений: 1,322
02.02.2017, 22:18  [ТС] 17
Операционная система на 3м счислении была уже давно придумана, вроде в россии, и работала быстрее...

Если сжать хотя бы 3 байта в 2 - это уже будет круто.

Байт(всегда число) как всем тут известно имеет диапазон 0-255 и 8 бит(всегда 0 или 1).
Просто я как ни крутил, зашифровать(сжать точнее) число в само себя не получается.
Т.е. можно брать 24 бита и зашифровывать их в 16 битах.

Например 1й бит в зашифрованном виде может говорить не является ли 1 байт 0м, 2й бит - для 2го байта, 3й - для 3го.
Дальше идет некая последовательность оперирования числами, если присутствует в 3х байтах 0, то оставшиеся 13 байт применяются для 2х.
Если нет нолей тогда уже делятся на 3 байта, и каким-то образом шифруются.

Это так, приблизительная схема, как я пытался сделать.
Только я 2к1 пробовал, и понял, что это невозможно, даже не обладая средними знаниями математики.
0
627 / 134 / 46
Регистрация: 22.12.2013
Сообщений: 1,123
Записей в блоге: 19
03.02.2017, 11:28 18
Цитата Сообщение от артист Посмотреть сообщение
Байт(всегда число) как всем тут известно имеет диапазон 0-255 и 8 бит(всегда 0 или 1).
Байт - это условность. Не на всех машинах байт = 8 бит.Из вики:
Из вики: "Однако в истории компьютерной техники существовали решения с иными размерами байта (например, 6, 32 или 36 битов)". И не только с этим количеством, были еще 7 бит.
Алгоритм упирается в принятую систему исчисления.
Если "разворачивать" число в другой системе исчисления и возвращать его обратно, то оно вернется с потерями?
Не использовать для вычислений XOR, а использовать только NOT и CNOT.
Да и для начала нужно четко определить , что такое сжатие? Что мы собираемся "сжимать"?

Добавлено через 1 минуту
Число - это по сути частично реализованная абстракция.

Добавлено через 1 час 28 минут
Null, 1,2,3,4,5,6,7,8,9, Десять(тут нет никакого перехода через 0)
0
96 / 23 / 20
Регистрация: 17.09.2014
Сообщений: 1,322
03.02.2017, 18:45  [ТС] 19
Сжимать размер нулей и единиц естественно.

Можно брать хоть по 9 бит(просто диапазон будет больше, 0-510) или по 4(диапазон 0-15), главное и неизменное - это 0 и 1, а данные, это просто поток.
Просто если брать нестандартную длину, то нужно будет кроме шифровки ещё и длину данных запаковывать...
Хотя и так, если сжатие будет 4 к 3, то уже длина данных не всегда будет делиться ровно на 4...

Добавлено через 17 минут
Сам не знаю для чего нужно представлять данные в виде чисел(просто в двоичном виде уже есть алгоритмы, и они просто на повторы идут), с числами удобнее работать.
Подумал так, и в итоге получается нужно придумать иную систему, которая будет короче всё это делать.

Например вот взять те же числа, 0 записывается в виде восьми нулей(допустим байт == 8 бит).
А мог бы записываться 1м байтом, просто 0.
Так же например 3 - это 6 нулей и 2 единицы в конце, а можно записать его как 2 единицы.
Т.е. отбрасывание нулей слева.
Но в таком случае, как понять где концается одно число, и начинается другое?
Разделителем, например 2 нуля, раз нолей может быть только 1.
Много конечно таким образом не сожмёшь, да и сжатие данных может быть только 1 раз, как и с повторяющимися битами...
И скорее всего такой алгоритм тоже уже давно придуман
0
627 / 134 / 46
Регистрация: 22.12.2013
Сообщений: 1,123
Записей в блоге: 19
04.02.2017, 06:08 20
Алгоритм скорее всего придуман. Но не обязательно.
Вопрос - как упаковать если у нас осталось 0 1 или 1 0. Пусть при этом 0 изобразим как круг а один как квадрат.
так мы выходим за рамки двоичного измерения. 0 1 будет у нас фигура квадрат в окружности, а 1 0 окружность в квадрате. Так мы вроде упаковали два в одно, без потери информации.

Добавлено через 11 минут
Но нам понадобилось для этого дополнительная информация - то что это окружность,a это квадрат.
И еще понадобилось знать окружность в квадрате или квадрат в окружности.
B в какой-то момент нам опять нужно эту информацию где-то хранить.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.02.2017, 06:08

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Алгоритм сжатия Jpeg
У кого ни будь есть готовый Алгоритм сжатия Jpeg? Хотя бы самый простой без задания качества итд....

Алгоритм сжатия аудио !
Нужна реализация алгоритма Райса для сжатия аудио файлов на С++ (наличие коментов приветствуется)....

Алгоритм сжатия RLE
Здравствуйте, очень нужна помощь в задании! Просто очень срочно, пожалуйста! Написать программу...

Алгоритм сжатия Хаффмана
Мне нужно реализовать сжатие текста алгоритмом Хаффмана. Я нашел неплохой исходник, но там...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.