Троичный код в сжатии двоичных данных

[Shaos]

Данных недостаков нету в предложенном на trinary.ru алгоритме.
К тому же он достаточно эффективен (степень сжатия 66,7%, т.е в 1,5 раза), не зависит от контекста, высокопроизводителен (поточное кодирование-декодирование по таблицам).

Какие будут соображения?

Сжатия в 1.5 раза там нету. Если брать что-то за основу для сравнения, то надо брать троичное представление байтов - 6 тритов на байт (8 бит) - или 1.333(3) битов на трит. В этом случае твоё "Кодирующее Устройство ¹3" (делающее из 3 битов 2 трита или 1.5 бита на трит или 1 трайт из 9 битов или каждые 9 байтов будут превращены в 8 6-тритных трайтов) даст выигрышь 11% и только лишь засчёт того, что байт напрямую в троичное представление не перевести, что добавляет избыточность в наше первоначальное представление.

[Mac Buster]

Данных недостаков нету в предложенном на trinary.ru алгоритме. К тому же он достаточно эффективен (степень сжатия 66,7%, т.е в 1,5 раза), не зависит от контекста, высокопроизводителен (поточное кодирование-декодирование по таблицам).

Есть предложение опубликовать здесь полное описание алгоритма.

[Alexandr]

Данных недостаков нету в предложенном на trinary.ru алгоритме.
К тому же он достаточно эффективен (степень сжатия 66,7%, т.е в 1,5 раза), не зависит от контекста, высокопроизводителен (поточное кодирование-декодирование по таблицам).

Какие будут соображения?

Сжатия в 1.5 раза там нету.

Странно... было 3 бита стало 2 трита, то есть количество разрядов уменьшилось в 1,5 раза.
Кстати, ты сам это и подтверждаешь:

делающее из 3 битов 2 трита или 1.5 бита на трит

Если брать что-то за основу для сравнения, то надо брать троичное представление байтов - 6 тритов на байт (8 бит) - или 1.333(3) битов на трит. В этом случае твоё "Кодирующее Устройство ¹3" (делающее из 3 битов 2 трита или 1.5 бита на трит или 1 трайт из 9 битов или каждые 9 байтов будут превращены в 8 6-тритных трайтов) даст выигрышь 11% и только лишь засчёт того, что байт напрямую в троичное представление не перевести, что добавляет избыточность в наше первоначальное представление.

В алгоритме речь идёт про преобразование двоичных данных (потока бит) в троичные (потока трит). Но нигде не сказано что идёт преобразование байтов, а тем более символов, то есть,

Если брать что-то за основу для сравнения, то надо брать троичное представление байтов - 6 тритов на байт (8 бит) - или 1.333(3) битов на трит.

рассматривать исходный поток в виде байтов, а полученный поток в виде трайтов будет некорректно, так как идёт преобразование битов в триты. И надо заметить что в алгоритме представлены 3 варианта кодирования с разной степенью сжатия, в которых разное соотвествие битов тритам: 3 бита в 2 трита, 84 бита в 53 трита, 569 бит в 359 трит.

[Alexandr]

Данных недостаков нету в предложенном на trinary.ru алгоритме. К тому же он достаточно эффективен (степень сжатия 66,7%, т.е в 1,5 раза), не зависит от контекста, высокопроизводителен (поточное кодирование-декодирование по таблицам).

Есть предложение опубликовать здесь полное описание алгоритма.

Добавлено описание.

Исходный двоичный поток битов преобразуется в троичный поток тритов в соотвествии с таблицами преобразований (например: 000 = --; 001 = -0; 010 = -+). Так существует 3 варианта кодирования, когда каждые 3 бита преобразуются в 2 трита, когда 84 бита в 53 трита или 569 бит в 359 трит.

[Shaos]

Сжатия в 1.5 раза там нету.

Странно... было 3 бита стало 2 трита, то есть количество разрядов уменьшилось в 1,5 раза.

Nu togda ya s hodu mogu predlozhit "szhatie v 7 raz" - zamenyaem kazhdie 7 bit na 1 ASCII-symvol

Esche raz - ETO NE SZHATIE...

[Alexandr]

Nu togda ya s hodu mogu predlozhit "szhatie v 7 raz" - zamenyaem kazhdie 7 bit na 1 ASCII-symvol

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

Что же касается:

zamenyaem kazhdie 7 bit na 1 ASCII-symvol

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

Esche raz - ETO NE SZHATIE...

Ещё раз:

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

Что в алгоритме:
1. Были 0,1
2. Перенесли на троичную платформу, получили 0,+
3. Перекодировали данные, использовав третье состояние
4. Получили 0,+,-
5. Количество используемых разрядов сократилось

[Shaos]

Приведу определение сжатия данных с википедии:

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

