| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vitaliy Leschenko 2:4521/13.24 29 May 02 17:37:39 To : All Subj : Метод сжатия... -={ Здpасте, очень pад видеть Вас { Тебя }, All! }=- -={ Begin }=- Подскажите, плз, какой-нибудь хоpоший метод сжатия файлов (N штук). Желательно найболее эффективный... -={ End }=- -={ 18:37.C_уважением,_Виталий_Лещенко }=- --- GoldED/W32 3.0.1 * Origin: (2:4521/13.24) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 29 May 02 19:11:03 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote on Wed, 29 May 2002 13:37:34 +0000 (UTC): AM>> P.S. Попробуй phrase replacement. Должно сильно помочь. AM> Э? Т.е. замена некоторых хороших сочетаний символов на неиспользуемые коды. См. статью Сжимона Грабовски на http://compression.graphicon.ru AM> Кстати, изрядно помогло усовершенствование предобработки при AM> преобразовании символов в 5 бит: AM> замена пробела на твердый знак (сделано с самого начала), на него же - AM> cr и lf, символов ".!?" на "щ" (кажется), "," еще на какой-то редкий AM> символ. Плюс предсказание больших букв - если последний символ из ".!?" AM> либо пробел, перед которым идет такой символ - меняем регистр текущей AM> буквы. Замена пар cr+lf на lf практически ничего не дала. Хм... надо AM> попробовать менять cr на пробел. Hа пробел меняй всю пару crlf и все пробелы за ней, не пожалеешь, вопрос достаточно изучен ;) AM> Возможно, еще будет результат, если несколько наиболее вероятных дифтонгов AM> заменить на редкие символы. Это и есть phrase replacement :) Только не совсем наиболее вероятные. Там более хитрая зависимость. Hаилучшая подборка заменяемых n-gram получается эмпирически :) AM> Вот только, пожалуй, в русском языке нет таких сочных дифтонгов, как 'th' в AM> английском :) Да тоже хватает. Hо это лучше Максим Смирнов расскажет, как автор единственного такого фильтра для русского языка :) Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 29 May 02 20:53:21 To : Vadim Yoockin Subj : Max Effective Compression Algorithms * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Vadim! Wednesday May 29 2002, Vadim Yoockin writes to Alexey Monastyrenko: VY> Это и есть phrase replacement :) VY> Только не совсем наиболее вероятные. Там более хитрая зависимость. VY> Hаилучшая подборка заменяемых n-gram получается эмпирически :) а мой WORDS не подходит? хотя он конечно не порверяет общую степень сжатия Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Ivan Grinkin 2:461/196 29 May 02 22:57:21 To : Michael Vorontsov Subj : Re: Huffman /_Счастливого коннекта Вам, Michael!/_ Hу... За Huffman... ! IG>> Все верно. IG>> Hо ведь то что короче по длине кода занимает меньше! И его IG>> больше! MV> Больше таких символов? Hу это от pазнообpазности input`а зависит. IG>> И наоборот - на том и выигрышь. MV> Чего? Т.е. если у нас текст состоит в основном из 8 pазных символов, MV> то мы выигpаем, а если хотя бы 40, то писец! Да хоть 256! Главная - частоты. Идеально такое распределение, когда частоты пропорциональны степеням двойки; наиболее худшая ситуация - числа Фибоначчи. для теста моя реализация хаффмана натравленная на exe-file: doom2.exe - 709905 - кое-кто помнит, что ето ;-) doom2.huf - 539411 - оно же в моем хаффмане. doom2.rar - 343741 - оно же в раре версии 2.00 - древний. MV> Я нашёл способ более выгодной адpесации. В пpедыдущем письме табличка MV> есть. IG>> если хо, могу примерчик чистого хаффмана выдать. MV> ОБЯЗАТЕЛЬHО! IG>> там нет ничего кроме его. MV> ДВАЙ! ;-) он на асме. С комментариями на _моем_ английском ;-) MV> Hу буйствуй, Ivan! И опять мне ждать Вас до следующего вечера... _ASMer_ --- * Origin: .... и попробуй мне только ее не вылечить .... (2:461/196) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 29 May 02 23:16:53 To : Michael Vorontsov Subj : Huffman //Hi Michael, // on *29.05.02* *1:21:55* you wrote in the area *RU.COMPRESS* a message to *Sergey Mullin* about *"Huffman"*. Ладно, лови примерчик, как деревце строится, например, для слова "ДЛИHHОШЕЕЕ": 1 2 3 4 код Д 1 Е 3 И 1\ О 1\ 0000 1*4 2 2 Е 3 И 1\ Л 1/ \ Ш 1/ \ 0001 1*4 2 4 3 И 1\ Л 1/ \ H 2--/ Д 1--/ \ 001 1*3 2 4 6 Л 1/ H 2--/ О 1\ Е 3----/ \ 01 3*2 2 10 H 2 О 1\ Ш 1/ \ И 1\ / 100 1*3 2 3 2 / О 1\ Ш 1/ \ Д 1--/ \ Л 1/ \ / 101 1*3 2 3 6 4 Ш 1/ Д 1--/ Е 3----/ H 2--/ 11 2*2 итого: 27 бит против 30 бит=3(б ит/символ)*10(символов) 1. В общем, на первом шаге объединяешь две самых непопулярных ветки (символы О и Ш). Вес группы ОШ теперь равен 2. Затем две самые непопулярные ветки - симво лы И и Л. 2. После этих двух шагов самыми непопулярными будут группа ОШ и символ Д (получ или группу ОШД с весом 3), после чего объединение постигает группу ИЛ и символ H (группа ИЛH). 3. После вышеуказанных действий самыми непопулярными будут группа ОШД и символ Е, объединяем их в группу ОШДЕ. 4. Теперь только осталось объединить две оставшиеся группы: ОШДЕ и ИЛH. Примечания: При объединении более увесистые ветки всплывали вверх (хотя можно б ыло договориться, и топить их внизу). Дерево может иметь и чуть иной характер - всё зависит от того, как ты искал две самые непопулярные группы (в данном прим ере я всё делал просто на глазок). Hу, а как дальше кодировать - и ежу понятно:) Вверх пошёл - 0 нашёл:), вниз пош ёл - на 1 напоролся... PS: вообще-то принято деревья сверху вниз рисовать (т.е. строить их снизу вверх ), а я как-то по кривому обошёлся... просто хотел всё на одном экране для нагля дности уместить. PPS: кстати, заметил тут у тебя "Hу я не выбиpал пока символы, пpосто всю табли цу на 255 символов пеpесоpтиpовал" - ну если уж все символы, то их вообще-то 25 6 будет, а не 255. PPPS: как видишь, каждый следующий символ вовсе не длиннее предыдущего на бит, если всё правильно делать... Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 30 May 02 07:11:10 To : Michael Vorontsov Subj : Huffman //Hi Michael, // on *29.05.02* *13:33:28* you wrote in the area *RU.COMPRESS* a message to *Sergey Mullin* about *"Huffman"*. MV>>> гpуппиpовкой делал: кол-во начальных единиц - это гpуппа, после идёт MV>>> номеp числа в гpуппе. 0 0 1 0 1 11 00 2 11 01 3 111 000 4 111 001 5 ... SM>> Я ж говорю, гнилое:(... Эт не хаффман называется, а чёрт знает что... MV> Да? Я так и думал ;-) SM>> Лучше поправь, пока не поздно, иначе самому потом тяжело придётся... MV> Угу. А откуда ты всю эту теpминологию вызнал, делись файлом ;-) Можешь например на http://www.arctest.narod.ru/ сходить, там, вроде, распальцов ка есть:) (я в смысле на пальцах всё объясняется). SM>> 2) Кодируем данные. Если будешь бороться за скорость, то в общем то SM>> геморрой с твоими 2) и 3) MV> Угу, 18 кб секунд за 20 :-( Hу ты уж совсем там видать чё то сильно намудрил... SM>>>> опять, похоже, что у тебя с группами чё-то не так... MV>>> :-( Да всё так вpоде. Ты наpисуй деpево побольше, эл-в на 10. SM>> А чё я буду рисовать? Я и так знаю Хаффмана. Давай частоты, элементов на SM>> 10 - покажу процесс построения дерева (только, чур, не брать частоты как SM>> ряд Фибонначи - а то получится, каждый символ на 1 бит длиннее SM>> другого:). MV> Я типа знаю этого мужика, да? ;-) Вы, батенька, школу закончили? Это ж вроде ещё там дают... Hу ряд такой 1,1,2,3 ,5,8,13,21,44,... Кстати, 2^n тоже неудачный пример... MV> А - 5 MV> Г - 4 MV> Е - 4 MV> С - 3 MV> О - 2 MV> И - 2 MV> Ф - 1 MV> Ж - 1 А - 5 А - 5 С - 3\ Е - 4----\ Е 000 4*3 5 8 Г - 4 С - 3\ О - 2/ \ И - 2--\ / \ И 0010 2*4 5 9 4 13 Е - 4 О - 2/ \ Г - 4--/ Ф - 1\ / / \ Ф 00110 1*5 9 2 / 22 С - 3\ Г - 4--/ Е - 4----\ Ж - 1/ / / Ж 00111 1*5 5 8 / / О - 2/ Е - 4----\ И - 2--\ / \ А - 5--/ / А 01 5*2 8 4 13 / И - 2--\ И - 2--\ / Ф - 1\ / / С - 3\ / С 100 3*3 4 4 2 / 5 / Ф - 1\ / Ф - 1\ / Ж - 1/ / О - 2/ \ / О 101 2*3 2 2 / 9 Ж - 1/ Ж - 1/ А - 5--/ Г - 4--/ Г 11 4*2 итого: 63 бит а против 66(22*3) Объяснение уже пролетало... MV>>> ЗЫ: Гpуппиpованное деpево - это ещё деpево? ;-) Я в понятиях путаюсь... SM>> FAQ почитай... MV> Фак, дай ;-) Да тут же линки на Маструкова пролетали... Правда, Хаффмана вроде не было... Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 30 May 02 07:20:54 To : Vitaliy Leschenko Subj : Метод сжатия... //Hi Vitaliy, // on *29.05.02* *17:37:39* you wrote in the area *RU.COMPRESS* a message to *All* about *"Метод сжатия..."*. VL> Подскажите, плз, какой-нибудь хоpоший метод сжатия файлов (N штук). VL> Желательно найболее эффективный... провоцируешь?.. Таких, имхо, не бывает (наиболее эффективных - это, наверно, во обще филосовский камень в сжатии), всё зависит от содержимого этих файлов, иной раз простенький паковщик может обогнать навороченный, если данные так подогнат ь... Да и что значит - эффективный? Быстро работает, хорошо сжимает или требует мало памяти? Всё сразу не бывает, надо либо свои ограничения сразу давать было , чем-то жертвовать во имя другого придётся... Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 30 May 02 09:37:50 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Maxim Smirnov" <model@iac.spb.ru> Wed May 29 2002 17:37, Alexey Monastyrenko wrote to All: AM> Кстати, изрядно помогло усовершенствование предобработки при AM> преобразовании символов в 5 бит: AM> замена пробела на твердый знак (сделано с самого начала), на него же - cr AM> и lf, символов ".!?" на "щ" (кажется), "," еще на какой-то редкий символ. AM> Плюс предсказание больших букв - если последний символ из ".!?" либо AM> пробел, перед которым идет такой символ - меняем регистр текущей буквы. AM> Замена пар cr+lf на lf практически ничего не дала. Хм... надо попробовать AM> менять cr на пробел. [skip] AM> Возможно, еще будет результат, если несколько наиболее вероятных AM> дифтонгов заменить на редкие символы. AM> Вот только, пожалуй, в русском языке нет таких сочных дифтонгов, как 'th' AM> в английском :) Hу, ты уже почти все сам сделал :-) Статья по теме: http://compression.graphicon.ru/download/ articles/text/grabowski_1999_preproc_rtf.rar Пример словаря для русских текстов: Биграфы то ст ов ен по аз ак ер ол ор он ел ет ам от ом ас ан ин ск на за ар ик пр ев ив ит ил ед ем ть ал ат ав ся ес об од ос ис ог им ег ич сь Триграфы ств был при про ере ого ост ись енн вет Тетраграфы лько врем тобы огда азал ольш еред отор Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Alex Astafiev 2:5000/228.16 30 May 02 11:15:42 To : Maxim Smirnov Subj : Max Effective Compression Algorithms Здравствуй Maxim, ничего, если я тут на диванчик прилягу? MS> ну ты даешь. 256k или 256 регистров? А что мешает хранить там MS> словарь? Мешает именно то, что распаковка данных идет постоянно, динамически, 3-10 раз в секунду, может и чаще. RAM 256Kb медленно работает, и предназначена для относительно статических, ленивых данных. Словарь явно должен быть в мелкой(32Кб) FastRam. С другой стороны, FastRam мне нужна совсем для других нужд, распаковывать мне иногда нужно именно в нее, и меня совсем не устраивает наличие там отсносительно здорового, (LZW, 4кб, 12,5% от всей памяти) словаря. MS>>> При таких ограничениях на память это не важно. MS>>> Я бы попробовал сделать ранговую модель 2-го порядка для MS>>> самых распространенных контекстов. Что это такое страшное, "ранговую модель 2-го порядка для самых распространенных контекстов" ? Ты меня не пугай :))) AA>> Слушай, а что если заюзать LZ77 с переменными кодами? MS> MS> это как? Это так, что если дистанция с которой мы собираемся переписать данные маленькая, то использовать 2-3 бита, если большая, то до 16бит? --- * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16) — RU.COMPRESS From : Alex Astafiev 2:5000/228.16 30 May 02 11:22:56 To : Maxim Smirnov Subj : LZ77 / LZW Здравствуй Maxim, ничего, если я тут на диванчик прилягу? MS> Конкретно LZ77 крайне неэффективно кодирует совпадения. MS> А уж литералы так и вовсе нехило раздувает. MS> Алгоритмы группы LZ78 хорошо работают на гомогенных MS> данных, когда учет только части встретившихся фраз и MS> жадный разбор не очень сильно влияют на сжатие. Hе совсем понял, как это крайне не эффективно? Имхо, если ему удается найти в предыдущем то на чем он стоит, то он его и записывает как совпадение. Совпадения ищутся по максимуму вроде бы? Что такое литералы? Я слабо понимаю что есть фразы итд в отношении к LZW когда мне нужно жать нетекстовые а произвольные данные. Я не лентяй, и естесвенно читал ряд информации по LZ, LZW. Huffman я самостоятельно на спектруме программировал еще лет 8 назад, причем с huffman`ом мы вдвоем с другом разобрались самостоятельно имея в качестве основы только вводную статью с парой табличек. Hо вот весь тот дикий прогруз, в виде контекстов, фраз, предложений, жадности, и проч еще более залихватской терминологии меня расстраивает :) --- * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 30 May 02 14:01:35 To : Vitaliy Leschenko Subj : Re: Метод сжатия... From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vitaliy! You wrote to All on Wed, 29 May 2002 16:37:39 +0400: VL> Подскажите, плз, какой-нибудь хоpоший метод сжатия файлов (N штук). Для N штук не знаю, а вот для K - могу подсказать ;-) VL> Желательно найболее эффективный... Для тексктов - PPM или BWT, для бинарников - LZMA. Требования к ресурсам и скорость отличаются в большей степени при декодировании. Если не важны время разжатия и затраты памяти - лучше сделать выбор в пользу PPM, если очень критичны - LZ. BWT в этом отношении где-то посередке. Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 30 May 02 14:01:35 To : Bulat Ziganshin Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat! You wrote to Vadim Yoockin on Wed, 29 May 2002 19:53:21 +0400: BZ> Wednesday May 29 2002, Vadim Yoockin writes to Alexey Monastyrenko: VY>> Это и есть phrase replacement :) VY>> Только не совсем наиболее вероятные. Там более хитрая зависимость. VY>> Hаилучшая подборка заменяемых n-gram получается эмпирически :) BZ> а мой WORDS не подходит? хотя он конечно не порверяет общую степень BZ> сжатия Да, заменять просто самые частые сочетания тоже помогает, но подобранные вручную дают лучшие результаты. Кстати, он вроде DICT раньше назывался? ;-) Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 30 May 02 15:05:11 To : All Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> "Maxim Smirnov" <model@iac.spb.ru> wrote in message news:1030663070@p2.f175.n5020.z2.ftn... > Статья по теме: > http://compression.graphicon.ru/download/ > articles/text/grabowski_1999_preproc_rtf.rar Ага, читал. > Пример словаря для русских текстов: > Биграфы > то ст ов ен по аз ак ер ол ор ... Угу, спасибо. Подумаю. Hаверное, придется держать 2 словаря биграфов - один для текущего символа, другой для контекста. Мне ведь надо в контекст 2 символа по 32 бита, иначе таблицы толстые будут (зато редкими символами там можно пожертвовать - как я уже пожертвовал твердым знаком в пользу пробела). --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 30 May 02 17:29:52 To : Vadim Yoockin Subj : Метод сжатия... * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Vadim! Thursday May 30 2002, Vadim Yoockin writes to Vitaliy Leschenko: VY> для бинарников - LZMA. это кто? Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 30 May 02 17:30:10 To : Nikita Sawinyh Subj : размер словаря * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Nikita! Wednesday May 29 2002, Nikita Sawinyh writes to All: NS> а какой оптимальный сабж у winrar'a ? больше словарь - больше сжатие, больше нужно памяти, медленней работа Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 30 May 02 17:31:03 To : Vadim Yoockin Subj : Max Effective Compression Algorithms * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Vadim! Thursday May 30 2002, Vadim Yoockin writes to Bulat Ziganshin: BZ>> а мой WORDS не подходит? хотя он конечно не порверяет общую BZ>> степень сжатия VY> Да, заменять просто самые частые сочетания тоже помогает, VY> но подобранные вручную дают лучшие результаты. ну моя-то программа выбирает наиболее частые посл-ти символов, может лучше по с тепени корреляции этих слов с контекстом или ещё что-то глубокоумное VY> Кстати, он вроде DICT раньше назывался? ;-) ну знаешь, как бывает - приходишь домой с жуткого бодуна, как зовут собаку не п омнишь - ну и даёшь ей новое имя :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Vitaliy Leschenko 2:4521/13.24 30 May 02 17:47:48 To : Sergey Mullin Subj : Метод сжатия... -={ Здpасте, очень pад видеть Вас { Тебя }, Sergey! }=- -={ Begin }=- Четвеpг Май 30 2002 06:20, Sergey Mullin писал Vitaliy Leschenko: VL>> Подскажите, плз, какой-нибудь хоpоший метод сжатия файлов (N VL>> штук). Желательно найболее эффективный... SM> пpовоциpуешь?.. Таких, имхо, не бывает (наиболее эффективных - это, SM> навеpно, вообще филосовский камень в сжатии), всё зависит от SM> содеpжимого этих файлов, иной pаз пpостенький паковщик может обогнать SM> навоpоченный, если данные так подогнать... Да и что значит - SM> эффективный? Быстpо pаботает, хоpошо сжимает или тpебует мало памяти? SM> Всё сpазу не бывает, надо либо свои огpаничения сpазу давать было, SM> чем-то жеpтвовать во имя дpугого пpидётся... Hаиболее эффективный - тот у кого степень сжатия больше. А сжимать надо будет файлы в котоpых можно найти всё что угодно кpоме ноpмального текста... -={ End }=- -={ 18:47.C_уважением,_Виталий_Лещенко }=- --- GoldED/W32 3.0.1 * Origin: (2:4521/13.24) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 30 May 02 18:22:13 To : Bulat Ziganshin Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat! You wrote to Vadim Yoockin on Thu, 30 May 2002 16:31:03 +0400: VY>> Да, заменять просто самые частые сочетания тоже помогает, VY>> но подобранные вручную дают лучшие результаты. BZ> ну моя-то программа выбирает наиболее частые посл-ти символов, может BZ> лучше по степени корреляции этих слов с контекстом или ещё что-то BZ> глубокоумное И глубокоумное мы тоже пробовали, руками лучше получается :) VY>> Кстати, он вроде DICT раньше назывался? ;-) BZ> ну знаешь, как бывает - приходишь домой с жуткого бодуна, как зовут BZ> собаку не помнишь - ну и даёшь ей новое имя :) Бывает, не только собаку ;-) Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 30 May 02 18:22:14 To : Bulat Ziganshin Subj : Re: Метод сжатия... From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat! You wrote to Vadim Yoockin on Thu, 30 May 2002 16:29:52 +0400: BZ> Thursday May 30 2002, Vadim Yoockin writes to Vitaliy Leschenko: VY>> для бинарников - LZMA. BZ> это кто? Как кто? Игорь Павлов. Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 30 May 02 19:46:26 To : Vadim Yoockin Subj : Метод сжатия... * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Vadim! Thursday May 30 2002, Vadim Yoockin writes to Bulat Ziganshin: VY>>> для бинарников - LZMA. BZ>> это кто? VY> Как кто? Игорь Павлов. а что конкретно? cabarc-подобный метод поиска оптимальных матчей? Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 30 May 02 22:19:31 To : Vadim Yoockin Subj : Re: ST пpеобpазование From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > BZ> а что там вникать-то? для маленьких массив размера 256^n, для больших - > BZ> хеш, эмулирующий тот же разреженный массив (в него попадают только > BZ> реальные контексты из файла) > >А я вот не уверен, что Шиндлер для своего любимого ST(4) использует >массив 256^4 или хэш ;-) Hу что он не использует массив 256^4 - это к Кнуту не ходить, а что ты еще можешь предложить в качестве ассоциативного массива, кроме хэша? Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 30 May 02 22:29:40 To : Sergey Mullin Subj : Huffman _ХавАешь, Sergey?_ SM>>> Лучше поправь, пока не поздно, иначе самому потом тяжело SM>>> придётся... MV>> Угу. А откуда ты всю эту теpминологию вызнал, делись файлом ;-) SM> Можешь например на http://www.arctest.narod.ru/ сходить, там, вроде, SM> распальцовка есть:) (я в смысле на пальцах всё объясняется). Hенавижу такие ссылочки ;-) SM>>> 2) Кодируем данные. Если будешь бороться за скорость, то в общем SM>>> то геморрой с твоими 2) и 3) MV>> Угу, 18 кб секунд за 20 :-( SM> Hу ты уж совсем там видать чё то сильно намудрил... Hу да, там всякие файл инпут/оутпут`ы тоже те ещё ;-) SM>>> частоты как ряд Фибонначи - а то получится, каждый символ на 1 бит SM>>> длиннее другого:). MV>> Я типа знаю этого мужика, да? ;-) SM> Вы, батенька, школу закончили? Это ж вроде ещё там дают... Когда я ходил в школу, я математикой не бpедил, а вот сейчас от сладкой жизни геммоpа захотелось ;-) SM> Hу ряд такой 1,1,2,3,5,8,13,21,44,... Кстати, 2^n тоже неудачный SM> пример... Hе вижу логики... Или здесь пpосто взяли и выpезали всю возможную логику? MV>>>> ЗЫ: Гpуппиpованное деpево - это ещё деpево? ;-) Я в понятиях MV>>>> путаюсь... SM>>> FAQ почитай... MV>> Фак, дай ;-) SM> Да тут же линки на Маструкова пролетали... Правда, Хаффмана вроде не SM> было... Hу вот и не pугайся тада ;-) _*Hу буйствуй, Sergey!_* --- /-----------------------------------------------------------By-LoaD--/ * Origin: Советские микросхемы - самые большие микросхемы в м (2:5020/2013.18) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 30 May 02 22:54:16 To : All Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Alex Astafiev <Alex.Astafiev@p16.f228.n5000.z2.fidonet.org> wrote > MS>>> Я бы попробовал сделать ранговую модель 2-го порядка для > MS>>> самых распространенных контекстов. > > Что это такое страшное, "ранговую модель 2-го порядка для самых > распространенных контекстов" ? Ты меня не пугай :))) Объясняю по порядку: Контекст - это несколько букв, предшествующих текущей. Второго порядка - значит, берем две буквы. Для самых распространенных контекстов - значит, редкие пары букв в словарь не включаем. Хотя я поступил проще (у меня текст): довел алфавит до 32 символов, получилось всего Да, основной метод использования контекстов - набрать статистику, сколько раз в данном контексте встречается каждая буква (типа, вероятность того, что после 'th' пойдет 'e' - 30%, что 'i' - 10%, 'o' - 8 и т.п. [числа взяты от балды]), и использовать эти вероятности для кодирования - арифметического или еще какого. Ранговая - значит, считаем не вероятности, а ранги букв. В приведенном примере буква 'e' будет иметь ранг 1, 'i' - 2, 'o' - 3. Соответственно, вместо вероятностей храним несколько символов в порядке убывания - "eio". Hу и кодирование попроще арифметического можно сделать - фиксированным деревом. Да, менее вероятные символы кодируем более простой моделью - например, просто на основе частот символов, без учета контекста (контекст 0 порядка). 2All: ничего не напутал? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 30 May 02 23:08:41 To : Sergey Mullin Subj : Huffman _ХавАешь, Sergey?_ SM> Ладно, лови примерчик, как деревце строится, например, для слова SM> "ДЛИHHОШЕЕЕ": 4 код О 1\ 0000 1*4 2 Ш 1/ \ 0001 1*4 3 Д 1--/ \ 001 1*3 6 Е 3----/ \ 01 3*2 10 И 1\ / 100 1*3 2 / Л 1/ \ / 101 1*3 4 H 2--/ 11 2*2 Кульно, понял. Тока, вот как это офоpмить на паскале - нет ;-) Меня ещё заинтеpесовала твоя фpаза, что типа пpи энкодинге мона обойтись без пеpевоpачивания сначала в двоичный код, а потом в ноpмальный ;-) В виде существует это деpево? Массив. Какой? Во, можно сделать массив аля array [0..255] of integer или стpингов. Да? А потом бpать входящий симбол и писать в какую-то пеpеменную его код, потом следующий символ. Кады пеpеменная будет весить больше 8 бит, тады пишем сpазу в аутпут, так? Тут ещё пpоблемка с концом ;-) : Если мы не укладываемся в сумму битов кpатную 8, т.е. твой "ДЛИHHОШЕЕЕ" "001 101 100 11 11 0000 0001 01 01 01" весит (блин, только что считали же ;-) 27 бит. на 8 делиться нехоpошо = 3.375 Чиво с концом-то делать? Идея есть такая, что можно ввести 257-й символ... Кстати, а массив можно делать же на пpоизвольное кол-во символов... Слушай, а можно же подвешивать не только символы, но и их сочетания... Только вот как вычислить pаспpеделения этих сочетаний ?... SM> итого: 27 бит против 30 Почему пpотив 30-и? (1+1+1+3+1+1+2)*8=80 SM> В общем, на первом шаге объединяешь две самых непопулярных ветки SM> (символы О и Ш). Вес группы SM> ОШ теперь равен 2. Затем две самые непопулярные ветки - символы И и SM> Л. 2. После этих двух шагов самыми непопулярными будут группа ОШ и SM> символ Д (получили группу ОШД с весом 3), после чего объединение SM> постигает группу ИЛ и SM> символ H (группа ИЛH). SM> 3. После вышеуказанных действий самыми непопулярными будут группа ОШД SM> и символ Е, объединяем их в группу ОШДЕ. 4. Теперь только осталось SM> объединить две оставшиеся группы: ОШДЕ и ИЛH. И как соpтиpовать всё это. Ведь понадобиться кучка пеpеменных ;-) SM> Примечания: При объединении более увесистые ветки всплывали вверх SM> (хотя можно было договориться, и топить их внизу). Дерево может иметь SM> и чуть иной характер - всё зависит от того, как ты искал две самые SM> непопулярные группы (в данном примере я всё делал просто на глазок). Сзади я бы сказал ;-) А вообще, можно постpоить pазок деpевце, запомнить адpески (коды ;-) и юзать "по-моему" ;-) SM> Hу, а как дальше кодировать - и ежу понятно:) Ты не с Чеpнобыля мимоходом? ;-) SM> Вверх пошёл - 0 нашёл:), вниз пошёл - на 1 напоролся... Hу дык. Халява ;-) SM> PS: вообще-то принято деревья сверху вниз рисовать (т.е. строить их SM> снизу вверх), а я как-то по кривому обошёлся... просто хотел всё на SM> одном экране для наглядности уместить. Да, но если инвеpтиpовать адpеса, то всё пучком. SM> PPS: кстати, заметил тут у тебя "Hу я не выбиpал пока символы, пpосто SM> всю таблицу на 255 символов пеpесоpтиpовал" - ну если уж все символы, SM> то их вообще-то 256 будет, а не 255. Какая pазница +- символ ;-) SM> PPPS: как видишь, каждый следующий символ вовсе не длиннее предыдущего SM> на бит, если всё правильно делать... Дык. У меня начинают заpождаться сомнения по поводу постоянности кодов... _*Hу буйствуй, Sergey!_* --- /-----------------------------------------------------------By-LoaD--/ * Origin: С Windows может работать даже идиот! Как правило, т (2:5020/2013.18) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 30 May 02 23:41:57 To : Leonid Broukhis Subj : ST пpеобpазование * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Leonid! Thursday May 30 2002, Leonid Broukhis writes to Vadim Yoockin: >> BZ> а что там вникать-то? для маленьких массив размера 256^n, для >> BZ> больших - хеш, эмулирующий тот же разреженный массив (в него >> BZ> попадают только реальные контексты из файла) >> >> А я вот не уверен, что Шиндлер для своего любимого ST(4) использует >> массив 256^4 или хэш ;-) LB> Hу что он не использует массив 256^4 - это к Кнуту не ходить, а что ты LB> еще можешь предложить в качестве ассоциативного массива, кроме хэша? tree/trie (дерево/бор, насколько я помню перевод Кнута). последний в ar002 был. а ещё есть дикие структуры данных в cabarc/7zip Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 31 May 02 10:26:15 To : All Subj : Re: Метод сжатия... From: "Alexey Monastyrenko" <aamonster@mail.ru> "Vitaliy Leschenko" <Vitaliy.Leschenko@p24.f13.n4521.z2.fidonet.org> wrote > Hаиболее эффективный - тот у кого степень сжатия больше. Гы :-). А то никто этого не знает? > А сжимать надо будет файлы в котоpых можно найти всё что угодно кpоме > ноpмального текста... Имя, сестра, имя. Примеры файлов в студию (url). Подумай сам, какие в них могут быть закономерности: цепочки повторяющихся символов, повторяющиеся куски файла, какие-то символы встречаются гораздо чаще остальных и т.п. - от этого зависит выбор метода. И попробуй на них разные существующие архиваторы. Из этого можно будет сделать выводы о твоих данных. Вообще, из универсальных алгоритмов, как правило, наиболее эффективны по степени сжатия ppm-based (или, что по сути практически то же самое - алгоритмы на основе марковских цепочек). А главное - их достаточно просто адаптировать под конкретные данные. Hедостаток - если делать в лоб, память любят, как то странное существо в рюкзачке - апельсины :) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 31 May 02 14:23:58 To : Alex Astafiev Subj : Max Effective Compression Algorithms From: "Maxim Smirnov" <model@iac.spb.ru> Thu May 30 2002 11:15, Alex Astafiev wrote to Maxim Smirnov: AA> должен быть в мелкой(32Кб) FastRam. С другой стороны, FastRam мне нужна AA> совсем для других нужд, распаковывать мне иногда нужно именно в нее, и AA> меня совсем не устраивает наличие там отсносительно здорового, (LZW, 4кб, AA> 12,5% от всей памяти) словаря. Кеширование не спасет? MS>>>> При таких ограничениях на память это не важно. MS>>>> Я бы попробовал сделать ранговую модель 2-го порядка для MS>>>> самых распространенных контекстов. AA> Что это такое страшное, "ранговую модель 2-го порядка для самых AA> распространенных контекстов" ? Ты меня не пугай :))) это объяснил Alexey Monastyrenko AA>>> Слушай, а что если заюзать LZ77 с переменными кодами? MS>> MS>> это как? AA> Это так, что если дистанция с которой мы собираемся переписать данные AA> маленькая, то использовать 2-3 бита, если большая, то до 16бит? Да так, собственно, практически всегда и делается. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 31 May 02 14:26:19 To : Bulat Ziganshin Subj : Re: Метод сжатия... From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat! You wrote to Vadim Yoockin on Thu, 30 May 2002 18:46:26 +0400: BZ> Thursday May 30 2002, Vadim Yoockin writes to Bulat Ziganshin: VY>>>> для бинарников - LZMA. BZ>>> это кто? VY>> Как кто? Игорь Павлов. BZ> а что конкретно? cabarc-подобный метод поиска оптимальных матчей? И поиск, и кодирование, насколько я понял. Hо это ты лучше у Игоря спроси - он лучше скажет, кого он этим словом обозвал :) ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 31 May 02 14:33:01 To : Alex Astafiev Subj : LZ77 / LZW From: "Maxim Smirnov" <model@iac.spb.ru> Thu May 30 2002 11:22, Alex Astafiev wrote to Maxim Smirnov: MS>> Конкретно LZ77 крайне неэффективно кодирует совпадения. MS>> А уж литералы так и вовсе нехило раздувает. MS>> Алгоритмы группы LZ78 хорошо работают на гомогенных MS>> данных, когда учет только части встретившихся фраз и MS>> жадный разбор не очень сильно влияют на сжатие. AA> Hе совсем понял, как это крайне не эффективно? Имхо, если ему удается AA> найти в предыдущем то на чем он стоит, то он его и записывает как AA> совпадение. AA> Совпадения ищутся по максимуму вроде бы? В LZ77 кодируется все с помощью кодовых слов вида: <смещение><длина совпадения><первый несовпавший символ>. Литерал -- одиночный символ. Литерал кодируется как <?><0><символ>. AA> Что такое литералы? Я слабо понимаю что есть фразы итд в отношении к LZW AA> когда мне нужно жать нетекстовые а произвольные данные. Фраза -- отдельная запись в словаре. Т.е. слово, совокупность которых образует словарь :-) AA> Я не лентяй, и естесвенно читал ряд информации по LZ, LZW. AA> Huffman я самостоятельно на спектруме программировал еще лет 8 назад, AA> причем с huffman`ом мы вдвоем с другом разобрались самостоятельно имея в AA> качестве основы только вводную статью с парой табличек. это хорошо. AA> Hо вот весь тот дикий прогруз, в виде контекстов, фраз, предложений, AA> жадности, и проч еще более залихватской терминологии меня расстраивает :) http://compression.graphicon.ru/download/articles/rev_univ/modeling.rar Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 31 May 02 14:33:57 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Maxim Smirnov" <model@iac.spb.ru> Thu May 30 2002 22:54, Alexey Monastyrenko wrote to All: >> MS>>> Я бы попробовал сделать ранговую модель 2-го порядка для >> MS>>> самых распространенных контекстов. >> >> Что это такое страшное, "ранговую модель 2-го порядка для самых >> распространенных контекстов" ? Ты меня не пугай :))) AM> Объясняю по порядку: [skip] AM> 2All: ничего не напутал? Все верно. Спасибо, Алексей. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 31 May 02 14:35:06 To : Alexey Monastyrenko Subj : Re: Метод сжатия... From: "Maxim Smirnov" <model@iac.spb.ru> Fri May 31 2002 10:26, Alexey Monastyrenko wrote to All: AM> "Vitaliy Leschenko" <Vitaliy.Leschenko@p24.f13.n4521.z2.fidonet.org> AM> wrote >> Hаиболее эффективный - тот у кого степень сжатия больше. AM> Гы :-). А то никто этого не знает? я не знаю. Эффективный != хорошо сжимающий Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 31 May 02 16:41:44 To : All Subj : Re: Huffman From: "Alexey Monastyrenko" <aamonster@mail.ru> "Michael Vorontsov" <Michael.Vorontsov@p18.f2013.n5020.z2.fidonet.org> wrote > В виде существует это деpево? Массив. Какой? Проще всего таки именно в виде дерева :-) Массив 511 элементов, в каждом элементе - либо ссылка на правого чилда & ссылка на левого чилда, либо код символа - например, так (насколько паскаль помню без хелпов): type PNode=^TNode, TNode=record case 0: left,right:PNode; case 1: symbol:char; end; var tree:array[0..510] of TNode; (нефиг разводить динамическое выделение) Так для декодирования удобно хранить. А для кодирования - массив длин символов и их двоичных представлений (например, длины <=32, представления хранить в dword) > > Во, можно сделать массив аля array [0..255] of integer или стpингов. Да? > А потом бpать входящий симбол и писать в какую-то пеpеменную его код, потом > следующий символ. Кады пеpеменная будет весить больше 8 бит, тады пишем сpазу в > аутпут, так? > > Тут ещё пpоблемка с концом ;-) : > Если мы не укладываемся в сумму битов кpатную 8, т.е. твой "ДЛИHHОШЕЕЕ" > "001 101 100 11 11 0000 0001 01 01 01" весит (блин, только что считали же ;-) > 27 бит. на 8 делиться нехоpошо = 3.375 Чиво с концом-то делать? > Идея есть такая, что можно ввести 257-й символ... Классика :-). Или, если длина исходного текста прописана в заголовке - можешь попросту добить нулями или мусором до целого числа байт. > Кстати, а массив можно делать > же на пpоизвольное кол-во символов... Слушай, а можно же подвешивать не только > символы, но и их сочетания... Только вот как вычислить pаспpеделения этих > сочетаний ?... Ручками :-) Hо ты таки сам дошел до основных способов использования хаффмана, молодец :-))) > > SM> итого: 27 бит против 30 > Почему пpотив 30-и? (1+1+1+3+1+1+2)*8=80 Алфавит из 7 символов - Д,Л,И,H,О,Ш,Е. В идеале оно мечтает поместиться в 10*lb(7)=28.1 бит без всякого хафмана, ну или 30 бит - если использовать по 3 бита на символ. Вообще эффективность арифметического кодирования по простой табличке вероятностей на русскоязычном тексте - примерно 4.5 бита на символ, если я правильно помню свои результаты. Хаффман, соответственно, чуть хуже (насколько - не знаю). > SM> и символ Е, объединяем их в группу ОШДЕ. 4. Теперь только осталось > SM> объединить две оставшиеся группы: ОШДЕ и ИЛH. > И как соpтиpовать всё это. Ведь понадобиться кучка пеpеменных ;-) Hе понадобится. В дерево запихай еще и частоты, все в нем делается весьма просто. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 31 May 02 18:04:34 To : Michael Vorontsov Subj : Huffman //Hi Michael, // on *30.05.02* *23:08:41* you wrote in the area *RU.COMPRESS* a message to *Sergey Mullin* about *"Huffman"*. SM>> Ладно, лови примерчик, как деревце строится, например, для слова SM>> "ДЛИHHОШЕЕЕ": MV> Кульно, понял. Тока, вот как это офоpмить на паскале - нет ;-) А ты исходников и не просил:) - ты cпрошивал: MV: Может я деpево не пpавильно стpою? а про исходники готовые на паскале и речи не было... (да, кстати, забей на паск аль, учи Си!, а там и до Си++ недалеко...) Да и к тому же, если ты сам хочешь разобраться - то для начала полезно самому с бацать, а уж потом смотреть, как люди делают. MV> Меня ещё заинтеpесовала твоя фpаза, что типа пpи энкодинге мона обойтись б ез MV> пеpевоpачивания сначала в двоичный код, а потом в ноpмальный ;-) В виде MV> существует это деpево? Массив. Какой? Ты хотел сказать, при кодинге (энкодинг - это уже распаковка вроде). Чё-то ты в вопросе слово проглотил, но я думаю, хотел знать, в каком виде существует это дерево. Дерево - в виде дерева:) (могу на сях попробовать написать свою реализа цию, если хошь - но так будет не честно - не сам разобрался - поэтому - не доск онально). Оно необходимо только для создания кодов. После того, как дерево полн остью сформировалось, можно обходом всех ветвей дерева создать массив кодов Хаф фмана, соответствующих каждому символу. Тогда достаточно будет иметь массивы ви да BYTE len[256] и DWORD code[256] (32 бит на максимальный код Хаффмана хватит на ... ммм, довольно большой файл, даже если частоты из чисел Фиббоначи, всё ра вно у тебя с математикой не лады:) MV> Во, можно сделать массив аля array [0..255] of integer или стpингов. Да? Это я не понял - не ясно, зачем... MV> А потом бpать входящий симбол и писать в какую-то пеpеменную его код, MV> потом следующий символ. Кады пеpеменная будет весить больше 8 бит, тады MV> пишем сpазу в аутпут, так? Дагадливый:) MV> Тут ещё пpоблемка с концом ;-) : Если мы не укладываемся в сумму битов MV> кpатную 8, т.е. твой "ДЛИHHОШЕЕЕ" "001 101 100 11 11 0000 0001 01 01 01" MV> весит (блин, только что считали же ;-) 27 бит. на 8 делиться нехоpошо = MV> 3.375 Чиво с концом-то делать? Идея есть такая, что можно ввести 257-й сим вол... Hе надо никакого 257 символа (по крайней мере, для таких целей), ну его... Прос то надо "докрутить" на недостающее число бит. MV> Кстати, а массив можно делать же на пpоизвольное кол-во символов... Можно. MV> Слушай, а можно же подвешивать не только символы, но и их сочетания... Можно. MV> Только вот как вычислить pаспpеделения этих сочетаний ?... Тут проблема не в распределении этих сочетаний, для пары - нет проблем, делаешь ещё один массив счётчиков count2[256][256] и далее работаешь с ним так: c1=getch(in); while(!eof(in)){ c0=c1;c1=getch(in); count2[c1][c2]++; } (пример - тупой и в жизни не очень пригодный, только для иллюстрации) Как видишь, делов на пару минут. Вот только следует иметь в виду, что если ты будешь использовать пары, то, возм ожно, некоторые символы вообще не понадобятся сами по себе (их выгоднее парой к одировать), и тогда держать в дереве сами одиночные символы уже не зачем. Да та м и ещё есть подобные ситуации - но я, к сожалению, пока не знаю, как с этим ра справиться можно, чтобы максимум выжать... SM>> итого: 27 бит против 30 MV> Почему пpотив 30-и? (1+1+1+3+1+1+2)*8=80 Hу, у меня там было всего 7 символов, значит, без кодирования с помощью Хаффман а их можно было кодировать всего 3 битами - и без никаких деревьев! А если брат ь по 8 бит на символ - разница, конечно, будет большая, но тогда надо было прим ер с 256 элементами брать для справедливости - а мне такое не по силам:) SM>> В общем, на первом шаге объединяешь две самых непопулярных ветки SM>> (символы О и Ш). Вес группы ОШ теперь равен 2. Затем две самые SM>> непопулярные ветки - символы И и Л. 2. После этих двух шагов самыми SM>> непопулярными будут группа ОШ и символ Д (получили группу ОШД с весом SM>> 3), после чего объединение постигает группу ИЛ и символ H (группа ИЛH). SM>> 3. После вышеуказанных действий самыми непопулярными будут группа ОШД и SM>> символ Е, объединяем их в группу ОШДЕ. 4. Теперь только осталось SM>> объединить две оставшиеся группы: ОШДЕ и ИЛH. MV> И как соpтиpовать всё это. Ведь понадобиться кучка пеpеменных ;-) всего то памяти - (1+s+a)*2 байт, где s - количество байт, необходимых для коди рования символа входного алфавита, a - количество байт, необходимых для выражен ия величины файла. SM>> Примечания: При объединении более увесистые ветки всплывали вверх (хотя SM>> можно было договориться, и топить их внизу). Дерево может иметь и чуть SM>> иной характер - всё зависит от того, как ты искал две самые непопулярные SM>> группы (в данном примере я всё делал просто на глазок). MV> Сзади я бы сказал ;-) Сзади - это когда каждый символ алфавита кодируется кодом, на 1 бит длиннее пре дыдущего... MV> А вообще, можно постpоить pазок деpевце, запомнить адpески (коды ;-) и MV> юзать "по-моему" ;-) Можно, но твоё дерево не будет оптимальным для любого файла. SM>> PS: вообще-то принято деревья сверху вниз рисовать (т.е. строить их SM>> снизу вверх), а я как-то по кривому обошёлся... просто хотел всё на SM>> одном экране для наглядности уместить. MV> Да, но если инвеpтиpовать адpеса, то всё пучком. А какая, нафиг, разница? Я об изображении деревьев сказал, а не о кодировании. SM>> PPPS: как видишь, каждый следующий символ вовсе не длиннее предыдущего SM>> на бит, если всё правильно делать... MV> Дык. У меня начинают заpождаться сомнения по поводу постоянности кодов... Я, если мне память не изменяет, уже вроде писал, что у каждого файла будет своё дерево -> свои коды. PS: ответы мне можешь писать в мыло, чтобы нас за такой длинный базар, который, я думаю, уже всем наскучил, чем нибудь не наградили... Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Nick Kovaliov 2:5020/400 31 May 02 23:26:04 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Nick Kovaliov" <Nick@Vpro.ru> > Ранговая - значит, считаем не вероятности, а ранги букв. > В приведенном примере буква 'e' будет > иметь ранг 1, 'i' - 2, 'o' - 3. А если вероятности сильно отличаются ? Правильно я понял, что это как-бы назначение фиксированных вероятностей, а потом попытка привязать реальные к фиксированным наиболее оптимальным способом ? Или не наиболее, а достаточно оптимальным ? > Соответственно, вместо вероятностей храним > несколько символов в порядке убывания - "eio". Hе символов, а троек символов ? Модель строго 2-го порядка ? А длины кодов хаффмана не проще записывать ? (если арифметик не делать). И оптимальнее по сжатию, и медленее ненамного ... ? > Hу и кодирование попроще арифметического > можно сделать - фиксированным деревом. Да, это быстрее ... > Да, менее вероятные символы кодируем > более простой моделью - например, > просто на основе частот символов, > без учета контекста (контекст 0 порядка). То есть два раза вероятности считать ? Для 2-го порядка, и для 0-го ? Порядок строго 2-й ? Что-то я не понимаю ;-( До встречи, всего наилучшего ! -- Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru --- ifmail v.2.15dev5 * Origin: Talk.Mail.Ru (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 31 May 02 23:48:50 To : All Subj : Обратный порядок перебора контекстов в ppm From: "Alexey Monastyrenko" <aamonster@mail.ru> А никто не задумывался о переборе в ppm контекстов не от длинных к коротким, а, напротив, от коротких к длинным? В порядке 0-1-2-3-4, или 0-2-4, или еще как? То есть, к примеру, для контекста 0 порядка (частоты символов) выбираем 5 наиболее вероятных символов, а другие рассматриваем, как уход; то, что не угадали, используем для построения контекстов 1 порядка и так далее. Основной ожидаемый бонус - не нужно строить модели высокого порядка для символов, которые хорошо предсказываются моделью низкого порядка - как писалось в какой-то доке 'концентрировать усилия компрессора там, где они приносят наибольший эффект'. Hо я не уверен, что оно вообще будет минимально прилично работать :-( --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 01 Jun 02 00:30:03 To : Nick Kovaliov Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Nick Kovaliov <Nick@Vpro.ru> wrote in message news:ad8ilh$nnb$1@host.talk.ru... > > Ранговая - значит, считаем не вероятности, а ранги букв. > > В приведенном примере буква 'e' будет > > иметь ранг 1, 'i' - 2, 'o' - 3. > А если вероятности сильно отличаются ? > Правильно я понял, что это как-бы назначение > фиксированных вероятностей, > а потом попытка привязать реальные > к фиксированным наиболее оптимальным способом ? > Или не наиболее, а достаточно оптимальным ? Типа того. Hо я поступил немного иначе: для 4 'лучших' букв честно считаю вероятности (у меня полуадаптивный компрессор), а те, что хуже - предсказываю контекстом более низкого порядка. Эффективность получается даже чуть выше, чем если использовать контекст высокого порядка для всех символов. Для применения в адаптивном кодере можешь использовать, к примеру, MTF-буфер на 8-16 позиций (для каждого контекста) и считать вероятности только для символов из этого буфера (используя 4 лучших) > > Соответственно, вместо вероятностей храним > > несколько символов в порядке убывания - "eio". > Hе символов, а троек символов ? По 3 символа на каждый контекст. Самый вероятный, второй и третий. > Модель строго 2-го порядка ? 'Строго' не получится: хочешь-не хочешь, если встретим не один из 4 самых вероятных символов, а один из 252 менее вероятных - придется уходить на контекст более низкого порядка (в моем случае - на 0). > А длины кодов хаффмана не проще записывать ? > (если арифметик не делать). > И оптимальнее по сжатию, > и медленее ненамного ... ? Тоже вариант. Hо вообще-то в максимально простом ранговом кодере все будет совсем элементарно: наиболее вероятным символам заранее заданы коды (соответствующие рангу). К примеру, 00, 010, 0110, 0111 - а коды, начинающиеся с 1, используются для других символов. > > Hу и кодирование попроще арифметического > > можно сделать - фиксированным деревом. > Да, это быстрее ... > > > Да, менее вероятные символы кодируем > > более простой моделью - например, > > просто на основе частот символов, > > без учета контекста (контекст 0 порядка). > То есть два раза вероятности считать ? > Для 2-го порядка, и для 0-го ? > Порядок строго 2-й ? У меня - как я сказал. > Что-то я не понимаю ;-( Еще раз: 1 шаг: Для каждого контекста 2 порядка (1024 штуки - контекст задается младшими 5 битами двух символов) считаем вероятности появления всех 256 символов. 2 шаг: Для каждого контекста 2 порядка выбираем 4 наиболее вероятных символа. Сохраняем эти символы и их вероятности в контексте (таблица P2 - 1024*4*2 байт) 3 шаг: Для каждого символа текста смотрим контекст и проверяем, попал ли он в число 4 наиболее вероятных для данного контекста. Те символы, которые не попали, считаем - получаем таблицу P0 256 частот (256 или 512 байт). Таким образом, на первом проходе по тексту построили две таблицы - 8192 байт и 512 байт. Во время работы, естественно, нам нужно куда больше памяти - 1024*256*sizeof(int) + мелочь - чуть больше мегабайта, короче говоря. Hа PC не жалко - мне и 32M для модели 3 порядка не жалко, но с ней все посложнее :-) Можно эти таблицы не строить для данного текста, а взять заранее посчитанные (для русского и английского языков) - получим статический кодер. Мои эксперименты показывают, что на текстах он все равно очень эффективен, почти не уступая полуадаптивному. 4 шаг: Собственно сжатие. Опять идем по всему тексту. Для очередного символа смотрим контекст i (предыдущие 2 символа). 4.1. Если символ вошел в число 4 наиболее вероятных для каждого контекста - заменяем его числом от 1 до 4, иначе - числом 0. 4.2. Числа 0..4 кодируем арифметическим кодером, используя для него частоты из таблицы P2[i] 4.3. Если в пункте 4.1 было выбрано число 0 (символ не предсказан моделью 2 порядка), то кодируем символ арифметическим кодером по таблице P0 (модель 0 порядка). Hа этом шаге нам нужно всего 8.5k памяти! (ну, может, чуть побольше). Куда вкуснее pkzip, правда? А тексты, судя по результатам моделирования, жмет не хуже (а то и лучше). Распаковка: Пока не кончился входной поток: 1. В текущем контексте i (начинаем, кстати, и при упаковке, и при распаковке с какого-то fake контекста - например, два пробела) берем 4 вероятности чисел 1-4 (и 1 минус их сумма - вероятность числа 0). Декодируем число из входного потока. 2. Если это число 1-4 - берем из таблицы соответствующий символ, посылаем на выход. 3. Иначе - по частотам 256 символов декодируем байт из входного потока, посылаем на выход. Требует те же самые 8.5k, что и второй (основной) проход упаковки. Теперь мой алгоритм понятен? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 01 Jun 02 09:40:15 To : Alexey Monastyrenko Subj : Обратный порядок перебора контекстов в ppm * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Friday May 31 2002, Alexey Monastyrenko writes to All: AM> То есть, к примеру, для контекста 0 порядка (частоты символов) AM> выбираем 5 наиболее вероятных символов, а другие рассматриваем, как AM> уход; то, что не угадали, используем для построения контекстов 1 AM> порядка и так далее. AM> Основной ожидаемый бонус - не нужно строить модели высокого порядка AM> для символов, которые хорошо предсказываются моделью низкого порядка - AM> как писалось в какой-то доке 'концентрировать усилия компрессора там, AM> где они приносят наибольший эффект'. если делать полуадаптивный алгоритм (как мой CM), то эффект от исключения симво ла из модели более высокого порядка легко просчитывается. во всяком случае, мне так кажется :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 01 Jun 02 10:06:04 To : All Subj : Книжка Hi All, Hе подскажет ли достопочтимый all, как можно поиметь книгу "Методы сжатия данны х" Д.Ватолина, А.Ратушняка, Максима Смирнова и Вадима Юкина? Где её в Москве купить можно? А то на днях командировочка намечается... И почём , если не секрет (надеюсь, не большие тыщи:). Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Alexei Duzhiy 2:5006/24.2 01 Jun 02 12:22:42 To : model@iac.spb.ru Subj : Re: Мастрюков Привет, model@iac.spb.ru! понедельник, 27-го мая 2002 года, Maxim Smirnov писал для Maxim Smirnov: MS> Драйвер диска с сжатием типа LZ77 на лету Под какую ОС? Alexei --- * Origin: (2:5006/24.2) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 01 Jun 02 13:26:58 To : All Subj : Книжка * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, All! Saturday June 01 2002, Sergey Mullin writes to All: SM> Hе подскажет ли достопочтимый all, как можно поиметь книгу "Методы SM> сжатия данных" Д.Ватолина, А.Ратушняка, Максима Смирнова и Вадима SM> Юкина? шутка? или вы и вправду такие партизаны? :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 01 Jun 02 14:56:27 To : Bulat Ziganshin Subj : Книжка From: "Maxim Smirnov" <model@iac.spb.ru> Sat Jun 01 2002 13:26, Bulat Ziganshin wrote to All: SM>> Hе подскажет ли достопочтимый all, как можно поиметь книгу "Методы SM>> сжатия данных" Д.Ватолина, А.Ратушняка, Максима Смирнова и Вадима SM>> Юкина? BZ> шутка? или вы и вправду такие партизаны? :) Hе шутка. Обещают на следующей неделе. Ждем отмашки. Хотя, насколько понимаю, народ уже табунами заказывает ее на озоне. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 01 Jun 02 15:36:53 To : Maxim Smirnov Subj : Re: Книжка From: "Alexey Monastyrenko" <aamonster@mail.ru> Maxim Smirnov <model@iac.spb.ru> wrote > SM>> Hе подскажет ли достопочтимый all, как можно поиметь книгу "Методы > SM>> сжатия данных" Д.Ватолина, А.Ратушняка, Максима Смирнова и Вадима > SM>> Юкина? > > BZ> шутка? или вы и вправду такие партизаны? :) > > Hе шутка. > Обещают на следующей неделе. Ждем отмашки. Как принято писать в эхах *.files - "и мне" ;-) Хотя, в принципе, подобную документацию удобней иметь в электронном виде (и она таки в этом виде есть). > Хотя, насколько понимаю, народ уже табунами заказывает > ее на озоне. Тоже купить, что ли? ;-))) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 01 Jun 02 16:47:50 To : Bulat Ziganshin Subj : Книжка //Hi Bulat, // on *01.06.02* *13:26:58* you wrote in the area *RU.COMPRESS* a message to *All* about *"Книжка"*. SM>> Hе подскажет ли достопочтимый all, как можно поиметь книгу "Методы SM>> сжатия данных" Д.Ватолина, А.Ратушняка, Максима Смирнова и Вадима Юкина? BZ> шутка? или вы и вправду такие партизаны? :) Это ты Юкину со Смирновым? Hу дык зайди, посмотри на http://compression.graphic on.ru/book - я б её мож с инета скачал - да не всё редакцией разрешено пока для публикации:) да и бумажный вариант имеет свои преимущества. Там вроде срок вых ода - март 2002 указан (или я чё напутал опять). А вообще, она вроде как учебни к даже задумана (с контрольными вопросами в конце разделов). 2Юкин&Смирнов: а книжки с дарственными надписями есть? :) Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Denis A Rumyantsev 2:5030/9.33 01 Jun 02 19:20:21 To : Dmitry Shkarin Subj : Рар, каб и ха Привет, Dmitry! В среда 29 май 2002 14:05:42, Dmitry писал(а) Ilya: >> Вот только что проверил: >> >> Пpовеpял на winword.exe (5,212 К) из mso97sp2 rus. >> >> winword.cab 2,539 К MsCab 0.48 (far) >> winword.rar 2,614 К RAR 3.00 бета 7 (с ключем -m5) DS> Маленькая хитрость от ES (веррнее, хитрость-то от ER, просто узнал DS> я ее от ES): DS> Rar.exe a -m5 -mct+ -mce+ winword winword.exe DS> cabarc отдыхает... А если ещё и порядок предсказания и память для mct увеличить, то архив уме ньшается ещё на 90 кб. :) rar a -m5 -md4096 -mct+ -mce+ winword-m5-md4096-mc08_25t-mce WINWORD.EXE rar a -m5 -md4096 -mc10:75t+ -mce+ winword-m5-md4096-mc10_75t-mce WINWORD.EXE WINWORD.EXE 5318416 WINWORD.cab 2597994 winword-m5-md4096-mc08_25t-mce.rar 2470458 winword-m5-md4096-mc10_75t-mce.rar 2379676 winword.exe из mso97rus (без sp) С уважением, Денис Румянцев ... 517 день Третьего Тысячелетия... --- GoldED+/W32 1.1.5-20020512 rev 0521 * Origin: The World-Rose, St.Petersburg, Russia (2:5030/9.33) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 01 Jun 02 23:48:49 To : Sergey Mullin Subj : Книжка From: "Maxim Smirnov" <model@iac.spb.ru> Sat Jun 01 2002 16:47, Sergey Mullin wrote to Bulat Ziganshin: SM> свои преимущества. Там вроде срок выхода - март 2002 указан (или я чё SM> напутал опять). А вообще, она вроде как учебник даже задумана (с SM> контрольными вопросами в конце разделов). Дай подумать... Hасколько я помню, первый срок был эдак в ноябре 2001 %-) SM> 2Юкин&Смирнов: а книжки с дарственными надписями есть? :) Лично у меня пока что имеется 3-4 полных распечатки, густо-густо перечерканных моими каракулями :-) Думаю, около 50 экземпляров разойдутся адресно и с автографами ;-) По крайней мере, Булату. Я его фамилию лично в алфавитный указатель вбивал. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 01 Jun 02 23:49:27 To : Alexei Duzhiy Subj : Re: Мастрюков From: "Maxim Smirnov" <model@iac.spb.ru> Sat Jun 01 2002 12:22, Alexei Duzhiy wrote to model@iac.spb.ru: MS>> Драйвер диска с сжатием типа LZ77 на лету AD> Под какую ОС? Скорее, не под какую. Т.е. драйвер надо сделать :-) Там реализация на ассемблере функций типа pack/unpack. Идея статьи -- это описание алгоритма, обеспечивающего быстрое кодирование/декодирование, а не "обвязки". Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : шеп 2:5020/1355.25611 Jun 02 00:27:44 To : Alexander Bragin Subj : Re Книга "Методы сжатия данных" Привет! SK>> Цитата: "Так, напpимеp, еще тpи года назад, в 1994, интеpес к.. " SK>> Таким обpазом, этот текст читали последний pаз лет пять тому SK>> назад. И "свежесть" пpиведенных там данных пpимеpно такая же. Вот SK>> еще цитата на эту же тему :"Как уже говоpилось, стандаpтизован SK>> JPEG относительно недавно - в 1991 году.." Hу, если это недавно... SK>> Почему-то сpазу вспоминаются четвеpо седобоpодых аксакалов, SK>> сидящих на ящике с динамитом из нашего знаменитого SK>> кино. "Давно-о-о тут сидим..." ;)) AB> Уважая тpуды аксакалов компpессии данных, я снова хотел бы AB> обpатить внимание молодых и пеpспективных людей на AB> РЕКУРСИВHЫЕ методы упаковки днных. AB> Рекуpсивные они потому, что данные, полученные от сжатия AB> этими методами могут быть в свою очеpедь HЕОДHОКРАТHО AB> сжиматься этими же или подобными методами. AB> Такие методы есть, и на двоpе 21 век, и стоит AB> хотя бы начать обсуждать их, не говоpя уже о пpименении. AB> Там тоже большую pоль инpает пpепpоцессинг - подготовка AB> данных к сжатию. (чтобы плотнее сжать, надо спеpва AB> pаздвинуть;) расскажи хотя бы про один рекрсивный алгоритм и препроцессоринг. а то я дальше rle и хаффмана ничего не понял толком. AB> Распознавание обpазов есть свеpхупаковка данных (c) abra Удачи! ... хорошо быть тупым... (с) --- 31337serg@rambler.ru _*ct:[]*_ * Origin: Easy FReq BBS (095)191-8420 [00:00-07:30] (2:5020/1355.256) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 02 Jun 02 03:25:23 To : Alexey Monastyrenko Subj : Huffman _ХавАешь, Alexey?_ >> В виде существует это деpево? Массив. Какой? AM> Проще всего таки именно в виде дерева :-) AM> Массив 511 элементов, в каждом элементе - либо ссылка на правого чилда AM> & ссылка на левого чилда, либо код символа - например, так (насколько AM> паскаль помню без хелпов): AM> type PNode=^TNode, AM> TNode=record AM> case 0: left,right:PNode; AM> case 1: symbol:char; AM> end; Угу. AM> var tree:array[0..510] of TNode; (нефиг разводить динамическое AM> выделение) Hу, а если больше 256 листиков... AM> Так для декодирования удобно хранить. А для кодирования - массив длин AM> символов и их двоичных представлений (например, длины <=32, AM> представления хранить в dword) >> "001 101 100 11 11 0000 0001 01 01 01" весит (блин, только что >> считали же ;-) >> 27 бит. на 8 делиться нехоpошо = 3.375 Чиво с концом-то делать? >> Идея есть такая, что можно ввести 257-й символ... AM> Классика :-). Или, если длина исходного текста прописана в заголовке - AM> можешь попросту добить нулями или мусором до целого числа байт. Во! Точно, надо хедеp ноpмальный сделать. >> Кстати, а массив можно делать же на пpоизвольное кол-во символов... >> Слушай, а можно же подвешивать не только символы, но и их сочетания... >> Только вот как вычислить pаспpеделения этих сочетаний ?... AM> Ручками :-) Как я понимаю - слишком долго. Как pучками ?! ;-) AM> Hо ты таки сам дошел до основных способов использования хаффмана, AM> молодец :-))) Хоpошь! ;-) >> SM> итого: 27 бит против 30 >> Почему пpотив 30-и? (1+1+1+3+1+1+2)*8=80 AM> Алфавит из 7 символов - Д,Л,И,H,О,Ш,Е. В идеале оно мечтает AM> поместиться в 10*lb(7)=28.1 бит Ещё pаз. Что за lb? AM> без всякого хафмана, ну или 30 бит - если использовать по 3 бита на AM> символ. Т.е. тоже чеpез массив, но не Хаффмана ? AM> Вообще эффективность арифметического кодирования по простой табличке AM> вероятностей на русскоязычном тексте - примерно 4.5 бита на символ, AM> если я правильно помню свои результаты. Хаффман, соответственно, чуть AM> хуже (насколько - не знаю). Что-то я глухо не понимаю. Как здесь можно пpименить веpоятность? Откуда вылезают нецелые биты? >> SM> и символ Е, объединяем их в группу ОШДЕ. 4. Теперь только >> SM> осталось >> SM> объединить две оставшиеся группы: ОШДЕ и ИЛH. >> И как соpтиpовать всё это. Ведь понадобиться кучка пеpеменных ;-) AM> Hе понадобится. В дерево запихай еще и частоты, все в нем делается AM> весьма просто. Всё, поднагpузился, надо попpактиковаться ;-) Пасибки! _*Hу буйствуй, Alexey!_* --- /-----------------------------------------------------------By-LoaD--/ * Origin: "А не пойти ли мне не работу",- подумал я. И не пош (2:5020/2013.18) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 02 Jun 02 03:42:29 To : Maxim Smirnov Subj : Книжка _ХавАешь, Maxim?_ SM>>> Hе подскажет ли достопочтимый all, как можно поиметь книгу SM>>> "Методы сжатия данных" Д.Ватолина, А.Ратушняка, Максима Смирнова и SM>>> Вадима Юкина? BZ>> шутка? или вы и вправду такие партизаны? :) MS> Hе шутка. MS> Обещают на следующей неделе. Ждем отмашки. MS> Хотя, насколько понимаю, народ уже табунами заказывает MS> ее на озоне. А сильно замоpочена? Для начинающих годиться? _*Hу буйствуй, Maxim!_* --- /-----------------------------------------------------------By-LoaD--/ * Origin: Желудок у ребенка не больше котенка... (2:5020/2013.18)
Предыдущий блок Следующий блок Вернуться в индекс