nedoPC.org

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

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

Другое дело хранение двоичного кода на троичной платформе.
Здесь и алгоритмы работают эффективнее (например Кодирующее устройство ¹2 реализует алгоритм кодирования по Хаффману) и простое прямое преобразование уменьшает количество кодов в 1,5 раза (Кодирующее устройство ¹3)

Да, речь идёт о сжатии двоичных данных при их хранении в троичной памяти. Я подразумеваю, что данные были перенесены 1 к 1, то есть двоичный 0 это троичный 0, двоичная 1, это троичная +1. Состояние -1 не используется, количество разрядов в двоичном и троичном представлениях одинаково.

Если переносить 1 к 1, то в чём кодирование?

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

Самым простым и очевидным применением троичного кода в сжатии двоичных данных мне представляется идея использования доступного третьего состояния для разделения неких фрагментов в исходных двоичных (несжатых) данных.

Использовать этот вариант (-1 как разделитель) можно несколькими способами.

1) Уплотнение двоичного кода
2) Сжатие последовательностей
3) Сжатие повторяющихся фрагментов

Пример можно какой-нибудь?
Вот есть у нас некая последовательность битов:
110 100 001 001 001 000 100 000 (24 бита)
которые запросто закодировать по алгоритму предложенному на trinary.ru
в такую послдовательность троичного кода:
+- 00 -0 -0 -0 -- 00 -- (16 трит)
Что сократило объём в 1,5 раза.

Как будет выглядить кодирование с использованием разделителей?

Это зависит от конкретной реализации.

1) Уплотнение двоичного кода

Рассмотрев исходные данные в их естественном представлении (например, в качестве последовательности байт), можно заметить, что в большинстве случаев в байтах хранится некоторое десятичное число, чьё двоичное представление оставляет свободными (нулевыми) один или несколько старших разрядов в байте. Можно сократить количество используемых элементарных разрядов (в нашем случае тритов) "уплотнив" последовательность. То есть мы будем брать каждые 8 разрядов и рассматривать каждый "байт", определяя есть ли в нем незадействованные разряды. Если они есть, то на место самого младшего из них будем ставить -1, после чего будем записывать получившееся число в принимающий буфер, адресуемый потритно. Соответственно, если незадействованных разрядов не обнаружено, нам придётся добавлять к исходному числу ещё один разряд, чтобы впоследствии, при восстановлении исходного потока можно было понять, где заканчивается очередной фрагмент. Такой способ позволит нам сократить исходные нулевые байты до 1 трита. Но не даст большого выигрыша на последовательностях в которых присутствует большое количество величин по значению превышающих 64. Однако можно рассматривать исходные данные не как байты, а как 12-, 16-, 24- и 32-разрядные слова, либо провести предварительный анализ данных и выбрать такую разрядность, при которой использование такого подхода будет наиболее эффективным. Может создаться впечатление, что можно уменьшить сокращённую троичную запись ещё минимум на один разряд заменяя на -1 не первый свободный 0, а самую старшую 1. Однако в этом случае мы не сможем записать исходное нулевое значение, т.к. в нем нет ни одной 1.

Дополнение: можно не добавлять -1 после 8-го разряда исходного байта, если в нем нет неиспользуемых разрядов. Тогда во время распаковки при чтении сжатых данных 8 разрядов не содержащих -1 надо рассматривать как "несжатый" исходный байт.

Ну что ж,
в каждом байте вместо ведущих нулей ставим -
тоесть если было
00000011
стало
-++
то есть сэкономили 5 разрядов,
по данному алгоритму на реальных данных получается уменьшение кодов в 1,05(текстовые данные) 1,31(двоичые данные) раза.

Это пока ещё не сжатие, а просто предварительная обработка, подготавливающая данные к сжатию.

Это, кстати, не требуется.

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

P.S. Добавил этот случай в опубликованное описание.

Надо отметить что данный алгоритм не отличается высокой эффективностью и сильно зависит от контекста:
смотрим ASCII, всего 63 из 256 симолов позволяют получить выгоду.
К тому же сильно требователен к вычислительной мощности, особенно при декодировании: так как, в случаях, когда идут подряд некодированные байты (т.е. те, что без ведущих 0 были) потребуется читать до первых кодированных (те, у которых в начале будет "-") или до конца потока.

Данных недостаков нету в предложенном на trinary.ru алгоритме.

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

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

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