Сначала про "Кодирующее Устройство ¹3" - в твоём случае объём данных НЕ уменьшается, а наоборот увеличивается. Сравнивать количество битов с количеством тритов на равных в общем случае неверно (вспоминаем детский мультик про то что удав в попугаях гораздо длиннее чем в слонёнках - один трит на самом деле это ln(3)/ln(2)=1,5849625007211561814537389439478 битов, т.е. если ты представляешь каждые три бита двумя тритами (что есть тоже самое что и 2*1.585=3.17 битов) то объём данных УВЕЛИЧИВАЕТСЯ в 3.17/3=1.057 раз или на 5.7% - так что это не сжатие, а "раздутие" данных

На самом деле этот алгоритим вполне можно использовать для быстрого преобразования последовательности битов в последовательность тритов, но без употребления термина "сжатие" ибо это не тот случай...

Что же касается сабжа - это "сжатие" только для очень небольшого количества входных данных из всех возможных, а именно данных с кодами от 0 до 2^((8/1.585-1)*1.585)=85. Превратить это в реальное сжатие можно путём учёта частоты появления символов в сообщении и замены наиболее часто встречающихся символов на более короткое представление - причём это всё можно просчитать на двоичном компьютере и передать на троичный через вышеобозначенное преобразование с разделением символов через -1. Однако троичный Хаффман этот алгоритм победит не глядя

[Alexandr]

Больше не вижу смысла спорить. Остаюсь при своём, чего и вам желаю

[Mac Buster]

Продолжим рассмотрение способов сжатия. Обратимся с алгоритму сжатия повторяющихся последовательностей - RLE. Рассмотрим основной принцип этого алгоритма на следующем примере.
Пусть имеется некоторая дискретная последовательность данных, в которой встречаются повторяющиеся последовательности. Например:

АБВАААГДЕЕЕЕЕЖЗ

Как видно, в последовательности присутствуют фрагменты, в которых есть серии из одинаковых стоящих рядом символов. Сжатие повторяющихся последовательностей предполагает замену таких серий фрагментами состоящими из двух частей: счётчика повторений СП и повторяемого значения ПЗ, причём если повторяющихся серия нет, то исходный не входящий в серию символ, остается неизменным. То есть, в нашем случае после сжатия последовательность преобразуется в следующую:

АБВ[3:А]ГД[5:Е]ЖЗ

Здесь в квадратных скобках приведены сжатые серии повторяющихся символов, где сначала стоит счётчик повторений (СП), затем, после двоеточия, сам символ, который необходимо повторить указанное количество раз (ПЗ). При восстановлении исходной последовательности читают сжатый поток, встретив признак серии чтение приостанавливается и в выходной поток записывается столько символов, сколько указано в счётчике повторений, затем чтение сжатой последовательности продолжается. На этом описание алгоритма завершается.
Очевидный недостаток этого алгоритма заключается в том, что после сжатия при необходимости восстановлении во время чтения сжатых данных надо каким-то образом отличать несжатый исходный символ и фрагмент показывающий что в ней заключается повторяющаяся серия. Для этого требуется ввести некоторый признак. Существует множество реализаций RLE, в каждом из которых есть свой способ формирования признака. Один из наиболее известных заключается в предварительном выделении наиболее редко повторяющегося символа, код которого при сжатии будет использоваться как признак начала сжатой серии. Сам этот символ записывается как серия состоящая из количества повторений равного 1 и самого этого символа.

[Shaos]

тут тоже можно -1 применить - например -1,-1 (два раза -1) будет означать признак того, что далее идёт размер и повторяющийся символ (разделённые -1 с отбрасыванием младших нулевых двоичных разрядов)...

[Mac Buster]

тут тоже можно -1 применить - например -1,-1 (два раза -1) будет означать признак того, что далее идёт размер и повторяющийся символ (разделённые -1 с отбрасыванием младших нулевых двоичных разрядов)...

Да, верно, можно поступить так:

- если в сжатом потоке встретился -1 - признак сжатой серии, значит за ним идёт уплотнённое значение счётчика повторений, так же завершающееся разрядом -1. После чего идут 8 разрядов представления повторяемого символа. Это даст возможность делать количество повторений фактически произвольным, при фиксированной разрядности повторяемого значения;

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

АБВАБВАБВАБВАБВАБВ

будет сжат в [6:АБВ].

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

[Mac Buster]

Можно также объединить уплотнение и RLE в одном методе следующим образом:

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

Соответственно, при восстановлении учитываем такой случай и при чтении из сжатого потока признака серии с однократным повторением (чего в общем случае, при сжатии обычным RLE, быть не должно), считаем что за счётчиком повторений следуют уплотнённые данные с указанной длиной.

На словах получилось несколько громоздко

[Mac Buster]

В резерве остаётся ещё один исключительный случай - признак серии с нулевым значением счётчика повторений.

[Mac Buster]

Можем сделать вот что:

- считать что нулевой счётчик - это указатель на сжатие серии байт;

- считать что единичный счётчик - это указатель на сжатие серий разрядов;

[Mac Buster]

Дальше будем рассматривать остальные блочные методы сжатия (LZ и прочие).