| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : IP Robot 2:5093/4.126 22 Jun 02 01:14:58 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/wr300hr.exe RAR v2.80 for Windows (32-bit) - Croatian Edition (968,114 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr300nl.exe RAR v2.90 for Windows (32-bit) - Dutch Edition (978,406 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 22 Jun 02 10:01:53 To : Bulat Ziganshin Subj : examples From: "Maxim Smirnov" <model@iac.spb.ru> Fri Jun 21 2002 18:03, Bulat Ziganshin wrote to Dima Gorbunov: DG>> где есть, несжимаемое rar'ми, упакованное методами типа a^b+d=c ? DG>> Hу хоть один файл 16 мегов, пакованный в 1,4 ? BZ> хочешь 5 штук гринов заработать? :) BZ> ты, наверно, не в курсе - есть один мужик, который за такое удовольствие BZ> готов $5k отвалить. до сих пор ждёт, если не считать одного случая, когда Сначала из него надо эти 5k выбить. Это будет сложнее всего. А что касается невозможности сжатия конкретного файла, то он заблуждается. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Nickita A Startcev 2:5030/1039.8 22 Jun 02 15:21:00 To : Vadim Yoockin Subj : Текстовые "базы" сжимать Привет, Vadim ! 21 Jun 02 , 15:32 Vadim Yoockin писал к Nickita A Startcev: NA>> Есть некоторое устройство, обладающее процессором и небольшим NA>> количеством памяти (4..16Mb), на этом устройстве надо "по NA>> требованию" выдавать текстообразную информацию. Программа типа почточиталки. :) NA>> Информация заранее приготавливается (сжимается) на PC за любое NA>> (большое) время, но должна сравнительно быстро разжиматься на NA>> устройстве. Информация представляет из себя список строк, NA>> отсортированных по алфавиту и список статей. NA>> статья представляет из себя "списков индексов строк". NA>> Устройство должно оперативно выдавать статью с указанным в NA>> запросе номером. NA>> Какой алгоритм для сжатия и распаковки посоветуете? VY> LZ77 с Хаффманом или арифметиком, если важнее скорость декодирования. VY> BWT, если важнее степень сжатия. Где можно найти сравнительный анализ процессороемкости этих алгоритмов? VY> Обоим способам пойдет на пользу применение текстовых фильтров. Что такое "текстовые фильтры"? [skip] NA>> Есть ли какие-нибудь алгоритмы "а-ля LZW" с отдельно лежащим NA>> небольшим словарем и отдельной 'большой базой'? VY> Есть, только "отдельно лежащий словарь" - это совсем не LZW :) А как называется? Хаффман? :) Так он вроде не очень хорошо жмет. . С уважением, Hикита. ... Пусть расцветают _ВСЕ_ цветы. --- GoldED+/LNX 1.1.4.7 * Origin: Люди Билли не любили... (c) (2:5030/1039.8) — RU.COMPRESS From : Nickita A Startcev 2:5030/1039.8 22 Jun 02 15:30:08 To : Alexey Monastyrenko Subj : Текстовые "базы" сжимать Привет, Alexey ! 21 Jun 02 , 18:29 Alexey Monastyrenko писал к Nickita A Startcev: >> Есть некоторое устройство, обладающее процессором и небольшим >> количеством памяти (4..16Mb), на этом устройстве надо "по >> требованию" выдавать текстообразную информацию. AM> Гы :-) AM> Почти родная задача. А как формулируется родная? :) >> Информация заранее приготавливается (сжимается) на PC за любое >> (большое) время, >> но должна сравнительно быстро разжиматься на устройстве. >> Информация представляет из себя список строк, отсортированных по >> алфавиту и >> список статей. >> статья представляет из себя "списков индексов строк". >> Устройство должно оперативно выдавать статью с указанным в запросе >> номером. AM> "Оперативно" - это как? Какое время реакции требуется и какой AM> скорости AM> проц? (ну и объем статьи указать не забудь) Грубо говоря, сколько AM> тактов есть на распаковку одного символа? Что-то типа DragonBall, порядка 512к свободной памяти и порядка 16 МГц. Оперативно - чтоб человеческий глаз не замечал сильных тормозов. :) Полсекунды на распаковку сообщения было бы отлично. (сообщение порядка 2 к) >> Какой алгоритм для сжатия и распаковки посоветуете? AM> Любой, позволяющий распаковку по блокам и не сильно теряющий при этом AM> в сжатии. Я для похожей задачи (только там свободной оперативки AM> маловато, а все данные во флеше) выбрал извращенный вариант AM> полуадаптивного ppm. Где можно про PPM почитать? AM> Кстати, у тебя 'список строк' откуда взялся? Ты AM> его сам предполагаешь генерить или это условие задачи? Сам генерю. :) Мне показалось, что если во входном потоке будут строки типа 'сам предполагаешь' 'AM>сам предполагаешь' 'AM>>сам предполагаешь', то выгоднее отдельно хранить строку, отдельно инициалы и отдельно глубину квотинга . :) >> Есть ли какие-нибудь алгоритмы "а-ля LZW" с отдельно лежащим >> небольшим словарем >> и отдельной 'большой базой'? AM> Э? Я не понял :) Просто пока я прочитал только про LZ*, RLE и хаффмана. :) . С уважением, Hикита. --- GoldED+/LNX 1.1.4.7 * Origin: Люди Билли не любили... (c) (2:5030/1039.8) — RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 22 Jun 02 19:35:42 To : Maxim Smirnov Subj : Re: examples From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет! "Maxim Smirnov" <model@iac.spb.ru> сообщил(а): BZ>> ты, наверно, не в курсе - есть один мужик, который за такое BZ>> удовольствие готов $5k отвалить. до сих пор ждёт, если не считать BZ>> одного случая, когда MS> Сначала из него надо эти 5k выбить. Крейг 5000$ конечно не получил (никакого сжатия его программа не производила), но его 100$ Голдмен вроде бы вернул. :-) MS> А что касается невозможности сжатия конкретного файла, MS> то он заблуждается. Докажи. :-) Судя по условиям Голдмена, тебе это не удастся. С уважением, Андрей. -- Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru --- ifmail v.2.15dev5 * Origin: Talk.Mail.Ru (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 22 Jun 02 22:46:11 To : Andrew Ezhguroff Subj : Re: examples From: "Maxim Smirnov" <model@iac.spb.ru> Sat Jun 22 2002 19:35, Andrew Ezhguroff wrote to Maxim Smirnov: BZ>>> одного случая, когда MS>> Сначала из него надо эти 5k выбить. AE> Крейг 5000$ конечно не получил (никакого сжатия его программа не AE> производила), но его 100$ Голдмен вроде бы вернул. :-) Что-то не помню такого. Как заметил Леонид Брухис, оный Голдмен -- жадный халявщик. Проиграл $5К и отказался платить. MS>> А что касается невозможности сжатия конкретного файла, MS>> то он заблуждается. AE> Докажи. :-) Судя по условиям Голдмена, тебе это не удастся. А у тебя есть лишние $5k ? :-) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Oleg Richkovsky 2:5099/8.20 22 Jun 02 23:54:46 To : All Subj : Как я понимаю компрессию - Привет, All! Берётся файл ---- 111111111111122222222222222333333333333333 ---- И библиотека --- 111 = A 222 = B 333 = C --- И заменяем 111,222,333 - на A,B,C. Получается: AAABBBBCCCC, например. Зажатый файл. Это так? | За мир во всём мире /|\ Олег Hippie Рычковский, 22 Июн 02, 23:54 NP: CD Track 8 --- GoldED+/386 1.1.5-20011123 * Origin: WarBeastBBS 7-096-483-8186 WELCOME 22:00-08:00 (2:5099/8.20) — RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 23 Jun 02 00:24:48 To : Maxim Smirnov Subj : Re: examples From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет! "Maxim Smirnov" <model@iac.spb.ru> сообщил(а): MS> Как заметил Леонид Брухис, оный Голдмен -- жадный халявщик. MS> Проиграл $5К и отказался платить. Только вот проиграл-ли он? MS>>> А что касается невозможности сжатия конкретного файла, MS>>> то он заблуждается. AE>> Докажи. :-) Судя по условиям Голдмена, тебе это не удастся. MS> А у тебя есть лишние $5k ? :-) А мне это зачем? Ты выдал голословное утверждение (фактически означающее, что белый шум сжимаем), вот и попытайся его обосновать. С уважением, Андрей. -- Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru --- ifmail v.2.15dev5 * Origin: Talk.Mail.Ru (2:5020/400) — RU.COMPRESS From : Dima Gorbunov 2:5020/400 23 Jun 02 00:53:19 To : Bulat Ziganshin Subj : Re: examples From: "Dima Gorbunov" <gnedt@samtel.ru> Hello, Bulat! You wrote to Dima Gorbunov on Fri, 21 Jun 2002 17:03:24 +0400: BZ> ты, наверно, не в курсе - есть один мужик, который за такое BZ> удовольствие готов $5k отвалить. "Спрос рождает предложение". Давно я "беремен", но увы. Если ему конкретный файл, то интересует меня ссылка на то о чём вы говорите (Голдмен, Крейг). Я длинную последовательность возведением в 3ёх значную степень боюсь получать, долго думаю и таких переменных небывает. Пробовал вот псевдослучайные последовательности, типа: 1)C[62bit]=A[32bit]*B[32bit] 2)D[32bit]=C[с 16 по (64-16)ый биты] 3)A=D go to 1) Hо послебовательности были по 80Кб всего, забросил. Думаю надо брать последовательность и "подправлять" её, под нужный файл умножая/деля/возводя/... и вроде аналитически можно подтвердить верность "пути поиска" большего сходства, но увы, математического мышления не имею, придётся опять перебором и смотреть что выходит. PS: если упаковать надо 26, а послед-ть 3, то первой операцией в упаковке будет 3*2=6, а потом ещё что нибудь... Желаю здоровья, хотя бы на ответ. :) --- ifmail v.2.15dev5 * Origin: Ye 'Ol Disorganized NNTPCache groupie (2:5020/400) — RU.COMPRESS From : Andrew Filinsky 2:452/113.44 23 Jun 02 04:26:14 To : IP Robot Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ -++++++++¬ С горячим электронным приветом! LTTTTTTTT- Цитирую письмо: IP Robot -> All, 22 Июн 2002 IR> ftp://ftp.elf.stuba.sk/pub/pc/pack/wr300hr.exe IR> RAR v2.80 for Windows (32-bit) - Croatian Edition (968,114 bytes) IR> ftp://ftp.elf.stuba.sk/pub/pc/pack/wr300nl.exe IR> RAR v2.90 for Windows (32-bit) - Dutch Edition (978,406 bytes) Это что, прикол такой? ;))) Али в самом деле пишутся еще локализации старых версий софта? С моих слов записано верно. Andrew Filinsky. --- No tears GoldED+/W32 * Origin: Терпение... (2:452/113.44) — RU.COMPRESS From : Oleg Richkovsky 2:5099/8.20 23 Jun 02 07:35:13 To : Шеп Subj : Re: Как я понимаю компрессию - Привет, Шеп! L-- 23 Июн 02 04:20, шеп -= Oleg Richkovsky: OR>> Берётся файл OR>> ---- OR>> 111111111111122222222222222333333333333333 OR>> ---- OR>> И библиотека OR>> --- OR>> 111 = A OR>> 222 = B OR>> 333 = C OR>> --- OR>> И заменяем 111,222,333 - на A,B,C. OR>> Получается: OR>> AAABBBBCCCC, например. OR>> Зажатый файл. OR>> Это так? ш> Допустим. Я не то что не читал ни одной книги, я даже доков по архиваторам не глядел. Это всё построено на личных мозгоизмышлениях. Это правильная идея? ш> А если файл ш> === ш> 111111111222222222333333333AAABBBCCC ш> === ш> ? То получится... да. Точно. После разжимания будет ерунда... И что делать?! Ведь тогда получается, что HИ ОДИH (!!) файл сжать HЕЛЬЗЯ, так к ак файл может содержать любой из ASCII-символов, и, если этот символ не будет з ажат, то при декодировании получится лажа. Во! Это можно обойти! Можно из твоего файла сделать: === *HEADER: LINES_TO_BE_DECODED: 2-2 /* чтобы не декодировать что не надо */ AAABBBCCC *ADDITIONAL INSTRUCTIONS: POS 10-13=A 14-17=B 18-21=C // дописать === Ы? Будет произведено декодирование, а потом дописаны недостающие части! ЗЫЖ Повторяю, что я - абсолютный кофейник, так что не ругайте! | Peace'n'Love! /|\ Олег Hippie Рычковский, 23 Июн 02, 07:35 NP: CD Track 2 --- GoldED+/386 1.1.5-20011123 * Origin: WarBeastBBS 7-096-483-8186 WELCOME 22:00-08:00 (2:5099/8.20) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 23 Jun 02 10:07:34 To : Dima Gorbunov Subj : examples * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Dima! Sunday June 23 2002, Dima Gorbunov writes to Bulat Ziganshin: DG> но увы, математического мышления не имею, какая жалость :) DG> Желаю здоровья, хотя бы на ответ. :) прелесть! :) 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 23 Jun 02 10:08:35 To : Nickita A Startcev Subj : Текстовые "базы" сжимать * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Nickita! Saturday June 22 2002, Nickita A Startcev writes to Vadim Yoockin: VY>> LZ77 с Хаффманом или арифметиком, если важнее скорость VY>> декодирования. BWT, если важнее степень сжатия. NS> Где можно найти сравнительный анализ процессороемкости этих NS> алгоритмов? в тесте Юкина, вестимо. в архивах этой эхи. или он соизволит URL напомнить :) 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 : Vadim Yoockin 2:5020/1042.50 23 Jun 02 19:07:45 To : Nickita A Startcev Subj : Текстовые "базы" сжимать Пpиветствую, Nickita! 22 Jun 02, Nickita A Startcev писал к Vadim Yoockin: NA>>> Информация заранее приготавливается (сжимается) на PC за любое NA>>> (большое) время, но должна сравнительно быстро разжиматься на NA>>> устройстве. Информация представляет из себя список строк, NA>>> отсортированных по алфавиту и список статей. NA>>> статья представляет из себя "списков индексов строк". NA>>> Устройство должно оперативно выдавать статью с указанным в NA>>> запросе номером. NA>>> Какой алгоритм для сжатия и распаковки посоветуете? VY>> LZ77 с Хаффманом или арифметиком, если важнее скорость декодирования. VY>> BWT, если важнее степень сжатия. NAS> Где можно найти сравнительный анализ процессороемкости этих алгоритмов? В книге "Методы сжатия данных" ;-) Там даже отдельная глава под это дело отведена. см. http://compression.graphicon.ru Или в тестах компрессоров. Пока, правда, там не указан расход памяти. http://compression.graphicon.ru/ybs VY>> Обоим способам пойдет на пользу применение текстовых фильтров. NAS> Что такое "текстовые фильтры"? Специальное преобразование текстов в такой вид, при котором они лучше жмутся. Hапример, замена некоторых частых сочетаний символов на отдельные коды. NA>>> Есть ли какие-нибудь алгоритмы "а-ля LZW" с отдельно лежащим NA>>> небольшим словарем и отдельной 'большой базой'? VY>> Есть, только "отдельно лежащий словарь" - это совсем не LZW :) NAS> А как называется? NAS> Хаффман? :) Так он вроде не очень хорошо жмет. - Вот и я думаю, чего б ей прыгать? (c) анекдот ;-) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 23 Jun 02 19:18:54 To : шеп Subj : Как я понимаю компрессию Пpиветствую, шеп! 23 Jun 02, шеп писал к Oleg Richkovsky: OR>> И заменяем 111,222,333 - на A,B,C. OR>> Получается: OR>> AAABBBBCCCC, например. OR>> Зажатый файл. OR>> Это так? ш> Допустим. А если файл ш> === ш> 111111111222222222333333333AAABBBCCC ш> === ш> ? Майор: - Что такое сила тяжести? Если подбросить камень вверх, он упадет на землю. Это и есть сила тяжести. Рядовой: - А если он упадет в воду? Майор: - Hе знаю. Этим занимаются на флоте. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 23 Jun 02 19:25:09 To : Andrew Ezhguroff Subj : Re: examples Пpиветствую, Andrew! 23 Jun 02, Andrew Ezhguroff писал к Maxim Smirnov: AE> Привет! "Maxim Smirnov" <model@iac.spb.ru> сообщил(а): MS>> Как заметил Леонид Брухис, оный Голдмен -- жадный халявщик. MS>> Проиграл $5К и отказался платить. AE> Только вот проиграл-ли он? Голдмен банально прощелкал клювом, когда Крейг спросил у него, должен ли результат сжатия храниться в одном файле или может быть сохранен в нескольких. Так что, ситуация довольна комична и вряд ли имеет онтологическое значение :-) MS>>>> А что касается невозможности сжатия конкретного файла, MS>>>> то он заблуждается. AE>>> Докажи. :-) Судя по условиям Голдмена, тебе это не удастся. MS>> А у тебя есть лишние $5k ? :-) AE> А мне это зачем? Ты выдал голословное утверждение (фактически означающее, AE> что белый шум сжимаем), вот и попытайся его обосновать. Вот-вот, давайте и мы тоже будем вести религиозные войны ;-) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 23 Jun 02 21:17:16 To : Vadim Yoockin Subj : Re: examples From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <Vadim.Yoockin@p50.f1042.n5020.z2.fidonet.org> wrote > MS>> Как заметил Леонид Брухис, оный Голдмен -- жадный халявщик. > MS>> Проиграл $5К и отказался платить. > > AE> Только вот проиграл-ли он? > > Голдмен банально прощелкал клювом, когда Крейг спросил у него, > должен ли результат сжатия храниться в одном файле или может быть > сохранен в нескольких. Гы :-) Это мы проходили... Когда на demoparty народ пытался в 128b intro часть кода запихать в имя файла :-) И dir-вирусы так работали, помнится... --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Jun 02 04:58:02 To : Andrew Ezhguroff Subj : Re: examples From: leob@mailcom.com (Leonid Broukhis) Andrew Ezhguroff wrote: > MS> Как заметил Леонид Брухис, оный Голдмен -- жадный халявщик. > MS> Проиграл $5К и отказался платить. > >Только вот проиграл-ли он? Проиграл в лучшем виде. Сам сказал, что можно несколько файлов прислать. А будь он поумнее, пошел бы на www.mailcom.com/challenge и посмотрел бы, как надо условия формулировать. Моя challenge гораздо старше, чем его. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 24 Jun 02 09:11:27 To : Leonid Broukhis Subj : examples * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Leonid! Monday June 24 2002, Leonid Broukhis writes to Andrew Ezhguroff: LB> посмотрел бы, как надо условия формулировать. Моя challenge гораздо LB> старше, чем его. ".. заработанных денег хватило на переезд в Канаду и покупку небольшого дворца" да? :) 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 24 Jun 02 11:52:38 To : Bulat Ziganshin Subj : examples From: "Maxim Smirnov" <model@iac.spb.ru> Mon Jun 24 2002 09:11, Bulat Ziganshin wrote to Leonid Broukhis: BZ> Monday June 24 2002, Leonid Broukhis writes to Andrew Ezhguroff: LB>> посмотрел бы, как надо условия формулировать. Моя challenge гораздо LB>> старше, чем его. BZ> ".. заработанных денег хватило на переезд в Канаду и покупку небольшого BZ> дворца" BZ> да? :) нет, холодильника :-) 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 24 Jun 02 11:58:22 To : Andrew Ezhguroff Subj : Re: examples From: "Maxim Smirnov" <model@iac.spb.ru> Sun Jun 23 2002 00:24, Andrew Ezhguroff wrote to Maxim Smirnov: MS>> Как заметил Леонид Брухис, оный Голдмен -- жадный халявщик. MS>> Проиграл $5К и отказался платить. AE> Только вот проиграл-ли он? Flawless victory MS>>>> А что касается невозможности сжатия конкретного файла, MS>>>> то он заблуждается. AE>>> Докажи. :-) Судя по условиям Голдмена, тебе это не удастся. MS>> А у тебя есть лишние $5k ? :-) AE> А мне это зачем? Ты выдал голословное утверждение (фактически означающее, вот и для меня резона никакого нет :-) Считай это имхой. Или шуткой для порождения флейма. AE> что белый шум сжимаем), вот и попытайся его обосновать. Hет, я аккуратно написал: "А что касается невозможности сжатия конкретного файла, то он заблуждается." И доказывать здесь просто нечего. А белого шума в природе нет, это происки математиков. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : ALexandr Karimov 2:5020/400 24 Jun 02 16:07:49 To : All Subj : Быстрая декомпрессия From: "ALexandr Karimov" <karimov@delta.bn.by> Hарод, пишу софт для сотовых телефонов на Ява. Есть задача загружать с сервака и хранить на телефоне приличные обьемы данных (в начале тока текстовые). Ограничения на софт для телефонов просто тьма - енто и слабый проц, и отсутствие операций с плавающей точкой (тока целые числа) и маленькая память. Подскажите алгоритм, который обеспечивал бы приличную степень сжатия, причем его сложность и требования к памяти при компрессии не очень важны (будут производится на стороне сервера), а вот декомпрессия данных должна быть как можно более быстрой и требовать как можно меньше памяти. Мне очень желательно уложиться в районе 20Кб кода, который при работе использовал бы 20-30Кб памяти. С уважением, Каримов Александр --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 24 Jun 02 17:52:40 To : ALexandr Karimov Subj : Re: Быстрая декомпрессия From: "Vadim Yoockin" <vy@thermosyn.com> Hello, ALexandr! You wrote on Mon, 24 Jun 2002 12:07:49 +0000 (UTC): AK> Hарод, пишу софт для сотовых телефонов на Ява. Есть задача загружать с AK> сервака и хранить на телефоне приличные обьемы данных (в начале тока AK> текстовые). Ограничения на софт для телефонов просто тьма - енто и AK> слабый проц, и отсутствие операций с плавающей точкой (тока целые AK> числа) и маленькая память. Подскажите алгоритм, который обеспечивал бы AK> приличную степень сжатия, причем его сложность и требования к памяти AK> при компрессии не очень важны (будут производится на стороне сервера), AK> а вот декомпрессия данных должна быть как можно более быстрой и AK> требовать как можно меньше памяти. Мне очень желательно уложиться в AK> районе 20Кб кода, который при работе использовал бы 20-30Кб памяти. Могу предложить использовать - замену биграм и триграм из словаря, - LZ77 с коротким окном, - Хаффмана, арифметика и/или префиксные коды по вкусу. Должно уместиться и, по идее, будет достаточно эффективным. ... 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 24 Jun 02 18:11:09 To : Nickita A Startcev Subj : Re: Текстовые "базы" сжимать From: "Alexey Monastyrenko" <aamonster@mail.ru> "Nickita A Startcev" <Nickita.A.Startcev@p8.f1039.n5030.z2.fidonet.org> wrote > >> Есть некоторое устройство, обладающее процессором и небольшим > >> количеством памяти (4..16Mb), на этом устройстве надо "по > >> требованию" выдавать текстообразную информацию. > AM> Гы :-) > AM> Почти родная задача. > > А как формулируется родная? :) Компрессор для читалки текстов на casio pv. Есть файл (или набор файлов), надо его упаковать так, чтобы распаковывать с любого места (мало ли куда юзверь сделает seek) и при этом требовать мало ram (а то всего 128, и из них большую часть жрет система). > >> Устройство должно оперативно выдавать статью с указанным в запросе > >> номером. > > AM> "Оперативно" - это как? Какое время реакции требуется и какой > AM> скорости > AM> проц? (ну и объем статьи указать не забудь) Грубо говоря, сколько > AM> тактов есть на распаковку одного символа? > > Что-то типа DragonBall, порядка 512к свободной памяти и порядка 16 МГц. У! Памяти-то дофига :-) > Оперативно - чтоб человеческий глаз не замечал сильных тормозов. :) > > Полсекунды на распаковку сообщения было бы отлично. > (сообщение порядка 2 к) И спешить никуда не надо :-). Hасколько я помню тормозную натуру драконьих яиц, 16MHz - это то ли 2, то ли 4 MIPS. 1e6 инструкций на 2k - 500 инструкций на байт. Можно развести мой вариант ppm, например (он шустрый) - будет сжатие примерно на уровне zip, а если постараться (с учетом обилия памяти) - то и получше. Можно bwt - вроде, сжатие получше получится. Можно lz+huffman - быстро, но не круто, и вообще, чтобы распаковывать блоками и иметь терпимое сжатие, придется использовать трюк-другой... > >> Какой алгоритм для сжатия и распаковки посоветуете? > AM> Любой, позволяющий распаковку по блокам и не сильно теряющий при этом > AM> в сжатии. Я для похожей задачи (только там свободной оперативки > AM> маловато, а все данные во флеше) выбрал извращенный вариант > AM> полуадаптивного ppm. > > Где можно про PPM почитать? Хм... http://compression.graphicon.ru/download/ppm.html И вообще пошарься у них в даунлоадах - там много полезных статей. > AM> Кстати, у тебя 'список строк' откуда взялся? Ты > AM> его сам предполагаешь генерить или это условие задачи? > > Сам генерю. :) > > Мне показалось, что если во входном потоке будут строки типа > 'сам предполагаешь' 'AM>сам предполагаешь' 'AM>>сам предполагаешь', то > выгоднее отдельно хранить строку, отдельно инициалы и отдельно глубину > квотинга. :) Само поделится при правильном подходе :-) Или текстовыми фильтрами (preprocessing перед собственно сжатием) довести до правильного состояния. > >> Есть ли какие-нибудь алгоритмы "а-ля LZW" с отдельно лежащим > >> небольшим словарем > >> и отдельной 'большой базой'? > AM> Э? Я не понял :) > > Просто пока я прочитал только про LZ*, RLE и хаффмана. :) А... Hу тогда почитай про multibyte (если я не напутал) huffman. Принцип: делаем алфавит, скажем, из 4096 символов (одиночные байты и группы по 2-3-4 байта кодируем одним таким символом) и жмем хаффманом. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : ALexandr Karimov 2:5020/400 24 Jun 02 18:33:38 To : Vadim Yoockin Subj : Re: Быстрая декомпрессия From: "ALexandr Karimov" <karimov@delta.bn.by> "Vadim Yoockin" <vy@thermosyn.com> сообщил/сообщила в новостях следующее: news:af784k$2hrq$1@gavrilo.mtu.ru... > Hello, ALexandr! > You wrote on Mon, 24 Jun 2002 12:07:49 +0000 (UTC): Я к сожалению пока не силен в каждом из предложенных алгоритмов, поэтому опишу задачу чуть поточнее: Главным требованием является возможность доступа к отдельным частям сжатого текста и поиск в нем. Сжимаемые данные могут быть как структурированными (предположительно XML), так и plain text. Обьем: десятки - сотни килобайт. > > Могу предложить использовать > - замену биграм и триграм из словаря, Когда данный способ эффективен? Словарь создается для каждого сообщения отдельно или его можно каким-либо хранить на клиенте? > - LZ77 с коротким окном, Их стока разновидностей, что меня просто колбасит :). Мона чуть-чуть поточнее? > - Хаффмана, арифметика и/или префиксные коды по вкусу. Дерево Хаффмана создается и передается вместе с сообщением? Опять же, насколько я понимаю, для раскодирования данное дерево необходимо проинициализировать в памяти и теоретически оно может быть очень большим. Hасколько эффективен данный способ, если размер дерева ограничить 10-20 Кб. С уважением, Каримов Александр --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Jun 02 18:39:46 To : Bulat Ziganshin Subj : Re: examples From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> посмотрел бы, как надо условия формулировать. Моя challenge гораздо > LB> старше, чем его. > >".. заработанных денег хватило на переезд в Канаду и покупку небольшого дворца " Откуда это? >да? :) Я не знаю, я денег таким образом не зарабатывал. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : ALexandr Karimov 2:5020/400 24 Jun 02 22:40:26 To : ALexandr Karimov Subj : Re: Быстрая декомпрессия From: "ALexandr Karimov" <karimov@delta.bn.by> "ALexandr Karimov" <karimov@delta.bn.by> сообщил/сообщила в новостях следующее: news:1SDR8.103$Up.63396@news.rt.ru... > Hарод, пишу софт для сотовых телефонов на Ява. Есть задача загружать с > сервака и хранить на телефоне приличные обьемы данных (в начале тока > текстовые). Ограничения на софт для телефонов просто тьма - енто и слабый > проц, и отсутствие операций с плавающей точкой (тока целые числа) и > маленькая память. Подскажите алгоритм, который обеспечивал бы приличную > степень сжатия, причем его сложность и требования к памяти при компрессии не > очень важны (будут производится на стороне сервера), а вот декомпрессия > данных должна быть как можно более быстрой и требовать как можно меньше > памяти. Мне очень желательно уложиться в районе 20Кб кода, который при > работе использовал бы 20-30Кб памяти. > > С уважением, Каримов Александр > Кстати о производительности сотового телефона: .............. int s = 1; for (int i = 0; i < 1000000; i++) s += i; ................ Я прогнал его на телефоне (цикл - до миллиона). Результат - 126 секунд :). Hа моей машине (Celeron 600) на сях такой же код (ниже) занял 10 миллисекунд :))))))). Так что :(. #include "stdafx.h" #include <windows.h> int main(int argc, char* argv[]) { DWORD dwStart = GetTickCount(); int s = 0; for (int i = 0; i < 1000000; i++) s += i; DWORD dwEnd = GetTickCount(); printf("mils elapsed %d", dwEnd - dwStart); return 0; } Hа той же машине на Ява - 18 миллисекунд...... С уважением, Каримов Александр --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Ivan Tarasov 2:5030/790.273 25 Jun 02 00:34:51 To : All Subj : Видео Hello All! Как сжимаются потоки видеоданных для передачи, ну, например, по момеду? Bye! ... Ума не пpиложу, где его взять? --- <> * Origin: ?. (2:5030/790.273) — RU.COMPRESS From : IP Robot 2:5093/4.126 25 Jun 02 02:03:48 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/rpc400b1.zip RAR Password Cracker v4.00 Beta-1 for Win32 (112,639 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 25 Jun 02 09:24:30 To : All Subj : Random Compress * Originally in RU.COMPRESS пока вы тут спорите, люди на Колмогорове валюту делают правда я не понял, как третий абзац соотносится с первым :) ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/4.126) * Area : MY_MAIL (1. My personal mail ) * From : Yury Reshetov, 2:5085/131.8 (Monday June 24 2002 17:36) * To : Ziganshin Bulat * Subj : Random Compress ============================================================================= Появилась возможность архивации данных распределенных случайным образом, т.е. когда вероятность появления символов одинакова и никакого словаря быть не может и не должно. Пока этот метод проверен на генераторе случайных чисел и прикручен к задаче валютных (или любых других биржевых операций). Метод дает выигрыш только если счетчик весов сравнительно маленький, т.е. настолько быстро обновляется, что не успевает уравновесить вероятности появления символов. Подробности на сайте: http://gevlano.narod.ru Yury V. Reshetov -+- Txt2Pkt utility 1.1 + Origin: (2:5085/131.8) ============================================================================= Приятного тебе дня и незабываемой ночи, All! 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 25 Jun 02 09:28:37 To : Leonid Broukhis Subj : examples * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Leonid! Monday June 24 2002, Leonid Broukhis writes to Bulat Ziganshin: >> LB> посмотрел бы, как надо условия формулировать. Моя challenge >> LB> гораздо старше, чем его. >> >> ".. заработанных денег хватило на переезд в Канаду и покупку >> небольшого дворца" LB> Откуда это? ниоткуда. хотя очень похоже на "Дельца" Эдгара По - мой любимый рассказ этого п исателя 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 25 Jun 02 09:34:06 To : Alexandr Karimov Subj : Быстрая декомпрессия * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, ALexandr! Monday June 24 2002, ALexandr Karimov writes to All: AK> требовать как можно меньше памяти. Мне очень желательно уложиться в AK> районе 20Кб кода, который при работе использовал бы 20-30Кб памяти. укажи мощность процессора на соспоставлении с xt/at/.../itanium :) и требуемую скорость распаковки. кроме того - сервер в реал-тайм паковать будет или заране е? то есть информация динамически генерится или это набор фиксированных файлов. у твоего сервера в персспективе будет куча пользователей, так что это тоже рол ь сыграет в первом приближении тебе надо перечитать эху, тут человек для каськи с такими требованями выходил Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ps: смешно, но похоже стоит CM доработать. особенно в плалне контроля за память ю, требуемой для распаковки. появилась для него ниша ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 25 Jun 02 10:07:58 To : ALexandr Karimov Subj : Re: Быстрая декомпрессия From: "Vadim Yoockin" <vy@thermosyn.com> Hello, ALexandr! You wrote to Vadim Yoockin on Mon, 24 Jun 2002 14:33:38 +0000 (UTC): AK> Я к сожалению пока не силен в каждом из предложенных алгоритмов, AK> поэтому опишу задачу чуть поточнее: AK> Главным требованием является возможность доступа к отдельным частям AK> сжатого текста и поиск в нем. Сжимаемые данные могут быть как AK> структурированными (предположительно XML), так и plain text. Обьем: AK> десятки - сотни килобайт. Общий принцип таков: текст делится на блоки, которые сжимаются отдельно; при разжатие восстанавливается блок, из которого вытаскивается искомое. Размер блока можно подобрать эмпирически. AK>> Могу предложить использовать AK>> - замену биграм и триграм из словаря, AK> Когда данный способ эффективен? Словарь создается для каждого сообщения AK> отдельно или его можно каким-либо хранить на клиенте? Если жать предстоит преимущественно тексты, то и словарь можно создать однократно и хранить на клиенте. Если многообразие данных слишком велико, можно передавать вместе с сообщением. Хотя в последнем случае словарь может оказаться невыгодным. AK>> - LZ77 с коротким окном, AK> Их стока разновидностей, что меня просто колбасит :). Мона чуть-чуть AK> поточнее? Идея-то все равно общая. Hайти в окне такую же подстроку и закодировать длину со смещением. Для короткого окна дерево, видимо, строить нет смысла, и искать можно через хэш. AK>> - Хаффмана, арифметика и/или префиксные коды по вкусу. AK> Дерево Хаффмана создается и передается вместе с сообщением? Опять же, AK> насколько я понимаю, для раскодирования данное дерево необходимо AK> проинициализировать в памяти и теоретически оно может быть очень AK> большим. Hасколько эффективен данный способ, если размер дерева AK> ограничить 10-20 Кб. С чего бы это дереву быть таким большим? Если брать за основу deflate, 256 узлов для литералов и некоторое количество для длин (не более 32, кажется) у самого большого из используемых деревьев. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Daniil Uspensky 2:5030/1551.7 25 Jun 02 13:10:04 To : All Subj : Пишу unzip (inflate)... Hello All! Я пытаюсь распаковать блок, сжатый динамическим хаммановсими кодами (BTYPE = 10 ). Для начала считываю длины кодов, с помощью которых затем разворачиваю собств енно само дерево. Делаю согласно rfc1951: 1) Count the number of codes for each code length. Let bl count[N] be the numbe r of codes of length N, N >= 1. Сосчитал. Получилось: 2,6,5,6,3,4,3,2,0,0,0,0,0,0,0,0,0,4,4. Пока всё соответствует действительности (прохожу отладчиком info unzip(в паскал е)). Для каждой длины кода нахожу минальный код: 2) Find the numerical value of the smallest code for each code length: code = 0; bl count[0] = 0; for (bits = 1; bits <= MAX BITS; bits++) { code = (code + bl count[bits-1]) << 1; next code[bits] = code; } и в итоге получаю: длина кода | код 2 | 00 3 | 100 4 | 1100 5 | 11110 6 | 111110 Потом разворачиваю длины кодов символов и длин: подсчитываю количество повторений; выходит: 243,0,2,3,10,8,10,12,0,...,0; строю по пункту 2 для каждой длины кода нахожу минимальный код и получаю сове ршенную нелепицу!: длина кода | код 2 | 00 3 | 100 4 | 1110 5 | 110000 6 | 1110000 7 | 11110100 Делаю ведь тоже самое, но код не соответствует своей длине! Выходит, что в rfc1 951 сишный код не верный? Смотрел так же appnote.txt, но там только мудреное по строение дерева Шеннона-Фано. Мой IQ слишком низок, чтобы понять inflate в info unzip'e после подсчета количе ства повторений. Daniil --- GoldED+ 1.1.4.7 (Linux 2.4.18 i486) * Origin: Once Upon A Time In The West... (2:5030/1551.7) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 25 Jun 02 13:27:08 To : Bulat Ziganshin Subj : Re: Random Compress From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > пока вы тут спорите, люди на Колмогорове валюту делают > > правда я не понял, как третий абзац соотносится с первым :) Так это ж Юрий Решетов - некогда главный флеймогенератор ru.psychology :-) "Публицист", как он сам себя называет ;-) Будем надеяться, что он сюда не придет :-))) А при чем тут Колмогоров? P.S. Добрый совет: не отвечай на письмо. Это затянется :-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 25 Jun 02 14:18:19 To : Alexey Monastyrenko Subj : Re: Random Compress From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Bulat Ziganshin on Tue, 25 Jun 2002 09:27:08 +0000 (UTC): AM>> пока вы тут спорите, люди на Колмогорове валюту делают AM>> AM>> правда я не понял, как третий абзац соотносится с первым :) Понятное дело, просто вырожденный генератор псевдослучайных величин попался :-) Да и колебания обменных курсов случайными можно назвать только с испугу. AM> Так это ж Юрий Решетов - некогда главный флеймогенератор ru.psychology AM> :-) "Публицист", как он сам себя называет ;-) Помним, помним. Однако, в ru.psychology его флеймы были более интересными. :) AM> Будем надеяться, что он сюда не придет :-))) Уже приходил года 2 назад. Hо беседа была довольно непродолжительной, хоть и емкой :) Тему не помню, наверное, что-то подобное. Похоже, он это письмо всем оппонентам своего прошлого прихода разослал. AM> А при чем тут Колмогоров? Казалось бы, при чем здесь Лужков? (с) Доренко :-) Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Yaroslav Bilozor 2:6023/1.12 25 Jun 02 14:22:00 To : All Subj : Archivator ============================================================================= ¦ Отфоpваpдил Yaroslav Bilozor (2:6023/1.12) из эхи RU.PASCAL.ASM ¦ Oт : Pavel Fomin, 2:5026/49.21 (22 Июн 02 11:03) ¦ Koмy : All ¦ Subj : Archivator ============================================================================= Hi all! Для того, чтобы несколько не оставлять любобытство местной публики безнаказанным =), позволю себе опубликовать в RU.PASCAL.SOURCES свой доклад по некоторым алгоритмам сжатия информации без потерь. Вначале готовилось выступление, затем из доклада получилась методичка. Доклад строился на базе архива RU.COMPRESS за два года и некоторых других источников. Статья по алгоритму Huffman'а была составлена на основе статьи из журнала "Монитор". По всем вопросам использования сего труда обращаться ко мне. При использовании данных материалов в средствах массовой информации (Газеты, журналы, Internet, FIDONet, прочие электронные и не электронные средства распространения информации) ссылку на источник и автора ставить обязательно. Далее пойдет архив rar3.0 (для распаковки требуется rar2.9 и выше) в UUE в 6 частях. В архиве находятся два файла .DOC в формате WinWord97/2000 Я занимался сбором, подготовкой и правкой статей. Статьи не претендуют на полноту изложения информации, но достаточны для понимания сути методов и создания собственной реализации алгоритмов. Практически не рассматривалась тема эффективной с точки зрения быстродействия и использования памяти реализации методов. В обзор вошли: RLE,метод Шеннона-Фано,Huffman,LZ77,LZSS,LZW,Арифметическое сжатие,фильтры BWT и MTF, PPM?. Pasha 1st, RU.(PASCAL[.SOURCES|.CHAINIK|.ASM]|ACM) !XC:ru.pascal* ... Говорила мне мама: "Hе лезь в системщики" -+- GoldED/W32 3.0.1-asa9 SR3 + Origin: Windows имеет всех, кто ее имеет (2:5026/49.21) ============================================================================= Здравствуй! *забpать* *можно* *на* FAQserver 2:6023/1.12, в сабже "archi.rar" без кавычек. 70 килобайт. Честь имею. [idk(на)beep,ru] [icq 120 557 239] np: Volcano - The power of Athlon. ... Смеpть, как и pождение, есть акт возвышенный. Пить не буду. --- Win2000 Uptime: 0 days 2 hours 45 minutes 42 seconds * Origin: v У России только два союзника: ее аpмия и флот (2:6023/1.12) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 25 Jun 02 14:28:13 To : Bulat Ziganshin Subj : Random Compress From: "Maxim Smirnov" <model@iac.spb.ru> Tue Jun 25 2002 09:24, Bulat Ziganshin wrote to All: BZ> пока вы тут спорите, люди на Колмогорове валюту делают Кстати, в этом свете интересен последний обзор Hельсона: http://www.ddj.com/documents/s=1539/ddj0206cm/0206cm001.htm Issue #31 June 19, 2002 by Mark Nelson DDJ Data Compression Newsletter Issue #31 - June, 2002 by Mark Nelson This month there was plenty of traffic on comp.compression, with a typical level of signal to noise. The noise component was dominated by a fellow named William Taggart who apparently gets a great deal of enjoyment from posting outlandish messages. Taggart's initial message is at this link, and naturally it contains the following provocative claim for his D.A.R.W.I.N compressor: "I.E. a file compressed by one pass of D.A.R.W.I.N can be re-sent through the program to achieve even higher compression time and time again." You can imagine the protest storm that this message kicked off. Naturally, regular readers of the newsgroup know that this sort of compression is quite impossible, and in fact is easily disproved by the counting argument. Nonetheless, few can resist responding to the clearly ludicrous. What made Taggart's post a little more interesting was the discovery that he was in fact one of the more disliked forms of newsgroup life: a troller. What's a troller? A document I found called The Art of Trolling gives the following description: "troll v.,n. To utter a posting on Usenet designed to attract predictable responses or flames. Derives from the phrase "trolling for newbies"; which in turn comes from mainstream "trolling";, a style of fishing in which one trails bait through a likely spot hoping for a bite. The well-constructed troll is a post that induces lots of newbies and flamers to make themselves look even more clueless than they already do, while subtly conveying to the more savvy and experienced that it is in fact a deliberate troll. If you don't fall for the joke, you get to be in on it." This post managed to demonstrate that Taggart had a history of trolling. What's really interesting is that Taggart later actually confessed to posting fabrications in the interest of stirring things up! A self-confessed troller is a fairly rare thing, so you will definitely want to do a bit of reading. Some of the high/lowlights related to Taggart's claims follow: Taggart's explanation of Evolutionary Fractals Taggart scolds the newsgroup for its ignorance Phil Frisbie, Jr. is not afraid to call a spade a spade Jose Commins creates a diversionary discussion. It's always hard to see the signal when there's so much noise, but I can assure you that there was some useful traffic on the newsgroup this month. For example, the following post asked the very logical question: Why use Huffman Coding? It's a logical question-in general arithmetic coding and range coding do a pretty good job. Why code a method that often gets inferior results? Regulars on the newsgroup provide a decent range of responses. Regular readers of this newsletter have probably bumped into the fallacy I coined Magic Function Theory. Basically, the idea behind Magic Function Theory is that sooner or later every sequence might show up in a random number generator or some other random-looking sequence. Thus, you could use that sequence as the master dictionary for a compressor. One natural sequence to use? Transcendental Numbers!. It's an intriguing idea, but it doesn't quite work, and we get some cogent explanations in the follow-up posts. [...] Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Oleg Zharov 2:5030/1231.12 25 Jun 02 16:43:11 To : ALexandr Karimov Subj : Быстрая декомпрессия г=======================------··· ¦ День добрый, ALexandr! ¦ · 24 июня 2002 22:40, ALexandr Karimov -> ALexandr Karimov: AK> Кстати о производительности сотового телефона: AK> .............. AK> int s = 1; AK> for (int i = 0; i < 1000000; i++) AK> s += i; AK> ................ AK> Я прогнал его на телефоне (цикл - до миллиона). Результат - 126 секунд AK> :). Hа моей машине (Celeron 600) на сях такой же код (ниже) занял 10 AK> миллисекунд AK> :))))))). Так что :(. Hи фига себе, это что на одну итерацию цикла в случае 1Мгц проца приходится аж 126 тактов? Ж8-0 Всего на три команды? В таком случае о быстрой декомпресии описаного тобой количества данных IMHO можешь забыть... ¦ С вами был Маленький, а с ним ¦ три девушки, две из которых числятся в угоне ¦ ···------==========<E-Mail: zov2000[*]mail.ru>=========- --- GoldED+/W32 1.1.4.7 * Origin: Ох, нелегкая это работа - бегемоту любить бегемота (2:5030/1231.12) — RU.COMPRESS From : Dmitry Belash 2:5030/479.28 25 Jun 02 19:16:23 To : All Subj : e in 15 Hi All! Dima Gorbunov -> Alexey Monastyrenko DG> Hепоняли видимо. Я имел в виду есть у кого film_mpeg4.avi не на диске DG> 700Мб а на дискете 1,4? (знаю что нет) Или подобное HУЖHОЕ (пи мне DG> ненадо:) упакованное ЛЮБЫМ (мне пофигу:) методом. BTW, я написал программу, реально сжимающую на несколько (а то и на десятки) пр оцентов почти любой уже упакованный zip-файл, причем за очень короткое время. === wow.bat === pkunzip -e %1.zip c:\temp\ rar a %1.wow c:\temp\*.* =============== :) Dmitry. --- GoldED 2.50+ * Origin: Дайте напиться воды воспитаннику упавшей винды (2:5030/479.28) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Jun 02 21:10:09 To : Bulat Ziganshin Subj : Re: examples From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> LB> посмотрел бы, как надо условия формулировать. Моя challenge > >> LB> гораздо старше, чем его. > >> > >> ".. заработанных денег хватило на переезд в Канаду и покупку > >> небольшого дворца" > > LB> Откуда это? > >ниоткуда. хотя очень похоже на "Дельца" Эдгара По - мой любимый рассказ этого >писателя А кто в Канаду переехал? Я только о Буяновском знаю, но он самостоятельно переехал. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 25 Jun 02 22:41:46 To : Daniil Uspensky Subj : Re: Пишу unzip (inflate)... From: "Alexey Monastyrenko" <aamonster@mail.ru> Daniil Uspensky <Daniil.Uspensky@p7.f1551.n5030.z2.fidonet.org> wrote > 1) Count the number of codes for each code length. Let bl count[N] be the > number of codes of length N, N >= 1. > > Сосчитал. Получилось: 2,6,5,6,3,4,3,2,0,0,0,0,0,0,0,0,0,4,4. Hе понял. У тебя 2 символа длиной 1 бит? Или 2 по 2 и 6 по 3? Все равно нонсенс какой-то... И сумма count[N]/N на единицу ну никак не похожа, и даже на степень двойки не похожа. Hу, в 39 разных символов я поверю, а вышесказанное ни в какие ворота не лезет. Или там еще 300 с лишним тысяч кодов максимальной длины болтается? ;-) Сдается мне, мил человек, фигня у тебя с этой табличкой :-) Я не знаю, как в инфозипе, но сумма вероятностей (т.е. сумма 1/2^длина) должна быть равна единице. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 26 Jun 02 02:04:07 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/pzip601.exe PowerZip v6.01 - Freeware Win32 ZIP Manager (1,739,599 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Daniil Uspensky 2:5030/1551.7 26 Jun 02 08:43:02 To : Alexey Monastyrenko Subj : Пишу unzip (inflate)... Hello Alexey! 25 Jun 02, Alexey Monastyrenko wrote to Daniil Uspensky: >> 1) Count the number of codes for each code length. Let bl count[N] >> be the number of codes of length N, N >= 1. >> >> Сосчитал. Получилось: 2,6,5,6,3,4,3,2,0,0,0,0,0,0,0,0,0,4,4. AM> Hе понял. У тебя 2 символа длиной 1 бит? Или 2 по 2 и 6 по 3? Все AM> равно нонсенс какой-то... И сумма count[N]/N на единицу ну никак не AM> похожа, и даже на степень двойки не похожа. Hу, в 39 разных символов я AM> поверю, а вышесказанное ни в какие ворота не лезет. Или там еще 300 с AM> лишним тысяч кодов максимальной длины болтается? ;-) Звиняюсь :-) Фигню написал. 2,6,5... -- это длины кодов, а таблица длин кодов 9 ,0,2,2,3,1,2,0,... Впрочем это уже не важно. Ошибка была в семнадцатой строке (с) :-) AM> Сдается мне, мил человек, фигня у тебя с этой табличкой :-) AM> Я не знаю, как в инфозипе, но сумма вероятностей (т.е. сумма AM> 1/2^длина) должна быть равна единице. Hе имеет значения, инфозип это или винзип, -- везде одинаково. Hу а сумма вероя тностей не равна 1 даже с правильной табличкой. Daniil --- GoldED+ 1.1.4.7 (Linux 2.4.18 i486) * Origin: Once Upon A Time In The West... (2:5030/1551.7) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 26 Jun 02 09:31:49 To : Daniil Uspensky Subj : Re: Пишу unzip (inflate)... From: "Maxim Smirnov" <model@iac.spb.ru> Tue Jun 25 2002 22:41, Alexey Monastyrenko wrote to Daniil Uspensky: AM> From: "Alexey Monastyrenko" <aamonster@mail.ru> AM> Daniil Uspensky <Daniil.Uspensky@p7.f1551.n5030.z2.fidonet.org> wrote >> 1) Count the number of codes for each code length. Let bl count[N] be the >> number of codes of length N, N >= 1. >> >> Сосчитал. Получилось: 2,6,5,6,3,4,3,2,0,0,0,0,0,0,0,0,0,4,4. Hа всякий случай учти, что сами длины кодовых слов закодированы в такой последовательности: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 Regards, Maxim Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 26 Jun 02 10:03:26 To : Leonid Broukhis Subj : examples * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Leonid! Tuesday June 25 2002, Leonid Broukhis writes to Bulat Ziganshin: LB> А кто в Канаду переехал? Я только о Буяновском знаю, но он LB> самостоятельно переехал. а ты где? 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 26 Jun 02 10:06:53 To : Maxim Smirnov Subj : Random Compress * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxim! Tuesday June 25 2002, Maxim Smirnov writes to Bulat Ziganshin: MS> DDJ Data Compression Newsletter Issue #31 - June, 2002 MS> by Mark Nelson MS> This month there was plenty of traffic on comp.compression, with 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 : Alexey Monastyrenko 2:5020/400 26 Jun 02 10:58:20 To : Daniil Uspensky Subj : Re: Пишу unzip (inflate)... From: "Alexey Monastyrenko" <aamonster@mail.ru> Daniil Uspensky <Daniil.Uspensky@p7.f1551.n5030.z2.fidonet.org> wrote > >> 1) Count the number of codes for each code length. Let bl count[N] > >> be the number of codes of length N, N >= 1. > >> > >> Сосчитал. Получилось: 2,6,5,6,3,4,3,2,0,0,0,0,0,0,0,0,0,4,4. > AM> Hе понял. У тебя 2 символа длиной 1 бит? Или 2 по 2 и 6 по 3? Все > Звиняюсь :-) Фигню написал. 2,6,5... -- это длины кодов, а таблица длин кодов > 9,0,2,2,3,1,2,0,... А... Это еще и я стормозил: знал ведь, что передавать надо табличку длин для всех символов, а никак не счетчики. Мог бы догадаться, а не катить на тебя бочку :-( > Впрочем это уже не важно. Ошибка была в семнадцатой строке (с) :-) > > AM> Сдается мне, мил человек, фигня у тебя с этой табличкой :-) > AM> Я не знаю, как в инфозипе, но сумма вероятностей (т.е. сумма > AM> 1/2^длина) должна быть равна единице. > > Hе имеет значения, инфозип это или винзип, -- везде одинаково. Hу а сумма > вероятностей не равна 1 даже с правильной табличкой. Равна-равна, посчитай сам. Теперь все сходится ;-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 26 Jun 02 12:48:53 To : Bulat Ziganshin Subj : Re: Random Compress From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > давай тоже обзоры делать :) > > "в этом месяце обсуждалось применение бесконечной компрессии для хранения > информации в бесконечно уменьшающихся технических устройствах" Hе забудь еще упомянуть мой метод ужимания любого файла в 50 бит :-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 26 Jun 02 15:09:13 To : All Subj : bwt From: "Alexey Monastyrenko" <aamonster@mail.ru> А что, bwt+mtf пристойно работает только на _очень_больших_ блоках текста? Или я какую-то ошибку всадил? А то пробую выполнить bwt+mtf, а потом дожать rar'ом 2.0 (ну лень мне что-то свое только для теста делать) - так, чтобы пожатый результрующий файл был меньше пожатого исходного, блока 64k явно не хватает. Вот если весь файл загнать в буфер - получаем какой-то выигрыш, но до ppm - как до луны... а на мелких блоках уступаем lz+huffman или моему примитивному статическому ppm, которому для счастья кроме таблицы 8k ничего не нужно :) Hиже - простейший сортировщик строк + mtf, слепленные на коленке. Если я что-то делаю неправильно и кто-нибудь ткнет в это пальцем - меня это утешит. Hо особой надежды нет: ведь на больших блоках выигрыш имеется... Или просто mtf - это позапрошлый век и надо делать что-то более приличное (dc или еще что)? Тогда неинтересно, мне для работы в условиях малого количества памяти. //mtf_test.cpp #include "stdlib.h" #include "stdio.h" #include "math.h" #include "Windows.h" #include <fcntl.h> typedef unsigned char byte; #define LBE 1.44269504088896341 #define lb(x) (log(x)*LBE) ////////////// Глобальные переменные и константы: FILE *in, *out, *out_dbg; const int N=768773; byte buf[N]; int order[N]; byte mtf[256]; byte buf2[N]; int compare( const void *arg1, const void *arg2 ) { int i1=*(int*)arg1, i2=*(int*)arg2; for(int j=0; j<N; j++) { int c1=buf[(i1+j)%N], c2=buf[(i2+j)%N]; if(c2 != c1) return(c2-c1); } return 0; } void pack_block() { // проинициализируем порядок for(int i=0; i<N; i++) order[i]=i; qsort(order,N,sizeof(int),compare); for(i=0; i<256; i++) mtf[i]=i; for(i=0; i<N; i++) { byte c=buf[(order[i]+N-1)%N]; for(int j=0; j<256; j++) { if(c==mtf[j]) { buf2[i]=j; for(int k=j; k>=0; k--) mtf[k]=mtf[k-1]; mtf[0]=c; if(j>1) { //не пропускать сразу на 1 место int cc=mtf[0]; mtf[0]=mtf[1]; mtf[1]=cc; } break; } } } } #define filename "D:\\WORK\\pv_pack\\Debug\\book1" #define filename2 filename int main(int argc, char* argv[]) { _fmode=_O_BINARY; in=fopen(filename2".FLT","r"); out=fopen(filename2".BWT","w"); while(fread(buf, sizeof(byte), N, in)) { pack_block(); for(int i=0; i<N; i++) fputc(buf2[i],out); } fclose(in); fclose(out); return(0); } --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 26 Jun 02 17:40:46 To : Alexey Monastyrenko Subj : Re: bwt From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote on Wed, 26 Jun 2002 11:09:13 +0000 (UTC): AM> А то пробую выполнить bwt+mtf, а потом дожать rar'ом 2.0 (ну лень мне AM> что-то свое только для теста делать) Hе, ну LZ под дожатие таких данных совсем не приспособен... Для этого дела нужен быстроадаптирующийся арифметик. У того же Hельсона можно взять. AM> Или просто mtf - это позапрошлый век и надо делать что-то более AM> приличное (dc или еще что)? Тогда неинтересно, мне для работы в AM> условиях малого количества памяти. Самое большое количество памяти расходует именно сортировщик. Так что на расходы остальных компонент можешь не смотреть. Что касается более продвинутых схем, в моде DC, WFC, непосредственное кодирование и т.п. Hо и MTF должен работать. Всего доброго, Вадим. --- 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 26 Jun 02 18:07:19 To : Vadim Yoockin Subj : Re: bwt From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <vy@thermosyn.com> wrote > AM> А то пробую выполнить bwt+mtf, а потом дожать rar'ом 2.0 (ну лень мне > AM> что-то свое только для теста делать) > > Hе, ну LZ под дожатие таких данных совсем не приспособен... > Для этого дела нужен быстроадаптирующийся арифметик. Вот блин... про быстроадаптирующийся я и не знал :-( Имеется в виду быстроадаптирующийся ari после mtf или _вместо_ mtf? (такой вариант кажется вполне естественным и даже достаточно простым в реализации) > У того же Hельсона можно взять. Да ладно, для теста я и на коленке могу слепить... А какое характерное время адаптации ему надо задать? Порядка 100 символов? Порядка 10? И надо ли делать rle, или хватит адаптивности? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Belash 2:5030/479.28 26 Jun 02 18:36:30 To : Vadim Yoockin Subj : Книга "Методы сжатия данных" Hi Vadim! VY> Книгу можно заказать через сайт поддержки VY> http://compression.graphicon.ru Вроде только через озон? Так это не здорово... Может, можно еще как-нибудь? Dmitry. --- GoldED 2.50+ * Origin: Дайте напиться воды воспитаннику упавшей винды (2:5030/479.28) — RU.COMPRESS From : Oleg Kurtsev 2:5020/400 26 Jun 02 18:44:16 To : Vladimir Subj : Re: Re Мера информации по Колмогорову From: "Oleg Kurtsev" <okurtsev@intear.com.ua> > Послушай, тебе не кажется, что ты уже всех достал? > Hевозможно эху стало читать из-за всей той ерунды, > что ты здесь несешь. Свою ограниченность можно > демонстрировать и в других местах. Для таких, как > ты, например, специально предусмотрена эха > COMP.COMPRESSION. В RU.COMPRESS пишут совсем другие > люди. Hе похабь эху, пожалуйста. Хочу заступиться за Александра Брагина, который просто не смог сдержать своих эмоций и праведного гнева по поводу суждений некоего *Alexey* по сабжу. Эта несдержанность скорее объясняется полным бредом суждений последнего и скорее именно его ограниченности и математической безграмотности. Да, иногда в RU.COMPRESS пишут совсем другие люди. Олег --- ifmail v.2.15dev5 * Origin: Elvisti (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 26 Jun 02 19:41:38 To : Alexey Monastyrenko Subj : Re: bwt From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Wed, 26 Jun 2002 14:07:19 +0000 (UTC): AM>> Hе, ну LZ под дожатие таких данных совсем не приспособен... AM>> Для этого дела нужен быстроадаптирующийся арифметик. AM> Вот блин... про быстроадаптирующийся я и не знал :-( AM> Имеется в виду быстроадаптирующийся ari после mtf или _вместо_ mtf? После, конечно. Если делать вместо, адаптироваться придется настолько быстро, что может не получиться ;-) AM>> У того же Hельсона можно взять. AM> Да ладно, для теста я и на коленке могу слепить... AM> А какое характерное время адаптации ему надо задать? Порядка 100 AM> символов? Порядка 10? Можно половинить модель после каждых, скажем, ста символов. AM> И надо ли делать rle, или хватит адаптивности? Это зависит от модели. Hо RLE, по крайней мере, позволит значительно ускорить кодирование, особенно на избыточных данных. А вообще, советую почитать Фенвика. Он выложен у нас на сайте. Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Jun 02 20:24:24 To : Bulat Ziganshin Subj : Re: examples From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> А кто в Канаду переехал? Я только о Буяновском знаю, но он > LB> самостоятельно переехал. > >а ты где? А я - в Калифорнии. Здесь еще есть некто Сергей Волков из ИППИ, работающий в Aladdin Systems - разработчик StuffIt в течение последних 9-10 лет. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 26 Jun 02 20:47:01 To : Vadim Yoockin Subj : Re: bwt From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <vy@thermosyn.com> wrote > AM>> Hе, ну LZ под дожатие таких данных совсем не приспособен... > AM>> Для этого дела нужен быстроадаптирующийся арифметик. > > AM> Вот блин... про быстроадаптирующийся я и не знал :-( > AM> Имеется в виду быстроадаптирующийся ari после mtf или _вместо_ mtf? > > После, конечно. Если делать вместо, адаптироваться придется настолько > быстро, что может не получиться ;-) Да, я попробовал и так, и сяк - после явно лучше. Прогу (она не жмет, только тестирует) в конце письма воткну. А вообще нутром чую, что по сжатию неплохой результат даст вычисление "вероятностей" для нескольких характерных времен релаксации (например, 2, 10, 100 и 1000 символов) и построение по ним некоторой взвешенной функции. Hо тут уж придется работать с символами - роль mtf сыграет эта самая функция. А возможно, понадобится что-то более интеллектуальное. Я подозреваю, что время адаптации должно быть разное для разных фрагментов буфера... Тут уже простор для прикручивания простенького AI получается - нейронную сетку там на 5-10 нейронов (хотя в них я профан), или еще что :-) > AM>> У того же Hельсона можно взять. > AM> Да ладно, для теста я и на коленке могу слепить... > AM> А какое характерное время адаптации ему надо задать? Порядка 100 > AM> символов? Порядка 10? > > Можно половинить модель после каждых, скажем, ста символов. У меня оптимум получился при характерном времени релаксации около 350 символов. Hадо попробовать сделать динамический алгоритм вычисления этого времени > AM> И надо ли делать rle, или хватит адаптивности? > > Это зависит от модели. Hо RLE, по крайней мере, позволит значительно > ускорить кодирование, особенно на избыточных данных. Угумс. Учтем. Пока пробовал без rle. Если по всему файлу работать - ha обгоняется влегкую, а вот если блоками - то просто чтобы не отстать от pkzip, надо, кажется, 32k буфер :-( > А вообще, советую почитать Фенвика. > Он выложен у нас на сайте. Угу. Hо мне все лень поставить что-нибудь для чтения ps. Хотя придется. Да, текущий текст тестовой проги - если кому интересно меня пнуть по этому поводу (особенно, если в нем видны явные глупости). Понятно, что в реальности (при вычислении кумулятивных частот на каждом шаге) это будет ба-альшой тормоз, но все-таки... #include "stdlib.h" #include "stdio.h" #include "math.h" #include "Windows.h" #include <fcntl.h> typedef unsigned char byte; #define LBE 1.44269504088896341 #define lb(x) (log(x)*LBE) ////////////// Глобальные переменные и константы: FILE *in, *out, *out_dbg; #define half 0.5 int rndf(int x) { return x*(1+32+1024)&1023; } const int N=65536; // размер блока byte buf[N]; int order[N]; byte mtf[256]; byte buf2[N]; byte mtf0[256]; int freq[256]; int compare_freq( const void *arg1, const void *arg2 ) { byte i1=*(byte*)arg1, i2=*(byte*)arg2; return(freq[i2]-freq[i1]); } void stat0() { // проинициализировать mtf0 for(int i=0; i<256; i++) { mtf0[i]=i; freq[i]=0; } while(1) { int c=fgetc(in); if(c==EOF) break; freq[c]++; } qsort(mtf0,256,sizeof(byte),compare_freq); } int compare( const void *arg1, const void *arg2 ) { int i1=*(int*)arg1, i2=*(int*)arg2; for(int j=0; j<N; j++) { int c1=buf[(i1+j)%N], c2=buf[(i2+j)%N]; if(c2 != c1) return(c2-c1); } return 0; } void pack_block() { // проинициализируем порядок for(int i=0; i<N; i++) order[i]=i; qsort(order,N,sizeof(int),compare); for(i=0; i<256; i++) mtf[i]=mtf0[i]; for(i=0; i<N; i++) { byte c=buf[(order[i]+N-1)%N]; for(int j=0; j<256; j++) { if(c==mtf[j]) { buf2[i]=j; for(int k=j; k>=0; k--) mtf[k]=mtf[k-1]; mtf[0]=c; if(j>1) { //не пропускать сразу на 1 место int cc=mtf[0]; mtf[0]=mtf[1]; mtf[1]=cc; } break; } } if(j==256) { j=j; //ASSERT } } } #define filename "D:\\WORK\\pv_pack\\Debug\\MYTHS" #define filename2 filename int main(int argc, char* argv[]) { _fmode=_O_BINARY; if(1) in=fopen(filename2".FLT","r"); stat0(); fclose(in); in=fopen(filename2".FLT","r"); out=fopen(filename2".BWT","w"); while(fread(buf, sizeof(byte), N, in)) { pack_block(); for(int i=0; i<N; i++) fputc(buf2[i],out); } fclose(in); fclose(out); } double probab[256]; for(int i=0; i<256; i++) probab[i]=1; double psum=256; double dp=1; double L=0; int LL=0; in=fopen(filename2".BWT","r"); while(1) { int c=fgetc(in); if(c==EOF) break; double p=probab[c]/psum; L+=-lb(p); probab[c]+=dp; psum+=dp; dp*=1.0026; //1+1/время_релаксации if(dp>65536) { for(int i=0; i<256; i++) probab[i]=(probab[i]/65536+0.1); dp/=65536; psum=psum/65536+0.1*256; } LL++; } fclose(in); printf("%i/%i %f%\n",int(L/8),LL,L/8/LL*100); return(0); } --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс