Обсуждение:Сжатие без потерь
 | Эта страница была предложена к объединению со страницей Сжатие звука без потерь. В результате обсуждения было решено страницы не объединять.
Аргументы и итог обсуждения доступен на странице Википедия:К объединению/10 августа 2010. Для повторного выставления статьи к объединению нужны веские основания, иначе такое действие будет нарушать правила. |
 | Эта статья была предложена к переименованию в Сжатие данных без потерь 14 марта 2020 года. В результате обсуждения было решено оставить название Сжатие без потерь без изменений. Для повторного выставления статьи на переименование нужны веские основания, иначе это может быть расценено как игра с правилами (см. пункт 8). |
Проект «Информационные технологии» (уровень III, важность для проекта средняя)
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Сжатие видео
H.264/MPEG-4 AVC
убрать пункт, это алгоритм сжатия с потерями! (или указать с оговоркой при каком битрейте достигается истинное сжатие без потерь) 80.237.97.253 23:27, 16 сентября 2008 (UTC)Paprika
Из комбинаторики следует, что нет алгоритма сжатия без потерь, способного уменьшить хотя бы на байт любой файл[источник не указан 24 дня].
уберите [источник не указан], думаю источник не нужен, это и так понятно. Тем более ссылка на комбинаторику есть. --91.76.86.139 12:27, 30 октября 2009 (UTC)
Рекурсивное сжатие без потерь. Пути развития и оптимизации алгоритмов.
правитьВ этой теме, мы обсудим пути развития и оптимизации алгоритмов сжатия без потерь, а также возможность реализации рекурсивного сжатия, которое потенцильно реализуемо, посредством снижения информационной энтропии. Внимание. Желательно прочитать код статьи, так как разметка искажена. Нажмите кнопку "Править код", чтобы увидеть код.
Очевидно, что невозможно гарантинованно сжать без потерь, случайные двоичные данные, длиной N бит, так как пространство их значений находится в диапазоне от 0 до 2^N-1, а пространство значений меньшей битности в диапазоне от 0 до 2^(N-1-k), где k - разница, в битах.
Применяя различные методы энтропийного кодирования https://ru.wiki.x.io/wiki/Энтропийное_кодирование можно добиться сжатия некоторых данных, в данные меньшей битности. Но не всех, а только СЖИМАЕМЫХ ДАННЫХ - данных, с низкой информационной энтропией Шеннона: https://ru.wiki.x.io/wiki/Информационная_энтропия Предел сжатия устанавливает Теорема Шеннона о источнике шифрования: https://ru.wiki.x.io/wiki/Теорема_Шеннона_об_источнике_шифрования При сжатии методами энтропийного кодирования, из низкоэнтропийных данных получаются данные с высокой информационной энтропией, то есть - НЕСЖИМАЕМЫЕ ДАННЫЕ.
Что такое НЕСЖИМАЕМЫЕ ДАННЫЕ? Это данные, с максимальной информационной энтропией Шеннона. То есть, данные, в которых количество единичных бит равно или примерно равно количеству бит нулевых. Несжимаемыми данными могут быть как исходные данные, так и случайные/зашифрованные данные, в которых вероятность появления единичного бита, равна или примерно равна вероятности появления бита - нулевого.
В пространстве значений от 0 до 2^N-1, где N - количество бит блока данных, уже содержатся НЕСЖИМАЕМЫЕ ДАННЫЕ.
Рассмотрим все значения нибла (полубайта) и подсчитаем количества единичных бит в них. Сразу же, отсортируем эти значения и количества единиц в них - по количеству единичных бит: 0000 - 0 0001 - 1 0010 - 1 0100 - 1 1000 - 1 0011 - 2 - несжимаемые данные 0101 - 2 - несжимаемые данные 0110 - 2 - несжимаемые данные 1001 - 2 - несжимаемые данные 1010 - 2 - несжимаемые данные 1100 - 2 - несжимаемые данные 0111 - 3 1011 - 3 1101 - 3 1110 - 3 1111 - 4 Очевидно, что значения, содержащие количество единичных бит, равное 0, 1, 3 и 4, соответственно - представляют из себя СЖИМАЕМЫЕ ДАННЫЕ, так как информационная энтропия этих двоичных данных - менее 50%. Более того, при применении операции негации к этим значениям ( https://ru.wiki.x.io/wiki/Отрицание ), числа содержащие 4 и 3 единицы - переходят в числа содержащие 0 и 1 единиц соответственно. Несжимаемые данные, же, после негации их - переходят в другие несжимаемые данные, и остаются НЕСЖИМАЕМЫМИ.
Заметим, что количество несжимаемых данных в полубайте (ниббл), равняется шести, и ровно шесть значений содержат две единицы и два нуля. Остальные значения, даже если они будут повторяться в данных - можно сжать, так как при частом повторении их, при помощи того же префиксного кодирования, в один бит могут быть сжаты либо "два нуля", либо "две единицы".
Из вышеуказанной таблицы, очевидно, что НЕСЖИМАЕМЫЕ ДАННЫЕ - это натуральные числа, биты в которых распределены, по биномиальному распределению: https://ru.wiki.x.io/wiki/Биномиальное_распределение
Их количество в блоке данных, длиной N бит, представляет из себя последовательность: https://oeis.org/A210736 >Expansion of (1 + sqrt( (1 + 2*x) / (1 - 2*x))) / 2 in powers of x. Этих значений в диапазоне 0 до 2^N-1, ровно вот столько: https://oeis.org/A210736/b210736.txt в зависимости от битовой длины N у блока двоичных данных.
Что с ними делать? Как их сжать? Очевидно, то, что чтобы эти НЕСЖИМАЕМЫЕ ДАННЫЕ, таки-сжать, нужно просто, каким-то образом, обратимо - ИЗМЕНИТЬ ИХ ИНФОРМАЦИОННУЮ ЭНТРОПИЮ, то либо снизить, либо повысить количество единичных бит, относительно количества бит - нулевых.
Тогда, быть может, применяя различные комплексные методы, такие как преобразование Барроуза-Уилера: https://ru.wiki.x.io/wiki/Преобразование_Барроуза_—_Уилера с последующим префиксным кодированием: https://ru.wiki.x.io/wiki/Префиксный_код таки-возможно будет - реализовать многораундовое рекурсивное сжатие.
Хотелось бы предложить, в качестве метода снижения энтропии - следующий алгоритм: Берём и принимаем на вход - исходную битовую строку, читаем её побитово, и пишем вторую строку - выходную: если бит исходной строки изменился, то бит выходной - 1, иначе, если не изменился то 0. На выходе - образуется другая бинарная строка. Преобразование может быть поточным. Обратное восстановление исходной стрки - обратно: Если на входе бит 1, то бит изменился, иначе - не изменился, и вписать предыдущий.
В результате экспериментов, удалось выявить следующую закономерность: Последовательность вышеописанных преобразований (выходная строка преобразуется ещё раз в выход2, выход2 в выход3, и т. д.) - эта последовательность зацикливается, выдавая изначальную двоичную строку - за количество шагов, равное 2^x-1, где x - некое число. При этом, в списке значений, образуются данные либо с наибольшим, либо с наименьшим количеством единичных бит, а значит изменяется информационная энтропия.
Дальше уже, эти данные можно подвергнуть негации, их можно пропустить через преобразование Барроуза-Уиллера, чтобы повысить сжимаемость их, и конечно же - пожать префиксным кодированием.
Возможно, вышеописанные дейстия удасться зациклить рекурсивно, позволяя неограниченно сжать огромные объёмы Big Data: https://ru.wiki.x.io/wiki/Большие_данные
Всего хорошего, Аноним.
109.200.246.96 00:52, 15 января 2020 (UTC)