— 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)
 Предыдущий блок
 Следующий блок
 Вернуться в индекс