<?xml version='1.0' encoding="utf-8"?>
      <rss version='2.0'>
      <channel>
      <title>Форум на Исходниках.RU</title>
      <link>https://forum.sources.ru</link>
      <description>Форум на Исходниках.RU</description>
      <generator>Форум на Исходниках.RU</generator>
  	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=2244133</guid>
        <pubDate>Wed, 15 Apr 2009 16:10:07 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=2244133</link>
        <description><![CDATA[Инночка123: Люди&#33;&#33;&#33;помогите)))где можно найти код примера решения задачи по алгоритму Хаффмана на бейсике????]]></description>
        <author>Инночка123</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=1027772</guid>
        <pubDate>Mon, 27 Feb 2006 07:02:41 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=1027772</link>
        <description><![CDATA[shadeofgray: Что-то в последнее время некрофилы стали доставать заступы и вилы...]]></description>
        <author>shadeofgray</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=1027688</guid>
        <pubDate>Mon, 27 Feb 2006 01:09:15 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=1027688</link>
        <description><![CDATA[Хакас: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>Я имею ввиду, для пользования сжатия по Хаффману обязательно ли сохранять в файл статистику символов??? </div></div><br>
Нет. Достаточно сохранить сам вид дерева. 2 бита на узел. Можно и ещё компактнее.]]></description>
        <author>Хакас</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185731</guid>
        <pubDate>Sat, 27 Apr 2002 16:31:21 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185731</link>
        <description><![CDATA[Demo_S: ладно, проехали:))<br>и так уже топик растянули до невозможности:))).]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185730</guid>
        <pubDate>Sat, 27 Apr 2002 16:28:49 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185730</link>
        <description><![CDATA[Kernel_Panic: Аа.. ты об этом. Я просто не понял вопроса - я думал, типа, временно сохранять дерево до начала кодирования. Короче, неважно..]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185729</guid>
        <pubDate>Sat, 27 Apr 2002 16:22:32 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185729</link>
        <description><![CDATA[Demo_S: не понял, что там за потери точности....<br>если надо хранитьчастоты символов, которые больше 256, то вполне могут начаться глюки при восстановлении по ним дерева (если ты их все переворотишь в байт).<br>я так понимаю, что воротить в байт из ворда будешь просто делением на 256. (ну или там насколько) при этом получишь целые числа.<br>так вот, пусть есть некие символы &quot;а,б,в,г&quot; с частотами 1000,3, 2 и 2.<br>так бы ты при восстановлении дерева сделал<br>1000 3 2 2   <br>1000 4(2+2) 3<br>1000 7(4+3)<br>1007<br><br>коды симолов<br>а -0<br>б -11<br>в 100<br>г 101<br>а после деления всего на 256<br>а б в г<br>3 0 0 0<br>3 0 0(в+г)<br>3 0<br>3<br><br>коды будут<br>а -0<br>б -10<br>в 110<br>г 111<br>дерево не то.... значит и восстановить правлиьно не сумеем...]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185728</guid>
        <pubDate>Thu, 25 Apr 2002 23:17:33 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185728</link>
        <description><![CDATA[Kernel_Panic: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>Вот тут подумал немного. пришел к выводу, что если нормиромать кол-ва вхождений символов, то нельзя потом будет дерево восстановить вообще.</div></div><br>Енто почему же? Представь, что ты сохранял всю инфу о количестве символов в 64-битных переменных. Что тебе помешало бы вернуться к 32-битным? Ты немного потерял бы точность, и вследствие этого слегка пострадала бы степень сжатия. Не больше. Если ты сохранил всё в виде 8-битных чисел, что тут такого??<br><br>И уж совсем не понял, о каких &quot;уровнях дерева&quot; ты говоришь..]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185727</guid>
        <pubDate>Thu, 25 Apr 2002 18:50:56 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185727</link>
        <description><![CDATA[Kernel_Panic: Апыска. Мои извенения.]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185726</guid>
        <pubDate>Thu, 25 Apr 2002 17:17:20 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185726</link>
        <description><![CDATA[7in: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <span class='tag-quote__quote-info'>Kernel Panic, 25.04.02, 02:14:22</span><div class='quote '>7in, ок, верю на слово.</div></div><br>Спасибо тебе огромное!!!<br>P.S. А чему именно ты веришь? :) :) :)]]></description>
        <author>7in</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185725</guid>
        <pubDate>Thu, 25 Apr 2002 13:48:38 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185725</link>
        <description><![CDATA[Demo_S: Вот тут подумал немного. пришел к выводу, что если нормиромать кол-ва вхождений символов, то нельзя потом будет дерево восстановить вообще. тк теряется инфао следующих уровных дерева. можно сохранить инфу только о первых двух.<br>]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185724</guid>
        <pubDate>Thu, 25 Apr 2002 12:19:08 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185724</link>
        <description><![CDATA[Demo_S: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <span class='tag-quote__quote-info'>Kernel Panic, 25.04.02, 02:14:22</span><div class='quote '>7in, ок, верю на слово.<br></div></div> \%))<br><div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '><br> Я, правда, не совсем понимаю, что ты имеешь в виду. Понятно, что есть случаи, в которых в конце концов всё стабилизируется и т. д. Однако это далеко не всегда так, и скорее в большинстве случаев ниччё не получится.<br></div></div><br>что не свосем понятно- это да, я тоже не сразу вьехал\%)<br>случаев, в которых все стабилизируеться, больше. <br>почти всегда, когда наибольший общий делитель длин всех кодов хаффмана равен 1.<br>а у тебя очень часто в дереве будут коды длиной 1, <br>или коды длиной 2 и 3, или 3 и 5.<br>(хотя в принципе это как бы неактуально, тк технологии хранения и передачи данных достаточно надежны)<br><br><div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>Примеры мыльну.</div></div><br>ловлю:)<br><br><br>2andyag не факт, однако если ты себе придумаешь соглашение <br>сохраняю символ, потом его частоту вхождений, нормироманную по байту,<br>потом след символ, частота вхождений которого меньше, то думаю нормально.<br>то есть если есть нпример<br>а 12<br>б 13<br>после нормиромания будет<br>а -0<br>б -0<br>надо сохранить <br>б - 0<br>а - 0<br><br>но можно же сохранять частоты в порядке следвоания символов в алфавите (это чтобы сами символы не писать) и <br>х1х2х3 где х1 &nbsp;вхождение символа а, х2 - символа б и т.д.<br>тогда точно не восстановишь.<br>кстати, идея о такой сохранении дерева - крута, я когда себе делал архивер, даже и не подумал о ней:) теперь сделаю:) спасибо.<br><br>вот еще мысля - можно сохранять кол-ва вхождений символов по порядочку<br>то есть сначала сохранить кол-во входжений сивола а, потом символа б и т.д.<br>но при этом эти самые вхождения сжимать при помощи кодов Элиаса. Фау, ничего себе идейка. надо будет зафигарить себе:)<br><br>Если нужна инфа что есть коды элиаса - пиши, расскажем:))]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185723</guid>
        <pubDate>Thu, 25 Apr 2002 07:26:37 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185723</link>
        <description><![CDATA[andyag: Вопрос.<br>У меня сейчас в файл сохраняется статистика символов в виде:<br><br>char c;<br>long f;<br><br>Если f пронормировать по байту и сохранять<br><br>char c;<br>unsigned char f;<br><br>то можно ли будет восстанавливать дерево без глюков???]]></description>
        <author>andyag</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185722</guid>
        <pubDate>Wed, 24 Apr 2002 22:14:22 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185722</link>
        <description><![CDATA[Kernel_Panic: 7in, ок, верю на слово. Я, правда, не совсем понимаю, что ты имеешь в виду. Понятно, что есть случаи, в которых в конце концов всё стабилизируется и т. д. Однако это далеко не всегда так, и скорее в большинстве случаев ниччё не получится. А как с этим обстоит дело в адаптивных алгоритмах - хз. Не задумывался. Но чё-то мне кажется, что будет приблизительно то же самое, хотя я могу и ошибаться.<br><br>Начиная с разных суффиксов не совсем понятно, но это не страшно.. <br><br>Примеры мыльну.]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185721</guid>
        <pubDate>Wed, 24 Apr 2002 19:43:42 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185721</link>
        <description><![CDATA[Demo_S: 2vot фидошник блин!.. :) что и плюсомет имееться? а как ты будешь [!] ставить и в рид-онли переводить? :)<br><br>2Kernel_Panic <br>по поводу конкретного примера самостабилизирующегося кода.<br>Пусть для алфавита ABCDE есть такие коды<br>A - 1<br>B 000<br>C 001<br>D 010<br>E 011<br>Последоватлеьность BCDAEB представляеться как<br>B &nbsp; &nbsp; C &nbsp; &nbsp; D &nbsp;A &nbsp;E &nbsp; &nbsp; B &nbsp; ABCCCC<br>000 001 010 1 011 000 &nbsp;xxxxxx<br>возьмем и выкинем первый бит.<br>00 001 010 1 011 000 xxxxxx<br>тогда эта последовательность битов раскодируеться как<br>000 010 1 010 1 1 000 xxxxxx<br> B &nbsp; &nbsp; D &nbsp;A &nbsp;D &nbsp; A A B &nbsp; &nbsp;ABCCCC<br>то есть после буквы B (второй) начался код такой же, как и был. изменение его не затронуло.<br>Так происходит для многих вариантов кодов хаффмана.<br>Этот факт обьясняеться тем, что много кодовых слов (011 и 1 например) оканчиваються одинаковой последов символов, поэтому при искажении даных оказываеться что кодер и декодер достигают концов этих последовательностей одновременно.<br>Для префиксных кодов:<br>пусть S - суффикс кодового слова. Если существует последовательность кодовых слов Г и Л таких что SГ=Л то Г являеться синхронизирующей последоватлеьностью для суффикса S.<br>В нашем примере Г=1 (код для А)<br>для суффикса 01 синхронизирующая поселедовательность такая<br>01 1=Л (011 - одно из кодовых слов)<br> S &nbsp;Г<br><br>для суффикса 10:<br>10 &nbsp; &nbsp;011 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;= 100 1 1.<br>суф &nbsp;код слово<br>Если люб суффикс любого кодов слова имеет синхр последоватлеьность, то код будет полностью самосинхронизирующимся.<br>не для любого суфф есть синхр послед - частичноо самосинхр,<br>ни для одного - полностью не самосинхр.<br><br><br>Теорема 1 (доказывать не буду)<br>Последовательность кодов символов будет самосинхронизирующейся когда наибольший общий делитель длин всех кдов будет равен 1.<br>Теорема 2. Послед никогда не будет самосинхронизирующейся, если ни один из суфиксов не являеться кодовым словом.<br><br><br>Ы-Ы-Ы-ЫХ.<br>надеюсь, хоть что-то будет понятно, и местами интерестно:)<br><br>ЗЫ &nbsp;а где же примеры арифметического кодирования?<br>ЗЗЫ а кто мне в слове &quot;колебаться&quot; две звезды вставил? ты его решил чтоли на части разбить. Надо тогда что-нить со словом &quot;мультиканальный&quot; придумать:)))]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185720</guid>
        <pubDate>Wed, 24 Apr 2002 14:50:01 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185720</link>
        <description><![CDATA[Kernel_Panic: vot, ну вот (забавный каламбур, а? ;) ). Пришёл Поручик Ржевский и всё опошлил.. Ок, теперь буду просто использовать слово из трёх букв, которые дети пишут на заборах, без которого не могут жить женщины и которое так бережно охраняют мужчины. (Слово &quot;мир&quot;. А ты что подумал? ;) )]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185719</guid>
        <pubDate>Wed, 24 Apr 2002 08:00:40 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185719</link>
        <description><![CDATA[vot: 2 Kernel Panic: Moderatorial [ * ]<br>2 Demo_s: Moderatorial [ * ]<br><br>  Выбирайте &quot;более другие&quot; примеры :)]]></description>
        <author>vot</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185718</guid>
        <pubDate>Tue, 23 Apr 2002 22:52:45 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185718</link>
        <description><![CDATA[Demo_S: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <span class='tag-quote__quote-info'>Kernel Panic, 24.04.02, 02:12:54</span><div class='quote '><br>
 Надеюсь, я излагаю более или менее доступно.<br>
</div></div>да, спасибо, я понял, очень интерестно:)<br>
<br>
<div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>Вот этого я не совсем понял. Нельзя ли поподробнее?</div></div>вот тебе кусок из книжки/доки<br>
<div class='tag-code'><span class='pre_code'></span><div class='code  code_collapsed ' title='Подсветка синтаксиса доступна зарегистрированным участникам Форума.' style=''><div><div><ol type="1"><div class="code_line">Дерево кода хаффмана непосредственноне представлено маркером, но оно может быть восстановлено из списка чисело кодов каждой битовой </div><div class="code_line">длины. Для каждой битовой длины коды этой длины численно меншье чем префиксы всех кодов большей длины. Недопустимы одинаковые</div><div class="code_line">коды - в этой модели они могут быть только префиксами более длинных кодов.</div><div class="code_line">&nbsp;</div><div class="code_line">Например, еслине сущ кодов длины 1 и 2, имеються два кода длины 3, пять длины 4, тогда первые семь кодов хаффмана будут:</div><div class="code_line">000, 001, 0100, 0101, 0110, 0111, 1000. Болеедлинные коды начнуться с 4-битовых последовательностей 1001 и более. Эти первые семь кдодов будт ассоциироваться</div><div class="code_line">с первыми семью символами в списке Vij.</div><div class="code_line">Последний байт кждого сегмента данных, закодированных по методу хаффмана, заполняеться битом 1. Это не может вызвать распознавание ложного кода хаффмана, поскольку нет кода, содержищго все биты, </div><div class="code_line">равыне 1. Дещифратор достигнет следующего маркера JPEG перед получением полного кода хаффмана.</div></ol></div></div></div></div><script>preloadCodeButtons('1');</script><br>
суть такова:<br>
храниться 16 чисел - кол-во кодов хаффмана соотв длин.<br>
после них идут некие числа/символы Vi- это символы, находящиеся в листьях дерева хаффмана.<br>
на основании этих 16 чисел мы строим дерево хаффмана.<br>
берем число 0. если есть 1 коддлины 1, то коду в дереве 0 ставим в соответствие первый из символов V1;<br>
добавляем к числу 1. сдвигаем на 1 влево. получаем 10 (если бы коды с длиной 1 не было,получили бы 00)<br>
если есть код с длиной 2, то коду 10 ставим в соответствие V2.<br>
(если число 00, то если есть коды с диной 2, например из 16 чисел второе равно 2, то коду 00 ставим в соотв число V1 (на первом шаге его не поставили) коду 01 ставим в соотв V2 (если бы было 3 кода, то коду 10 поставили бы V3) )<br>
...<br>
есть число 10010. есть 5 кодов длины 5.<br>
 в 10010 - первый из них<br>
в 10011 - второй<br>
в 10100 - третий<br>
в 10101 - 4<br>
в 10110 - 5.<br>
потом число становиться 101100 и снова таже история для кодов дины 6.<br>
<br>
только дерево должно облдать каким-то св-вом типа &quot;каждое левое поддерево небольше правого&quot; т.е. любое дерево сохранить так не удасться... хотя сдаеться мне, что есть способы сохранения любых деревьев, тоже экономные. поспрошаю еще:)<br>
<br>
<div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>%) Если хочешь, могу отмылить сырцы примеров из той книжки. Она с двумя пятидюймовыми дискетами продаётся, так что.. =)<br>
</div></div>давай.<br>
<div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '><br>
Неееее..... =)  Предположим, есть у тебя последовательность битов:<br>
01 010111 101011110<br>
и т. п., которая раскодируется как<br>
Это к примеру, конечно.<br>
И представь, что второй бит превратился из единицы в ноль. Получится:<br>
000 101 11 1010 11110<br>
Вариант не идеальный, но придумывать что-то умное впадляк. И объясни мне, в чём в этом случае принципиальная разница между статическим и динамическим методами? ;) В любом случае получится не то, что нужно.. Это только если использовать фиксированные длины кодируемых данных, то можно чего-то такого избежать. Но тогда.. почему бы не пользовать ASCII? ;)</div></div>Ы... как бы долго обьяснять, но ...<br>
 в статическом после определенного места пойдет неповредженный код.<br>
