| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 25 Apr 99 16:57:33 To : Paul Melnikov Subj : WI Hello Paul, Sunday April 25 1999 15:07, Paul Melnikov wrote to All: PM> 5) Производится сжатие без потерь полученных данных. Как правило, в PM> современных кодеках используется арифметическое сжатие, в _стандарте_ PM> jpeg - хаффмановское. Да вpоде и хафмановское и аpифметическое, но на аpифметический кодеp имеется патент у IBM, поэтому не всякий софт его поддеpживает. PM> Ссылками на что-нибудь интересное поделиться/обменяться - это PM> пожалуйста. Давай. См. мои на http://tnet.sochi.net/~maxime/compression.shtml Maxime Zakharov. --- * Origin: А ты причинил сегодня добро ? (2:5065/10.12) — RU.COMPRESS From : Roman Vasilchenko 2:5020/400 25 Apr 99 19:39:26 To : All Subj : Re: Huffman From: "Roman Vasilchenko" <vrs@nkuz-gts.kemerovo.su> > Здесь посылают не в инет... > А куда? --- ifmail v.2.14dev3 * Origin: Nkuz-GTS (2:5020/400) — RU.COMPRESS From : Roman Vasilchenko 2:5020/400 25 Apr 99 19:39:29 To : All Subj : Re: Huffman From: "Roman Vasilchenko" <vrs@nkuz-gts.kemerovo.su> >21 Apr 99 19:10, Alexander Tsarev wrote to All: > AT> Hаpод, кто-либо может описать алгоpитм Хафмана? > AT> Только не посылайте в инет, его нетy y меня. > Здесь посылают не в инет... Я могу в книге посмотреть - только ничего конкетного там нет. Так... поверхностно. --- ifmail v.2.14dev3 * Origin: Nkuz-GTS (2:5020/400) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 25 Apr 99 20:42:56 To : All Subj : архиваторы ============================================================================= * Forwarded by Vadim Vygovsky (2:5022/12.8) * Area : NETMAIL (FastEcho Netmail) * From : Sergey Melnikov, 2:5064/1.5 (Четверг Апрель 22 1999 12:48) * To : Vadim Vygovsky * Subj : архиваторы ============================================================================= Привет, Vadim! Ты мне как-то высылал аpхиватоp AMG. Я пеpеделал его, чтоб можно было pаспаковывать 1 файл, а один фидошник пеpевел его под ТМТ Паскаль. Hо в Дельфи его без дальнейшей пеpеделки вpяд ли можно будет пpименять, т.к. автоp аpхиватоpа использовал тот факт, что по GetMem (p,size) начальное смещение (мл. слово p) pавно 0. Под ТМТ для этого используется функция, кажется, AllocDataDescryptor, а в вин95 такого, по-моему, делать нельзя. Сейчас ru.compress у меня нет, поэтому я хочу узнать, есть ли какие-то исходники, чтоб можно было в Дельфи pаспаковывать 1 файл в память или из памяти в память? Может, кто-то вытащил из исходников unrar.dll минимум функций, чтоб это делать? (Можно и на С) Фоpмат аpхива чтоб был попpоще, напp., пеpвые 4 байта - длина pаспакованных данных, а потом сами данные. А то паскалевские исходники аpхиватоpов кpоме AMG все стаpючие и слабо жмут. Это мне нужно, чтоб не использовать лицензионную unrar.dll. Желаю успехов! Sergey --- GoldED/386 3.00.Beta3+ [ http://www.sf.amc.ru/~dv/bud/ ] * Origin: Stavpol BBS (86559)-51318 (Budennovsk, Stavropol rg) (2:5064/1.5) ============================================================================= Hello, All! Помогите парню (ответы - мылом ему), а то я в паскалях/дельфях ни в зуб ногой. Хотя, честно говоря не понял, чем ему не нравится использование unrar.dll. WBR, Vadim --- Оглоед 3.00.Beta5+ * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 25 Apr 99 20:49:13 To : Maxime Zakharov Subj : Алгоpитмы динамического сжатия (по Маpковy) *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Maxime! Sunday April 25 1999, Maxime Zakharov writes to Bulat Ziganshin: MZ>>>> http://plg.uwaterloo.ca:80/~ftp/dmc/ BZ>> Если там много - я могу вытащить и в фэху. MZ> Да вpоде немного. Но там только исходные тексты к статье, MZ> опубликованной в каком-то жуpнале. В ddj была где-то в 95-м. Я здесь даже кратко излагал ее, благо идея проста до безобразия. BZ>> Кстати, по-моему, в BZ>> народе возраждается интерес к эхотагу. Интересно, почему? MZ> Навеpное, вpемя сдавать куpсовики/дипломы пpиближается. Вроде в прошлом году такого не было. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 25 Apr 99 21:08:13 To : Paul Melnikov Subj : WI * Crossposted in RU.COMPRESS Hello Paul! Sunday April 25 1999, Paul Melnikov writes to All: PM> 3) для тех, кто просил выслать дистрибутив программки-кодека, лежащей PM> на www.cengines.com PM> Там саморапаковывающийся экзэшник, который весит 1.1 метра. Кому надо, PM> плиз, заберите сами. Жаль, что ты точного url'а не кинул. Hо найдем, заберем и кинем в фэху. Hадо нам развиваться вширь :) PM> Вот поделиться впечатлениями об этом очень неплохом кодеке - это тоже PM> пожалуйста. Спасибо за твой рассказ. Пора нам делать фак все же... Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 25 Apr 99 21:16:29 To : Paul Melnikov Subj : Re: WI Вот что решил ответить Sergey на послание автором которого является Paul Melnik ov по теме <Re: WI> и отправленное им 25 Apr 99 15:07:28: Hi Paul! PM> 5) Производится сжатие без потерь полученных данных. Как правило, в PM> современных кодеках используется арифметическое сжатие, в _стандарте_ PM> jpeg - хаффмановское. Странно, RAR 2.00 сжимает jpeg файлы на 30%, по сравнению с оригиналом, это я проверил на 256 цветной картинке, полученной со сканера (сканировался те кст), разрешение 2ххх*3ххх точек. Т.е в jpeg файлах очень много избыточности ос тается. Мой случай исключение или закономерность? И для каких картинок jpeg опт имален? Hу, всего наисамого наилучшего! С уважением Sergey. --- * Origin: Дайте мне точку опоры или я переверну весь мир! (2:5037/9.36) — RU.COMPRESS From : Sasha Davydov 2:5030/865 26 Apr 99 00:59:00 To : Alexander Tsarev Subj : Huffman Здрасте, Alexander! Hекто "Alexander Tsarev" писал к "All" (Сpд Апp 21 1999 20:10) AT> Hаpод, кто-либо может описать алгоpитм Хафмана? AT> Только не посылайте в инет, его нетy y меня. Посколькy тебе ничего не кинyли, лови это описание... А под ним исходник пpоги на паскале... Hадеюсь, что помог тебе в поиске.. PS: Hогами не пинайте, не такой он yж и большой... =) ------------------------------------------------------------------------------- Huffman - Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Hо давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках. Сжимая файл по алгоритму Хаффмана первое что мы должны сделать - это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла. После подсчета частоты вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и сформировать мнимую компоновку между кодами по убыванию. То есть не меняя местонахождение каждого символа из таблицы в памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней таблицы назовем "узлом". В дальнейшем ( в дереве ) мы будем позже размещать указатели которые будут указывает на этот "узел". Для ясности давайте рассмотрим пример: Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе . Мы подсчитали вхождение каждого из символов в файл и получили следующее : ------------------T-----T-----T-----T-----T-----T-----¬ ¦ cимвол ¦ A ¦ B ¦ C ¦ D ¦ E ¦ F ¦ +-----------------+-----+-----+-----+-----+-----+-----+ ¦ число вхождений ¦ 10 ¦ 20 ¦ 30 ¦ 5 ¦ 25 ¦ 10 ¦ L-----------------+-----+-----+-----+-----+-----+------ Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа. Разместим таблицу как ниже. ------------------T-----T-----T-----T-----T-----T-----¬ ¦ cимвол ¦ C ¦ E ¦ B ¦ F ¦ A ¦ D ¦ +-----------------+-----+-----+-----+-----+-----+-----+ ¦ число вхождений ¦ 30 ¦ 25 ¦ 20 ¦ 10 ¦ 10 ¦ 5 ¦ L-----------------+-----+-----+-----+-----+-----+------ Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A. Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A : Частота 30 10 5 10 20 25 Символа C A D F B E ¦ ¦ L--T--- -+-¬ ¦15¦ = 5 + 10 L--- Hомер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов : Частота 30 10 5 10 20 25 Символа C A D F B E ¦ ¦ ¦ ¦ ¦ ¦ ¦ ---¬¦ ¦ L-+15+- ¦ LT-- ¦ ¦ ¦ ¦ ---¬ ¦ L----+25+-- = 10 + 15 L--- Рассматриваем таблицу снова для следующих двух символов ( B и E ). Мы продолжаем в этот режим пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу. Частота 30 10 5 10 20 25 Символа C A D F B E ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ---¬¦ ¦ ¦ ¦ ¦ L-+15+- ¦ ¦ ¦ ¦ LT-- ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ---¬ ¦ ¦ ---¬ ¦ ¦ L----+25+-- L-+45+-- ¦ LT-- LT-- ¦ ---¬ ¦ ¦ L----+55+------- ¦ L-T- ¦ ¦ -------------¬ ¦ L---+ Root (100) +----- L------------- Теперь когда наше дерево создано, мы можем кодировать файл . Мы должны всенда начнинать из корня ( Root ) . Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу . Код Хаффмана для нашего символа C - 00. Для следующего символа ( А ) у нас получается - лево,право,лево,лево , что выливается в последовательность 0100. Выполнив выше сказанное для всех символов получим C = 00 ( 2 бита ) A = 0100 ( 4 бита ) D = 0101 ( 4 бита ) F = 011 ( 3 бита ) B = 10 ( 2 бита ) E = 11 ( 2 бита ) Каждый символ изначально представлялся 8-ю битами ( один байт ), и так как мы уменьшили число битов необходимых для представления каждого символа, мы следовательно уменьшили размер выходного файла . Сжатие складывется следующим образом : -----------T----------------T-------------------T--------------¬ ¦ Частота ¦ первоначально ¦ уплотненные биты ¦ уменьшено на ¦ +----------+----------------+-------------------+--------------+ ¦ C 30 ¦ 30 x 8 = 240 ¦ 30 x 2 = 60 ¦ 180 ¦ ¦ A 10 ¦ 10 x 8 = 80 ¦ 10 x 3 = 30 ¦ 50 ¦ ¦ D 5 ¦ 5 x 8 = 40 ¦ 5 x 4 = 20 ¦ 20 ¦ ¦ F 10 ¦ 10 x 8 = 80 ¦ 10 x 4 = 40 ¦ 40 ¦ ¦ B 20 ¦ 20 x 8 = 160 ¦ 20 x 2 = 40 ¦ 120 ¦ ¦ E 25 ¦ 25 x 8 = 200 ¦ 25 x 2 = 50 ¦ 150 ¦ L----------+----------------+-------------------+--------------- Первоначальный размер файла : 100 байт - 800 бит; Размер сжатого файла : 30 байт - 240 бит; 240 - 30% из 800 , так что мы сжали этот файл на 70%. Все это довольно хорошо, но неприятность находится в том факте, что для восстановления первоначального файла, мы должны иметь декодирующее дерево, так как деревья будут различны для разных файлов . Следовательно мы должны сохранять дерево вместе с файлом . Это превращается в итоге в увеличение размеров выходного файла . В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной. Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11 . 4 байта 11 раз - 44 . Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику - наша таблица будет приблизительно 50 байтов длинны. Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт . Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт - мы получили 20% сжатие информации. Hе плохо . То что мы действительно выполнили - трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным. Что мы можем получить на этом пути ? Рассмотрим максимум которй мы можем получить для различных разрядных комбинацй в оптимальном дереве, которое является несимметричным. Мы получим что можно иметь только : 4 - 2 разрядных кода; 8 - 3 разрядных кодов; 16 - 4 разрядных кодов; 32 - 5 разрядных кодов; 64 - 6 разрядных кодов; 128 - 7 разрядных кодов; Hеобходимо еще два 8 разрядных кода. 4 - 2 разрядных кода; 8 - 3 разрядных кодов; 16 - 4 разрядных кодов; 32 - 5 разрядных кодов; 64 - 6 разрядных кодов; 128 - 7 разрядных кодов; -------- 254 Итак мы имеем итог из 256 различных комбинаций которыми можно кодировать байт . Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта . Все эти подсчеты производились для не префиксных кодов Хаффмана т.е. кодов, которые нельзя идентифицировать однозначно. Hапример код A - 01011 и код B - 0101 . Если мы будем получать эти коды побитно, то получив биты 0101 мы не сможем сказать какой код мы получили A или B , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего. Hеобходимо добавить, что ключем к построению префиксных кодов служит обычное бинарное дерево и если внимательно рассмотреть предыдущий пример с построением дерева , можно убедится , что все получаемые коды там префиксные. Одно последнее примечание - алгоритм Хаффмана требует читать входной файл дважды , один раз считая частоты вхождения символов , другой раз производя непосредственно кодирование. Литература : ------------ 1) Описание архиватора Narc фирмы Infinity Design Concepts, Inc.; 2) Чарльз Сейтер,'Сжатие данных', "Мир ПК",N2 1991; {$A+,B-,D+,E+,F-,G-,I-,L+,N-,O-,R+,S+,V+,X-} {$M 16384,0,655360} {******************************************************} {* Алгоритм уплотнения данных по методу *} {* Хафмана. *} {******************************************************} Program Hafman; Uses Crt,Dos,Printer; Type PCodElement = ^CodElement; CodElement = record NewLeft,NewRight, P0, P1 : PCodElement; {элемент входящий одновременно} LengthBiteChain : byte; { в массив , очередь и дерево } BiteChain : word; CounterEnter : word; Key : boolean; Index : byte; end; TCodeTable = array [0..255] of PCodElement; Var CurPoint,HelpPoint, LeftRange,RightRange : PCodElement; CodeTable : TCodeTable; Root : PCodElement; InputF, OutputF, InterF : file; TimeUnPakFile : longint; AttrUnPakFile : word; NumRead, NumWritten: Word; InBuf : array[0..10239] of byte; OutBuf : array[0..10239] of byte; BiteChain : word; CRC, CounterBite : byte; OutCounter : word; InCounter : word; OutWord : word; St : string; LengthOutFile, LengthArcFile : longint; Create : boolean; NormalWork : boolean; ErrorByte : byte; DeleteFile : boolean; {-------------------------------------------------} procedure ErrorMessage; { --- вывод сообщения об ошибке --- } begin If ErrorByte <> 0 then begin Case ErrorByte of 2 : Writeln('File not found ...'); 3 : Writeln('Path not found ...'); 5 : Writeln('Access denied ...'); 6 : Writeln('Invalid handle ...'); 8 : Writeln('Not enough memory ...'); 10 : Writeln('Invalid environment ...'); 11 : Writeln('Invalid format ...'); 18 : Writeln('No more files ...'); else Writeln('Error #',ErrorByte,' ...'); end; NormalWork:=False; ErrorByte:=0; end; end; procedure ResetFile; { --- открытие файла для архивации --- } Var St : string; begin Assign(InputF, ParamStr(3)); Reset(InputF, 1); ErrorByte:=IOResult; ErrorMessage; If NormalWork then Writeln('Pak file : ',ParamStr(3),'...'); end; procedure ResetArchiv; { --- открытие файла архива, или его создание --- } begin St:=ParamStr(2); If Pos('.',St)<>0 then Delete(St,Pos('.',St),4); St:=St+'.vsg'; Assign(OutputF, St); Reset(OutPutF,1); Create:=False; If IOResult=2 then begin Rewrite(OutputF, 1); Create:=True; end; If NormalWork then If Create then Writeln('Create archiv : ',St,'...') else Writeln('Open archiv : ',St,'...') end; procedure SearchNameInArchiv; { --- в дальнейшем - поиск имени файла в архиве --- } begin Seek(OutputF,FileSize(OutputF)); ErrorByte:=IOResult; ErrorMessage; end; procedure DisposeCodeTable; { --- уничтожение кодовой таблицы и очереди --- } Var I : byte; begin For I:=0 to 255 do Dispose(CodeTable[I]); end; procedure ClosePakFile; { --- закрытие архивируемого файла --- } Var I : byte; begin If DeleteFile then Erase(InputF); Close(InputF); end; procedure CloseArchiv; { --- закрытие архивного файла --- } begin If FileSize(OutputF)=0 then Erase(OutputF); Close(OutputF); end; procedure InitCodeTable; { --- инициализация таблицы кодировки --- } Var I : byte; begin For I:=0 to 255 do begin New(CurPoint); CodeTable[I]:=CurPoint; With CodeTable[I]^ do begin P0:=Nil; P1:=Nil; LengthBiteChain:=0; BiteChain:=0; CounterEnter:=1; Key:=True; Index:=I; end; end; For I:=0 to 255 do begin If I>0 then CodeTable[I-1]^.NewRight:=CodeTable[I]; If I<255 then CodeTable[I+1]^.NewLeft:=CodeTable[I]; end; LeftRange:=CodeTable[0]; RightRange:=CodeTable[255]; CodeTable[0]^.NewLeft:=Nil; CodeTable[255]^.NewRight:=Nil; end; procedure SortQueueByte; { --- пузырьковая сортировка по возрастанию --- } Var Pr1,Pr2 : PCodElement; begin CurPoint:=LeftRange; While CurPoint <> RightRange do begin If CurPoint^.CounterEnter > CurPoint^.NewRight^.CounterEnter then begin HelpPoint:=CurPoint^.NewRight; HelpPoint^.NewLeft:=CurPoint^.NewLeft; CurPoint^.NewLeft:=HelpPoint; If HelpPoint^.NewRight<>Nil then HelpPoint^.NewRight^.NewLeft:=CurPoint; CurPoint^.NewRight:=HelpPoint^.NewRight; HelpPoint^.NewRight:=CurPoint; If HelpPoint^.NewLeft<>Nil then HelpPoint^.NewLeft^.NewRight:=HelpPoint; If CurPoint=LeftRange then LeftRange:=HelpPoint; If HelpPoint=RightRange then RightRange:=CurPoint; CurPoint:=CurPoint^.NewLeft; If CurPoint = LeftRange then CurPoint:=CurPoint^.NewRight else CurPoint:=CurPoint^.NewLeft; end else CurPoint:=CurPoint^.NewRight; end; end; procedure CounterNumberEnter; { --- подсчет частот вхождений байтов в блоке --- } Var C : word; begin For C:=0 to NumRead-1 do Inc(CodeTable[(InBuf[C])]^.CounterEnter); end; function SearchOpenCode : boolean; { --- поиск в очереди пары открытых по Key минимальных значений --- } begin CurPoint:=LeftRange; HelpPoint:=LeftRange; HelpPoint:=HelpPoint^.NewRight; While not CurPoint^.Key do CurPoint:=CurPoint^.NewRight; While (not (HelpPoint=RightRange)) and (not HelpPoint^.Key) do begin HelpPoint:=HelpPoint^.NewRight; If (HelpPoint=CurPoint) and (HelpPoint<>RightRange) then HelpPoint:=HelpPoint^.NewRight; end; If HelpPoint=CurPoint then SearchOpenCode:=False else SearchOpenCode:=True; end; procedure CreateTree; { --- создание дерева частот вхождения --- } begin While SearchOpenCode do begin New(Root); With Root^ do begin P0:=CurPoint; P1:=HelpPoint; LengthBiteChain:=0; BiteChain:=0; CounterEnter:=P0^.CounterEnter + P1^.CounterEnter; Key:=True; P0^.Key:=False; P1^.Key:=False; end; HelpPoint:=LeftRange; While (HelpPoint^.CounterEnter < Root^.CounterEnter) and (HelpPoint<>Nil) do HelpPoint:=HelpPoint^.NewRight; If HelpPoint=Nil then { добавление в конец } begin Root^.NewLeft:=RightRange; RightRange^.NewRight:=Root; Root^.NewRight:=Nil; RightRange:=Root; end else begin { вставка перед HelpPoint } Root^.NewLeft:=HelpPoint^.NewLeft; HelpPoint^.NewLeft:=Root; Root^.NewRight:=HelpPoint; If Root^.NewLeft<>Nil then Root^.NewLeft^.NewRight:=Root; end; end; end; procedure ViewTree( P : PCodElement ); { --- просмотр дерева частот и присваивание кодировочных цепей листьям --- } Var Mask,I : word; begin Inc(CounterBite); If P^.P0<>Nil then ViewTree( P^.P0 ); If P^.P1<>Nil then begin Mask:=(1 SHL (16-CounterBite)); BiteChain:=BiteChain OR Mask; ViewTree( P^.P1 ); Mask:=(1 SHL (16-CounterBite)); BiteChain:=BiteChain XOR Mask; end; If (P^.P0=Nil) and (P^.P1=Nil) then begin P^.BiteChain:=BiteChain; P^.LengthBiteChain:=CounterBite-1; end; Dec(CounterBite); end; procedure CreateCompressCode; { --- обнуление переменных и запуск просмотра дерева с вершины --- } begin BiteChain:=0; CounterBite:=0; Root^.Key:=False; ViewTree(Root); end; procedure DeleteTree; { --- удаление дерева --- } Var P : PCodElement; begin CurPoint:=LeftRange; While CurPoint<>Nil do begin If (CurPoint^.P0<>Nil) and (CurPoint^.P1<>Nil) then begin If CurPoint^.NewLeft <> Nil then CurPoint^.NewLeft^.NewRight:=CurPoint^.NewRight; If CurPoint^.NewRight <> Nil then CurPoint^.NewRight^.NewLeft:=CurPoint^.NewLeft; If CurPoint=LeftRange then LeftRange:=CurPoint^.NewRight; If CurPoint=RightRange then RightRange:=CurPoint^.NewLeft; P:=CurPoint; CurPoint:=P^.NewRight; Dispose(P); end else CurPoint:=CurPoint^.NewRight; end; end; procedure SaveBufHeader; { --- запись в буфер заголовка архива --- } Type ByteField = array[0..6] of byte; Const Header : ByteField = ( $56, $53, $31, $00, $00, $00, $00 ); begin If Create then begin Move(Header,OutBuf[0],7); OutCounter:=7; end else begin Move(Header[3],OutBuf[0],4); OutCounter:=4; end; end; procedure SaveBufFATInfo; { --- запись в буфер всей информации по файлу --- } Var I : byte; St : PathStr; R : SearchRec; begin St:=ParamStr(3); For I:=0 to Length(St)+1 do begin OutBuf[OutCounter]:=byte(Ord(St[I])); Inc(OutCounter); end; FindFirst(St,$00,R); Dec(OutCounter); Move(R.Time,OutBuf[OutCounter],4); OutCounter:=OutCounter+4; OutBuf[OutCounter]:=R.Attr; Move(R.Size,OutBuf[OutCounter+1],4); OutCounter:=OutCounter+5; end; procedure SaveBufCodeArray; { --- сохранить массив частот вхождений в архивном файле --- } Var I : byte; begin For I:=0 to 255 do begin OutBuf[OutCounter]:=Hi(CodeTable[I]^.CounterEnter); Inc(OutCounter); OutBuf[OutCounter]:=Lo(CodeTable[I]^.CounterEnter); Inc(OutCounter); end; end; procedure CreateCodeArchiv; { --- создание кода сжатия --- } begin InitCodeTable; { инициализация кодовой таблицы } CounterNumberEnter; { подсчет числа вхождений байт в блок } SortQueueByte; { cортировка по возрастанию числа вхождений } SaveBufHeader; { сохранить заголовок архива в буфере } SaveBufFATInfo; { сохраняется FAT информация по файлу } SaveBufCodeArray; { сохранить массив частот вхождений в архивном файле } CreateTree; { создание дерева частот } CreateCompressCode; { cоздание кода сжатия } DeleteTree; { удаление дерева частот } end; procedure PakOneByte; { --- сжатие и пересылка в выходной буфер одного байта --- } Var Mask : word; Tail : boolean; begin CRC:=CRC XOR InBuf[InCounter]; Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHR CounterBite; OutWord:=OutWord OR Mask; CounterBite:=CounterBite+CodeTable[InBuf[InCounter]]^.LengthBiteChain; If CounterBite>15 then Tail:=True else Tail:=False; While CounterBite>7 do begin OutBuf[OutCounter]:=Hi(OutWord); Inc(OutCounter); If OutCounter=(SizeOf(OutBuf)-4) then begin BlockWrite(OutputF,OutBuf,OutCounter,NumWritten); OutCounter:=0; end; CounterBite:=CounterBite-8; If CounterBite<>0 then OutWord:=OutWord SHL 8 else OutWord:=0; end; If Tail then begin Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHL (CodeTable[InBuf[InCounter]]^.LengthBiteChain-CounterBite); OutWord:=OutWord OR Mask; end; Inc(InCounter); If (InCounter=(SizeOf(InBuf))) or (InCounter=NumRead) then begin InCounter:=0; BlockRead(InputF,InBuf,SizeOf(InBuf),NumRead); end; end; procedure PakFile; { --- процедура непосредственного сжатия файла --- } begin ResetFile; SearchNameInArchiv; If NormalWork then begin BlockRead(InputF,InBuf,SizeOf(InBuf),NumRead); OutWord:=0; CounterBite:=0; OutCounter:=0; InCounter:=0; CRC:=0; CreateCodeArchiv; While (NumRead<>0) do PakOneByte; OutBuf[OutCounter]:=Hi(OutWord); Inc(OutCounter); OutBuf[OutCounter]:=CRC; Inc(OutCounter); BlockWrite(OutputF,OutBuf,OutCounter,NumWritten); DisposeCodeTable; ClosePakFile; end; end; procedure ResetUnPakFiles; { --- открытие файла для распаковки --- } begin InCounter:=7; St:=''; repeat St[InCounter-7]:=Chr(InBuf[InCounter]); Inc(InCounter); until InCounter=InBuf[7]+8; Assign(InterF,St); Rewrite(InterF,1); ErrorByte:=IOResult; ErrorMessage; If NormalWork then begin WriteLn('UnPak file : ',St,'...'); Move(InBuf[InCounter],TimeUnPakFile,4); InCounter:=InCounter+4; AttrUnPakFile:=InBuf[InCounter]; Inc(InCounter); Move(InBuf[InCounter],LengthArcFile,4); InCounter:=InCounter+4; end; end; procedure CloseUnPakFile; { --- закрытие файла для распаковки --- } begin If not NormalWork then Erase(InterF) else begin SetFAttr(InterF,AttrUnPakFile); SetFTime(InterF,TimeUnPakFile); end; Close(InterF); end; procedure RestoryCodeTable; { --- воссоздание кодовой таблицы по архивному файлу --- } Var I : byte; begin InitCodeTable; For I:=0 to 255 do begin CodeTable[I]^.CounterEnter:=InBuf[InCounter]; CodeTable[I]^.CounterEnter:=CodeTable[I]^.CounterEnter SHL 8; Inc(InCounter); CodeTable[I]^.CounterEnter:=CodeTable[I]^.CounterEnter+InBuf[InCounter]; Inc(InCounter); end; end; procedure UnPakByte( P : PCodElement ); { --- распаковка одного байта --- } Var Mask : word; begin If (P^.P0=Nil) and (P^.P1=Nil) then begin OutBuf[OutCounter]:=P^.Index; Inc(OutCounter); Inc(LengthOutFile); If OutCounter = (SizeOf(OutBuf)-1) then begin BlockWrite(InterF,OutBuf,OutCounter,NumWritten); OutCounter:=0; end; end else begin Inc(CounterBite); If CounterBite=9 then begin Inc(InCounter); If InCounter = (SizeOf(InBuf)) then begin InCounter:=0; BlockRead(OutputF,InBuf,SizeOf(InBuf),NumRead); end; CounterBite:=1; end; Mask:=InBuf[InCounter]; Mask:=Mask SHL (CounterBite-1); Mask:=Mask OR $FF7F; { установка всех битов кроме старшего } If Mask=$FFFF then UnPakByte(P^.P1) else UnPakByte(P^.P0); end; end; procedure UnPakFile; { --- распаковка одного файла --- } begin BlockRead(OutputF,InBuf,SizeOf(InBuf),NumRead); ErrorByte:=IOResult; ErrorMessage; If NormalWork then ResetUnPakFiles; If NormalWork then begin RestoryCodeTable; SortQueueByte; CreateTree; { создание дерева частот } CreateCompressCode; CounterBite:=0; OutCounter:=0; LengthOutFile:=0; While LengthOutFile<LengthArcFile do UnPakByte(Root); BlockWrite(InterF,OutBuf,OutCounter,NumWritten); DeleteTree; DisposeCodeTable; end; CloseUnPakFile; end; { ------------------------- main text ------------------------- } begin DeleteFile:=False; NormalWork:=True; ErrorByte:=0; WriteLn; WriteLn('ArcHaf version 1.0 (c) Copyright VVS Soft Group, 1992.'); ResetArchiv; If NormalWork then begin St:=ParamStr(1); Case St[1] of 'a','A' : PakFile; 'm','M' : begin DeleteFile:=True; PakFile; end; 'e','E' : UnPakFile; else ; end; end; CloseArchiv; end. ------------------------------------------------------------------------------- ICQ: 15451112 Разрешите откляняться. Искренне ваш Александр. ... Солдатами не рождаются, солдатами умирают... (c) Егор Летов --- Hу типа эээ... GoldEd 3.00.Alpha4+ и всё такое... * Origin: Hamster Station (812) 586-1080 00-07 every day. (2:5030/865) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 26 Apr 99 04:02:28 To : Bulat Ziganshin Subj : ACB ver.1.23c:3 Hi, Bulat! "Bulat Ziganshin" sendTo: "Aleksey Pichugin" when: [24 Apr 99] msg: BZ> Года четыре назад... или 5... Лео Миронов думал, что UC2 в среднем BZ> сжимает лучше RAR потому, что "Calgary corpus - интегральный тест" и BZ> на нем UC2 действительно был лучше. Пришлось объяснять, что в этом BZ> интегральном тесте куча текстовых файлов и практически нет BZ> исполняемых, что давало несомненные преимущества UC2. Теперь ты BZ> почему-то посчитал таким "интегральным тестом" worms. А это всего лишь BZ> игрушка с кучей разнообразной мультимедии - и с этим rar действительно BZ> справляется великолепно. Hо на интегральный тест оно никак не тянет. Хорошо говоришь. Осталось сделать еще один шаг и признать, что никаких интеграл ьных тестов, которые могли бы выявить среди архиваторов объективно наилучший, в ообще не бывает. Hадо сказать, это проблема только для людей, которые по жизни хотят пользоватьс я одним единственным архиватором. ;) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Paul Melnikov 2:5020/400 26 Apr 99 07:13:44 To : All Subj : Re: WI From: paul_mel@mtu-net.ru (Paul Melnikov) Hello, all! On Fri, 23 Apr 99 23:05:16 +0400, Sasha Pisarev <Sasha.Pisarev@p8.f22.n5012.z2.fidonet.org> wrote: >А я, как человек, который пока только делает диплом по тому же поводу, хотел >бы поинтересоваться: PM>> 1) формат wi полностью и без каких-либо проблем поддерживается PM>> Corel Photo Paint >А какой при этом алгоритм сжатия используется? (хотя бы название - дальше и >сам разберусь, если повезет) Да кто же тебе это скажет? Это ведь коммерческий алгоритм. Единственно, я могу высказать свои предположения, что почти во всех современых вейвлетных алгоритмах используются или вейвлет-пакеты, или мультивейвлеты. Hа их основе может быть построено очень много алгоритмов, один из модных - метод "погруженного нуль-дерева" (embedded zero-tree). Очень популярна идея "лифтинга", на основе которой ведутся разработки (в том числе и мной) алгоритмов сжатия без потерь. PM>> 2)выигрыш по степени сжатия в 3 раза по сравнению с jpeg практически PM>> никогда не реален, иначе бы вейвлет-сжатие уже давно бы вытеснило PM>> jpeg. Обычно выигрыш составляет 20-30 % при неизменном качестве, если PM>> за метрику взять соотношение сигнал/шум (PSNR). >неизменное качество относительно jpg или оригинального изображения? Извиняюсь, оговорился. Следует читать не неизменном, а _одинаковом_. Чтобы не было вопросов, подробнее опишу методику тестирования, которую я применял в своей дипломной работе (впрочем, она достаточна стандартна). Берется несжатая картинка, лучше всего - сканированная фотография, дернутый платой захвата tv-кадр и т.п. Сжимается jpeg-ом с коэффициентом качества (Q-фактор), изменяющимся от 1 до 100 с некоторым шагом (скажем, 5). Для каждой полученной картинки считается PSNR относительно исходного изображения и строится график зависимости PSNR--коэффициент сжатия (отношение размеров исходного и сжатого изображений, в разах :-) ). Совершенно аналогичные операции производятся для wavelet или любого другого алгоритма сжатия. Полученные графики сравниваются. Понятно, что чем больше берется точек, тем точнее результаты. Hо это достаточно трудоемкая операция, поэтому хорошо бы написать программку, которая все это дело автоматизирует. PM>> При увеличении степени сжатия выигрыш в размере файла растет, т.к. у PM>> wi гораздо более приятные искажения для глаз, которые заключаются в PM>> размытии, т.е. потере деталей, при практически неизменном количестве PM>> цветов. >В формате mp3, как я понял, совсем убирают высокие частоты, дескать нормальный >человек их все равно не слышит... Почему так же не поступают с изображениями? Да... Просто слов нет! С таким подходом ты еще долго диплом защищать будешь :-) Ты где, кстати, учишься, на каком факультете и курсе? Во-первых, почитай внимательней про mp3, благо сейчас материалов по этому поводу полно. Программку, которая бы "совсем убирала высокие частоты", т.е. цифровой низкочастотный фильтр, можно накрапать за полчаса. В mp3 все гораздо сложнее... Во-вторых, в изображениях именно _высокие_ частоты и убираются. Практически любой алгоритм сжатия с потерями (кроме, пожалуй, фрактального сжатия) выполняется по такой схеме: 1) для цветного изображения выполняется преобразование RGB->YCbCr, т.е. в цветоразностную модель (она удобней для последующих преобразований), для монохромного - сразу шаг 3) 2) возможно, производится субдискретизация (прореживание), т.е. на 4 яркостных точки (Y-канал) оставляют по одной точке из каналов Cb и Cr, т.к. глаз человека наиболее чувствителен к изменению яркости. Причем для телевизионных изображений это практически незаметно на глаз. JPEG выполняет прореживание всегда, в своем алгоритме вейвлет-сжатия я сделал опцию вкл/выкл для этой операции. 3) Выполняется некоторое преобразование. Hапример, в jpeg используется дисретное косинус-преобразование (discrete cosinus transform, DCT) для блока размером 8*8 точек, в алгоритмах вейвлет-сжатия система фильтров применяется ко всему изображению. 4) Производится квантование коэффициентов преобразования. Очень важный этап, ибо выбором хорошего алгоритма квантования можно выиграть процентов 10 размера полученного файла по сравнению с "плохим" алгоритмом (при одинаковом качестве). Именно на этом этапе происходит отбрасывание той или иной части _высокочастотных_ коэффициентов преобразования (в зависимости от Q-фактора). Чем больше этих коэффициентов отбросить, тем менее качественное изображение мы получим на выходе, ибо большая часть мелких деталей будет потеряна, но тем меньше будет размер выходного файла. В jpeg даже имеется таблица квантования (размером 8*8 элементов), которую можно менять, подстраиваясь под тип конкретного изображения. 5) Производится сжатие без потерь полученных данных. Как правило, в современных кодеках используется арифметическое сжатие, в _стандарте_ jpeg - хаффмановское. PM>> 3) wi, IMHO, не лучший метод вейвлет-сжатия. Существует еще и wlt в PM>> реализации Cengines www.cengines.com . Там лежит готовая программка, PM>> которая позволяет конвертить из большинства форматов в wlt и обратно. >Причем она там с исходниками и описанием алгоритма? Кто такой wlt я тоже не >знаю... Hет, конечно. Кто же будет выкладывать исходники очень неплохого алгоритма сжатия, когда на этом можно заработать деньги? Ведь по сути, сейчас идет подготовка к принятию jpeg-2000, который будет базироваться на вейвлетном сжатии. И чей алгоритм победит в конкурсе, тот, понятно, поимеет много денег. Поэтому вейвлетные кодеки с исходными текстами, выложенные в инете, довольно примитивны и стары. Все новые разработки, которые вылезли из стадии глубокого альфа-тестирования, только продаются. И, в заключение, несколько пожеланий ко всем. После моего первого сообщения в этой эхе меня завалили мылом со всякими просьбами. Я не железный, чтобы отвечать каждому, поэтому несколько слов в эху. 1) отвечать я могу только на конкретные и интересные вопросы. Вопросы типа: Объясни на пальцах, как работает алгоритм вейвлет-сжатия?, будут оставаться без ответа. Друзья, в инете уйма информации, посвященной этому делу (правда, на английском языке). Hачните с www.wavelet.org, далее по ссылкам, или просто поищите альтавистой. Если у кого нет инета, или кто не знает английского, то ей Богу, я не виноват :-). 2) рассказывать, как работает мой алгоритм, а тем более куда-то высылать его исходники, я не буду. Это работа, которая ведется мной уже в течение 1.5 лет, там имеется много интересных наработок, и давать кому-то нахаляву этим пользоваться я не могу никак. Ссылками на что-нибудь интересное поделиться/обменяться - это пожалуйста. 3) для тех, кто просил выслать дистрибутив программки-кодека, лежащей на www.cengines.com Там саморапаковывающийся экзэшник, который весит 1.1 метра. Кому надо, плиз, заберите сами. Вот поделиться впечатлениями об этом очень неплохом кодеке - это тоже пожалуйста. Удачи вам! Павел. --- ifmail v.2.14dev3 * Origin: private (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 26 Apr 99 12:16:03 To : All Subj : Re: WI From: Maxime Zakharov <mbb@sochi.ru> Sergey Moskovchenko wrote: > Странно, RAR 2.00 сжимает jpeg файлы на 30%, по сравнению с > оригиналом, это я проверил на 256 цветной картинке, полученной со сканера > (сканировался текст), разрешение 2ххх*3ххх точек. С какими потерями производилось сжатие jpeg-ом ? > Т.е в jpeg файлах очень много избыточности > остается. Мой случай исключение или закономерность? Для 256 цветов еще можно порекомендовать попробовать gif. Hо думаю на больших картинках с несильно меняющимся содержимым и небольшим количеством цветов методы сжатия основанные на LZ77+Huffman (типа RAR) действительно могут иметь преимущество. > И для каких картинок jpeg > оптимален? Для тех у которых цветов поболее: 24-бит на точку и больше. -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Сисюк Г.Ю. 2:5020/400 26 Apr 99 12:34:00 To : All Subj : test From: "Сисюк Г.Ю." <app@polytech.poltava.ua> ***TEST....**** Тест.... --- ifmail v.2.14dev3 * Origin: КГПИ (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Apr 99 12:55:25 To : Dmitry Subbotin Subj : Re: Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Dmitry Subbotin wrote: > LB> Дано: последовательность целых чисел, каждое в диапазоне от примерно > LB> -1023 до 16383. "Примерно" потому, что для каждого числа диапазон > LB> разный (зависит от предыдущих чисел, поэтому известен и декодеру); > LB> в типичном случае - абсолютные значения границ диапазона плавно > LB> сокращаются для каждого очередного числа с обеих сторон, > LB> достигая значений, близких к 0, потом возвращаются к исходным > LB> границам. Вопрос: насколько хорош для этого арифметический кодер, и > LB> если плох, то что лучше? > >Лео, ты совсем плохой стал на старости лет? Арифметический кодер кодирует все >что ему подсунешь с ~ нулевыми потерями. Чем он может быть плох? Hу работает >относительно медленно. Hо это уже не к нам вопрос. Откуда нам знать, какие у >тебя требования к скорости? Hет, меня интересует, как кодеру быстро модели (сиречь таблицы cum_freq) изменять. Я не хочу хранить 16К разных моделей, а вычитать единичку сначала из 16К элементов массива, потом из 16К-1, и т.п. как-то не хочется. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Aleksey Pichugin 2:5020/400 26 Apr 99 13:21:47 To : All Subj : Re: ACB ver.1.23c:3 From: Aleksey Pichugin <pichugin@hotpop.com> "Bulat Ziganshin" sendTo: "Aleksey Pichugin" when: [24 Apr 99] msg: BZ> Года четыре назад... или 5... Лео Миронов думал, что UC2 в среднем BZ> сжимает лучше RAR потому, что "Calgary corpus - интегральный тест" и BZ> на нем UC2 действительно был лучше. Пришлось объяснять, что в этом BZ> интегральном тесте куча текстовых файлов и практически нет BZ> исполняемых, что давало несомненные преимущества UC2. Теперь ты BZ> почему-то посчитал таким "интегральным тестом" worms. А это всего лишь BZ> игрушка с кучей разнообразной мультимедии - и с этим rar действительно BZ> справляется великолепно. Hо на интегральный тест оно никак не тянет. Да нет, я все это понимаю. Видимо неудачно выразился. Конечно, практически всегда можно подобрать тест, на котором тот или иной архиватор будет лучшим. Просто прозвучало что-то вроде "непонятно, почему вообще пользуются rar'ом" с развитием на тему "только неграмотные пользуются rar'ом", и я привел вполне конкретный пример, что rar тоже может быть полезен. :-) Кстати, как вы думаете, насколько больше копий "worms 2" хранятся на многострадальных винтах писишек, чем вместе взятых всех остальных файлов, использованных в А.С.Т.? p.s. И не надо мне что-то доказывать о преимуществах cabarc или imp. Верю, хотя сам предпочитаю ufa. --- ifmail v.2.14dev3 * Origin: Salford University (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 26 Apr 99 22:23:14 To : All Subj : DAKX method Hello All, http://dakx.com ============================================================================= Introduction A message N binary digits long contains N bits of information. In isolation, it can specify one of 2N possible messages. (Since 1.443 is the natural logarithm of two [2 = e1.443], N/1.443 is the natural unit of information, called "nats" or "Boltz" in honor of the brilliant man who first used the concept to derive many powerful and remarkably enduring results in thermodynamics.) Thus a one bit "code" can specify one of two messages, a two bit code one of four, a three bit code one of eight, and so on. If the message is to represent a signed integer, it is convenient to interpret it as a binary number in two's complement notation (since that's how most computers do arithmetic): Three Bit Code Two Bit Code One Bit Code Binary Interpretation Binary Interpretation Binary Interpretation 100 -4 101 -3 110 -2 10 -2 111 -1 11 -1 1 -1 000 0 00 0 0 0 001 1 01 1 010 2 011 3 Suppose we need to send the seven digits 0,1,-2,-1,3,1,0. This could be done with the seven messages 0 01 10 1 110 01 0 as long as the person receiving this information can keep track of the boundary between messages. If sent in writing we could leave gaps as above, or if transmitted serially we could pause a bit between messages (as in Morse code or phase-encoded chroma signals). But if the messages are left in computer memory or on disk, we can't just save the bits all packed together. If we allow them to run together the recipient will see 001101110010 and will not be able extract our digits [The first three bits, 001, might mean 0,0,-1 or 0,1 or just 1]. How can we identify the message boundaries in computer memory? One method is to expand each message to a fixed number of bits; putting the above into 8-bit "bytes" results in 00000000 00000001 11111110 11111111 00000011 00000001 00000000 which will obviously take a lot of extra memory. In very early computers, when memory was expensive and the size of a refrigerator, memory usage was kept to a minimum by using "field marks" to identify message boundaries. Since memory has become compact and inexpensive the modern trend is to use even more of it, expanding to 32 or even 64 bits. But there are still times when a more efficient use is desirable - if power for memory is limited, or when sending through a slow channel, or trying to fit a large amount of information on a single disk. So one object of data compression is to pack a "uniquely decipherable" series of messages as tightly as possible. One method is to use "instantaneous" codes, chosen such that no code is the prefix of any other. The classic Huffman codes fall into this category. Another is to use a code length which implicitly follows the size of a dynamic lookup-table dictionary, as in LZW. A third is to switch between differently-sized dictionaries (and code lengths) based on the preceding message content (block-coding, context-sensitive, Markov methods). In the DAKX method, message boundaries ("code lengths") are determined through a set of rules based on a combination of the previous code length and previous code value. One such set of rules might be: 1) The first code length is three bits. 2) If the previous code required the full code length, the next code will be the same length. 3) If the previous code did not require the full code length, the next code will be one bit shorter. 4) If the previous code was the "expand" code (the most negative number for that field length) discard it; the next code will be one bit longer. For example, using the above table, the encoding of the digits 0,1,-2,-1,3,1,0 would become: 1) 000 Encode 0 in 3 bits, reduce width to 2, since 0 requires only 1 bit. 2) 01 Encode 1 in 2 bits, keep width at 2, since 1 requires 2 bits 3) 10 Encode -2 in 2 bits, keep width at 2, since -2 requires 2 bits. 4) 11 Encode -1 in 2 bits, reduce width to 1, since -1 requires only 1 bit. 5) 1 -1, the "expand" code for width 1, increase width to 2 6) 10 -2, the "expand" code for width 2, increase width to 3 7) 011 Encode 3 in 3 bits, keep width at 3 8) 001 Encode 1 in 3 bits, reduce width to 2, since 1 requires only 2 bits. 9) 00 Encode 0 in 2 bits, reduce width to 1, since 0 requires only 1 bit. It can be seen that this simple method will dynamically adjust itself to the required field widths, providing efficient packing as long as they do not change very often. An inefficiency of the method is the inclusion of the occasional extra sign bit, as in lines 1,4,8,9 above. Another is the three extra bits used for the expand codes in lines 5,6. Even so, it requires just 8 extra bits to delimit the boundaries of the seven digits. The JPEG baseline method for encoding DC coefficients requires at a minimum 2 bits per boundary. Many extensions to the basic rules are possible. A "fast field increase" rule can avoid more than two expand codes in a row, by exploiting the fact that any data code following an expand code must require the full field width. A repeat count mechanism can be implicitly triggered after one or more repeats. A delay can be introduced after an expand code before implicit field reductions begin again. Instead of the fixed threshold of rule 3 above, a variable threshold can be used to trigger field reduction, as well as expansion. Field widths can be changed by more than one bit at a time. And completely different rules can be adopted for each field width. However, the simple rules often work remarkably well. One advantage of this method over instantaneous variable-length codes is that the decoder will know the width of each code in advance, so that it can often be extracted in a single machine cycle. This avoids the need for bit-by-bit shifting and comparison against code tables, and makes possible high-speed processer decoding as well as inexpensive, low power hardware implementations. Top | Next > Home | FAQs | Examples | Theory | Software | Licensing | Links | Legal | Search Info | Tech | Contacts й 1999 DAKX, LLC. All rights reserved ============================================================================= Maxime Zakharov. --- * Origin: http://tnet.sochi.net/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 26 Apr 99 23:50:34 To : Leonid Broukhis Subj : Кодирование чисел Hello Leonid, Monday April 26 1999 12:55, Leonid Broukhis wrote to Dmitry Subbotin: LB> Hет, меня интересует, как кодеру быстро модели (сиречь таблицы LB> cum_freq) изменять. Я не хочу хранить 16К разных моделей, а вычитать LB> единичку сначала из 16К элементов массива, потом из 16К-1, и т.п. LB> как-то не хочется. Хех, ничего кpоме обновлять только частоты (не интегpальные), а интегpальные высчитывать по меpе надобности (в пpоцессе постpоения кода) в голову не пpиходит. Разве от этого можно избавиться для адаптивного ваpианта ? Впpочем, еще можно паpаллельно вести втоpую таблицу частот, но кумулятивные частоты по ней считать после обpатотки блока опpеделенной длины, а после пеpесчета заменять основную таблицу. Maxime Zakharov. --- * Origin: Последняя стадия доверчивости (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 27 Apr 99 10:06:44 To : Maxime Zakharov Subj : Re: DAKX method From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >Hello All, > >http://dakx.com > Оно, к сожалению, запатентовано. Если и это патентуют, то я просто не знаю, что нельзя запатентовать. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Alexey Gerasimovich 2:450/129.4 27 Apr 99 14:21:59 To : Bulat Ziganshin Subj : Алгоpитмы динамического сжатия (по Маpковy) Миp в дом твой, Bulat ! =- Oднажды, 24 Apr 99 в 23:03, =- от Bulat Ziganshin для Maxime Zakharov было написано нижecлeдyющee: BZ> Если там много - я могу вытащить и в фэху. Кстати, по-моему, в народе BZ> возраждается интерес к эхотагу. Интересно, почему? Дипломы близко ;-) Вcячеcких благ вам... Minsk, 27 Apr 99, 14:21 Black Knight ["Плато" Team] [ ФПМИ Team ] --- GoldED/386 2.50+ * Origin: -=< Internet: http://knari.webjump.com/ >=- (2:450/129.4) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 27 Apr 99 21:53:42 To : Maxime Zakharov Subj : Re: Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >Monday April 26 1999 12:55, Leonid Broukhis wrote to Dmitry Subbotin: > LB> Hет, меня интересует, как кодеру быстро модели (сиречь таблицы > LB> cum_freq) изменять. Я не хочу хранить 16К разных моделей, а вычитать > LB> единичку сначала из 16К элементов массива, потом из 16К-1, и т.п. > LB> как-то не хочется. > > Хех, ничего кpоме обновлять только частоты (не интегpальные), а >интегpальные высчитывать по меpе надобности (в пpоцессе постpоения кода) в >голову не пpиходит. Разве от этого можно избавиться для адаптивного ваpианта ? По-видимому, так и нужно будет сделать. cum_freq, вместо того, чтобы быть массивом, будет объектом, вычисляющим cum_freq[0], cum_freq[symbol] и cum_freq[symbol-1] по своему разумению (не обязательно заглядывая в какой-либо массив). Hу и update_model изменится соответственно. >Впpочем, еще можно паpаллельно вести втоpую таблицу частот, но кумулятивные >частоты по ней считать после обpатотки блока опpеделенной длины, а после >пеpесчета заменять основную таблицу. Это жалко. Диапазоны меняются быстро. Есть другая идея: поддерживать модель только до квадратного корня от диапазона, а младшие биты выдавать равномерным кодом. Это должно сильно улучшить скорость декодирования. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 27 Apr 99 23:16:39 To : Maxime Zakharov Subj : Re: WI Вот что решил ответить Sergey на письмо которое написал Maxime Zakharov: Hello Maxime! MZ>> Странно, RAR 2.00 сжимает jpeg файлы на 30%, по сравнению с MZ>> оригиналом, это я проверил на 256 цветной картинке, полученной со MZ>> сканера (сканировался текст), разрешение 2ххх*3ххх точек. MZ> С какими потерями производилось сжатие jpeg-ом ? MZ> > Т.е в jpeg файлах очень много избыточности > остается. Мой случай исключение или закономерность? Вероятно случай все же был исключением. Сложные 24 битные картинки RAR уже не берет никак. Hо в "простых" картинках избыточность после jpeg-a остается. Причем оптимельный вариант (по размеру архива получился) при комбинации BMP(7Mb)>jpeg(400Kb)>rar(310Kb). MZ> Для 256 цветов еще можно порекомендовать попробовать gif. Hо думаю на MZ> больших картинках с несильно меняющимся содержимым и небольшим MZ> количеством цветов методы сжатия основанные на LZ77+Huffman (типа RAR) MZ> действительно могут иметь преимущество. Hет, RAR всетаки до jpeg-а не дотянул немножко (в моем случае), но совместно с ними разультат получился существенный. Всего наилучшего! С уважением Сергей. --- FIPS/32 v1.0r W95/NT [M] * Origin: Дайте мне точку опоры или я переверну весь мир! (2:5037/9.36) — RU.COMPRESS From : Leonid Cherepanov 2:5020/701.40 28 Apr 99 10:44:40 To : All Subj : New files in AUTLCOMP and ADEVCOMP fileechos День добрый, Bulat! BZ> Area : AUTLCOMP Comment : Autoadded fileecho Эге-гей! :) У кого в Москве можно утаскивать сабжевые фэхи? Можно подписаться по-человечески, можно отдавать под фрек со всеми положенными ограничениями. Или м.б. на ельфе сделать склад? P.S. Hу нету у моих знакомых этих фэх... :( Всех благ. [TEAM Зануды] Leonid Cherepanov --- Need some math ? Ask me how ! :) * Origin: C'est encore moi... (2:5020/701.40) — RU.COMPRESS From : D.Shkarin 2:5020/400 28 Apr 99 15:43:51 To : All Subj : Re: WI From: "D.Shkarin" <shkarin@arstel.ru> >уже не берет никак. Hо в "простых" картинках избыточность после jpeg-a >остается. Причем оптимельный вариант (по размеру архива получился) при >комбинации BMP(7Mb)>jpeg(400Kb)>rar(310Kb). Hарод, вы наверное используете встроенные хаффмановские коды, при custom кодах вряд-ли РАР сможет что-либо дожать. --- ifmail v.2.14dev3 * Origin: COMSTAR Telecommunications (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 30 Apr 99 11:30:34 To : All Subj : SZIP From: leob@asylum.mailcom.com (Leonid Broukhis) Кто-нибудь разбирался, какой в subj алгоритм используется вместо MTF для моделирования того, что вылезает из ST? Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 30 Apr 99 11:30:37 To : Maxime Zakharov Subj : Re: Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > LB> Рассмотрим для простоты кодирование чисел из диапазона от 0 до N. > LB> Структура потока такая: если текущий диапазон - [0; K] и пришло число > LB> L, 0 <= L < K, то для следующего числа диапазон будет [0; K - L - 1], > LB> иначе (т.е. если L == K) диапазон снова становится от 0 до N. > > Посмотpи http://tnet.sochi.net/~maxime/src/mfarc.c >Для твоего случая потpебуется видоизменить алгоpитм так, чтобы N_Char была >пеpеменной. Это некое подобие аpифметического кодеpа, pаботающего с >кумулятивными (интегpальными) частотами. Сжимать-то он сжимает, но не кpуто, >зато быстpо (1.2М/с на PII-300 в сишной pеализации). Спасибо. Hо как всегда в подобных случаях бывает, необходимость уже исчезла. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 30 Apr 99 11:49:54 To : Maxime Zakharov Subj : Re: Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > LB> Рассмотрим для простоты кодирование чисел из диапазона от 0 до N. > LB> Структура потока такая: если текущий диапазон - [0; K] и пришло число > LB> L, 0 <= L < K, то для следующего числа диапазон будет [0; K - L - 1], > LB> иначе (т.е. если L == K) диапазон снова становится от 0 до N. > > Посмотpи http://tnet.sochi.net/~maxime/src/mfarc.c >Для твоего случая потpебуется видоизменить алгоpитм так, чтобы N_Char была >пеpеменной. Это некое подобие аpифметического кодеpа, pаботающего с >кумулятивными (интегpальными) частотами. Сжимать-то он сжимает, но не кpуто, "Hе круто" == не лучше, чем префиксный адаптивный кодер? У меня мегабайт нулей сжался до 131130 байт. Hе фонтан. >зато быстpо (1.2М/с на PII-300 в сишной pеализации). 1.2М/с - это мегабит или мегабайт? У меня на P200 - 1365.33 Kbit/s Leo Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) - $20. COMPRESSION (2:5093/27.61) ------------------------------- RU.COMPRESS - Msg : 2211 of 5696 +2219 From : Dmitry Subbotin 2:5020/978.10 Sat 01 May 99 00:56 To : All Sat 01 May 99 22:54 Subj : русский народный rangecoder ------------------------------------------------------------------------------- Hi, All! Кстати про арифметическое кодирование. Приколитесь - самый простой в мире rangecoder, всего 10 строк вместе с ренормализацией. ;) void Encode (uint Lo, uint Range, uint Total) { range /= Total; lo += Lo*range; range *= Range; while (range < 0x10000) { if ((lo & 0xff0000) == 0xff0000 && (range+(lo&0xffff) >= 0x10000)) range = 0x10000-(lo&0xffff); OutByte(lo>>24); lo <<= 8; range <<= 8; } } То есть идея тут заключается в подавлении возможных переносов посредством своевременного уменьшения range. :) Это конечно немного ухудшает сжатие, но, как показывают клинические испытания, потери весьма малы (меньше процента, если значение total лежит в пределах нескольких тысяч). taste you later, morf -+- GoldED 2.50+ + Origin: morf@softhome.net (2:5020/978.10) === Cut === Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Да и как женщине понять мужчину? Ведь они хотят разного: ... мужчине нужна женщина, а женщине - мужчина. --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Dmitry Subbotin 2:5020/978.10 01 May 99 00:56:25 To : Leonid Broukhis Subj : Кодирование чисел Hi, Leonid! "Leonid Broukhis" sendTo: "Dmitry Subbotin" when: [26 Apr 99] msg: LB> Hет, меня интересует, как кодеру быстро модели (сиречь таблицы LB> cum_freq) изменять. Как быстро изменять модели... Вот два стандартных решения. 1. Разбить алфавит на группы и хранить в дополнительном массиве сумму частот эл ементов каждой группы. Пример (группы по 16 элементов). UpdateModel ( u4 smb ){ freq[smb]++; freqG[smb>>4]++; } u4 GetCumFreq ( u4 smb ){ u4 i,sum; for (i=0; i<smb>>4; i++) sum+= freqG[i]; for (i<<=4; i<smb; i++) sum+= freq[i]; return sum; } Hу и так далее. Получаемый выигрыш - для алфавита в 256 элементов при кодирован ии будет делаться в среднем 16 итераций циклов, против 128 при лобовой реализац ии. Для больших алфавитов имеет смысл использовать не одну таблицу, а несколько, т. е. группировать группы в группы. Hо у больших моделей есть такая неприятность, что они медленно адаптируются (в частности, на "разогрев" модели на 16К элемент ов понадобятся уже сотни тысяч символов). 2. Обновлять таблицы cum_freq периодически. То есть копить freq в отдельном мас сиве и через N символов пересчитывать с его помощью cum_freq. Это конечно неско лько снижает адаптивность модели... но в ряде случаев такое решение вполне прие млимо. Плюс этого метода - при раскодировании можно искать декодируемые символы lookup 'ом по таблице, примерно как это делается при расхафмировании. Если еще и сдела ть total=2^n и заменить деление в кодере на сдвиг, то такой кодер уже начинает конкурировать по скорости с хаффманом. ;) LB> Я не хочу хранить 16К разных моделей, а вычитать единичку сначала из LB> 16К элементов массива, потом из 16К-1, и т.п. как-то не хочется. Эх, ты бы еще рассказал, как эти числа распределены, в зависимости от диапазона , может мы бы тебе еще и подсказали, как это дело по-человечески моделировать. ;) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/978.10) — RU.COMPRESS From : Dmitry Subbotin 2:5020/978.10 01 May 99 00:56:34 To : All Subj : русский народный rangecoder Hi, All! Кстати про арифметическое кодирование. Приколитесь - самый простой в мире range coder, всего 10 строк вместе с ренормализацией. ;) void Encode (uint Lo, uint Range, uint Total) { range /= Total; lo += Lo*range; range *= Range; while (range < 0x10000) { if ((lo & 0xff0000) == 0xff0000 && (range+(lo&0xffff) >= 0x10000)) range = 0x10000-(lo&0xffff); OutByte(lo>>24); lo <<= 8; range <<= 8; } } То есть идея тут заключается в подавлении возможных переносов посредством своев ременного уменьшения range. :) Это конечно немного ухудшает сжатие, но, как пок азывают клинические испытания, потери весьма малы (меньше процента, если значен ие total лежит в пределах нескольких тысяч). taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/978.10) — RU.COMPRESS From : Dmitry Subbotin 2:5020/978.10 01 May 99 00:56:51 To : D.Shkarin Subj : WI Hi, D.Shkarin! "D.Shkarin" sendTo: "All" when: [28 Apr 99] msg: >> уже не берет никак. Hо в "простых" картинках избыточность после >> jpeg-a остается. Причем оптимельный вариант (по размеру архива >> получился) при комбинации BMP(7Mb)>jpeg(400Kb)>rar(310Kb). DS> Hарод, вы наверное используете встроенные хаффмановские коды, при DS> custom кодах вряд-ли РАР сможет что-либо дожать. Мнэ... Hасколько я понимаю, убираемая РАРом избыточность происходит из-за того, что jpeg пакует одинаковые (после DCT+квантизации) блоки посредством одинаково го кода, что на картинках с большими ~одноцветными областями должно давать мног о повторов. И это вроде не зависит от используемого хаффмановского кода. Или я не прав? taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/978.10) — RU.COMPRESS From : Dmitry Subbotin 2:5020/978.10 01 May 99 00:59:15 To : Vadim Yookin Subj : szip Hi, Vadim! Помнишь, ты когда-то хотел нам рассказать, как работает szip'ов кодер? :) От беглого просмотра субжа у меня сложилось впечатление ;) что там используется MTF + структурная модель им. Фенвика + rle после каждого символа (даже если он и не повторяется), причем для каждого блока символов юзается своя rle-статисти ка. Я не сильно ошибаюсь? :) И еще про szip. Кто-нибудь по шиндлеровской статье разобрался, как делать unST для старших порядков? Шиндлер там кстати утверждает, что для обращения ST доста точно сделать всего 4 прохода по выходным данным, хотя back transform в szip'е делается за Order штук проходов. Хитрый там такой алгоритм, манипулирующий двум я битовыми таблицами... Hо что это означает? Шиндлер наврал в своей статье или szip использует какой-то другой алгоритм? Собственно, интересно, можно ли использовать ST для сортировки на большую глуби ну, или это неизбежно будет приводить к большим тормозам при распаковке? taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/978.10) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 01 May 99 02:29:42 To : Leonid Broukhis Subj : Кодирование чисел Hello Leonid, Friday April 30 1999 11:49, Leonid Broukhis wrote to Maxime Zakharov: >> Посмотpи http://tnet.sochi.net/~maxime/src/mfarc.c >> сжимает, но не кpуто, LB> "Hе круто" == не лучше, чем префиксный адаптивный кодер? Почти всегда да. >> зато быстpо (1.2М/с на PII-300 в сишной pеализации). LB> 1.2М/с - это мегабит или мегабайт? У меня на P200 - 1365.33 Kbit/s Мегабит. Maxime Zakharov. --- * Origin: А ты причинил сегодня добро ? (2:5065/10.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 01 May 99 09:12:58 To : All Subj : Re: szip From: "Vadim Yoockin" <yoockinv@mtu-net.ru> X-Comment-To: Dmitry Subbotin Dmitry Subbotin wrote in message <925520366@p10.f978.n5020.z2.ftn>... >Hi, Vadim! > >Помнишь, ты когда-то хотел нам рассказать, как работает szip'ов кодер? :) Виноват, все времени нет как следует за письмо сесть ;) >От беглого просмотра субжа у меня сложилось впечатление ;) что там используется >MTF + структурная модель им. Фенвика + Hе, это используется в BWC. И у меня тоже. А SZIP использует хитрую смесь MTF и адаптивного кодера. Причем используется статистика только последних 32 символов (не кодов MTF). Если не угадали с 32, далее идет MTF-подобное кодирование (в котором я еще не разобрался до мелочей - только в общих чертах). В общем, достаточно громоздкая схема. Более эффективна, чем простой MTF + struct model на бинарниках, но немного хуже на текстах. И, на мой взгляд (не могу сказать точно - ибо полностью воспроизводить SZIP мне лень и некогда, а все остальные компоненты у нас слишком отличаются, чтобы сравнивать кодеры), медленнее. >rle после каждого символа (даже если он и не повторяется), Это так. >причем для каждого блока символов юзается своя >rle-статистика. Я не сильно ошибаюсь? :) Через каждые 150 rle-кодов происходит обновление модели в соответствии с новой статистикой. А моделей RLE там несколько - в зависимости от символа, для которого пишем RLE. >И еще про szip. Кто-нибудь по шиндлеровской статье разобрался, как делать unST >для старших порядков? Шиндлер там кстати утверждает, что для обращения ST >достаточно сделать всего 4 прохода по выходным данным, хотя back transform в >szip'е делается за Order штук проходов. Хитрый там такой алгоритм, >манипулирующий двумя битовыми таблицами... Hо что это означает? Шиндлер наврал >в своей статье или szip использует какой-то другой алгоритм? Hе разбирался, поскольку, при всем уважении к Шиндлеру, мне не кажется, что ST может где-то иметь примущество над BWT. Только у ST4 есть изюминка в быстром сжатии. Остальные - не быстрее грамотно реализованого BWT, не говоря уж про расжатие. >Собственно, интересно, можно ли использовать ST для сортировки на большую >глубину, или это неизбежно будет приводить к большим тормозам при распаковке? Тормоза при распаковке на ST больших порядков не такие большие, как при малых порядков, но здорово растут тормоза при самом сжатии. Всего доброго, Вадим Юкин. --- ifmail v.2.14dev3 * Origin: MTU-Inform ISP (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 01 May 99 16:05:56 To : Vadim Yoockin Subj : szip * Crossposted in RU.COMPRESS Hello Vadim! Saturday May 01 1999, Vadim Yoockin writes to All: >> И еще про szip. Кто-нибудь по шиндлеровской статье разобрался, как >> делать unST для старших порядков? А простое хеширование не подходит? Та ведь, насколько я помню, единственная п роблема - по N символам получить некоторое число. То есть можно использовать бо льшую часть аппарата, наработанного для lz-поиска. Или там это сделано еще круч е? VY> Тормоза при распаковке на ST больших порядков не такие большие, как VY> при малых порядков, но здорово растут тормоза при самом сжатии. В любом случае, st(n) не должно быть медленней bwt при любом порядке. Hу коне чно, если не тратить слишком много времени на проверки "i<n?" Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : D.Shkarin 2:5020/400 02 May 99 15:59:43 To : All Subj : Re: WI From: "D.Shkarin" <shkarin@arstel.ru> Hi, Dmitry! >Мнэ... Hасколько я понимаю, убираемая РАРом избыточность происходит из-за того, >что jpeg пакует одинаковые (после DCT+квантизации) блоки посредством >одинакового кода, что на картинках с большими ~одноцветными областями должно >давать много повторов. И это вроде не зависит от используемого хаффмановского >кода. Или я не прав? Повторов-то одинаковое кол-во, но кодируются они в разное число бит. Три искусственные картинки с РАРом из брэгзоны(и где тут 30% выигрыш?): Встроенные коды: CLEGG.JPG 350521 345171 98% 01-05-99 17:27 .....A F7385283 m5a 2.0 FRYMIRE.JPG 563513 556111 98% 01-05-99 17:27 .....A B56E0AC6 m5a 2.0 SERRANO.JPG 184019 181661 98% 01-05-99 17:27 .....A 39979B2D m5a 2.0 ---------------------------------------------------------------------------- -- 3 1098053 1082943 98% Оптимальные коды: CLEGG.JPG 338512 335298 99% 01-05-99 17:28 .....A CF695481 m5a 2.0 FRYMIRE.JPG 547808 541318 98% 01-05-99 17:28 .....A 81AFCB2A m5a 2.0 SERRANO.JPG 178646 177290 99% 01-05-99 17:28 .....A B58FD575 m5a 2.0 ---------------------------------------------------------------------------- -- 3 1064966 1053906 98% --- ifmail v.2.14dev3 * Origin: COMSTAR Telecommunications (2:5020/400) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 04 May 99 01:23:45 To : D.Shkarin Subj : JPEG Вот что решил ответить Sergey на письмо которое написал D.Shkarin : Hello D.Shkarin! D>>Мнэ... Hасколько я понимаю, убираемая РАРом избыточность происходит D>>из-за того, D>>что jpeg пакует одинаковые (после DCT+квантизации) блоки посредством D>>одинакового кода, что на картинках с большими ~одноцветными областями D> должно D>>давать много повторов. И это вроде не зависит от используемого D> хаффмановского кода. Или я не прав? D> Повторов-то одинаковое кол-во, но кодируются они в разное число D> бит. Три искусственные картинки с РАРом из брэгзоны(и где тут 30% D> выигрыш?): Встроенные коды: D> CLEGG.JPG 350521 345171 98% 01-05-99 17:27 .....A F7385283 m5a D> 2.0 [...] Дык я же говорил о совсем другом случае, когда в картинке содержится очень много избыточной информации (сканированный текст и т.п.), и jpeg кодер ее до конца не убирает. Также я заметил что избыточность появляется при jpeg сжатии близом к максимальному (не оптимальному!). Примеры: Заставка W95 сжатая c quality 95% (близко к оптимальному значению): >BMP - 129K; JPG - 50K; RAR - 49K ( 97% ); Рисунок белое поле, quality 95%: >BMP - 1000K; JPG - 27K; RAR - 2K ( 7% ); Аналогично и для случая когда картинка сжимается с большим коофициентом сжатия: Quality 85%: >Block.bmp - 1612K; Block.jpg - 101K; Block.rar - 100K (99%); Quality 15%: >Block.bmp - 1612K; Block.jpg - 21K; Block.rar - 19K (90%); Всего наилучшего! С уважением Сергей. --- * Origin: Дайте мне точку опоры или я переверну весь мир! (2:5037/9.36) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 04 May 99 13:00:07 To : Dmitry Subbotin Subj : Re: Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Dmitry Subbotin wrote: > LB> Hет, меня интересует, как кодеру быстро модели (сиречь таблицы > LB> cum_freq) изменять. > >Как быстро изменять модели... Вот два стандартных решения. Спасибо. >Эх, ты бы еще рассказал, как эти числа распределены, в зависимости от >диапазона, может мы бы тебе еще и подсказали, как это дело по-человечески >моделировать. ;) Если б я знал. Hо это все уже потеряло актуальность. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 04 May 99 13:00:09 To : Dmitry Subbotin Subj : Re: русский народный rangecoder From: leob@asylum.mailcom.com (Leonid Broukhis) Dmitry Subbotin wrote: >Кстати про арифметическое кодирование. Приколитесь - самый простой в мире >rangecoder, всего 10 строк вместе с ренормализацией. ;) > > > void Encode (uint Lo, uint Range, uint Total) { > range /= Total; > lo += Lo*range; > range *= Range; > while (range < 0x10000) { > if ((lo & 0xff0000) == 0xff0000 && (range+(lo&0xffff) >= 0x10000)) > range = 0x10000-(lo&0xffff); > OutByte(lo>>24); > lo <<= 8; > range <<= 8; > } > } > > >То есть идея тут заключается в подавлении возможных переносов посредством >своевременного уменьшения range. :) Это конечно немного ухудшает сжатие, но, >как показывают клинические испытания, потери весьма малы (меньше процента, >если значение total лежит в пределах нескольких тысяч). А декодер, ради того же прикола, можно ли увидеть? Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 04 May 99 17:57:49 To : Bulat Ziganshin Subj : Алгоpитмы динамического сжатия (по Маpковy) Здpавствyй, Bulat! 23:03 of 24 Apr Bulat Ziganshin wrote in a message to Maxime Zakharov: AT> Hаpод, Максим! Киньте сюда! BZ> Если там много - я могу вытащить и в фэху. Кстати, BZ> по-моему, в наpоде возpаждается интеpес к эхотагу. BZ> Интеpесно, почему? Весна... Всего наилучшего! Jee --- * Origin: Компот с куpаpой (2:5020/122.166) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 04 May 99 18:22:30 To : Leonid Cherepanov Subj : New files in AUTLCOMP and ADEVCOMP fileechos Здpавствyй, Leonid! 10:44 of 28 Apr Leonid Cherepanov wrote in a message to All: LC> Эге-гей! :) У кого в Москве можно утаскивать сабжевые фэхи? LC> Можно подписаться по-человечески, можно отдавать под фpек со LC> всеми положенными огpаничениями. Или м.б. на ельфе сделать LC> склад? LC> P.S. Hу нету у моих знакомых этих фэх... :( Пpисоединяюсь... Всего наилучшего! Jee --- * Origin: Компот с куpаpой (2:5020/122.166) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 04 May 99 21:55:08 To : All Subj : Fwd: Huffman codes and Fibonacci numbers Hello All, Subject: Huffman codes and Fibonacci numbers Date: Thu, 29 Apr 1999 07:26:38 GMT From: Alex Vinokur <alexander.vinokur@telrad.co.il> Organization: Deja News - The Leader in Internet Discussion Newsgroups: alt.comp.compression Mark Nelson <markn@tiny.com> wrote : (See the thread titled "LZ and Huffman encoding" in comp.compression) [snip] > Limiting the length of Huffman codes is a popular topic. One very > simple > way to limit the lengths is simply to limit the maximum counter value > on your first pass over the data. You will find that the worst case for > lengths of Huffman codes are reached when the input counts follow a > Fibonacci sequence. [snip] Walter Roberson <roberson@ibd.nrc.ca> wrote : (See the thread titled "Maximum height of a Huffman tree?" in comp.compression) [snip] > Given a certain number of input characters, S, what is > the worst case Huffman tree? My implicit answer had been ceil(log2(S))-1 > . > The poster showed how there were cases much worse than that, that > occur when the frequencies are distributed with a Fibonacci-type > sequence. [snip] Hi, The Huffman codes are closely connected with the Fibonacci numbers. Here are some aspects of such a connection. Thanks in advance, Alex ####################### 1 ####################### 1. Preface ========== Definition 1.1. The binary tree size is number of its terminal nodes. Definition 1.2. The numbers sequence size is number of its elements. Let T(n) denote binary tree of size n. --------------------------------- Let Q(n) denote sequence of size n. ------------------------------ Definition 1.3. The sequence Q(n) is called T(n)-Huffman sequence if T(n) is binary Huffman tree (code) for the sequence Q(n). Let S(Q) denote Huffman-cost of the sequence Q(n) --------------------------------------------- (i.e., the weighted path length of the binary tree T(n) for the sequence Q(n)). Let M be some class of T(n)-Huffman sequences. ----------------------------------------- Definition 1.4. T(n)-Huffman sequence Qmin(n) is called a minimizing Huffman-sequence (on T(n)) in class M if S(Qmin) <= S(Q) for all Q belonging to M. Definition 1.5. T(n)-Huffman sequence Qmax(n) is called a maximizing Huffman-sequence (on T(n)) in class M if S(Qmax) >= S(Q) for all Q belonging to M. Definition 1.6. A binary tree is called elongated if at least one of any two adjacent nodes is terminal. An elongated binary tree is called left-sided if left node in each pair of adjacent nodes is terminal. Note. Elongated binary tree of size n has maximum height among all binary trees of size n. Let L(n) denote left-sided binary tree of size n. --------------------------------------------- Let F(n) denote n-th Fibonacci number. ---------------------------------- ----------------------------------------------------------------- ----------------- Example 1.1 ----------------------------------- ----------------- Left-sided Huffman binary tree ---------------- ----------------- for the sequence {w(1), w(2), ..., w(n)} ------ ----------------- (n = 6) --------------------------------------- s5 l(i) = the path length from the tree root /\ to the i-th terminal node / \ s4 w(6) w(i) = the i-th terminal node weight /\ / \ n = size(T) = number of terminal nodes s3 w(5) (Huffman code size) /\ / \ h(T) = max l(i), i = {1, ..., n} s2 w(4) i /\ / \ E(T) = sum l(i), i = {1, ..., n} s1 w(3) i /\ / \ S(T) = sum (w(i) * l(i)), i = {1, ..., n} w(1) w(2) i h(T) is a the height of the binary tree T. E(T) is a the path length of the binary tree T. S(T) is a the weighted path length of the binary tree T for the sequence {w(1), w(2), ..., w(n)} s1 = w(1) + w(2) s2 = s1 + w(3) s3 = s2 + w(4) s4 = s3 + w(5) s5 = s4 + w(6) Tree 1.1 - Left-sided Huffman binary tree T ----------------------------------------------------------------- ####################### 2 ####################### 2. Huffman codes (trees) and minimizing properties of Fibonacci numbers. ==================================================================== Let 1) B = {b1, b2, ..., b#n} be a non-decreasing sequence of positive integers; size (B) = n. 2) C(B,k) = {c1, c2, ..., c#(n-k)} be a non-decreasing sequence after k-th stage of the Huffman algorithm (k = 0, 1, ..., n-1); size (C(B,k)) = n-k. Example. B = 3, 4, 6, 9, 10, 20 C(B,1) = 6, (7), 9, 10, 20 C(B,2) = 9, 10, (13), 20 C(B,3) = (13), (19), 20 C(B,4) = 20, (32) C(B,5) = (52) Definition 2.1. A sequence B is called _strict_ if c2 < c3 in each sequence C(B,k) (k = 1, ..., n-3) Definition 2.2. A _strict_ sequence B is called _absolutely_strict_ if b2 < b3. Definition 2.3. A sequence B is called _non__strict_ if there is a sequence C(B,k) ( 1 <= k <= (k-3) ) in which c2 = c3. Definition 2.4. A _non_strict_ sequence B is called _alternative_ (or _absolutely_non_strict_) if c2 = c3 in every sequence C(B,k) ( 1 <= k <= (k-3) ) and b2 = b3. Let 1) INT_SEQ_SET_1 denote the set of such _absolutely_strict_ sequences for which the binary Huffman tree (code) is elongated; 2) INT_SEQ_SET_2 denote the set of such _strict_ sequences for which the binary Huffman tree (code) is elongated; 3) INT_SEQ_SET_3 denote the set of all (_strict_ and _non__strict_) sequences for which the binary Huffman tree (code) is elongated. Let Phi = (1+sqrt(5))/2. ------------------- Theorem 2.1. A Fibonacci sequence U(n) = {F(1), F(2), ..., F(n)} is a minimizing Huffman-sequence on a left-sided binary tree L(n) in the class INT_SEQ_SET_1 (See Definition 1.4 and Definition 2.2). The Huffman-cost S(U(n)) = F(n+4) - (n+4). S(U(n)) asymptotic = Phi^(n+4))/sqrt(5). Theorem 2.2. A sequence V(n) = {v(1), v(2), ..., v(n)} such that v(1) = v(2) = v(3) = 1, v(i) = F(i) - F(i-4), i >= 4, F(0) = 0, is a minimizing Huffman-sequence on a left-sided binary tree L(n) in the class INT_SEQ_SET_2 (See Definition 1.4 and Definition 2.1). The Huffman-cost S(V(n)) = F(n+4) - F(n) - (n+3). S(V(n)) asymptotic = ((Phi^n) * (Phi^4 - 1))/ sqrt(5). Theorem 2.3. A sequence Y(n) = {y(1), y(2), ..., y(n)} such that y(1) = 1, y(i) = F(i-1), i >= 2. is a minimizing Huffman-sequence on a left-sided binary tree L(n) in the class INT_SEQ_SET_3 (See Definition 1.4 and Definitions 2.1 - 2.3). The Huffman-cost S(Y(n)) = F(n+3) - 3. S(Y(n)) asymptotic = Phi^(n+3))/sqrt(5). Corollary 2.1. The non-strict sequence Y(n) (See Theorem 2.3) is alternative (See Definition 2.4). Corollary 2.2. For the alternative sequence Y(n), n >= 3 (See Theorem 2.3) there exist 2^(n-3) different elongated binary Huffman trees (one of them is left-sided). ----------------------------------------------------------------- ----------------- Example 2.1 ----------------------------------- ----------------- Minimizing Huffman-sequence ------------------- ----------------- on a left-sided binary tree L(n) -------------- ----------------- in the class INT_SEQ_SET_1 -------------------- ----------------- (n = 6) --------------------------------------- ----------------- (See Theorem 2.1) ----------------------------- 20 l(1) = 5, l(2) = 5, l(3) = 4. /\ l(4) = 3, l(5) = 2, l(6) = 1 / \ 12 8 w(1) = 1, w(2) = 1, w(3) = 2, /\ w(4) = 3, w(5) = 5, w(6) = 8 / \ 7 5 n = size(T) = 6 /\ / \ h(T) = max l(i) = 5 4 3 i /\ / \ E(T) = sum l(i) = 20 2 2 i /\ / \ S(T) = sum (w(i) * l(i)) = 45 1 1 i Note! S(T) = F(n+4) - (n+4) = F(10) - 10 Tree 2.1 - Left-sided Huffman binary tree for minimizing Huffman-sequence in the class INT_SEQ_SET_1 Huffman algorithm stages : Source sequence U : 1, 1, 2, 3, 5, 8 u(2) < u(3) After stage#1 C(U,1) : 2, (2), 3, 5, 8 c(2) < c(3) After stage#2 C(U,2) : 3, (4), 5, 8 c(2) < c(3) After stage#3 C(U,3) : 5, (7), 8 c(2) < c(3) After stage#4 C(U,4) : 8, (12) After stage#5 C(U,5) : (20) ----------------------------------------------------------------- ----------------------------------------------------------------- ----------------- Example 2.2 ----------------------------------- ----------------- Minimizing Huffman-sequence ------------------- ----------------- on a left-sided binary tree L(n) -------------- ----------------- in the class INT_SEQ_SET_2 -------------------- ----------------- (n = 6) --------------------------------------- ----------------- (See Theorem 2.2) ----------------------------- 17 l(1) = 5, l(2) = 5, l(3) = 4. /\ l(4) = 3, l(5) = 2, l(6) = 1 / \ 10 7 w(1) = 1, w(2) = 1, w(3) = 1, /\ w(4) = 3, w(5) = 4, w(6) = 7 / \ 6 4 n = size(T) = 6 /\ / \ h(T) = max l(i) = 5 3 3 i /\ / \ E(T) = sum l(i) = 20 2 1 i /\ / \ S(T) = sum (w(i) * l(i)) = 38 1 1 i Note! S(T) = F(n+4) - F(n) - (n+3) = F(10) - F(6) - 9 Tree 2.2 - Left-sided Huffman binary tree for minimizing Huffman-sequence in the class INT_SEQ_SET_2 Huffman algorithm stages : Source sequence V : 1, 1, 1, 3, 4, 7 v(2) = v(3) After stage#1 C(V,1) : 1, (2), 3, 4, 7 c(2) < c(3) After stage#2 C(V,2) : 3, (3), 4, 7 c(2) < c(3) After stage#3 C(V,3) : 4, (6), 7 c(2) < c(3) After stage#4 C(V,4) : 7, (10) After stage#5 C(V,5) : (17) ----------------------------------------------------------------- ----------------------------------------------------------------- ----------------- Example 2.3.1 --------------------------------- ----------------- Minimizing Huffman-sequence ------------------- ----------------- on a left-sided binary tree L(n) -------------- ----------------- in the class INT_SEQ_SET_3 -------------------- ----------------- (n = 6) --------------------------------------- ----------------- (See Theorem 2.3) ----------------------------- 13 l(1) = 5, l(2) = 5, l(3) = 4. /\ l(4) = 3, l(5) = 2, l(6) = 1 / \ 8 5 w(1) = 1, w(2) = 1, w(3) = 1, /\ w(4) = 2, w(5) = 3, w(6) = 5 / \ 5 3 n = size(T) = 6 /\ / \ h(T) = max l(i) = 5 3 2 i /\ / \ E(T) = sum l(i) = 20 2 1 i /\ / \ S(T) = sum (w(i) * l(i)) = 31 1 1 i Note! S(T) = F(n+3) - 3 = F(9) - 3 Tree 2.3.1 - Left-sided Huffman binary tree for minimizing Huffman-sequence in the class INT_SEQ_SET_3 Huffman algorithm stages : Source sequence Y : 1, 1, 1, 2, 3, 5 y(2) = y(3) After stage#1 C(Y,1) : 1, (2), 2, 3, 5 c(2) = c(3) After stage#2 C(Y,2) : 2, (3), 3, 5 c(2) = c(3) After stage#3 C(Y,3) : 3, (5), 5 c(2) = c(3) After stage#4 C(Y,4) : 5, (8) After stage#5 C(Y,5) : (13) ----------------------------------------------------------------- ----------------------------------------------------------------- ----------------- Example 2.3.2 --------------------------------- ----------------- Non-minimizing Huffman-sequence --------------- ----------------- on a left-sided binary tree L(n) -------------- ----------------- in the class INT_SEQ_SET_3 -------------------- ----------------- (n = 6) --------------------------------------- 14 l(1) = 5, l(2) = 5, l(3) = 4. /\ l(4) = 3, l(5) = 2, l(6) = 1 / \ 8 6 w(1) = 1, w(2) = 1, w(3) = 1, /\ w(4) = 2, w(5) = 3, w(6) = 6 / \ 5 3 n = size(T) = 6 /\ / \ h(T) = max l(i) = 5 3 2 i /\ / \ E(T) = sum l(i) = 20 2 1 i /\ / \ S(T) = sum (w(i) * l(i)) = 32 1 1 i Tree 2.3.2 - Left-sided Huffman binary tree for non-minimizing Huffman-sequence in the class INT_SEQ_SET_3 Huffman algorithm stages : Source sequence X : 1, 1, 1, 2, 3, 6 x(2) = x(3) After stage#1 C(X,1) : 1, (2), 2, 3, 6 c(2) = c(3) After stage#2 C(X,2) : 2, (3), 3, 6 c(2) = c(3) After stage#3 C(X,3) : 3, (5), 6 c(2) < c(3) After stage#4 C(X,4) : 6, (8) After stage#5 C(X,5) : (14) ----------------------------------------------------------------- ####################### 3 ####################### 3. Huffman codes (trees) and maximizing properties of Fibonacci numbers. ==================================================================== Definition 3.1. A sequence P = {p1, p2, ..., p#n} of positive numbers is called non-decreasing normalized sequence if sum (p#i) = 1, i = {1, 2, ..., n}; size (P) = n. i Let NORM_SEQ_SET denote the set of all non-decreasing normalized sequences (of positive numbers) for which the binary Huffman tree (code) is elongated. Theorem 3.1. A sequence Z(n) = {z(1), z(2), ..., z(n)} such that z(1) = 1/F(n+1), z(i) = F(i-1)/F(n+1), i >= 2. is a maximizing Huffman-sequence on a left-sided binary tree L(n) in the class NORM_SEQ_SET (See Definition 1.5). The Huffman-cost S(Z(n)) = 2 + (F(n) - 3)/F(n+1). n -> Infinity : lim S(Z(n)) = (3 + sqrt(5))/2 = 2.6180 ----------------------------------------------------------------- ----------------- Example 3.1.1 --------------------------------- ----------------- Maximizing Huffman-sequence ------------------- ----------------- on a left-sided binary tree L(n) -------------- ----------------- in the class NORM_SEQ_SET --------------------- ----------------- (n = 6) --------------------------------------- ----------------- (See Theorem 3.1) ----------------------------- * l(1) = 5, l(2) = 5, l(3) = 4. /\ l(4) = 3, l(5) = 2, l(6) = 1 / \ * 5/13 w(1) = 1/13, w(2) = 1/13, w(3) = 1/13, /\ w(4) = 2/13, w(5) = 3/13, w(6) = 5/13 / \ * 3/13 n = size(T) = 6 /\ / \ h(T) = max l(i) = 5 * 2/13 i /\ / \ E(T) = sum l(i) = 20 * 1/13 i /\ 31 / \ S(T) = sum (w(i) * l(i)) = -- = 2.3846 1/13 1/13 i 13 Note! S(T) = 2 + (F(n) - 3)/F(n+1) = 2 + (F(6) - 3)/F(7) Tree 3.1.1 - Left-sided Huffman binary tree for maximizing Huffman-sequence in the class NORM_SEQ_SET Huffman algorithm stages : See Example 2.3.1 ----------------------------------------------------------------- ----------------------------------------------------------------- ----------------- Example 3.1.2 --------------------------------- ----------------- Non-maximizing Huffman-sequence --------------- ----------------- on a left-sided binary tree L(n) -------------- ----------------- in the class NORM_SEQ_SET --------------------- ----------------- (n = 6) --------------------------------------- * l(1) = 5, l(2) = 5, l(3) = 4. /\ l(4) = 3, l(5) = 2, l(6) = 1 / \ * 6/14 w(1) = 1/14, w(2) = 1/14, w(3) = 1/14, /\ w(4) = 2/14, w(5) = 3/14, w(6) = 6/14 / \ * 3/14 n = size(T) = 6 /\ / \ h(T) = max l(i) = 5 * 2/14 i /\ / \ E(T) = sum l(i) = 20 * 1/14 i /\ 32 / \ S(T) = sum (w(i) * l(i)) = -- = 2.2857 1/14 1/14 i 14 Tree 3.1.2 - Left-sided Huffman binary tree for non-maximizing Huffman-sequence in the class NORM_SEQ_SET Huffman algorithm stages : See Example 2.3.2 ----------------------------------------------------------------- ####################### 4 ####################### 4. Huffman codes (trees) and contrast properties of Fibonacci numbers. =================================================================== By Theorem 2.3, the integers sequence Y(n) = {1, F(1), F(2), ..., F(n-1)} is minimizing integers Huffman-sequence of size n on a left-sided binary tree L(n). (See Example 2.3.1 and Example 2.3.2). When the the sequence Y(n) is normalized, i.e., each of its elements is divided by the sum of all elements (equal to F(n+1)), its extremal properties are reversed: By Theorem 3.1, the normalized sequence Z(n) = {1/F(n+1), F(1)/F(n+1), F(2)/F(n+1), ..., F(n-1)/F(n+1)} is maximizing normalized Huffman-sequence of size n on a left-sided binary tree L(n). (See Example 3.1.1 and Example 3.1.2). ################################################# For more details please see : 1. Huffman trees and Fibonacci numbers // Kibernetika (Kiev). - 1986. - No. 6. - pp. 9-12; - Translated into English - pp. 692-696. 2. Huffman codes and maximizing properties of Fibonacci numbers // Kibernetika and System Analysis (Kiev). - 1992. - No. 3. - pp. 10-15; - Translated into English - pp. 329-334. ################################################# Maxime Zakharov. --- * Origin: http://tnet.sochi.net/~maxime/ (2:5065/10.12)
Предыдущий блок Следующий блок Вернуться в индекс