ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : EinWill                              2:5020/400     22 Oct 2001  10:01:50
 To : All
 Subject : И еще раз, об оптимальном сжатии...
 -------------------------------------------------------------------------------- 
 

 И еще раз, приветствую всех.
 
  Hи одно доброе дело не остается безнаказанным.
                                           Томас Брукс.
 
 Это я к тому, что (как здесь уже верно сказали) излогаю методику subj, все
 несколько напутал...
 
 Более простым и даже более эффективным методом является, такой:
 Хранить массив из 256 элментнов (для "байтового" алфавита); значение
 элемента -- длина кода соответствующего символа. Возвращаясь к старому
 примеру, для дерева:
 А    Б  Г      Д    В
 5    10 11    14    40
  \  /     \  /     /
   15       25    /
     \    /     /
       40     /
         \  /
          80
 это будет вот такой массив: [3,3,1,3,3]. То есть, буква A у нас кодируется 3
 битами, буквы Б, Г и Д -- тоже тремя, а вот буква В -- одним битом.
 
 Далее идея аналогична изложенной в предыдущем письме: по такому массиву мы
 фиксированным образом строим новое дерево, и именно его используем для
 кодирования/декодирования информации.
 
 Так как "размах" длин, используемых для кодирования, как правило, не
 превышает 16, то, соответственно, можно тратить по 4 бита для передачи
 каждого элемента. Таким образом, массив передается ~ 130 байтами.
 
 Избыточность информации (как отмечалось, многие коды имеют одну и ту же
 длину) можно сократить, если _полученный массив_ тоже сжать Huffman'ом.
 Только это сжатие лучше проводить либо статическим деревом (заранее
 построенным по некоторой репрезентативной выборке), либо (что эффективнее,
 но сложнее) используя динамическое кодирование Huffman'а (когда алгоритм
 Huffman'а стартует с некоторого фиксированного дерева, а по ходу кодирования
 дерево перестраивается с учетом уже обработанной информации).
 
 Что до моих изысканий... А пусть себе живут, может кто и придумает ситуацию,
 когда будут полезны изложенные там идеи. :-)
 
 --
 .... C Уважением,  EinWill
 --- ifmail v.2.15dev5
  * Origin: Fidolook Express 2.000  www.fidolook.da.ru (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор