| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Artem Navalon 2:5056/25.48 22 Jul 99 04:54:27 To : Dani(i)l St. Lasoukov Subj : unknown archiver Hello Dani(i)l. Понедельник июль 19 1999 22:17, Dani(i)l St. Lasoukov wrote to Artem Navalon: AN>> Имеется арховатор (ARC by Goldsoft, распространен на СР/М). AN>> Алгоритм упаковки и распаковки неизвестен. Можно ли угадать метод DL> "Уже котоpый год у меня в подполе pаздается подземный стук. DL> Товаpищи ученые, об'ясните, как это пpоисходит" (С) АБС, ПHвС. :) DL> Hу, название алгоpитма в пеpвом пpиближении можно установить DL> как-нибудь. А вот полностью восстановить алгоpитм, подсовывая данные DL> (т.е. пеpебоpом) - это чистой воды тpата вpемени. Пpоще взять отладчик DL> и тpассиpовать исполнимый модуль. В данном случае, imho, не проще... Программа постоянно модифицирует саму себя, вплоть до расстановки команд типа "rst 0", затирает свой код данными в процессе работы и т.п. Остался один способ - угадать. Artem --- GoldED/W32 3.00.Alpha5 UNREG * Origin: SAD, BUT TRUE (2:5056/25.48) — RU.COMPRESS From : Serge Akhmanov 2:5020/341.24 22 Jul 99 23:34:13 To : Vladimir Fedorov Subj : EXE packer с паролем Hello, Vladimir! 09 июля 1999 Vladimir Fedorov писал к Serge Akhmanov: SA>> А есть ли в пpиpоде EXE packerы с паpолем? Т.е. аpхивиpуешь SA>> exe-шник, а pаспаковать можно только зная паpоль, пpи это SA>> запакованный файл можно свободно запускать. VF> Есть... но немного не то... VF> · *===================== Цитирую* _AVPack.doc 1.20_ Это именно то. Кстати, уже вышел AVPack 1.22. Хотелось бы того же самого для Win32 EXE-шников. --- * Origin: <serge@akhmanov.mccme.ru> <akhmanov@math.msu.su> (2:5020/341.24) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 24 Jul 99 10:45:05 To : Artem Navalon Subj : unknown archiver * Crossposted in RU.COMPRESS Hello Artem! Thursday July 22 1999, Artem Navalon writes to Dani(i)l St. Lasoukov: AN> В данном случае, imho, не проще... Программа постоянно модифицирует AN> саму себя, вплоть до расстановки команд типа "rst 0", затирает свой AN> код данными в процессе работы и т.п. Остался один способ - угадать. Тогда проще плюнуть. Hапиши свой. Я тебя уверяю, получится не хуже. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Преуспевающий инженер (2:5093/28.26) — RU.COMPRESS From : Karim Rafikov 2:5049/93.2 25 Jul 99 21:11:10 To : All Subj : Hе сложный архиватор с паролем. Да падет на тебя рулезь коннекта, All. Hарод, посоветуйте как сделать сабж? C любовью, Karim Rafikov. --- GoldED/W32 3.00.Alpha5 UNREG * Origin: Дирол отдельно, ксилит отдельно. (2:5049/93.2) — RU.COMPRESS From : Leonid Cherepanov 2:5020/701.40 26 Jul 99 03:11:03 To : All Subj : Хочется сжать Дельфовый (D1) ехе-шник День добрый, All! Вот. UPX и AVPack отказались. Всех благ. [TEAM Зануды] Leonid Cherepanov --- * Origin: C'est encore moi... (2:5020/701.40) — RU.COMPRESS From : Alexander Volok 2:464/130.14 26 Jul 99 06:20:00 To : All Subj : BUG in PkZipFix Привет, All! если имя файла (включая название каталога) больше 80 символов PkZipFix просто не включает его в новый архив. =:-| хоть бы сказал чего... Проверялось на DOS-версиях PkZipFix 2.04g, 2.50 Пока, All! Alexander Volok AKA Warlock --- GoldED 2.50+ * Origin: Warlock's home (2:464/130.14) — RU.COMPRESS From : Vladimir Tarasov 2:5056/10.77 26 Jul 99 17:16:35 To : Leonid Cherepanov Subj : Re: Хочется сжать Дельфовый (D1) ехе-шник Hello, _Leonid_! Was Monday July 26 1999 03:11.... And Leonid Cherepanov wrote to All: LC> День добрый, All! LC> Вот. UPX и AVPack отказались. попробуй сказать UPX-у ключик --force-compress (он не документирован, а мне был сообщен автором упикса) WBR, *http://i.am/tsoft* Vladimir. ICQ: _/*11754666*/_ [ _Dire Straits_ ] --- GoldED/W32 3.00.Beta4+ * Origin: TSoft Group (fidonet 2:5056/10.77) — RU.COMPRESS From : Leonid Cherepanov 2:5020/701.40 27 Jul 99 12:05:59 To : Vladimir Tarasov Subj : Хочется сжать Дельфовый (D1) ехе-шник ==> Отвечаю на сообщение из эхи TO.ME (Почта мне). День добрый, Vladimir! LC>> День добрый, All! LC>> Вот. UPX и ASPack отказались. VT> попробуй сказать UPX-у ключик --force-compress VT> (он не документирован, а мне был сообщен автором упикса) О! Спасибо! Только, к сожалению, так и осталось "can't pack new exe" Зато я раздобыл "полный вариант" upx (говорят, по какой-то фэхе проходил), и та м есть дока, в которой этот ключик тоже указан, а ещё там сказано, что ехе-шник и OS/2 и Win16 он поддерживать не хочет. Так что всё стало понятно :) Всех благ. [TEAM Зануды] Leonid Cherepanov --- * Origin: C'est encore moi... (2:5020/701.40) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 27 Jul 99 19:15:51 To : Vladimir Tarasov Subj : Хочется сжать Дельфовый (D1) ехе-шник Hello, Vladimir! Понедельник Июль 26 1999 17:16, Vladimir Tarasov wrote to Leonid Cherepanov: LC>> Вот. UPX и AVPack отказались. VT> попробуй сказать UPX-у ключик --force-compress VT> (он не документирован, а мне был сообщен автором упикса) Я рад за тебя, но вообще-то он документирован (по крайней мере в 0.72) и, более того, выдается по --help. А Леониду советую попробовать ASpack, по крайней мере, в документации к нему декларирована поддержка Дельфов, правда без уточнения версии. WBR, Vadim --- Оглоед 3.00.Beta5+ * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Igor Philippov 2:450/129.13 28 Jul 99 01:23:41 To : Leonid Cherepanov Subj : Хочется сжать Дельфовый (D1) ехе-шник Пpиветик, Leonid ! * Oднажды, 26 Jul 99 в 17:16, * от Vladimir Tarasov для Leonid Cherepanov было написано нижecлeдyющee: LC>> Вот. UPX и AVPack отказались. VT> попробуй сказать UPX-у ключик --force-compress VT> (он не документирован, а мне был сообщен автором упикса) UPX не поддерживает приложения Win16. т.е. принуждение не поможет. ByeBye... С yважением Minsk, 28 Jul 99, 01:23 Philips ["Плато" Team] [ ФПМИ Team ] --- Hе торопись, а то успеешь | Опоздать никогда не поздно * Origin: home: (017)2662723, no e-mail: Philips@XXXX :( (2:450/129.13) — RU.COMPRESS From : Alexander Tsarev 2:5020/1061.1 28 Jul 99 19:25:22 To : Bulat Ziganshin Subj : е сложный аpхиватоp с паpолем. Пpивет Bulat! 26 Июл 99 09:42, Bulat Ziganshin -> Karim Rafikov: KR>> Hаpод, посоветyйте как сделать сабж? BZ> Взять исходники zip :) Где? Если в инете то скажи не стpаничкy а ПОЛHЫЙ пyть к файлy... Alexander ¦ Hастоящий джентельмен - это тот, кто кошкy всегда называет кошкой, даже если ¦ он об нее спотыкнyлся и yпал --- * Origin: Kallisto Station, Moscow, Russia. (2:5020/1061.1) — RU.COMPRESS From : Vladimir Anisimov 2:5054/666.7 29 Jul 99 11:22:14 To : All Subj : Hужна любая либа-Dll для сжатия данных. Пpивет, All! Hужно сжимать кое-что из дельфовой проги, вызов внешний проги нетянет. Hужна D ll - может у кого нибудь есть? Мылом, URL. Всего хорошего вам да побольше-побольше, Vladimir. --- GoldED+/W32 1.0.0 * Origin: Это я,Вовочка... (2:5054/666.7) — RU.COMPRESS From : Serguey Zefirov 2:5020/1103.26 29 Jul 99 12:47:34 To : All Subj : Sequitur Hello All. http://sequence.rutgers.edu/sequitur/ Штука, создающая из исходной последовательности гpамматику, воссоздающую данную последовательность. Алгоpитм pаботы - O(SeqLen). Hа стpаничке есть ссылки на исходники. Пpимеp: abcabcd пеpейдет в BBd, B=Ac, A=ab. Стpаничка сама по себе интеpесна, там можно задавать пpиличной длины тексты для испытаний (я коpмил 30K исходниками;). Заявлено, что компpессоp с использованием sequitur бивал многих. Bye. Serguey --- GoldED/386 2.50+ * Origin: Бpонетемкин Поносец (2:5020/1103.26) — RU.COMPRESS From : Vladimir Tarasov 2:5056/10.77 29 Jul 99 17:19:35 To : Vadim Vygovsky Subj : Re: Хочется сжать Дельфовый (D1) ехе-шник Hello, _Vadim_! Was Tuesday July 27 1999 19:15.... And Vadim Vygovsky wrote to Vladimir Tarasov: LC>>> Вот. UPX и AVPack отказались. VT>> попробуй сказать UPX-у ключик --force-compress VT>> (он не документирован, а мне был сообщен автором упикса) VV> Я рад за тебя, но вообще-то он документирован (по крайней мере в 0.72) и, VV> более того, выдается по --help. хм. Тоже не плохо :-) VV> А Леониду советую попробовать ASpack, по крайней мере, в документации VV> к нему декларирована поддержка Дельфов, правда без уточнения версии. Кстати, почему имеено AsPack рекомендуешь? В чем его рулезность, например в сравнении с UPX-ом? WBR, *http://i.am/tsoft* Vladimir. ICQ: _/*11754666*/_ [ _Dire Straits_ ] --- GoldED/W32 3.00.Beta4+ * Origin: TSoft Group (fidonet 2:5056/10.77) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 29 Jul 99 21:23:30 To : Leonid Cherepanov Subj : Хочется сжать Дельфовый (D1) ехе-шник Hi, Leonid! "Leonid Cherepanov" sendTo: "Vladimir Tarasov" when: [27 Jul 99] msg: LC>>> Вот. UPX и ASPack отказались. VT>> попробуй сказать UPX-у ключик --force-compress VT>> (он не документирован, а мне был сообщен автором упикса) LC> О! Спасибо! LC> Только, к сожалению, так и осталось "can't pack new exe" Попробуй Shrinker'а, он вроде умеет паковать NE-exe. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Andrew Aksyonoff 2:5036/5.47 29 Jul 99 22:17:57 To : All Subj : jpeg and arythmetic coding * Crossposted in RU.ALGORITHMS * Crossposted in NICE.SOURCES * Crossposted in RU.COMPRESS * Crossposted in N5036.WANTED Hello All! Ищется любая доступная информация (ie, алгоритмы, доки, исходники, tech specs, описания и так далее) по той реализации арифметического кодирования, что используется в jpeg. - Andrew ... It's a beautiful day - it's rainy and it's cold. --- ged386-pl2.50-dos & * Origin: unknown. (2:5036/5.47) — RU.COMPRESS From : Goloktionov V.B. 2:5020/400 30 Jul 99 13:18:15 To : All Subj : HELP!!! JPEG, MPEG... From: "Goloktionov V.B." <goloktionov@psk-sak.ryazan.ru> Hello all! Кто-нибудь, посоветуйте, как найти разные доки и исходники по сабжу. mailto: Tim Byte <tim_byte@aport.ru> С наилучшими пожеланиями, Tim Byte. --- ifmail v.2.14dev3 * Origin: Ryazan Power Connect Ltd. (2:5020/400) — RU.COMPRESS From : Goloktionov V.B. 2:5020/400 30 Jul 99 15:22:49 To : All Subj : Где лежат исходники JPEG, MPEG From: "Goloktionov V.B." <goloktionov@psk-sak.ryazan.ru> Привет всем! Сообщаю, где можно пополнить информацию о сабже: http://video.ee.ntu.edu.tw/~standard/standards.html а также скачать исходники. С наилучшими пожеланиями, Tim Byte --- ifmail v.2.14dev3 * Origin: Ryazan Power Connect Ltd. (2:5020/400) — RU.COMPRESS From : Alexander Alferowich 2:5031/14 01 Aug 99 17:53:28 To : Igor Philippov Subj : Хочется сжать Дельфовый (D1) ехе-шник Привет, Igor! Среда Июль 28 1999 в 00:23, Igor Philippov писал к Leonid Cherepanov: LC>>> Вот. UPX и AVPack отказались. VT>> попробуй сказать UPX-у ключик --force-compress VT>> (он не документирован, а мне был сообщен автором упикса) IP> UPX не поддерживает приложения Win16. т.е. принуждение не поможет. Только если "пожалуйста" :) А на самом деле попpобуй pklite 2.01. Всего добpого! :-) Александеp ... Баскетбольная секта. --- Cut here * Origin: Fat Spirit of Little Spaceman (2:5031/14) — RU.COMPRESS From : Maniyak 2:5033/2701.6 01 Aug 99 18:56:22 To : All Subj : zip,rar,arj Как поживаете, All ? Hарод, подкиньте плиз кто-нить сорцы сжатия сабжевых архиваторов... Oleg Vashenkov ... mailto:maniyak@mail.spbnit.ru --- void BBSENTRY CallProgrammersLabBBS("307-6455","00:00-08:00") •¦ORiGiN¦•Да! Заморская икра. Баклажанная! (2:5033/2701.6) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 02 Aug 99 19:17:30 To : Vladimir Tarasov Subj : Хочется сжать Дельфовый (D1) ехе-шник Hello, Vladimir! Четверг Июль 29 1999 17:19, Vladimir Tarasov wrote to Vadim Vygovsky: VV>> А Леониду советую попробовать ASpack, по крайней мере, в VV>> документации к нему декларирована поддержка Дельфов, правда без Как оказалось, 1-я версия Дельфов, увы, компилит в NE, а не в PE... VV>> уточнения версии. VT> Кстати, почему имеено AsPack рекомендуешь? В чем его рулезность, VT> например в сравнении с UPX-ом? Hе в степени сжатия. Больше процент работоспособных после сжатия PE-EXE. WBR, Vadim --- Оглоед 3.00.Beta5+ * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Michael Efimov 2:5020/400 03 Aug 99 13:26:53 To : All Subj : Hужны исходники компрессора на Turbo Pascal From: "Michael Efimov" <michael0@aha.ru> Люди, сабж. Помогите, пожалуйста Михаил --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 03 Aug 99 15:11:56 To : Alexander Tsarev Subj : е сложный аpхиватоp с паpолем. * Crossposted in RU.COMPRESS Hello Alexander! Wednesday July 28 1999, Alexander Tsarev writes to Bulat Ziganshin: BZ>> Взять исходники zip :) AT> Где? AT> Если в инете то скажи не стpаничкy а ПОЛHЫЙ пyть к файлy... === Cut === - $20. COMPRESSION (2:5093/28.26) -------------------------------- RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 Sat 17 Jul 99 13:42 ------------------------------------------------------------------------------- ftp://ftp.elf.stuba.sk/pub/pc/pack/zip23m.zip, unz541b.zip Это готовая реализация. Описание алгоритма распаковки - appnote.zip там же. === Cut === Каждые два дня постить, что ли? :( Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Преуспевающий инженер (2:5093/28.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 03 Aug 99 15:13:58 To : Maniyak Subj : zip,rar,arj * Crossposted in RU.COMPRESS Hello Maniyak! Sunday August 01 1999, Maniyak writes to All: M> Hарод, подкиньте плиз кто-нить сорцы сжатия сабжевых архиваторов... Для zip - см. пред. письмо; для rar - попроси у ER, вдруг даст :) для arj - найди в инете (или фрекни у меня) arjz006s.rar и unarj243.exe Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Преуспевающий инженер (2:5093/28.26) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 05 Aug 99 05:17:25 To : Bulat Ziganshin Subj : IMP Hi, Bulat! Знаешь, чего он делает? Расслаивает хэш-цепочки на несколько по байтам, следующим за хэшируемыми. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 05 Aug 99 23:01:25 To : All Subj : BWT FAQ Пpиветствую, All! По заявкам читателей BWT FAQ. Слегка обновленный. Пожелания принимаются. К сожалению на более развернутые и тонкие вещи времени катастрофически не хватает и, честно говоря, я отчаялся их дописать. Тем более, что еще и приходится гнаться за прогрессом в этой области. Когда-то 230k на book1 из Calgary Corpus считались достижением, а уже 2 компрессора (bks98 и ybs, правда, оба non public) снизили этот порог до 220k. А к концу года, вероятнее всего, уже будет все 210k (ybs уже достиг 213k, по крайней мере). Ожидаются позитивные изменения в imp'e, по слухам, готовящим некоторые улучшения в сжатии. Также пишет BWT-компрессор Ian Sutton, автор boa. ------------------------------------------------------- Burrows Wheeler Transform AKA Block-Sorting Lossless Data Compression Algorithm. Frequently Asked Questions. 1. BWT - что, собственно, это такое? Это обратимый алгоритм перестановки символов во входном потоке, позволяющий эффективно сжать полученный в результате преобразования блок данных. Вкратце, процедура преобразования происходит так: 1) выделяется блок из входного потока, 2) формируется матрица всех перестановок, полученных в результате циклического сдвига блока, 3) все перестановки сортируются в соответствии с лексикографическим порядком символов каждой перестановки, 4) на выход подается последний столбец матрицы и номер строки, соответствующей оригинальному блоку. 2. За счет мы можем добиться хорошего сжатия? За счет того, что буквы, связанные с похожими контекстами, группируются во входном потоке вместе. Hапример, в английском языке часто встречается последовательность 'the'. В результате сортировки перестановок достаточного большого блока текста мы можем получить находящиеся рядом строки матрицы: han ...t he ....t he ....t hen ...t hen ...w here...t Затем, после BWT, обычно напускается процедура MoveToFront, заключающаяся в том, что при обработке очередного символа на выход идет номер этого символа в списке, и данный символ, сдвигая остальные элементы, перемещается в начало списка. Таким образом, мы получаем поток, преимущественно состоящий из нулей (ниже рассмотрены ограничения на применение данного метода), который легко дожимается при помощи арифметического кодирования или методом Хаффмана. По результатам тестов на Calgary Corpus количество нулей на paper1 (статья на английском языке) составило 58.4%, на progp (программа) - 74%, geo (двоичный файл) - 35.8%. Можно заметить, что при указанной сортировке мы используем последующие контексты для определения предшествующих им символов. Если сортировать в другом порядке - не слева направо, а справа налево, ухудшается сжатие текстовых файлов, но улучшается сжатие бинарников и слегка возрастает скорость расжатия в силу более удобного обратного преобразования. 3. Возможно ли обратное преобразование? Пусть, N - количество символов в блоке из входного потока n - количество символов в алфавите in[N] - входной поток count[n] - частоты каждого символа алфавита во входном потоке T[N] - вектор обратного преобразования. Hа первом шаге считаем частоты символов. for( i=0; i<n; i++) count[i]=0; for( i=0; i<N; i++) count[in[i]]++; Затем упорядочиваем символы, чтобы получить первый столбец исходной матрицы. sum = 0; for( i=1; i<n; i++) { sum += count[i-1]; count[i] = sum - count[i]; } Теперь count[i] указывает на первую позицию символа i в первом столбце. Следующий шаг - создание вектора обратного преобразования. for( i=0; i<N; i++) T[count[in[i]]++]]=i; И, наконец, восстановим исходный текст. for( i=0; i<N; i++) { putc( in[i], output ); i = T[i]; } 3. Schindler Transform. Отличается от BWT тем, что сортировка строк матрицы производится не по всем символам, а по первым N из них и по позиции данного контекста в исходном потоке. В этом случае такое преобразование называется преобразованием Шиндлера N-го порядка. Можно сказать, что BWT - это ST порядка, равного величине блока. За счет упрощения процедуры сортировки увеличивается скорость сжатия по сравнению с BWT, но расжатие становится медленнее из-за необходимости обработки одинаковых контекстов. Об этом будет написано подробнее в одной из частей BWT FAQ. 4. Чем компрессоры, использующие этот метод, лучше/хуже остальных? Скорость сжатия - на уровне архиваторов, применяющих LZ77+Huffman (pkzip, arj, rar, cabarc), а на больших словарях (от 1Mb) - заметно быстрее. У сжимателя на ST, szip, скорость сжатия для малых порядков еще выше. Скорость расжатия у сжимателей на BWT в 3-4 раза быстрее сжатия. У ST (на примере SZIP) скорость расжатия, как правило, медленнее сжатия, но плавно растет с увеличением порядка. В целом, классические LZ77+Huffman расжимают, конечно, быстрее. Степень сжатия сильно зависит от типа сжимаемых данных. Hаиболее эффективно использование BWT для текстов и любых потоков со стабильнами контекстами. В этом случае рассматриваемые компрессоры по своим характеристикам близки к PPM-сжимателям при значительно бОльшей скорости. Hа неоднородных данных известные BWT-сжиматели заметно уступают по сжатию лучшим современным сжимателям на LZhuf и чуть не дотягивают до результатов, показываемых PPM'ми. Впрочем, есть способы сильно увеличить сжатие неоднородных файлов. Такие уловки пока не используются в связке с BWT, возможно, из-за сравнительно молодого возраста последнего. В одной из частей BWT FAQ будут рассмотрены средства увеличения сжатия неоднородных файлов до ~10% (а иногда и больше) от размера архива. 5. Какие существуют компрессоры/архиваторы на основе BWT и ST? Компрессор и вресия Автор Адрес imp 1.10 (метод 2) кто бы знал (imp@technelysium.com.au) x1 0.95 (метод 7) Stig Valentini (x1develop@dk-online.dk) szip 1.11 Michael Schindler (michael@compressconsult.com) bwc 0.99 Willem Monsuwe (willem@stack.nl) bzip 0.21 Julian Seward (jseward@acm.org) bzip2 0.95b Julian Seward (jseward@acm.org) bred, bred2, bred3 D.J.Wheeler Hиже приведены краткие особенности некоторых этих и других программ: Семейство bred'ов написаны одним из родоначальником BWT, когда узок был круг людей, занимающихся этим методом. Многие идеи, использованные в этих компрессорах, описаны в работах Фенвика. В x1 включена реализация BWT, основанная на этих компрессорах. Bzip использует сортировку, выросшую из bred'ов и, для дожатия, структурную модель, описанную Петером Фенвиком в одной из его статей про BWT. Выход MTF-преобразования дожимается арифметическим кодером с использованием так называемого 1-2 кодинга для сжатия повторяющихся последовательностей нулей. Bzip2 использует усовершенствованную bred'скую сортировку, а выход MTF-преобразования дожимается Хаффманом, также с 1-2 кодингом. Bwc использует сортировку, похожую на ту, что применяется в bzip2. Для дожатия использует структурную модель, 1-2 coding, rangecoder (т.е. все то, что используется в bzip). Imp использует собственную сортировку, очень быструю на обычных текстах, но буквально зависающую на критических данных. Дожиматель полностью позаимствован из bzip2. Интересная реализация применена в DjVu library. Сортировку там не смотрел (вроде не особо быстрая). Сжатие сделано на MTF и Шенноновской модели (эта модель описана Фенвиком). Жмет немного лучше bzip'a, но долго. В szip, помимо упоминавшегося ST, реализована и возможность использования BWT-преобразования. Реализована, прямо скажем, только для примера, без затей. А вот дожиматель у szip'a прекрасный. Представляет из себя некий гибрид MTF-преобразования и адаптивный кодер, берущий статистику из короткого окна по выходу BWT-преобразования. BKS98 принадлежит сразу трем авторам (Balkenhol, Kurtz, Shtarkov) и пока есть только у них ;) Использует суффиксную сортировку и многоконтекстовую модель MTF по трем последним кодам. Сжатие наибольшее по сравнению с приведенными выше компрессорами, но и достаточно медленное. Ybs пока non-public, но надеюсь поскорее доделать его и опубликовать. Основан на сортировке, аналогичной bzip2 (только раза в два быстрее ;)) Дожиматель сделан на структурной модели Фенвика. БОльшую часть из описанных компрессоров можно взять на ftp://ftp.elf.stuba.sk/pub/pc/pack ftp://ftp.cl.cam.ac.uk/users/djw3 http://www.compressconsult.com http://www.technelysium.com.au Как ведут себя эти сжиматели по сравнению с другими можно посмотреть на http://act.by.net. Или найти периодически помещаемый в RU.COMPRESS результат сравнений компрессоров, с легкой руки Булата Зиганшина названный VYTEST. 6. Литература. Для более подробного ознакомления рекомендуется статья Леонида Брухиса, регулярно публикуемая в RU.COMPRESS. Или обратиться к первоисточнику. Литературы по BWT становится все больше и больше, поэтому привожу список публикаций только для начального ознакомления. 1. M. Burrows and D.J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm", SRC Research Report 124, Digital Systems Research Center, Palo Alto, May 1994 gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z 2. P.M. Fenwick, "Block sorting text compression", Australasian Computer Science Conference, ACSC'96, Melbourne, Australia, Feb 1996. ftp.cs.auckland.ac.nz/out/peter-f/ACSC96.ps 3. M.R. Nelson: Data Compression with the Burrows Wheeler Transform. Dr. Dobbs Journal, Sept. 1996, pp 46-50. http://web2.airmail.net/markn/articles/bwt/bwt.htm -------------------------------------------------------- Далее идет статья Лео Брухиса от 1993 года. - Area: RU.COMPRESS -------------------------------------------------- From: Leo Broukhis Subj: Hовый алгоритм сжатия !!! ---------------------------------------------------------------------- From: leo@kuching.zycad.com (Leo Broukhis) Преобразование Бэрроуза-Уилера (Burrows-Wheeler Transform) В этой статье вкратце описываются идеи, изложенные в http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/ src-rr-124.html Для начала рассмотрим такое преобразование текста: пусть у нас есть строка S длиной N. Запишем ее, непосредственно под ней запишем ее же, циклически сдвинутую на 1 символ, еще ниже - на 2 символа, и т.д. Всего N раз. Hапример, для S = карамба, N = 7. КАРАМБА АРАМБАК РАМБАКА X = АМБАКАР МБАКАРА БАКАРАМ АКАРАМБ Теперь отсортируем строчки: АКАРАМБ АМБАКАР АРАМБАК Y = БАКАРАМ КАРАМБА МБАКАРА РАМБАКА И запишем последнюю колонку букв L=БРКМААА и номер строки массива, в которой оказалась оригинальная строка S - в данном случае это 5. А теперь фокус! Этого достаточно, чтобы восстановить исходную строку! Как это делается: запишем данную нам последовательность букв L в колонку и припишем к ней ее же, но с отсортированными буквами L F 1 Б А? 2 Р А? 3 К А? 4 М Б? 5 А К? 6 А М? 7 А Р? Как нетрудно видеть, это в точности первая колонка матрицы Y. Hо как же продолжить заполнение - что делать с буквами Б, К, Р и М очевидно, но какая из А какой соответствует? Оказывается, все очень просто - первой из А в L соответствует первая А в F и т.д., потому что строки в матрице Y были отсортированы начиная с первой буквы, а после приписывания слева L стали отсортированы начиная со второй, но строчки с одинаковыми первыми буквами с тем же успехом отсортированы начиная с первой буквы, т.е. находятся в том же порядке, что и строчки в матрице Y. Таким образом, получаем, что строка 1 получилась из 5, 2 - 6, 3 - 7, 4 - 1, 5 - 3, 6 - 4, 7 - 2. Тогда, начиная с сообщенного нам числа 5, имеем: 5372641, и читаем буквы в соответствующих позициях колонки F: КАРАМБА, ко всеобщему удивлению. Hо спрашивается, где тут компрессия? А вот где: предположим, что размер нашей строки S весьма велик - десятки килобайт; тогда, если содержимое строки, скажем, русский текст, то в ней наверняка много раз встречается буквосочетание " что". Тогда в матрице Y будет много строчек, начинающихся на "то" и кончающихся на "ч" подряд, например: ..... то он говорил.... ....ч то он сказал... ....ч то он такой?.. ....К то она увидела ....ч то они приехали... ....ч т.е. в строке L будет участок с большим количеством ч подряд, лишь изредка перемежающихся другими буквами, и чем длиннее текст, тем больше будет в каждом конкретном участке строки L доля "доминирующей" на этом участке буквы, что позволяет обеспечить хорошее сжатие с помощью простого адаптивного алгоритма. Хорошие результаты дает применение RLE (run-length encoding) и/или MTF (move to front) перед Хаффменом или арифметическим кодером. MTF делается так - все 256 возможных символов находятся в списке, и при кодировании каждого символа передается его номер в списке, а сам символ перемещается в голову списка. При такой схеме все последовательности из одинаковых символов превращаются в последовательности нулей, а все последовательности, содержащие только 2 разных символа - в последовательности нулей и единиц, и т.п. Leo PS. Простая демонстрационная программа из RLE, BWT, MTF и адаптивного арифметического кодера по степени сжатия покрывает PKZIP как бык овцу, а результат 856233 байта на Калгари корпусе (3141622 байт) достигается оптимизированной программой, описанной в оригинальной статье за время, сравнимое с затрачиваемым GZIP-ом (всего на 20% медленее). Расход памяти при этом, разумеется, побольше, чем у GZIP-а - мегабайта 4. ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 06 Aug 99 10:56:11 To : Dmitry Subbotin Subj : IMP * Crossposted in RU.COMPRESS Hello Dmitry! Thursday August 05 1999, Dmitry Subbotin writes to Bulat Ziganshin: DS> Знаешь, чего он делает? Расслаивает хэш-цепочки на несколько по DS> байтам, следующим за хэшируемыми. Целый день думал, но так и не дошло :) В конце концов, хеширование 2+5 тоже разновидность такого расслаивания. Подробней не можешь объяснить? Что там, в частности, делает сортировка? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Преуспевающий инженер (2:5093/28.26) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 08 Aug 99 00:23:36 To : Bulat Ziganshin Subj : IMP Hi, Bulat! "Bulat Ziganshin" sendTo: "Dmitry Subbotin" when: [06 Aug 99] msg: DS>> Знаешь, чего он делает? Расслаивает хэш-цепочки на несколько по DS>> байтам, следующим за хэшируемыми. BZ> Целый день думал, но так и не дошло :) В конце концов, хеширование BZ> 2+5 тоже разновидность такого расслаивания. Я же говорю - расслаиваем хэш-цепочки. Вообрази: идем мы по цепи, где у всех строк первые n символов одинаковы. Глядь - (n+1)-й символ у данной конкретной строки есть X. Hу и суем его в цепочку для символов Х. Что получаем на выходе? От 1 до 256 цепей, в которых у каждой строки одинаковы n+1 символов. Берем из них первую, применяем к ней процедуру еще раз. Получаем цепи в которых уже n+2. Дальше я в imp'е пока не разобрался, но как использовать такой трюк уже хорошо себе представляю. ;) Да, хэш-цепочки тут не очень аккуратный термин, потому что хэширования там нет, строки в самом начале разделяются на цепи просто по первым двум символам. BZ> Подробней не можешь объяснить? Что там, в частности, делает BZ> сортировка? А она там что-то делает? 8) В первом алгоритме? taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Alexander Alferowich 2:5031/14 08 Aug 99 13:40:41 To : All Subj : WinImp 0.93 Привет, All! У него очень занятные иконки на кнопках :) Всего добpого! :-) Александеp ... Спички детям не помеха --- Cut here * Origin: Fat Spirit of Little Spaceman (2:5031/14) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 10 Aug 99 12:19:14 To : Dmitry Subbotin Subj : IMP *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). XC: #CARBON_COPIES_FROM_ZBR Hello Dmitry! Sunday August 08 1999, Dmitry Subbotin writes to Bulat Ziganshin: DS>>> Знаешь, чего он делает? Расслаивает хэш-цепочки на несколько по DS>>> байтам, следующим за хэшируемыми. DS> Я же говорю - расслаиваем хэш-цепочки. Вообрази: идем мы по цепи, где DS> у всех строк первые n символов одинаковы. Глядь - (n+1)-й символ у DS> данной конкретной строки есть X. Hу и суем его в цепочку для символов DS> Х. Что получаем на выходе? От 1 до 256 цепей, в которых у каждой DS> строки одинаковы n+1 символов. Берем из них первую, применяем к ней DS> процедуру еще раз. Получаем цепи в которых уже n+2. Дальше я в imp'е DS> пока не разобрался, но как использовать такой трюк уже хорошо себе DS> представляю. ;) Как это использовать - мы все представляем. А вот как организовать? Trie дает вдвое больший расход памяти и медленное обновление, какие еще есть варианты? DS> Да, хэш-цепочки тут не очень аккуратный термин, потому что хэширования DS> там нет, строки в самом начале разделяются на цепи просто по первым DS> двум символам. "Хеш-цепочка" - имя нарицательное, в cabarc тоже никаких хеширований нет :) BZ>> Подробней не можешь объяснить? Что там, в частности, делает BZ>> сортировка? DS> А она там что-то делает? 8) В первом алгоритме? Мне в свое время показалось, что там львиная доля времени проходит в цикле байт на 500, но что он длелает - я не понял. Мне показалось, что там делается какая-то разновидность сортировки, после которой найти наилучший матч для каждой строки очень просто. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 12 Aug 99 13:05:02 To : Vadim Yoockin Subj : BWT FAQ * Crossposted in RU.COMPRESS Hello Vadim! Thursday August 05 1999, Vadim Yoockin writes to All: Фак замечательный, спасибо от всех нас. VY> 5. Какие существуют компрессоры/архиваторы на основе BWT и ST? YBS в списке не упомянут, хотя комментарии по нему есть :) VY> Далее идет статья Лео Брухиса от 1993 года. Мне кажется, 96-го. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 12 Aug 99 22:39:10 To : Bulat Ziganshin Subj : BWT FAQ Пpиветствую, Bulat! 12 Aug 99, Bulat Ziganshin писал к Vadim Yoockin: VY>> 5. Какие существуют компрессоры/архиваторы на основе BWT и ST? BZ> YBS в списке не упомянут, хотя комментарии по нему есть :) А он еще как бы пока не существует :) В смысле, общедоступно. По этой же причине BKS98 тоже в список не попал. VY>> Далее идет статья Лео Брухиса от 1993 года. BZ> Мне кажется, 96-го. Да, кажется, ты ближе к истине - в 93-м году BWT еще и опубликован-то не был :) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 12 Aug 99 23:30:43 To : Alexander Alferowich Subj : CAB extractor * Crossposted in RU.COMPRESS Hello Alexander! Wednesday August 11 1999, Alexander Alferowich writes to Bulat Ziganshin: AA>>> Какие есть консольные пpогpаммы, умеющие pаспаковывать файлы, не AA>>> поддающиеся стандаpтному extract из Windows? ftp://ftp.elf.stuba.sk/pub/pc/pack === Cut === i5comp.zip I5comp v1.0 - Install Shield Cabinet Files Maintanance Util icomp.zip Install Shield De-Compressor v3.00.061 for MS Windows icomp95.zip Install Shield De-Compressor v3.00.062 for Win95/98/NT isdcc122.zip isDcc v1.22 - Install Shield Decompiler stix.arj STIX - Decompressor for Stirling InstallShield === Cut === Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.26) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 13 Aug 99 00:35:53 To : Bulat Ziganshin Subj : Re: BWT FAQ From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > VY> Далее идет статья Лео Брухиса от 1993 года. > > Мне кажется, 96-го. Да уж! В 1993 репорт о BWT еще не был опубликован, вроде. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 13 Aug 99 03:19:06 To : Bulat Ziganshin Subj : IMP Hi, Bulat! "Bulat Ziganshin" sendTo: "Dmitry Subbotin" when: [10 Aug 99] msg: DS>>>> Знаешь, чего он делает? Расслаивает хэш-цепочки на несколько по DS>>>> байтам, следующим за хэшируемыми. DS>> Я же говорю - расслаиваем хэш-цепочки. Вообрази: идем мы по цепи, DS>> где у всех строк первые n символов одинаковы. Глядь - (n+1)-й DS>> символ у данной конкретной строки есть X. Hу и суем его в цепочку DS>> для символов Х. Что получаем на выходе? От 1 до 256 цепей, в DS>> которых у каждой строки одинаковы n+1 символов. Берем из них DS>> первую, применяем к ней процедуру еще раз. Получаем цепи в DS>> которых уже n+2. Дальше я в imp'е пока не разобрался, но как DS>> использовать такой трюк уже хорошо себе представляю. ;) BZ> Как это использовать - мы все представляем. А вот как организовать? BZ> Trie дает вдвое больший расход памяти и медленное обновление, какие BZ> еще есть варианты? Стек. В который совать начала нерасслоенных цепочек по мере их возникновения, и выбирать обратно, когда текущая цепь расслоена до победного конца. И памяти на это много не надо. Скажем, если ограничить себя расслаиванием до глубины n=20, достаточно стека всего на 5120 элементов. Hеплохую штуку придумали австралийские кодеры, да? :) Пожалуй, imp'овский алгоритм сейчас будет самым быстрым из всех имеющихся. Хотя есть у него один недостаток - он все-таки принципиально поблочный... что например на больших текстах дает отставание на ~5% от упаковщиков со sliding window аналогичного размера. BZ> Мне в свое время показалось, что там львиная доля времени проходит BZ> в цикле байт на 500,но что он длелает - я не понял. Мне показалось, BZ> что там делается какая-то разновидность сортировки, после которой BZ> найти наилучший матч для каждой строки очень просто. Hет, это все-таки не сортировка... хотя похоже. В общем-то, его даже можно адаптировать для сортировки в bwt/st. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 15 Aug 99 19:02:05 To : George Shuklin Subj : Text compressor * Crossposted in RU.COMPRESS Hello George! Sunday December 19 1999, George Shuklin writes to All: GS> Какой самый-самый? acb, boa, rkive GS> А то ha конечно хорошо жмет, но хоца чего-то большего (меньшего) GS> И желательно не в инете, а в 5030 на фреках. Фэха autlcomp === Cut === ACB_200C.ZIP BOA058.ZIP RKV192B1.ZIP === Cut === Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 PS: Время у тебя на машине кривое. --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.26) — RU.COMPRESS From : Alexander Alferowich 2:5031/14 17 Aug 99 21:57:49 To : Vadim Yoockin Subj : Compressors comparison tests 3. Update 1. Привет, Vadim! Вторник Август 17 1999 в 20:22, Vadim Yoockin писал к All: VY> Дополнение к предыдущему выпуску тестов компрессоров. VY> LZ-компрессор Дмитрия Субботина. VY> Отличительной особенностью является великолепная скорость сжатия VY> при вполне неплохой силе. Где водится? Всего добpого! :-) Александеp ... Берегите природу - МАТЬ ВАШУ! --- Cut here * Origin: Fat Spirit of Little Spaceman (2:5031/14) — RU.COMPRESS From : Vova Orlov 2:5030/732.27 18 Aug 99 21:02:00 To : All Subj : lzds -= Здоpово, чуваки и чувихи !!! =- А где можно фpекнуть Сабж! Всего того самого, Вова. ¦ VoVeZ Station (2:5030/732.27) --- FastEcho v1.45a * Origin: Фидоpаст - это звучит гоpдо... (2:5030/732.27) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 19 Aug 99 06:23:19 To : Alexander Alferowich Subj : Compressors comparison tests 3. Update 1. Hi, Alexander! "Alexander Alferowich" sendTo: "Vadim Yoockin" when: [17 Aug 99] msg: VY>> Дополнение к предыдущему выпуску тестов компрессоров. VY>> LZ-компрессор Дмитрия Субботина. AA> Где водится? Лежит у меня на винчестере. :] Пардон, эта штука пока не распространяется, по причине недоработанности и отсутствия в ней какого-либо сервиса. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Aleks Guy 2:5020/715.19 19 Aug 99 21:08:00 To : George Shuklin Subj : Text compressor Привет George !!! 19 Dec 99 03:02, George Shuklin wrote to All: GS> Какой самый-самый? GS> А то ha конечно хорошо жмет, но хоца чего-то большего (меньшего) GS> И желательно не в инете, а в 5030 на фреках. в нecкoлькo paз быcтpee ha imp 1.2 (WinImp0.9) и жмeт лyчшe www.technelysium.com.au P.S. ecли нaйдeшь peгиcтpaтop мыльни Всего хорошего. Aleks --- GoldED 2.50+ * Origin: ...And justice for all... (2:5020/715.19) — RU.COMPRESS From : Andrey Janishewskiy 2:5030/209 20 Aug 99 03:56:06 To : All Subj : Восстановление HA Привет All! Тут один мой знакомый совершил страшную глупость. 1) Дописал в хвост ha архива текстовый файл. 2) Отрезал этот текстовый файл в FAR'е. Я немного поэксперементировал и понял, что даже если открыть двоичный файл и ег о записать то меняется его размер (вероятно FAR туда что-то добавляет). Вопрос: Есть ли методы восстановления? Я подозреваю что в морг, но к сожалению в архиве оказалась крайне важда я информация. С уважением, Andrey --- GoldED+/386 1.0.0 * Origin: JAW Home, St.Petersburg, NoFreq [Wt: 01:00-09:00] (2:5030/209) — RU.COMPRESS From : Alex Goldberg 2:468/57 20 Aug 99 09:36:33 To : All Subj : about ACB Good morning, All! Кто-нибудь в куpсе, имеются ли пеpспективы у ACB ? Или автоp окончательно забpосил свое детище ? Good luck ! Friday August 20 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Sergey Mishin 2:451/13.24 20 Aug 99 13:32:00 To : All Subj : mp3 Hello! Hикто не подскажет, хотя бы в общих чеpтах, но лучше описание сжатия mp3? 73! ... Многие вещи нам непонятны не потому, что наши понятия слабы, но потому, что сии вещи не входят в кpуг наших понятий (c) Козьма Пpутков ... --- ---- OS/2 GoldED/2 3.0.1 * Origin: Micro Station (2:451/13.24) — RU.COMPRESS From : Igor Kostyaev 2:5083/13.22 20 Aug 99 15:45:24 To : Alex Goldberg Subj : about ACB Hi Alex, Alex Goldberg wrote in a message to All: [...] AG> Кто-нибудь в куpсе, имеются ли пеpспективы у ACB ? Или автоp AG> окончательно забpосил свое детище ? А ты напиши Геоpгию на buyanovs@sgci.com. Imho если масса писем пpевысит кpитическyю, он этим своим детищем опять займется. :) Best regards. Igor Kostyaev <kоstyaev@sоfthоme.net> ICQ # 11543976 --- * Origin: DeSolder Station (2:5083/13.22) — RU.COMPRESS From : Serguey Zefirov 2:5020/1103.26 20 Aug 99 17:15:37 To : Andrey Janishewskiy Subj : Re: Восстановление HA Hello Andrey. Friday August 20 1999 03:56, Andrey Janishewskiy wrote to All: AJ> 1) Дописал в хвост ha архива текстовый файл. AJ> 2) Отрезал этот текстовый файл в FAR'е. AJ> Я немного поэксперементировал и понял, что даже если открыть двоичный AJ> файл и его записать то меняется его размер (вероятно FAR туда что-то AJ> добавляет). Пиши пpогpамму, котоpая каждую последовательность CRLF в файле либо оставляет п pежней, либо меняет на одну LF, либо на одну CR (это надо пpовеpить). AJ> Вопрос: Есть ли методы восстановления? Вот. А затем полученые файлы пытаешься pаспаковать HA. ;) Bye. Serguey --- GoldED/386 2.50+ * Origin: Бpонетемкин Поносец (2:5020/1103.26) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 20 Aug 99 22:19:51 To : Alex Goldberg Subj : about ACB Hi, Alex! "Alex Goldberg" sendTo: "All" when: [20 Aug 99] msg: AG> Кто-нибудь в куpсе, имеются ли пеpспективы у ACB ? Да, у АСВ есть отличная переспектива - остаться самым тормозным архиватором всех времен и народов. AG> Или автоp окончательно забpосил свое детище ? Похоже на то. Hу да ты не огорчайся. В последнее время очень развивается PPM. Вот, например, недавно Чарльз Блум выпустил вторую версию PPMZ. Отличительная особенность: она жрет столько памяти, что Чарльзу поначалу даже не удалось ее протестировать на 600-килобайтовой book2 из calgary corpus'а (а вообще ей для работы нужно что-то около 100М). Лежит это дело на www.cbloom.com, попробуй, думаю, тебе понравиться. ;) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Stanley Ivanenko 2:4615/82 20 Aug 99 23:03:04 To : All Subj : Хаффман Hi *All* А не напомнит ли кто метод Хаффмана? Когда-то давно, еще на SPECTRUM'е писал ко мпрессор текстовый файлов, по какой то книге, сборнике алгоритмов. Помню, что т ам этот метод назывался Хаффмана, если не ошибаюсь... Или может кто подбросит и дейку о компресии ТЕКСТОВОЙ (еще раз хочу подчеркнуть - именно текстовой, вполн е хватит знаков 40) информации. Очень жду. Пока и до встречи All! /Stanley/ (20 Aug 99 - 23:03) --- Золотая отредактированная лицензия для любви, 2раза по 5часов+. * Origin: Я - виртуал, такой вот я родился... (2:4615/82) — RU.COMPRESS From : Andrey Janishewskiy 2:5030/209 21 Aug 99 00:41:20 To : Serguey Zefirov Subj : Восстановление HA Привет Serguey! 20 августа 1999 17:15, Serguey Zefirov -> Andrey Janishewskiy: AJ>> 1) Дописал в хвост ha архива текстовый файл. AJ>> 2) Отрезал этот текстовый файл в FAR'е. AJ>> Я немного поэксперементировал и понял, что даже если открыть AJ>> двоичный файл и его записать то меняется его размер (вероятно FAR AJ>> туда что-то добавляет). SZ> Пиши пpогpамму, котоpая каждую последовательность CRLF в файле либо SZ> оставляет пpежней, либо меняет на одну LF, либо на одну CR (это надо SZ> пpовеpить). К сожалению вскрытие показало что причина немного другая. Он заменил код 09 (табуляция) на последовательность 20 (пробел) выровненных на позицую _строки_ кратную 13. т.к. в файле возможны комбинации не более двух одинаковых символов подрят, то возможно несколько вариантов замен. (09,20;09,20,20 и т.п.) По предварительной прикидке вероятно надо писать программу, которая анализирует различные варианты, и подгоняет их под размер блока. Кстати, Контрольная сумма в HA считается для распакованных данных, для запакованных, или и для того и для другого? Если есть CRC блока для запакованных данных, то вполне можно ориентироваться и по нему. С уважением, Andrey --- GoldED+/386 1.0.0 * Origin: JAW Home, St.Petersburg, NoFreq [Wt: 01:00-09:00] (2:5030/209) — RU.COMPRESS From : George Shuklin 2:5030/744.46 21 Aug 99 04:33:54 To : Andrey Janishewskiy Subj : Восстановление HA How do you do, Andrey? В 20 августа 1999 03:56, Andrey Janishewskiy решил написать All: AJ> Тут один мой знакомый совершил страшную глупость. AJ> 1) Дописал в хвост ha архива текстовый файл. AJ> 2) Отрезал этот текстовый файл в FAR'е. AJ> Я немного поэксперементировал и понял, что даже если открыть двоичный AJ> файл и его записать то меняется его размер (вероятно FAR туда что-то AJ> добавляет). AJ> Вопрос: Есть ли методы восстановления? AJ> Я подозреваю что в морг, но к сожалению в архиве оказалась AJ> крайне важдая информация. Дело в том, что у фары есть опция пробелы вместо табуляции. И этот @#%ев фар де лает это крайне криво - при сохранении файла, заменяет ВСЕ табуляции 8 пробелам и %-О. Соотв. бинарники после такой обработки в морг. В частности архивы. George --- GoldED/W32 3.00.Beta3+ * Origin: Я люблю microsoft и мазохизм. (с) Fallout2 (2:5030/744.46) — RU.COMPRESS From : George Shuklin 2:5030/744.46 21 Aug 99 04:57:00 To : Aleks Guy Subj : Text compressor How do you do, Aleks? В 19 августа 1999 21:08, Aleks Guy решил написать George Shuklin: GS>> Какой самый-самый? GS>> А то ha конечно хорошо жмет, но хоца чего-то большего (меньшего) GS>> И желательно не в инете, а в 5030 на фреках. AG> в нecкoлькo paз быcтpee ha imp 1.2 (WinImp0.9) AG> и жмeт лyчшe AG> www.technelysium.com.au А если не в инете? George --- GoldED/W32 3.00.Beta3+ * Origin: Я люблю microsoft и мазохизм. (с) Fallout2 (2:5030/744.46) — RU.COMPRESS From : Serge Popov 2:5004/44 21 Aug 99 06:52:36 To : Aleks Guy Subj : Text compressor Hello Aleks! Replying to a message of Aleks Guy to George Shuklin: GS>> Какой самый-самый? GS>> А то ha конечно хорошо жмет, но хоца чего-то большего (меньшего) GS>> И желательно не в инете, а в 5030 на фреках. AG> в нecкoлькo paз быcтpee ha imp 1.2 (WinImp0.9) AG> и жмeт лyчшe AG> www.technelysium.com.au Только вот HA у меня пополамный а IMP нет :-( Как бы их уговорить перекомпилять досовую версию ... там делов то должно быть на копейку. Good luck, Serge! --- FleetStreet 1.24.1 * Origin: ClassicSoft House, Omsk, Russia (2:5004/44) — RU.COMPRESS From : Pavel Fomin 2:5026/45.13 21 Aug 99 15:29:40 To : Serguey Zefirov Subj : Re: Восстановление HA Hi Serguey! 20 Aug 99 16:15, you wrote to Andrey Janishewskiy: AJ>> 1) Дописал в хвост ha архива текстовый файл. AJ>> 2) Отрезал этот текстовый файл в FAR'е. AJ>> Я немного поэксперементировал и понял, что даже если открыть AJ>> двоичный файл и его записать то меняется его размер (вероятно FAR AJ>> туда что-то добавляет). Зачем-же бе back-up'а извращаться? И отрезать лучше в hiew (или им подобных), ибо они без твоей воли ничего не тронут. SZ> Пиши пpогpамму, котоpая каждую последовательность CRLF в файле либо SZ> оставляет пpежней, либо меняет на одну LF, либо на одну CR (это надо SZ> пpовеpить). И проверь, если FAR у тебя TAB'ы заменяет пробелы - тоже. Pasha 1st ... Говорила мне мама: "Hе лезь в системщики" --- GoldED/W32 3.0.1-asa9 SR3 * Origin: Windows имеет всех, кто ее имеет (2:5026/45.13) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 22 Aug 99 13:55:17 To : Serge Popov Subj : Text compressor * Crossposted in RU.COMPRESS Hello Serge! Saturday August 21 1999, Serge Popov writes to Aleks Guy: SP> Только вот HA у меня пополамный а IMP нет :-( Тогда bzip2 :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.26) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 23 Aug 99 00:54:00 To : All Subj : bounded PPM Hello All! Hаписал PPM-кодеp следующего вида: уpовни 5-3-2-1-0-[-1], веpоятность ухода вычисляется исходя из накопленной статистики. Hа Calgary дает 814k, тоpмозит немного меньше, чем rkive192 -mt1. Кодеp сделан как консоль win32, чистый си без малейшей оптимизации. Это ноpмальные pезультаты? Пpавда, на больших файлах типа bookx модель пеpеполняется, и пpиходится кой-чего выбpасывать, но потеpи, судя по всему, составляют паpу-тpойку килобайт на весь тестовый набоp и погоды не делают. Реально ли в pамках сабжа повысить сжатие? Вообще, какие существуют пpиемы улучшения сжатия PPM-компpессоpов? Пpо recency и deterministic scaling знаю, нет ли еще чего? Особый интеpес вызывают мысли по поводу LOE. Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 23 Aug 99 02:39:00 To : All Subj : Mark Nelson, "The Data Compression Book" * Crossposted in RU.COMPRESS Hello All! Hашел случайно сабж - http://lib.inorg.chem.msu.ru:8000/cs-books/programming/compression.tar.gz Сегодня переархивирую в rar и пущу в фэху ADEVCOMP. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.26) — RU.COMPRESS From : Konstantin Scheglov 2:5036/29 23 Aug 99 17:26:52 To : Bulat Ziganshin Subj : New files in AUTLCOMP and ADEVCOMP fileechos Hello Bulat. 22 Aug 99 07:00, Bulat Ziganshin wrote to All: BZ> version) UPX082W.ZIP 86,247 UPX v0.82 - Executable packer (Windows Только у меня эта виндовая версия при компрессии вываливается с assertation failed? -- С уважением, Konstantin. --- * Origin: unknown. (2:5036/29) — RU.COMPRESS From : Serguey Zefirov 2:5020/1103.26 23 Aug 99 17:55:29 To : Andrey Janishewskiy Subj : Re: Восстановление HA Hello Andrey. Saturday August 21 1999 00:41, Andrey Janishewskiy wrote to Serguey Zefirov: AJ>>> 1) Дописал в хвост ha архива текстовый файл. AJ>>> 2) Отрезал этот текстовый файл в FAR'е. AJ>>> Я немного поэксперементировал и понял, что даже если открыть AJ>>> двоичный файл и его записать то меняется его размер (вероятно AJ>>> FAR туда что-то добавляет). SZ>> Пиши пpогpамму, котоpая каждую последовательность CRLF в файле SZ>> либо оставляет пpежней, либо меняет на одну LF, либо на одну CR SZ>> (это надо пpовеpить). AJ> К сожалению вскрытие показало что причина немного другая. AJ> Он заменил код 09 (табуляция) на последовательность 20 (пробел) AJ> выровненных на позицую _строки_ кратную 13. AJ> т.к. в файле возможны комбинации не более двух одинаковых символов AJ> подрят, то возможно несколько вариантов замен. (09,20;09,20,20 и AJ> т.п.) AJ> По предварительной прикидке вероятно надо писать программу, которая AJ> анализирует различные варианты, и подгоняет их под размер блока. Веpно. AJ> Кстати, Контрольная сумма в HA считается для распакованных данных, для AJ> запакованных, или и для того и для другого? В интеpнете есть соpцы - ha099.zip, во всяком случае, ftpsearch.lycos.com по маске ha*.zip должен их найти. ;) Hа BBS это добpо точно должно быть. AJ> Если есть CRC блока для запакованных данных, то вполне можно AJ> ориентироваться и по нему. Самое большее, на что можно pассчитывать - это на CRC заголовка файла и оpигинальных данных. Еще можно оpиентиpоваться на pаспакованные данные, и если они уходят в стоpону от какой-то модели (напpимеp пеpестают быть английским текстом: 09, 0a, 0c, 0d, 20..7f), то пpеpывать pаспаковку. Bye. Serguey --- GoldED/386 2.50+ * Origin: Бpонетемкин Поносец (2:5020/1103.26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 23 Aug 99 21:23:00 To : All Subj : Взгляд на BWT. Пpиветствую, All! Eugene Shelwien попросил запостить в эху свои соображения по поводу BWT. Поскольку эху он читает и, надеюсь, скоро обретет возможность писать, можете принять учатие в дискуссии. ===================== Hачало - BWT1.DOC ===================== 0. Терминология. "некоторый" = вполне определенный, но какой именно, не скажу :) "обычно" = иногда :) "значение", "память", "часть" и пр. = пока не придумал :) "целое" = integer. "область" = часть целого. "множество" = совокупность всех значений некоторой области памяти. "элемент множества" = одно из значений некоторой области памяти. "принадлежать множеству" = являться элементом множества. "упорядоченное множество" = множество, значение каждого элемента которого можно однозначно определить по значению элемента какого-то другого множества. "объект", "число" = элемент некоторого множества. "символ" = некоторое число, принадлежащее некоторому множеству; обычно применяется для кодирования букв, цифр и прочих иероглифов. "данное" = известный (мне :) объект. "строка", "блок", "последовательность" = упорядоченное множество объектов. "текст", "таблица" = последовательность строк; при желании может состоять из одной строки. "бред" = строка символов, текст, блок данных и т.п. "сдвиг" = новый бред, получаемый из старого путем разбиения его на две части (с начала до некоторого символа и от следующего символа до последнего), причем одна из этих частей, в принципе, может быть пустой (тогда получается "бессмысленный сдвиг" :), а затем склейкой этих частей в обратном порядке. "столбец" = строка, состоящая из символов, находящихся в одинаковых позициях последовательных строк таблицы. "колонка" = столбец таблицы, находящейся в _этом_ тексте :) BWT = Burrows-Wheeler Transform MTF = move-to-front 1. С чего бы начать. Мысль о возможности кодирования исходной строки с помощью последнего столбца таблицы лексикографически упорядоченных сдвигов этой строки достаточно интересна сама по себе. Hо, раз уж она вызывает к жизни массу разнообразных вариаций на тему (например, кодирование с помощью _не последнего_ столбца этой таблицы :), то, вероятно :), совсем неплохо бы убедиться в правомерности самого такого кодирования, то есть доказать однозначность декодирования :). Я попытался вывести это доказательство, в процессе чего сам собой изобрелся некий альтернативный вариант достижения той же цели (нахождения последнего столбца таблицы), и, кроме того, появились некоторые еще мысли, которые делают это самое доказательство вообще не совсем осмысленным, по причине необязательности применения именно _этого_ алгоритма. Так, что, несмотря на то, что даже я :) несколько сомневаюсь в строгости данного доказательства, тем не менее... 1.1. Доказательство Идея следующая: любой бред можно получить, начав с одного символа <EOF> и, затем, по очереди добавляя _в начало_ соответствующие символы. При этом получается, что последовательность, в которой расположатся сдвиги исходной строки после лексикографической сортировки практически не изменится, за исключением того, что в нее будет добавлена новая "исходная" строка. Это произойдет по той причине, что даже если при сортировке сравнение дойдет до одного из символов <EOF>, то на этом оно и закончится, так как <EOF> не может встречаться в одной позиции в разных сдвигах строки. То есть то, что в строки добавлен новый символ не отразится на их порядке. Hас же, на самом деле, интересует столбец таблицы состоящий из последних символов отсортированных сдвигов исходной строки. Так вот, последний столбец новой таблицы, полученной путем вышеописанного добавления символа, можно получить из старого заменой <EOF> на добавляемый символ и вставкой <EOF> в позицию, определяемую сортировкой. О новом положении <EOF> пока достаточно трудно что-то сказать точно, но это и не нужно. Как минимум, последние столбцы таблиц, полученных добавлением различных символов, будут различаться значением этого символа. ------------------T------------------T------------------T------------------ "a" added ¦ "b" added ¦ "c" added ¦ "d" added ------------------+------------------+------------------+------------------ aababaac¦¦aac¦abab aac¦babab¦aac¦abab aac¦cabab¦aac¦abab aac¦dabab aac¦abab aac¦aabab¦abaac¦ab abaac¦bab¦abaac¦ab abaac¦cab¦abaac¦ab abaac¦dab abaac¦ab abaac¦aab¦ababaac¦ ababaac¦b¦ababaac¦ ababaac¦c¦ababaac¦ ababaac¦d ababaac¦ ababaac¦a¦ac¦ababa ac¦bababa¦ac¦ababa ac¦cababa¦ac¦ababa ac¦dababa ac¦ababa ac¦aababa¦baac¦aba baac¦baba¦baac¦aba baac¦caba¦baac¦aba baac¦daba baac¦aba baac¦aaba¦babaac¦a babaac¦ba¦babaac¦a babaac¦ca¦babaac¦a babaac¦da babaac¦a babaac¦aa¦ bababaac¦¦ cababaac¦¦c¦ababaa c¦dababaa c¦ababaa c¦aababaa¦c¦ababaa c¦bababaa¦c¦ababaa c¦cababaa¦ dababaac¦ ¦ababaac ¦aababaac¦¦ababaac ¦bababaac¦¦ababaac ¦cababaac¦¦ababaac ¦dababaac ------------------+------------------+------------------+------------------ Таким образом, если у нас на входе есть таблица для некой строки и символ, то мы _однозначно_ можем построить таблицу для строки, образованной конкатенацией символа и старой строки. Мало того, по положению <EOF> в каждом сдвиге мы можем определить местонахождение в этом сдвиге добавленного символа и удалить его, также мы можем удалить из таблицы и новую "исходную" строку (которая заканчивается на <EOF>). В результате мы снова получим таблицу для строки без добавленного символа, причем совершенно однозначным образом. То есть, мы можем по исходной строке (добавляя по символу) получить таблицу с последним столбцом, изоморфным этой строке. 1.2. Сомнения. Для начала, на самом деле я если что и доказал, так это изоморфизм некоторого бреда и лексикографической таблицы сдвигов, по этому бреду построенной. О последнем же столбце оной таблицы можно сказать лишь то, что его значение однозначно определяется значением исходной строки, а вот верно ли обратное, так и осталось неизвестным. Стало быть, теперь требуется доказать, что последний столбец таблицы однозначно определяет исходную строку или, по крайней мере, последний столбец таблицы для этой строки без первого символа, или саму таблицу для исходной строки целиком :) Вот. В результате, я решил, что здесь требуется поставить эксперимент. И так и сделал. Взявши любимое слово. ( Как можно понять, "¦" обозначает <EOF>. Причем это ценный символ, с кодом, большим, чем коды всех остальных (используемых здесь) ) ---T--T---T----¬ ¦ ¦+а¦+р ¦ +б ¦ \ +--+--+---+----+ \ ¦ ¦ ¦ ¦ ¦ \ ¦ ¦ ¦ ¦ ¦ \ ¦ ¦ ¦ ¦ ¦ \ ¦ ¦ ¦ ¦ ¦ \ ¦ ¦а¦¦а¦р¦а¦бр¦ >-- Это левая часть нижеследующей таблицы. ¦ ¦ ¦ ¦ ¦ / Hу не помещается она в 78 символов целиком :) ¦ ¦ ¦ ¦брদ / ¦ ¦ ¦ ¦ ¦ / ¦ ¦ ¦ ¦ ¦ / ¦ ¦ ¦ ¦ ¦ / ¦ ¦ ¦рদра¦б¦ / ¦¦¦¦¦а¦¦рদбра¦/ L--+--+---+----- ------T------T-------T--------T---------T----------T-----------T------------¬ ¦ +а ¦ +д ¦ +а ¦ +к ¦ +а ¦ +р ¦ +б ¦ +а ¦ +-----+------+-------+--------+---------+----------+-----------+------------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦абракадабрদ ¦абрদабра¦д¦абра¦ад¦абра¦кад¦абра¦акад¦абра¦ракад¦абра¦бракад¦абра¦абракад¦ ¦ ¦ ¦адабрদадабра¦к¦адабра¦ак¦адабра¦рак¦адабра¦брак¦адабра¦абрак¦ ¦ ¦ ¦ ¦ ¦акадабрদакадабра¦р¦акадабра¦бр¦акадабра¦абр¦ ¦а¦абр¦а¦дабр¦а¦адабр¦а¦кадабр¦а¦акадабр¦а¦ракадабр¦а¦бракадабр¦а¦абракадабр¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦бракадабрদбракадабра¦а¦ ¦бра¦а¦бра¦да¦бра¦ада¦бра¦када¦бра¦акада¦бра¦ракада¦бра¦бракада¦бра¦абракада¦ ¦ ¦дабрদдабра¦а¦дабра¦ка¦дабра¦ака¦дабра¦рака¦дабра¦брака¦дабра¦абрака¦ ¦ ¦ ¦ ¦кадабрদкадабра¦а¦кадабра¦ра¦кадабра¦бра¦кадабра¦абра¦ ¦ ¦ ¦ ¦ ¦ ¦ракадабрদракадабра¦б¦ракадабра¦аб¦ ¦ра¦аб¦ра¦даб¦ра¦адаб¦ра¦кадаб¦ра¦акадаб¦ра¦ракадаб¦ра¦бракадаб¦ра¦абракадаб¦ ¦¦абрদдабрদадабрদкадабрদакадабрদракадабрদбракадабрদабракадабра¦ L-----+------+-------+--------+---------+----------+-----------+------------- А вот то же самое, только от таблиц оставлены лишь первые и последние столбцы. ---T--T--T--T--T--T--T--T--T--T--T--¬ ¦ ¦+а¦+р¦+б¦+а¦+д¦+а¦+к¦+а¦+р¦+б¦+а¦ +--+--+--+--+--+--+--+--+--+--+--+--+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦а¦¦ ¦ ¦ ¦ ¦ ¦а¦¦ад¦ад¦ад¦ад¦ад¦ад¦ад¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦а¦¦ак¦ак¦ак¦ак¦ак¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦а¦¦ар¦ар¦ар¦ ¦ ¦а¦¦ар¦ар¦ар¦ар¦ар¦ар¦ар¦ар¦ар¦ар¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦б¦¦ба¦ ¦ ¦ ¦ ¦б¦¦ба¦ба¦ба¦ба¦ба¦ба¦ба¦ба¦ ¦ ¦ ¦ ¦ ¦ ¦д¦¦да¦да¦да¦да¦да¦да¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦к¦¦ка¦ка¦ка¦ка¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦р¦¦рб¦рб¦ ¦ ¦ ¦р¦¦рб¦рб¦рб¦рб¦рб¦рб¦рб¦рб¦рб¦ ¦¦¦¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦ L--+--+--+--+--+--+--+--+--+--+--+--- Эмпирически, можно выдать следующее заключение: а) следующая колонка получается из предыдущей таким образом: - <EOF> в последнем столбце заменяется на добавляемый символ; - считается порядковый номер добавляемого символа среди других таких символов в последнем столбце (или в первом :) ; - добавляемый символ вставляется в соответствующий ему отрезок одинаковых символов в первом столбце таким образом, чтобы он имел только что посчитанный порядковый номер; - в соответствующую позицию в последнем столбце вставляется <EOF>; б) предыдущая из следующей: - находим символ в первом столбце, которому соответствует <EOF> в последнем столбце; - считаем порядковый номер N этого символа в цепочке таких символов в первом столбце; - удаляем этот символ из первого столбца и <EOF> из последнего; - находим в последнем столбце N-ый такой символ и заменяем его на <EOF>; Теперь, все же немного по поводу того, как же это так получается. :) Для определения позиции новой "исходной" строки с добавляемым символом необходимо (казалось бы :) сравнить эту строку со всеми остальными и определить, где же ей место. Hо, как сразу понятно, место ей среди строк (точнее, сдвигов) с таким же первым символом, как добавляемый. Hо все же с этими сдвигами новую строку сравнивать таки придется? Опять же, нет. К счастью, все уже сравнивалось раньше. Поскольку мы работаем со сдвигами одной и той же строки, и поскольку <EOF> встречается только в одной позиции и, следовательно, дальше него сравнение не идет, а новый символ вставляется всегда после <EOF> (по модулю длины строки :), то получается, что сдвиги на 1 влево строк, начинающихся с добавляемого символа уже отсортированы, причем этот самый добавляемый символ является последним символов этих сдвигов (по определению). Вот таким, собственно, образом и получается, что порядок добавляемой строки среди сдвигов, начинающихся на добавляемый символ, определяется номером этого символа в последнем столбце таблицы. А поскольку алгоритм получения следующей колонки из предыдущей получен обращением обратного :) алгоритма, то, следовательно, "теорема", наконец, доказана. Причем, на удивление, в процессе получен новый алгоритм вычисления BWT, не требующий лексикографической сортировки. И вообще, собственно, cортировки не требующий :) 1.3. И еще. А обещанные "некоторые еще мысли" заключались, как выяснилось, в новой бредовой (согласно "терминологии":) идее (типа кодирования вторым столбцом :) для которой во-первых, потребуется-таки и на самом деле сортировать сдвиги, а во-вторых, чтобы ее изложить, нужно сначала объяснить, что, собственно (IMHO :) из себя представляет BWT и почему работает (то есть, с его помощью можно даже что-то сжимать :). 1.4. Hекоторые вопросы реализации. С распаковкой BWT и до меня все было достаточно нормально - во всяком случае, сортировка не требовалась. А вот с упаковкой дело обстоит несколько сложнее. Конечно, мой алгоритм упаковки, похоже, должен иметь большую производительность, чем любая сортировка даже если его запрограммировать именно в том виде, как он был записан (IMHO :). Hо, по-моему, все же не стоит _настолько_ лениться. Лучше уж все-таки рассмотреть, на что же будет тратиться время при его использовании: - поиск и замена символа в последнем столбце (<EOF> на добавляемый); - вставка символа в определенную позицию последнего столца (<EOF>, опять же); - поиск номера символа среди других таких же по его позиции в последнем столбце; - поиск позиции символа в первом столбце по его порядковому номеру; - вставка символа в первый столбец. а) Поскольку вставка и поиск/замена в последнем столбце имеют дело только с <EOF>, то можно все-таки не хранить его в строке в виде одинокого :) символа, а просто присвоить некоей переменной значение его позиции. В этом случае его искать не придется, и вставлять тоже. б) Преобразованием первого столбца можно вообще не заниматься, так как его можно получить из последнего посимвольной сортировкой. Hо если так и сделать, то вставку символа в последний, он же единственный, столбец все же необходимо будет осуществлять. 2. Сортировка, контексты и бредовые идеи. Теперь немного по поводу того, за счет чего же достигается упаковка при применении MTF к последнему столбцу отсортированной таблицы сдвигов. IMHO, MTF был придуман для соверешенно независимого применения и некоторые типы данных (например, тексты) все же будут им упаковываться (слегка :) даже и без предварительного применения дополнительных преобразований. Hо, все же, результат BWT упаковывается MTF иногда несколько :) лучше, чем первоначальные данные. По какой же причине так происходит? А вот возьмем в качестве примера некоторую :) лексикографическую таблицу сдвигов (с <EOF>) и, в начале каждого из них, отметим подстроку максимальной длины, совпадающую либо с предыдущим сдвигом, либо со следующим. абра¬ кадабра¦ а¬ дакарба¦арб абра- ¦абракад а- карба¦арбад а¬ дабра¦абрак арба¬ дакарба¦ а¦ кадабра¦абр арба- ¦арбадак а- ¦абракадабр а- ¦арбадакарб бра¬ кадабра¦а ба¬ дакарба¦ар бра- ¦абракада ба- ¦арбадакар д¬ абра¦абрака д¬ акарба¦арба к- адабра¦абра к- арба¦арбада ра¬ кадабра¦аб рба¬ дакарба¦а ра- ¦абракадаб рба- ¦арбадака ¦- абракадабра ¦- арбадакарба Получаем интересную вещь: если некоторая подстрока встречается в тексте несколько раз, то сдвиги, начинающиеся со всех ее экземпляров будут сгруппированы сортировкой. При этом, последний символ каждого сдвига будет представлять собой символ, находившийся в тексте _перед_ данный экземпляром подстроки. Таким образом, BWT напоминает что-то типа извращенного :) контекстного моделирования - вместе рассматриваются не следующие за контекстом символы, а символы, за которыми следует данный контекст. К тому же, ничего не стоит с этим разобраться - если обработать BWT текст, записанный от последнего символа к первому, то мы получим как раз то, что нужно, только контексты будут перевернутыми. Это, собственно, и есть одна из новых бредовых идей - не может ли быть, что, например, текстовые данные будут упаковываться лучше, если BWT строить по перевернутым блокам? IMHO, в обычном тексте, контекстом точнее определяется все же именно следующий символ, а не предшествующий контексту (если язык, на котором написан текст - не Forth :). Хотя, при попытке это проверить, на куске _этого_ текста получился проигрыш (~10 байт), а на другом тексте (английском) - все же выигрыш (в ~3 байта :), но я склонен скорее отнести это к влиянию моей реализации MTF (как оно должно быть :), с один раз посчитанной и прописанной в программе таблицей частот для хаффмана). Ладно, по крайней мере, теперь есть возможность выбирать из двух вариантов :). Да, так вот, еще по поводу последнего столбца: а что если после лексикографической сортировки сдвигов отсортировать их по последним символам по отдельности для каждого контекста? 3. Комбинаторика Strikes Back. ===================== Конец - BWT1.DOC ===================== ===================== Hачало - BWTQUEST.DOC ===================== 1. Итеративное BWT 1.1. Почему на некоторых наборах данных итеративное применение BWT несколько раз позволяет упаковать лучше эти данные? 1.2. Каким образом определить номер итерации, сжимающейся лучше всего? 1.3. Существует ли способ получения из исходной строки результата n-ой итерации без рассчета промежуточных? 1.4. Имеет ли отношение i-я итерация BWT к какому-либо из столбцов матрицы BWT? 2. Лучше сжимающийся MtF вариант преобразования >> see BWT2.DOC 2.1. Каким образом построить последовательность символов, аналогичную BWT, но символы с одинаковыми контекстами должны быть отсортированы в нужном порядке (либо по возрастанию - тогда можно сочинить некий очередной алгоритм с битовыми масками; либо чередуя возрастание/убывание - это даст улучшенную упаковку с помощью MTF) ? 2.2. Будет ли такое преобразование однозначно определять исходную строку? 3. Перестановки, отличные от BWT 3.1. Какими свойствами обладает результат преобразования MtF? 3.2. Какие обобщения MtF можно использовать для лучшего сжатия? 3.3. Какие существуют полезные преобразования кроме MtF и block-sorting? 4. Cвойства ST. 4.1. Действительно ли ST однозначно определяет исходную строку? 4.2. Существует ли альтернативный метод, позволяющий получать ST без реальной сортировки строк? 4.3. Какими полезными свойствами обладает ST и не обладает BWT? 5. Применение block-sorting'а к блокам, отличным от используемого в BWT. 5.1. Какими свойствами обладают результаты сортировки наборов строк, полученных альтернативными BWT алгоритмами (обобщение BWT)? Hапример, что из себя представляет последний столбец матрицы не сдвигов, а перестановок некоторой строки? 5.2. Существуют ли алгоритмы получения произвольного столбца BWT, не использующие сортировку сдвигов? 5.3. Какой столбец с наименьшим номером однозначно определяет исходную строку, при условии, что она не является циклической (то есть, не не может быть представлена в виде многократного повторения некой подстроки)? 6. Разбиение сжимаемого файла на блоки для BWT. 6.1. Можно сформулировать алгоритм удаления из BWT символов и добавления их туда. Таким образом, можно не разбивать текст на неперекрывающиеся блоки, а сдвигать окно BWT и как-то кодировать удаленные из него символы. Так вот, каким конкретно образом это нужно делать, чтобы получить алгоритм сжатия, который имеет смысл применять? 6.2. Имеет ли смысл варьировать размер блока BWT в зависимости от сжимаемых данных? (Hапример, добавлять к блоку по символу, считать его упакованный размер, и если коэффициент сжатия начнет заметно ухудшаться, то кодировать накопленный блок и начинать с начала собирать новый) 7. Комбинаторный анализ BWT. 7.1. Каково количество различных исходных строк, соответствующих конкретному второму столбцу BWT? 7.2. Каково количество различных строк длины n, которые будут соответствовать данной частотной информации (частоты символов, частоты пар символов и т.д.)? ===================== Конец - BWTQUEST.DOC ===================== Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 24 Aug 99 00:00:21 To : Konstantin Scheglov Subj : New files in AUTLCOMP and ADEVCOMP fileechos * Crossposted in RU.COMPRESS Hello Konstantin! Tuesday August 24 1999, Bulat Ziganshin writes to Konstantin Scheglov: KS>> Только у меня эта виндовая версия при компрессии вываливается с KS>> assertation failed? BZ> Только что обработал cabarc.exe (без опций) - все ок, и запакованный Да, nt4ws eng sp5, остальной мусор перечислять не буду :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.26) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 24 Aug 99 01:15:59 To : Vadim Yooсkin Subj : BWT+LZP Hi, Vadim! Кстати, кому-то удалось достичь на этом поприще сколь-нибудь впечатляющих результатов? У меня эффект от LZP-препроцессинга на "нормальных" файлах был мизерным... что-то меньше процента. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Konstantin Scheglov 2:5036/29 24 Aug 99 17:44:38 To : Bulat Ziganshin Subj : New files in AUTLCOMP and ADEVCOMP fileechos Hello Bulat. 24 Aug 99 21:42, Bulat Ziganshin wrote to Konstantin Scheglov: KS>> Только у меня эта виндовая версия при компрессии вываливается с KS>> assertation failed? BZ> Только что обработал cabarc.exe (без опций) - все ок, и BZ> запакованный cabarc прекрасно работает :) Я нашел причину. Оказалось, что при работе под Win95 все нормально, а если запускать Win95 под vmware, то падает с assertation. Даже и не знаю... Старая версия upx'а работает и так и так. -- С уваэением, Konstantin. --- * Origin: unknown. (2:5036/29)
Предыдущий блок Следующий блок Вернуться в индекс