после изменения бита станет<br>
могу привести конкретные примеры.<br>
вообще этот эффект наблюдается не для каждого набора данных, но как правило он присутствует. только вот длина участка стабилизации (на котором глюки, но после которого неизменный текст) может колебаться.<br>
кроме того, к самостабилизирующимся относиться также метод фиббоначчи. <br>
а вот динамический ХАффмана, коды элиаса (вроде бы), и шеннона-фано не явл. самостабилизирующимися.<br>
причем динамич хаффмана не самостабилизир, из-за того, что алфавит храниться вместе с кодами.<br>
ЗЫ конкретный пример даду завтра, седни лом искать, поздно.<br>
ЗЗЫ классная у тебя подпись:))]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185717</guid>
        <pubDate>Tue, 23 Apr 2002 22:12:54 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185717</link>
        <description><![CDATA[Kernel_Panic: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>Не понял, что есть кодирование 2, 3 порядка.</div></div>Не знаю, так ли это называется по-нашему, но суть такова. Вместо обыкновенного сжатия (когда создаётся статистика для каждого символа) используется более продвинутый метод. Т.к. в большинстве случаев можно предсказать вероятность употребления определённого символа после предыдущего (скажем, в английских текстах: вероятность более 99%, что после q идёт u), этим фактом нельзя не воспользоваться. В результате получаем следующее. Встречается нам в английском тексте буква q. Мы знаем, что по статистике (возможно, нами же и выявленной) после неё в 99% случаев следует u, поэтому при построении деревьев Хаффмана (а их уже 256, т.е. для каждого байта; а может, и больше) мы указываем, что для _данного_контекста_ (сразу после буквы q) единицу следует использовать для обозначения буквы u, а на ноль разветвлять все остальные буквы (ну, может, сокращение какое-нибудь). Надеюсь, идея более или менее ясна. Так же и для модели третьего порядка. Теперь уже учитываются _два_ предыдущих символа. В примере с тем же q и u наибольшую вероятность следования после них имеют (насколько я знаю) символы e и a. Поэтому их расписываем на 00 и 01 (двоичные), а единицу отдаём на откуп врагам. Ээ.. хмм.. другим, в общем, символам. А если представить, что мы работали бы в модели 1-го порядка (вообще-то, по-моему, это называется модель 0-го порядка; так что не мешало бы у всех порядков поотнимать по единице; я вполне мог чё-нить перепутать) - так вот, в модели этого-самого 1-го (или нулевого) порядка буквы u и a имели бы совсем не такие вероятности. Вследствие чего сжималось бы всё хреновее. Надеюсь, я излагаю более или менее доступно.<br>
<br>
<div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>там от дерева хранятсья только количества кодов</div></div>Вот этого я не совсем понял. Нельзя ли поподробнее?<br>
<br>
<div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>а пример или дока по этому арифметическому кодированию есть?.</div></div>%) Если хочешь, могу отмылить сырцы примеров из той книжки. Она с двумя пятидюймовыми дискетами продаётся, так что.. =)<br>
<br>
<div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>А вот динамический не обладает таким сво-вом. в нем если испортиться хоть один бит (выпадет, измениться с 1 на 0 или с 0 на 1) то заглючит вся оставшаяся часть архива.</div></div>Неееее..... =) Падажи... %) Предположим, есть у тебя последовательность битов:<br>
01 010111 101011110<br>
и т. п., которая раскодируется как<br>
<br>
Это к примеру, конечно.<br>
И представь, что второй бит превратился из единицы в ноль. Получится:<br>
000 101 11 1010 11110<br>
<br>
Вариант не идеальный, но придумывать что-то умное впадляк. И объясни мне, в чём в этом случае принципиальная разница между статическим и динамическим методами? ;) В любом случае получится не то, что нужно.. Это только если использовать фиксированные длины кодируемых данных, то можно чего-то такого избежать. Но тогда.. почему бы не пользовать ASCII? ;)]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185716</guid>
        <pubDate>Tue, 23 Apr 2002 20:06:55 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185716</link>
        <description><![CDATA[Demo_S: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <span class='tag-quote__quote-info'>Kernel Panic, 23.04.02, 12:29:21</span><div class='quote '><br><br>Насчёт степени сжатия. Статический упаковщик должен будет хранить в файле дерево. А если делать упаковщик второго или третьего порядка (когда кодирование каждого символа зависит от предыдущего), то вместо 256 элементов в дереве получаем 65536 и больше<br></div></div><br>Не понял, что есть кодирование 2, 3 порядка.<br>есть способы, чтобы хранить дерево, так чтобы оно не занимало много места.<br>например тот способ, какой использует жпег. там от дерева хранятсья только количества кодов определенной длины. то есть массив 1..16 - i-тый эл-т которого - кол-во кодов длины i. Только для этого нужно дерево специальное строить, чтобы его омжно было так записать.<br><div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <span class='tag-quote__quote-info'>Kernel Panic, 23.04.02, 12:29:21</span><div class='quote '><br><br>Книги в инете вроде нету.</div></div><br>жаль...<br>а пример или дока по этому арифметическому кодированию есть?.<br><br><br>насчет архиваторов, насколько я знаю, рар пользует LZW+HUFFMAN(статический)<br><br>О еще вспомнил, статический вариант есть самовосстанавливающийся. т.е. если возникнетошибка в записи данных (пропадет один бит, или измениться на противоположный) то глюкавая обл-ть затронет только какую-то часть архива. <br>например для оригинального архива 12341234123412341234<br>если где-то сглючит, то получиться типа 12341223321212341234<br>Это конечно неприемлеме для прог, а вот для картинок можно.<br>А вот динамический не обладает таким сво-вом. в нем если испортиться хоть один бит (выпадет, измениться с 1 на 0 или с 0 на 1) то заглючит вся оставшаяся частьархива.]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185715</guid>
        <pubDate>Tue, 23 Apr 2002 16:55:34 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185715</link>
        <description><![CDATA[Kernel_Panic: Об арифметическом сжатии можно лишь сказать, что оно лучше, чем сжатие по Хаффману. Оно (само по себе) не использует словарей, и поэтому его возможности ограничены.<br><br>Кстати, в ЗИПе действительно используется словарный метод (один из LZ*) в сочетании с кодом Хаффмана (статическим, насколько я помню). А в LHA (по-моему) пользуют вместо Хаффмана арифметическое.]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185714</guid>
        <pubDate>Tue, 23 Apr 2002 14:34:09 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185714</link>
        <description><![CDATA[murph: арифметическое сжатие само по себе - не так уж хорошо, но и к нему можно прикрутить словарь и будет рулез. Мне казалось, что рар на этом основан, хотя это догадки.]]></description>
        <author>murph</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185713</guid>
        <pubDate>Tue, 23 Apr 2002 08:29:21 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185713</link>
        <description><![CDATA[Kernel_Panic: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>Для динамического метода дерево не создаеться заново для каждого символа</div></div><br>Угу, я ж писал типа &quot;это можно представить, как...&quot;. Фактически дерево становится таким, как если бы его построили заново.<br><br>Насчёт степени сжатия. Статический упаковщик должен будет хранить в файле дерево. А если делать упаковщик второго или третьего порядка (когда кодирование каждого символа зависит от предыдущего), то вместо 256 элементов в дереве получаем 65536 и больше. Поэтому дерево в файл не пишется; оно создаётся на лету. При этом используется управляющий символ, который в сжатом потоке указывает, что следующий символ нужно добавить в таблицу. Таким образом, этот управляющий символ - единственное, что влияет на размер получающегося при сжатии файла. Насколько я понимаю.<br><br>Книги в инете вроде нету.]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185712</guid>
        <pubDate>Sun, 21 Apr 2002 16:16:30 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185712</link>
        <description><![CDATA[andyag: Люди, а арифметическое сжатие сильно жмет???]]></description>
        <author>andyag</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185711</guid>
        <pubDate>Sat, 20 Apr 2002 19:34:32 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185711</link>
        <description><![CDATA[Demo_S: 2Kernel_Panic<br>Для динамического метода дерево не создаеться заново для каждого символа, а перестраиваеться. и все данные (закодированные) созадаютсья за один проход, в то время, как для статического метода нужно два прохода по файлу данных - один для вычисления частот, другой для кодирования.<br><br>Насчет кто лучше сжимает - <br>насколько я помню, для динамического есть оценка<br>[S-N+1,2S+t-4N+2]<br>где S - длина статического кода хаффмана для этой последовательности,<br>N - длина алфавита, <br>t - число сообщений (хз, наверное длина незакодированного сообщения)<br><br>отсюда - на некоторых наборах данных динамический может быть лучше статического, на N-1 код, в на других наборах данных - почти в два раза длиннее...<br>хотя в среднем статический все же чуть лучше сживает, чем динамический.<br><br>А вот с арифметическим буду разбираться... надо, и полезно будет наверное:)<br><br>слушай, а книги, что ты говоришь, в инете нет случайно?]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185710</guid>
        <pubDate>Sat, 20 Apr 2002 16:08:26 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185710</link>
        <description><![CDATA[Kernel_Panic: Для статического метода - да. И у упаковщика, и у распаковщика должна быть копия дерева. Т.е. или ты должен сохранять дерево в файл, или использовать всегда одно и то же дерево (но это очень редко применяется; к тому же, для каждого типа файлов статистика будет разная, поэтому этот способ эффективен только при сжатии одного типа файлов).<br><br>При использовании динамического метода дерево сохранять не нужно. И упаковщик, и распаковщик начинают работу с пустым деревом (или с одним символом типа Escape, которым ты будешь указывать, что следующий символ нужно добавить в дерево). И по ходу дела перестраивают его.]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185709</guid>
        <pubDate>Sat, 20 Apr 2002 14:38:53 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185709</link>
        <description><![CDATA[andyag: Я имею ввиду, для пользования сжатия по Хаффману обязательно ли сохранять в файл статистику символов???]]></description>
        <author>andyag</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185708</guid>
        <pubDate>Fri, 19 Apr 2002 21:11:51 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185708</link>
        <description><![CDATA[Kernel_Panic: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <div class='quote '>имхо наоборот</div></div><br>Да нет. Представь, что ты некоторое время вычилсяешь какую-то функцию, потом запоминаешь её результат и с этим результатом работаешь. С другой стороны, представь, что ты эту функцию вычисляешь для каждого байта данных :) .<br>То же самое и со статическим методом Хаффмана против динамического (адаптивного). Для динамического тебе придётся после каждого байта данных подправлять дерево, т.к. статистика изменилась. В общем, при динамическом методе каждый символ рассматривается, как последний. Т.е. это можно представить, так: ты прочитал один байт - создал дерево. Переместился в файле на байт дальше - создал дерево заново. Ещё дальше - опять. ...Только всё это можно оптимизировать.. Вот поэтому и получаются быстрые динамические алгоритмы сжатия :) ..<br><br>Арифметическое кодирование действительно медленнее, но позволяет сжимать данные гораздо лучше, чем метод Хаффмана, т.к., как я уже писал, максимальное сжатие по Хаффману - 8:1 (8 битов к одному биту, если использовать 8-битные слова), а для арифметического способа соотношение не ограничено :) .<br><br>ЗЫ. Доказательство - всё в той же книге: &quot;The Data Compression Book&quot;.]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185707</guid>
        <pubDate>Fri, 19 Apr 2002 20:31:35 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185707</link>
        <description><![CDATA[Demo_S: <div class='tag-quote'><span class='tag-quote-prefix'>Цитата</span> <span class='tag-quote__quote-info'>Kernel_Panic, 19.04.02, 22:42:31</span><div class='quote '>Алгоритм Хаффмана используется статический и динамический (с построением дерева на лету). Последний - самый медленный, но также и наиболее эффективный. </div></div><br>:) имхо наоборот.<br><br>кстати, про арифметическое кодирование:<br>я думал оно несколько медлненнее, труднее в реализации и сжимает чуть хуже чем статический метод хаффмана.<br>нам на лекции это вроде даже доказали, через энтропии всякие...<br>(хотя может доказывали и не совсем это, я не очень внимательно слушал, кстати зря..)<br><br>]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185706</guid>
        <pubDate>Fri, 19 Apr 2002 18:42:31 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185706</link>
        <description><![CDATA[Kernel_Panic: Из дерева Хаффмана, вероятнее всего, и получается код Хаффмана. =)<br>Я тоже не совсем понял, что имел в виду andyag. Дерево Хаффмана - это, фактически, двоичное дерево, по которому можно узнать (при наличии статистических данных) какой последовательностью бит выгоднее всего кодировать данный символ. Алгоритм Хаффмана используется статический и динамический (с построением дерева на лету). Последний - самый медленный, но также и наиболее эффективный. А вообще, я бы порекоммендовал пользовать т.н. арифметическое кодирование.. Алгоритм Хаффмана позволяет кодировать один байт (или, скажем, слово, или что ты там выберешь) минимум одним битом. Арифметическое кодирование позволяет сжимать одну единицу (байт, слово и т. д.) до бесконечного малой доли бита.<br><br>ЗЫ. Кстати, если серьёзно занимаешься этим, почитай &quot;The Data Compression Book&quot; Марка Нельсона.]]></description>
        <author>Kernel_Panic</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185705</guid>
        <pubDate>Fri, 19 Apr 2002 18:22:00 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185705</link>
        <description><![CDATA[Demo_S: скорее всего &quot;да конечно&quot;<br><br>только не очень понятно, что же ты имел ввиду<br>под построением дерева по коду..<br>что это за код и откуда ты его берешь?]]></description>
        <author>Demo_S</author>
        <category>Алгоритмы</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185704</guid>
        <pubDate>Thu, 18 Apr 2002 17:01:03 +0000</pubDate>
        <title>Дерево Хаффмана</title>
        <link>https://forum.sources.ru/index.php?showtopic=26287&amp;view=findpost&amp;p=185704</link>
        <description><![CDATA[andyag: Слышал, что можно строить сабж по коду Хаффмана. Это реально?]]></description>
        <author>andyag</author>
        <category>Алгоритмы</category>
      </item>
	
      </channel>
      </rss>
	