Четыре алгоритма лучше чем код Хаффмана
Немного истории.
после Пи-кодирования Rar не сжал текст лучше чем в 2 раза как я надеялся..
пришлось думать как бы еще сжать. При пи-кодировании слова заменяются
на их номер в словаре, поэтому частота встречи слова в тексте не такая как
частота букв и похожих блоков меньше, первая идея была убирать самые частые,
через адресные ряды - ищем все адреса этого символа и пакуем этот ряд,
а из общего массива убираем. Потом выснилось: начинать надо с редких,
а последний частый - это просто повторение Min - кодируется двумя числами,
и наконец, что надо не символы, а блоки искать, сначала самые длинные с редких
к частым, потом короче и в конце по одному числу. но дело это долгое..
Так вот адресный ряд rar вообще отказался сжимать, 256 чисел 0..3000 сжал
в 400+ байт, а у меня уже тогда был формат p78 который тоже самое сжал в 386!.
Формат простейший 7 бит +1 бит флаг продолжения +8 бит. Числа меньше 128
занимают 1 байт, а 128..32к+128 2 байта. Это был мой первый безразмерный
формат. (а самый последний метод сжал эти 256 чисел в 296 байт)
В чем же секрет? В том, что для слабоповторных рядов все используют коды Хаффмана,
и ими убирают экспонециальность в информационных рядах. Долгое время считалось
что это вершина минимизации избыточности, но тут появился я и доказал что
уже существует 4 метода которые это делают намного лучше.. :)
Xing Soft 2015(с)
при перепечатке ссылка на первоисточник обязательна.
Где-то возможны повторения - писал долго и кусками.
Обозначения в этой научной статье. (могут отличаться от общепрятых)
Контрольный ряд - 256 чисел от 3 до 2980 - (это отн. адреса i-слова в тексте из
70+ тыс слов, рар/зип его сжал в 412, арифм кодер в 391, мой метод3 в 298)
Информационный ряд чисел - (инфо-ряд) массив чисел, с экп. распределением
значений, если его отсортировать, то график - экпонента (геометрич. прогресия)
Цепочка - массив 16 битных чисел.
Комбо - упаковка ряда чисел от 0 до M-1 размером N=M. частота всех чисел = 1.
например 50261734 пакуется в 8! (длинное целое число от 0 до 8!-1)
Это множество - перестановка (побробней см. комбинаторика Ньютона,Эйлера)
Комби - упаковка ряда чисел от 0 до M-1 без пропусков где числа могут повторяться,
это мультимножество. Его можно преобразовать в цикл перестановки (ЦиклоП).
и разложить на множество мелких комбо-циклопиков, которые иногда лучше LZ77
и вместо таблицы частот надо хранить длины и начала нес-х микро-комбо.
но если хранить таблицу частот то для нее можно тупо пронумировать все возможные
комбинации и это будет длинное целое число комби. восстановление однозначное,
но восстановить по СДЧ перестановку не так просто и долго.
256-блок - инфо-ряд размером 256 (обычно 12 битные числа)
3+ -числа от 3х и больше (до максимума)
Бит-поле/полоса - массив битов. числа только 0 или 1
Бит-ёмкость числа - сколько бит занимает число. "65" занимает 7 битов.
Битовая полоса - бит поле флагов шириной 1 бит, длина=длине массива
осн - основание системы исчисления
5(9) - число 5 по осн 9
Объём ёмкости - для 8 бит - объем 256 - сколько чисел влазит в эту ёмкость.
Плотность ёмкости - уровень заполнения объёма числами (8бит 0-255)(средний/макс)
СуперДлинное число(СДЧ) - цепочка байт из битов числа от длинной арифметики.
(числа длиной больше 256 бит использовать нежелательно - считает долго)
упаковка в СДЧ - умножение СДЧ на осн + число, где осн > числа
БРЧ - безразмерные числа из метода 4.
допустим идет сжатие по 256 блокам. а инфо-ряд можно разложить на табл. значений
и перестановку мультимножества, если блоков мало, то это не выгодно, а если много
и частоты блоков и таблицы значений почти совпадают, то можно хранить разницу
между ними - тогда это уже выгодно. а перестановки каждого блока пакуем в комби,
или в БРЧ если повторов мелочи сильно больше и график значений с изгибом.
Про неравномерности. Лучше пройтись скользящим окном и посчитать средний и
частоты, если различие больше 10% и редко, то разбить на куски и сжать разными
методами, если разность частая, то сжимать кусками по 256/512/1024 байт.
Почему проиграло кодирование слов?
потому что словарь соответствия (слово=номер)
включали в заголовок архива и его размер превышал выигрыш.
а использование общего единого словаря 1)требовало чтобы у всех он был.
(но его можно как часть архиватора сделать)
2)номера получались с промежутками - а это ни один алгоритм, кроме моих
не может сжать эффективно - нужна таблица перекодировки в сплошной ряд чисел
без пропусков, тогда адаптивный арифметик сожмет с учетом рейтинга слова,
но таблица перекодировки тоже место занимает, хотя поменьше чем весь словарь
соотвествия. Так что выигрыш получался мизер и про это забыли..
Почему проигрывает PPMd?
потому что он думает что все числа это байты от 0 до 255
но это не так, в обычных текстах, больше 100 символов не используются
а иногда не больше 40..
и если заменить пропущеные символы - самыми частыми словами (сделать
микрословарь в заголовке) то небольшой выигрыш 3-7% будет.
Идеальное сжатие
оптимально надо переводить байты в биты+ 1+0..0 -это концовка.
конечный бит=1 в последнем байте это признак конца цепочки битов,
до конца заполняется нулями. длина_файла*8-длина_концовки=длина_цепочки_битов
дальше считаем кол-во 0 и 1 и для этого мультимножества есть число(СДЧ)
- номер этой комбинации для данных частот 0/1.
потом это число снова сжимаем пока выгодно. кол-во сжатий -первое число.
Запись чисел.(в формате р7*8) это 7 битные числа а в конце 8 битное.
кол-во_итераций, кол-во_нулей,кол-во_единиц, длина СДЧ. сама цепочка(СДЧ)
но нужна длинная арифметика - это долго. хотя можно использовать мат.сопроцессор,
и графич ускоритель(там тоже есть возможность). в идеале нужен сопроцессор сжатия
который будет аппаратно умножать 1024 битные числа. в нес-ко потоков.
Почему проигрывает арифметик?
если числа с пропусками и макс значение соизмеримо с длиной цепочки,
например 51 2 33 44 3 5, то на диапазон отводится больше места чем самих
чисел, можно сделать замену 51=1 33=4 44=6, но для таблицы значений часто
нужно места больше, и в итоге только хуже. Еще большинство арифметиков
настроены на байтовый вход и числа 0-255. Это неправильно, если найти максимум
и настроить макс_число_сиволов=макс+1, то результат будет лучше. Так же
выгодно находить минимум и вычитать из всех чисел. макс и мин - сохранять
в начале архива - обычно это выгодно. Символ "конец текста" иногда выгоднее
просто заменить размером цепочки - он тоже занимает место в Диапазоне(range),
а при мелких числах 0-5 это уже заметно. Для блочного или потокового входа
(мпег видео, интернет, сети) длина цепочки мала, а значения чисел соизмеримы
с ней, поэтому все классические методы энтропийного сжатия обычно хуже.
Но если файл есть целиком и данных много, то возможны варианты и комбинации:
сделать замену по значениям, убрать пропуски чисел и сжать арифметиком,
Но если числа 16 битные и малоповторные, график экспонента, а длина меньше
64к, то методы 1-4 - обычно лучше чем коды Хаффмана и др. алгоритмы.
Можно ими дожимать выходы других методов, выход гиф ппмд жмет в 1.5 раза
лучше чем родной код с переменной длиной - так что есть куда улучшать.
Арифметик расчитан на числа без пропусков, но в жизни они с пропусками и
экспотенциальные, но если разбить на участки по схеме:
массив-ведущие 0-размер емкости q1, 1-размер ёмкости q2 ,
2+ это коэф деления на ёмкость q3 минус ёмкости q1+q2 (туда не влезло)
дальше идут 3 массива с макс1 макс2 макс2 - сжимаем все 4 массива
арифметиком с макс знач для каждого свой. длину знаем. - символ конец
потока не нужен - тоже экономия диапазона.
лучше использовать битовое поле вместо массива байт-удобней.
и указывать точную длину: 2 байта 64кБит=8кБайт макс длина
Файл целиком качать по сети невыгодно - лучше сначала скачать начало,
распаковать и оставить на диске поврежденный, посмотреть что там реально,
может там спам какой - на файлообменниках всякое бывает, верить нельзя.
Поэтому 7z мертвый формат и интерфейс так себе, и выбирать самому надо,
много минусов, поэтому пока оптимальный это RAR и он распространен в РФ.
Далее рассматриваются только инфо-ряды: частые-мелкие, редкие-крупные,
значения чисел с пропусками, с частотами не больше 10 на 256 блок.
в отличие от кодов Хаффмана методы 1-4 имеют много вариантов и большой
выбор параметров - в зависимости от значений чисел, кривизны экспоненты,
и какую долю занимают нули (тогда методы с отсрочкой или разделение бит-полосой,
что фактически тоже самое) Линейные данные сжать можно при Max<N - можно попробовать апроксимировать прямой,
иногда сжать можно, если таблица поправок не сильно большая.
Для кучи частых чисел метод 3 хуже арифм. кодирования на 5%, остальные на 10+%,
если макс знач ряда меньше его длины то арифм кодирование лучше - но если
больше и мало повторов то арифм,lz* намного хуже. и даже rar/7z и прочие.
Метод 1. Метод максимальных выемок с рекурсией.
пусть даны числа: как видно из графика, их ёмкость это экпонента.
000000 если их хранить 6 бит/число то это 48_бит
000001 теперь ищем максимальную выемку нулей сверху слева
000001 это прямоугольники 4х5 5х4 6х3 макс=20
000001 теперь разделяем массив на 2 части битовой полосой
000010 половина чисел 1 бит *4 другая 6 бит *4 итого 28 бит+ 8 бит
000111 флаги и число 1(8) - экономия на 30%
001001 Далее продолжаем с этими половинками рекурсивные выемки
101101 пока это выгодно. Когда экп. приблизится к линии то служ.
информация будет больше экономии, тогда ставим флаг-конец деления и выход.
В реале используется не двоичная, а длинная арифметика, числа-разделители
входят в массив и запоминаются по осн(макс+1) + позиция, но можно запоминать
как уровень локализованной экпоненты F(макс,средний). Длины запоминать не надо
- это кол-во 0 или 1 от предыдущей бит-полосы, а длина первой всегда 256.
а выход LZW жмет лучше чем переменные коды в GIF на 10+%
Это брат близнец 2х каскадного метода - быстрее, но хуже. Но обоим нужны
малоповторные эксп. данные. где макс. соизмерим с длиной. С другими к PMD.
Метод 2. Метод с плавающими основаниями.
У каждой экпоненты есть линейный участок от 0 до 1/3 примерно,
который смело можно отделить и сжать по осн(макс1+1).
далее вычитаем макс1 из всех оставшихся чисел и применяем метод каскадного
деления(метод 3) одно или реже 2х каскадный(обычно выигрыш мизер)
эти 2 числа ищем методом перебора и поиска максимального сжатия.
эта функция имеет нес-ко минимумов и найти оптимальный быстро нельзя.
(но здесь используется обобщение, а сейчас нейронные сети достаточно
продвинулись и их можно использовать для поиска, прогноза и построения
статистических моделей в том числе)
этот метод показал 306 байт для контрольного ряда 256.
Бит-поле бывает выгодно упаковать в инфо-ряд и еще сжать методами 1-4
арифметик его тоже жмет неплохо, если разница частот "0" и "1" 30+%
Метод 3. Метод каскадного деления с отсеиванием.
на сегодня этот метод показал самые лучшие результаты (298_байт)
есть три разновидности: одно- 2х и многокаскадный.
Графически - это метод апроксимации экспоненты секущими с углом наклона
К1, К1*2, К1*3 итд. К1-это переломочное число.
это удивительно, но даже апроксимация полиномами Чебышева-Лежандра даёт,
больше служебной информации, хотя может кто нить придумает как уменьшить её.
к тому же есть Хана, Мейкснера, Кравчука и Шарлье (Классические ортогональные
полиномы дискретной переменной.-М.Наука 1985 216с) - эти я не пробовал.
алгоритм такой:
1.делим все числа инфо-ряда на К1 (подбор от 2 до Макс-1)
остатки пакуем по осн К1 в СДЧ , а ряды коэф-тов в БРЧ.
Считаем выгоду - если есть - фиксируем рез-т, если нет - откат назад и выход.
при однокаскадном, числа больше не ищем - это связано с тем, что потом
из этих чисел формируется новый массив длиной 1хT где Т- кол-во частей если
по 32 то это 8 32*8=256. плюс также минимумы частей тоже вычитаются и входят
в этот массив. итого 16 чисел. при 2х каскадном это 24 числа.
а при многокаскадном нужно запоминать еще длину каскадов для каждой части,
что часто уже невыгодно.
Для двухкаскадного делим инфо-ряд битовой полосой, нули удаляем, уменьшаем
все числа на 1. остатки пакуем в общее супердлиннное, а коэф-ты делаем
текущим инфо-рядом, и переход к 1.
при 2х каскадном ищем только 2 числа, а при многокаскадном ищем до упора
и возвращаем массив произвольной длины.
на выходе общая бит-полоса, общее СДЧ, но для каждого микро-блока свои q1,
q1q2, qq() числа - их накапливаем в массив и в конце пакуем методами 1-4
как выгодней. выбор отражаем флагами в служебном БРЧ. бит полосу жмём
тоже и запоминаем вначале блока- для распаковки.
Метод 4 . Безразмерные числа Хинга.
По научному это называется - энтропийное сжатие. -избыточность убираем.
у кодов Хаффмана выбор ограничен и привязка к длинам алфавита - у меня длина любая,
и выбор большой, выбираем быстро из N вариантов. (наиболее ходовые)
(в очень редких случаях коды Хаффмана лучше на нес-ко бит (0.1%)
Если частота чисел не по порядку возрастания значения, то частотная замена
обязательна! например число двоек больше чем 1 - меняем 1 и 2 местами и запоминаем это.
Этот метод для сохранения мелких чисел (средний меньше 16) - если больше, то
выгоднее каскадно разделить и отсеить нулевые. А если адаптивное арифм кодирование
и пр. может эту мелочь лучше сжать - то лучше ими сжимать, но разница не лучше 10%.
фактически это метод 3 по осн 2^N для уменьшения служ. инф. которая в мелких
рядах играет ну очень существенную роль. чуть лишний бит и сразу хуже на 20+%
можно конечно делать словарь - и менять большие числа на маленькие номера в словаре,
но вот только когда больших чисел много а их частота мала, то это совсем не выгодно!
Иногда надо сохр. число, а его размер неизвестен, тут помогут БРЧ.
хотя он и требует больше бит на число, но за счет того что маленьким числам
нужно меньше бит, а большим больше, а всё в этом мире имеет экп. распределение,
в том числе и расположение слов в тексте (и видео/фото тоже, про звук не знаю) то
в итоге всё равно бит будет потрачено меньше, чем для фикс. длины или для
2 бита - на длину длины, 1-4 бита для длины и 1-16 бит для числа. (но иногда
и такие инфо-ряды бывают, редко правда, но надо иметь ввиду и этот формат)
также можно использовать БРЧ для длины числа в битах. Еще выгодней хранить
не степень 2 а степень Экспоненты=2.72 или 3 а паковать в СДЧ по любому осн.
Пра-родитель этих чисел - число б/р100 1b=0d 01b=1d 001b=2d 0001b=3d
(сколько нулей такое и число, в конце всегда 1)
Это безразмерные числа - их можно писать друг за другом, без указания длины.
Конец это всегда 1, но если ограничено длиной 4, то 0000'01 это 4 и 1
Упаковка в СДЧ : пихаем 0(2) N раз и 1(2) - признак конца числа,
извлекаем из СДЧ по осн 2 если 0 - сч++ 1-конец. на выходе сч=число.
можно биты просто двигать - это быстрее, чем длинная арифметика.
Кроме двоичных чисел можно использовать числа Фибоначи (след число равно сумме
двух предыдущих - пишут что они имеют такие свойства, но я не проверял)
Далее б/р100 делится на 3 большие класса :
1 класс ведущее б/р100 + N бит
к б/р100 еще доп бит или два или 3+.
Длина такого числа будет на 1-2-3+ бит больше но и вместимость выше.
1.1 подкласс - с отсрочкой - биты добавляются не сразу а начиная с некоторого
числа, обычно 1=0 без доп. бита а дальше 01+1 001+1, в случае где море
нулей а остальных чисел умеренно много, то этот формат лучше других.
1.2 подкласс с ограничением - длина ведущего б/р100 ограничена - см. выше.
2 класс ведущее б/р100 + F(N) бит/осн
обычно арифм прогр с шагом 1. 1+0 01+00 001+000 (добавляем биты с нарастающей)
или шагом 2/3+ 1+00 01+0000 001+000000 +2 +4 +6
другой вариант удваивание 1+0 01+00 001+0000 0001+00000000 +2 +4 +8 бит
третий вариант табличный 1+q1 бит 01+q2 бит итд - похож на метод 2 немного.
отсрочка и ограничение также есть и здесь. Не обязательно 2^N формат,
можно использовать плавающее основание и длинную арифметику.
(но для скорости обрабатывать блоки по 256 байт, порядок такой : как только
длина супердлинного выше 256*8 бит - записываем его в файл и начинаем с 0)
например для 58 ведущее 0001, Vexp(1)+Vexp(2)+Vexp(3)+Vexp(4)= пакуем по осн
exp(4)=55 но объемы предыдущих уровней вычитаются из числа. 58-3-8-21=26(55)
ведущее можно упаковать в то же супердлинное - N(0(2))+1(2)-end или числами
фибоначи(не пробовал не знаю, может и выгоднее) но в общем случае лучше
разбить их на бит-поля по принципу длина первого бит поля равна длине инфо-ряда,
а длина второго кол-ву единиц в первом бит-поле и так далее. Дальше это бит-поле
можно сжать т.к там много 0..0, 1..1 блоков которые можно заменить на числа,
(например LZW методом) сделать частотную замену и еще сжать на 10+%.
(но как показали опыты лучше оставить эти биты в массиве в виде маркера=макс+1
или все числа++ а маркер=0 - так в итоге выгоднее выходит)
Ведущее можно раскидать по самим группам - сам алгоритм его найдет.
например ведущее -огр 1 бит, формат p78 числа 0-127 7бит, 8й бит это
ведущее/флаг: 0-нет продолжения, 1-есть. и след 8бит+ 7бит от прежнего для
128-32к+128 чисел. Лучше в первом сохр ст.7 бит + флаг, а мл. в след. 8 бит.
Этот формат выгоден если сумма частот чисел 0-128 больше чем для 128+
и что самое главное сохраняется байтовая сгрупированность данных-
что очень важно для PPMd - он оптимизирован для 8 битных чисел, большие
не работают - массивы байтовые, а меньшие можно, но рез-т похуже из-за
того что эмпирические коэф-ты расчитаны на диапазон 0-255.
Еще один формат p3334 - здесь ведущее огр. 3 бита для каждого полубайта
4й бит это флаг продолжения а 3 бита данные, в последнем 4 бита для данных.
в 16 бит влазит всего 8к+512+64+8 чисел, но в обычном тесте больше разных
слов не бывает, и за счет _меньшей_ служ. информации этот формат лучше
кодов Хаффмана если частоты распределены по экспоненте (а в тексте это так)
Для сравнения 77тыс 12 битных пи-кодов текста без одиночек и не слов:
87400 байт в формате p3344 - скорость на уровне копирования.
82900 байт в формате ведущее+N бит шаг 1, очень быстро.
84200 байт - метод1 (максимальных выемок по блокам по 256, быстро)
92200 байт сжал рар (который использует PPMd+анализ+парсер)
91200 байт Zip и gzip-который потоком жмет трафик интернета.
95600 байт динамич Хаффман(FGK алгоритм) (и медленнее в 100 раз)
93750 байт классический Хаффман (от Мастрюкова)
92700 байт адаптивный Арифметик (от Мастрюкова)
lzss/lzw от него же, больше 110к - намного хуже.
худшие результаты еще из-за того что архиваторы не знают что это
12 битные числа в 16 битном формате, поэтому жмут их как байты,
чистый арифметик 12 битные числа сжал в 84500 но медленнее в 100 раз.
77400 байт PPMd от Шкарина (7z-также, но надо качать весь архив)
а после преобразования в формат p78+PPMd 73990 байт - это по сравнению
с gzip на 20% лучше и он поточный тоже - часть скачал-часть текста увидел.
а за счет того что словарь не передается в каждом архиве, а в самом декодере
и кодере (540 тыс слов - в порядке интернет рейтинга в формате p7778)
обычно 99% текста это 5 тыс слов - 1/2 байтовый пи-код -номер слова в словаре.
HTML еще можно почистить - удалить все коменты, лишние пробелы и теги /TD/TR-
они лишние, так же можно удалить скрипты и стили если в браузере они отключены
и в запросе есть указание их не принимать. Также можно сделать автозамену по
словарю пи-синонимов заменить сленг, опечатки и ошибки на правильные слова.
Сменить кодировки UTF/Unicode/DOS/KOI на win1251 (экономия до 7+%)
Заменить все знаки препинания на теги (это еще 10+% за счет того что перед
точкой и запятой надо вставлять пробел(потом декодером убрать) и следующее
слово начинать с маленькой буквы(слово. Слово -> слово . слово ) это повышает
кол-во одинаковых слов/блоков а декодируется однозначно, но если слово после
точки не начиналось с заглавной, то вставляется управляющий пи-код который
принудительно начнет слово с нужного регистра (подробней см. документацию)
В итоге текст 440к сжатый gzip в 120к, будет сжат пи-кодером+p78+PPMd в 80к
без потери информации, в 60к с потерей - удаление мусора с сохр. смысла.
А если поточность и скорость не важна то в 40к за счет поиска оптимальных
блоков и адресных выборок - это медленно, но выгодно. т.в в 2-3 раза!
(Демо прогу можно посмотреть здесь, работает пока медленно и словарь бета)
3 класс - это класс 2 без ведущего, но есть в конце маркер: все единицы 1111
но из-за этого в остальных ячейках его не можем использовать
000+010+110+001+111
отсрочка и ограничения тоже есть и для этого класса.
при некотором распределении частот этот класс бывает лучше, но редко.
БРЧ фактически это однокаскадное деление на 2^N +б/р100
и в общем случае можно всегда найти переломочное число получше, но
его запоминать надо, а здесь просто номер метода по осн 32 фикс. 5 бит.
но если числа распределены равномерно в диапазоне 0..2^N-1 то есть метод 0
это просто фикс. бит на число - но доп. надо запоминать кол-во бит и длину!
(а запоминание длины очень невыгодная операция и требует много доп.места)
БРЧ ещё можно представить как набор бит-полос 256х1-бит первая + кол-во "1"
это длина след. бит-полосы и так далее. такие бит-поля можно еще доп.сжать.
БРЧ это не метод, это способ хранения чисел, ничего считать не надо,
доступ произвольный - адрес 1го бита это сумма длин всех предыдущих, для
скорости можно временно в ОЗУ развернуть таблицу адресов через 10/100 и пр.
Это всяко быстрее чем zip папки от MicroSoft, а сжатие чуть лучше в целом.
Почему проигрывают коды Хаффмана
Безразмерные числа прожорливы в плане хранения, фиксированный формат в этом
плане экономичный и для равномерных чисел оптимальный. БРЧ Хинга это гибрид
безразмерного и фиксированного формата, для обозначения диапазона чисел
используется одно БРЧ (ведущее слово) - в этом экономия.
Как выбрать оптимальный формат БРЧ?
допустим если числа, в квадр. скобках их частота.
0-[100] 1 1 +0
1-[70] 01 1 +1
2-[10] 001 01 +0 (минус объемы от предыдущих емкостей)
3-[5] 0001 01 +1
4-[0] 00001 001+1 (минус объемы от предыдущих емкостей)
для БРЧ 100 надо 100*1+70*2+10*3+5*4=290 бит
но если тратить не одно БРЧ на одно число, а на группы 1,2 и 3,4
то служебная информация будет 1*170+2*15=200 бит +185 бит на данные = больше.
для кол-ва разных чисел кратных 2^N ситуация другая чем для остальных.
для 1-3 БРЧ100 всегда лучше чем фиксированно по 2 бита на число, т.к заполнение
объема 4 емкости 2 будет 3/4, даже для равномерных чисел, лучше только арифметик
или паковать в СДЧ длинной арифметикой. - это дольше, но иногда лучше.
для 1-5 уже возможны варианты:
0-[100] 1-[90] 2-[85] 3-[70] 4-[50]
1185 фикс 3бита/число, 1065 БРЧ100, 1045 БРЧ101
За счет чего получился выигрыш?
при БРЧ100 на число "4" служебное слово занимало 5 бит и 250 бит всего,
в БРЧ101 3 бита и 150 бит всего - выиграли 100 бит, но из-за групировки
потеряли на "0" +100 бит, но на "3" снова выиграли +70
100*1+90*2+85*3+70*4+50*5= 1065
(100+90)*2+(85+70)*3+50*4= 1045 (а с ограничением это еще -50 бит)
по сложным формулам можно вычислить сразу без перебора по таблице частот,
какой метод лучше , а затем сжать им - номер метода это первый байт 0-255.
пока есть 25 форматов, но потом можно добавлять самые ходовые - их много.
выгода БРЧ при количествах разных чисел не кратных степени 2 бывает 30+%
лучше только длинная арифметика но она намного дольше считает..
Ещё формат 00 01 10 11+00 11-флаг продолжения числа в след 2х битах
(100+90+85)*2+(70+50)*4=1030 бит + еще есть место для 2х чисел 11+10 11+11
так что от частотного распределения нужно выбирать самый выгодный формат.
Блоки чисел по 2..5 тоже надо считать, если частота 1_2_3 выше чем у 7
то 7 кодируем бО'льшим числом а блок 1_2_3 числом по порядку частотной замены.
Это и к буквам и к словам относится со знаками препинания и разделителями..
Так как имеет место много паралельных независимых вычислений то лучше
этот кодер сделать аппаратным в виде сопроцессора делающим одновременно
N делений и сравнений. тогда будет быстро сжимать - почти мгновенно.
Так же неплохо использовать облачные нейронные сети которые будут
через сервер обмена общаться между собой и обмениваться накопленным опытом,
тогда по графику значений и частотам будет выбираться нужный метод на основе
обобщения, предсказания и накопленного опыта.
-----------------------
Графический метод сжатия эксп. ряда.
1. считаем частотное распределение и кол-во символов всего.
символ это 8 бит число - байт или 2-N группа байтов с частотой
больше суммы частот этих символов по отдельности(?)
2. замена символов на числа по схеме:
локальная - таблица замены в заголовке архива.
глобальная (встроены в архиватор-одна для всех)
легкий хтмл, 5% тегов и лат букв
тяжелый хтмл 5-40%
смешанный 40%-60%
латинский больше 60%
невыгодно сжимать - равномерно распределены все 0-255 числа.
3. строим график -если это экпонента, то в зависимости от крутизны
разбиваем на 2/4/8/16/N блоков равных по объему занимаемое емкости-
емкость чисел*кол-во в блоке - например 100 чисел 0-31 5бит*100=500бит.
числа каждого следующего блока надо уменьшать на минимум этого блока-
он равен макс+1 предыдущего блока. - это немного экономит место и однозначное
восстановление. и в блоке числа будут от 0 до N-СУММА(Ёi) i=0..N-1
внутри блока числа условно равномерные - их можно сжимать по основанию макс+1
в СДЧ или сохр по битам если близко к степени двойки 32-64-128 итд
можно сжимать арифметиком- он повторы и небольшую эксп. сожмет ещё.
Ведущие числа можно сжать в БРЧ при сильной неравномерности.
или арифметиком, или PMD.. (кто ниче не понял, значит не дано..)
Кстати планшет я изобрел в 2003 году, потом идею свиснули.
Следующее моё изобретение будет "Искуственный разум".. (шутка)
ну а пока я ищу удаленную работу/подработку в хорошей фирме.
побробности у меня сайте. explay-m3.narod.ru
с VB6 перехожу на Java, PHP, C# (на С++ вряд ли. там много лишнего)
на VС+ оказалось удобней DLL-с flat-asm писать - там отличный отладчик.
Xing октябрь 2015г
при перепечатке ссылка на первоисточник обязательна.