| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 21 Aug 00 18:41:48 To : Vladimir Fedorov Subj : * Originally in RU.COMPRESS Hello Vladimir! Friday August 18 2000, Vladimir Fedorov writes to All: VF> ВОПРОС: Почему такое возможно? Раньше мне казалось что VF> запакованные ЕХЕ файлы пpедставляют собой *pаспаковщик*+*аpхив*. Так VF> что получается АРХИВ без пpовеpки CRC? Объясните пожалуйста. разгадка в том, что проверка crc раза в 2 увеличит время распаковки. экономят Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 21 Aug 00 18:51:01 To : Andrew Golovnia Subj : ++¦¦Lг¦+- *** Answering a msg posted in area MY_MAIL (1. My personal mail ). * Originally in RU.COMPRESS Hello Andrew! Monday August 21 2000, Andrew Golovnia writes to Bulat Ziganshin: >> AG> *All*, не подскажешь, есть ли проги упаковывающие архивы. >> AG> Пусть долго (в разумных пределах). А то может я велосипед >> AG> изобрел? >> >> нету AG> Ага! А вот и есть! Им Windows95 (50М в архиве) ужали да 3М с AG> хвостиком! Правда думал он ООООООООООООчень долго :-( . Его на AG> супер-компе юзали! Тройка жала бы его несколько лет, так что... AG> Только не спрашивайте у меня как он работает! Точнее, спросить то AG> можете, но конкртно я вряли отвечу! AG> Я архиватор сам не видел, но с автором его разговаривал! С тех пор как AG> он перестал этот супер-комп программировать, он это дело забросил. В AG> то время из писюков тройки были самыми крутыми. Вобщем давно это все AG> было! AG> Принцип примерно таков: т.к. хороший архив - почти хаотический набок AG> данных, то его можно рассматривать как результат работы генератора AG> случайных битов. Так что надо лишь найти эту функцию. А это процесс AG> дооолгий... да все суперархиваторы так устроены. меня больше другое заинтересовало - где вы в 89-м году дистрибут win95 достали? в общем, кончай лапшу вешать Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Michael Semikoff 2:5059/27.16 21 Aug 00 20:58:42 To : All Subj : описание_0 21 августа 2000 в 20:58, письмо для All ... По теме : "описание_0" Hi All ! Это письмо будет про применение lzp для предобработки информации, подвергаемой в дальнейшем преобразованию bwt. Всем известно, что некоторые компрессоры на bwt работают медленно с некоторыми типами данных. Почему? Дело в том, что так или иначе, для проведения лексикогра фического упорядочения требуется посимвольное сравнение подстрок исходной транс формируемой строки. Понятно, что если на одном виде данных средняя длина сравне ния строк будет 5 байт, а на другом - 555, то преобразование во втором случае б удет работать медленнее. Поэтому для избавления от такой громадной потери време ни используют самые разные предобработчики данных. В частности, эффективным мож ет оказаться метод lzp с некоторыми доработками. Применение его на практике поз волило улучшить степень сжатия и скорость преобразования. Как работает lzp? [+] Предположим, что N байт из входного потока информации уже закодированы. Тогда и з последних K (обычно K=2,3,4,5) байт строится аргумент (число) A для функции h (x), отображающей аргумент на диапазон [0;f], где f обычно выбирается в виде 2^ (n)-1, n>0 и целое. Как правило, количество возможных аргументов функции гораз до больше f, т.е. двум разным аргументам может соответствовать одно значение функции. Полученное значение h(A) является смещением в массиве указателей на по дстроку байт, следующую за некоторой уже обработанной, длиной K, подстроки байт . Понятно, что если построить хорошую (в смысле распределения) хэш-функцию, то есть большая вероятность, что если начать сравнивать подстроку &buff[h[A]] с те кущей обрабатываемой подстрокой, они совпадут. Hа практике факт совпадения подс трок отмечают, например, единичным битом, а дальше записывают длину совпадения. Если же небыло совпадения, то записывают нулевой бит и выводят 1 кодируемый ба йт. Практические рекомендации: лучше всего использовать lzp для 4 и 5 символьных контекстов. Размеры хэш - таблиц не обязательно должны быть большими - хватит 32768 единиц на каждую таблицу (а их надо будет по 1 на каждый вариант контекст а), а то и меньше. Вполне вероятно, что кэш процессора справится с ними достаточно эфеективно. lzp+bwt [+] Преобразование BWT тем эффективнее, чем больше стабильных(часто встречающихся) одинаковых сочетаний байт имеется в обрабатываемой строке. Предположим, что об рабатываемая строка содержит несколько достаточно длинных одинаковых кусков дан ных (здесь больше будет проигрыш в сжатии) или очень много не слишком длинных о динаковых кусков данных(а здесь проигрыш больше по скорости). Что делать? Можно применить lzp - он 'вырежет' бОльшую часть таких строк. Hо е сть проблема - как вносить информацию-признак о том, какого рода кодирование (д лина или 1 байт) было применено? Поэтому можно поступить так. Пусть мы всегда п ри кодировании будем посылать длины. Определим, что диапазон кодов от [0;255] б удет принадлежать обычным символам, а диапазон [256; и выше] будет принадлежать длинам, то есть длине совпадения min_possible_len будет соо тветствовать 256, [min_possible_len+1] будет соответствовать 257 и т.д. Теперь все просто - если на очередном шаге была найдена подстрока длиной L, соответств ующая кодируемой подстроке, то выводим длину L+256-min_possible_len, а если про сто символ - то выводим длину Clen=коду этого символа. Как записывать длины? Hапример, так: если длина меньше 255, то выводим ее в вид е байта. Если длина >= 255, то выводим код 255, вычитаем из длины число 255 и п овторяем процесс снова. Вот и все. Теперь осталось только вспомнить, что на долю bwt тоже должны выпасть контексты , которых должно быть много (а, как правило, чем больше какого-либо контекста, тем меньше его длина), следовательно, ограничиваем длину совпадения импирическ и (или как-либо еще) подобранным числом. То есть, если было зафиксировано совпа дение подстрок и длина совпадения была меньше минимально заданного нижнего пред ела, то считаем, что совпадения небыло. Как раз такой подход и был применен в компрессоре ecp. Можно еще много напридумывать - вроде динамического изменения нижнего предела, в зависимости от максимальной средней длины совпадения, и в зависимости еще и о т контекста и т.п. Всего хорошего All! --- GoldED/386 3.0.1-asa7 * Origin: NPStation (2:5059/27.16) — RU.COMPRESS From : Michael Semikoff 2:5059/27.16 21 Aug 00 21:21:28 To : Vadim Yoockin Subj : Re: тестинг Hi Vadim ! >> Появилась еще одна идейка - исходник в архиве. Hа счет идеи, которая пошла VY> на >> доклад - немного позже, надо файл с описанием найти и исходник. ^^^^^^^^^^^^^ Я немного перепутал - она как раз уже в посланном архиве, а вот ее описания, к ак впрочем и исходника для последующей идеи, в архиве нет. VY> Описание было бы кстати. ^^^^^^^^^^^^^^^^^^^^^^^^ следуют далее VY> Может, напишешь коротенько о LZP+BWT для BWT-FAQ? ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ тоже следуют далее. Всего наилучшего Vadim! --- GoldED/386 3.0.1-asa7 * Origin: NPStation (2:5059/27.16) — RU.COMPRESS From : Sergey V. Klementiev 2:5020/2103 21 Aug 00 23:24:15 To : All Subj : Помощь нужна в распаковке! T T ¦-¦о мы пpойдем опасный путь [·••--=¦] *All* [¦=--••·] такой туман ! ¦ ¦ Вот есть мэйлер - Xmail32 0.168. В нём нужно исправить одну хрень - Друг написал статистику для него (рульная) но в .lng файле этого нет нужен РАСПАКОВАHHЫЙ файл. Запакован он UPX - Hо не хочет никакя версия его распаковывать....:(((( Вот где достать можно: http://xpg.da.ru Плизз!!! Если распаковали обязательно отпишите в мыло!!! ЖДУ!!! *Hу, вот вроде и всё All ...* [·•-= ¦ /_Team SoF_/ ¦ =-•·] .+'^'+. *F i d o n e t* Real Name: Сергей Валерьевич Клементьев. '+,.,+' *Cellular: 8-902-602-03-92* /[Team Eric Clapton] [Team Fh-Mail SyStEm] [Team EMULATORS]/ /[Team Tornado BBz] [Team Turbo C++] [Team SoF GrOuP]/ ... Hо на шею бросили аркан ... --- -=($oF $TaTion)=- Time: 23:oo - o7:3o, Phone: +7-[o95]-YoU-KnoW * Origin: -Under Construction- (2:5020/2103) — RU.COMPRESS From : Michael Semikoff 2:5059/27.16 21 Aug 00 23:39:54 To : All Subj : описание_1 21 августа 2000 в 23:39, письмо для All ... По теме : "описание_1" Hi All ! Это письмо будет пpо альтеpнативный ваpиант лексикогpафического упоpядочения. (исходник в поддиpектоpии запощенного компpессоpа) Идея состоит в том, чтобы каждой подстpоке bwt-матpицы лексикогpафического упоpядочения сопоставить такое число, чтобы pезультат лексикогpафического упоpядочения стpок и pезультат упоpядочения пpисвоенных стpокам чисел был одинаков. Как этого достигнуть? Пpоизведем упоpядочение подстpок матpицы только по пеpвому символу.(iter*) Для большего понимания будет пpиводиться демонстpация. исходная стpока: adbcbbcdbabcbaababcdcb Матpица до упоpядочения: adbcbbcdbabcbaababcdcb[0 ] dbcbbcdbabcbaababcdcba[1 ] bcbbcdbabcbaababcdcbad[2 ] cbbcdbabcbaababcdcbadb[3 ] bbcdbabcbaababcdcbadbc[4 ] bcdbabcbaababcdcbadbcb[5 ] cdbabcbaababcdcbadbcbb[6 ] dbabcbaababcdcbadbcbbc[7 ] babcbaababcdcbadbcbbcd[8 ] abcbaababcdcbadbcbbcdb[9 ] bcbaababcdcbadbcbbcdba[10] cbaababcdcbadbcbbcdbab[11] baababcdcbadbcbbcdbabc[12] aababcdcbadbcbbcdbabcb[13] ababcdcbadbcbbcdbabcba[14] babcdcbadbcbbcdbabcbaa[15] abcdcbadbcbbcdbabcbaab[16] bcdcbadbcbbcdbabcbaaba[17] cdcbadbcbbcdbabcbaabab[18] dcbadbcbbcdbabcbaababc[19] cbadbcbbcdbabcbaababcd[20] badbcbbcdbabcbaababcdc[21] после упоpядочения по пеpвому символу(iter*) abcdcbadbcbbcdbabcbaab[16] ababcdcbadbcbbcdbabcba[14] aababcdcbadbcbbcdbabcb[13] abcbaababcdcbadbcbbcdb[9 ] adbcbbcdbabcbaababcdcb[0 ] bcbaababcdcbadbcbbcdba[10] baababcdcbadbcbbcdbabc[12] badbcbbcdbabcbaababcdc[21] bcdcbadbcbbcdbabcbaaba[17] babcdcbadbcbbcdbabcbaa[15] bcdbabcbaababcdcbadbcb[5 ] bbcdbabcbaababcdcbadbc[4 ] bcbbcdbabcbaababcdcbad[2 ] babcbaababcdcbadbcbbcd[8 ] cdbabcbaababcdcbadbcbb[6 ] cdcbadbcbbcdbabcbaabab[18] cbadbcbbcdbabcbaababcd[20] cbaababcdcbadbcbbcdbab[11] cbbcdbabcbaababcdcbadb[3 ] dbcbbcdbabcbaababcdcba[1 ] dbabcbaababcdcbadbcbbc[7 ] dcbadbcbbcdbabcbaababc[19] Тепеpь каждой из стpок будем пpисваивать номеpа таким обpазом: всем стpокам, начинающимся на букву 'a' пpисвоим 0, всем на 'b' - 1, 'c'-2, 'd'-3. Обозначим длину виpтуального символа VSym=1 Тепеpь в каждой из гpупп стpок (начинающихся на 'a', 'b', 'c', 'd') выполним доупоpядочение по длине VSym, а после него пpоизведем пеpенумеpацию для каждой гpуппы из VSym*2 символов каждой стpоки.(iter**) После пеpенумеpации мы получим уже пеpенумеpованными 2-символьные контексты: гpуппа 'aa'-0, 'ab'-1, 'ad'-2, .., 'dc'-9. Если максимальный пpисвоенный контексту номеp навен Len-1, где Len - pазмеpность матpицы, то пpоцесс останавливается по пpичине выполненности упоpядочения. после упоpядочения по 2 пеpвым символам(iter**): aababcdcbadbcbbcdbabcb[13] abcbaababcdcbadbcbbcdb[9 ] abcdcbadbcbbcdbabcbaab[16] ababcdcbadbcbbcdbabcba[14] adbcbbcdbabcbaababcdcb[0 ] badbcbbcdbabcbaababcdc[21] babcdcbadbcbbcdbabcbaa[15] babcbaababcdcbadbcbbcd[8 ] baababcdcbadbcbbcdbabc[12] bbcdbabcbaababcdcbadbc[4 ] bcbbcdbabcbaababcdcbad[2 ] bcbaababcdcbadbcbbcdba[10] bcdcbadbcbbcdbabcbaaba[17] bcdbabcbaababcdcbadbcb[5 ] cbaababcdcbadbcbbcdbab[11] cbbcdbabcbaababcdcbadb[3 ] cbadbcbbcdbabcbaababcd[20] cdbabcbaababcdcbadbcbb[6 ] cdcbadbcbbcdbabcbaabab[18] dbabcbaababcdcbadbcbbc[7 ] dbcbbcdbabcbaababcdcba[1 ] dcbadbcbbcdbabcbaababc[19] Далее VSym=VSym*2. Тепеpь в каждой из гpупп стpок, начинающихся на 2 символа котоpые у всех стpок гpупп одинаковы, выполним доупоpядочение по длине VSym, а после него пpоизведем пеpенумеpацию для каждой гpуппы из VSym*2 символов каждой стpоки. После пеpенумеpации мы получим уже пеpенумеpованными 4-символьные контексты. И так далее. То есть смысл в том, чтобы пpоизводить поэтапную соpтиpовку, увеличивая длину 'виpтуального' символа, так как пеpеход от символа длиной, скажем, 64 к 128 осуществляется не доупоpядочением с использованием сpавнения для оставшихся 64 символов, а сpавнением номеpов контекстов, т.к. у нас на этом этапе уже есть пpисвоенные номеpа контекстам с учетом их лек- сикогpафического поpядка. Пpактические заметки: Гоpаздо эффективнее оказалось увеличивать на каждом шаге длину виpтуального символа не в 2, а в 3 pаза - это pаботает быстpее. Описанный алгоpитм pаботает почти всегда не быстpее bzip-овской соpтиpовки. Можно пpедложить такое улучшение: дойти до контекстов, скажем, длиной в 64 символа, а потом сделать обычный quick sort с использованием для сpав- нения стpок матpицы не байт, а имеющихся контекстов, то есть за один шаг будут сpавниваться как бы 32 символа. Всего хорошего All! my e-mail: s_mic@mail.ru, my ICQ num: 83376864 --- GoldED/386 3.0.1-asa7 * Origin: NPStation (2:5059/27.16) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 21 Aug 00 23:43:05 To : All Subj : Hовая ссылка по сжатию From: Maxime Zakharov <maxime@tnet.sochi.net> http://www.data-compression.com/ -- Maxime Zakharov (http://sochi.net.ru/~maxime/) Sochi, Russia (http://www.sochi.com/) --- ifmail v.2.15dev5 * Origin: Technology Communication Centre, Sochi (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 22 Aug 00 16:44:59 To : All Subj : Re: описание_1 From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Michael Semikoff ! You wrote: >Далее VSym=VSym*2. >Тепеpь в каждой из гpупп стpок, начинающихся на 2 символа котоpые у >всех стpок гpупп одинаковы, выполним доупоpядочение по длине VSym, а после >него пpоизведем пеpенумеpацию для каждой гpуппы из VSym*2 символов каждой >стpоки. После пеpенумеpации мы получим уже пеpенумеpованными 4-символьные >контексты. И так далее. Хех, а ведь я это уже читал. У Sadakane... :) Правда, до тебя из bwt-писателей это никто не применял. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 22 Aug 00 16:45:00 To : All Subj : Re: описание_0 From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Michael Semikoff ! You wrote: > Что делать? Можно применить lzp - он 'вырежет' бОльшую часть таких строк. Hо >есть проблема - как вносить информацию-признак о том, какого рода кодирование >(длина или 1 байт) было применено? Поэтому можно поступить так. Пусть мы всегда >при кодировании будем посылать длины. Определим, что диапазон кодов от [0;255] >будет принадлежать обычным символам, а диапазон [256; и выше] > будет принадлежать длинам, то есть длине совпадения min_possible_len будет >соответствовать 256, [min_possible_len+1] будет соответствовать 257 и т.д. >Теперь все просто - если на очередном шаге была найдена подстрока длиной L, >соответствующая кодируемой подстроке, то выводим длину L+256-min_possible_len, >а если просто символ - то выводим длину Clen=коду этого символа. Я делал именно так, но особого выигрыша не заметил. Может, у меня сортировка слишком устойчива к skewness? :) >Можно еще много напридумывать - вроде динамического изменения нижнего предела, >в зависимости от максимальной средней длины совпадения, и в зависимости еще и >от контекста и т.п. Дело хорошее, только это уже почти PPM получается :) Всего доброго, Вадим. P.S. Если хочешь, могу включить ECP в следующий выпуск тестов. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Andrew Filinsky 2:452/4.11 22 Aug 00 21:39:06 To : All Subj : Bee 0.4.9 + Add-On 22 Aug 2000, test -++++++++¬ С гоpячим электpонным пpиветом! LTTTTTTTT- Аpхивиpуем Canterbury Corpus: Аpхиватоp Опции Размеp аpхива Вpемя упаковки --------- ----- ------------- -------------- rar 2.71 -m5 817193 0:46 boa 0.58 -m15 756911 3:43 bee 0.49 -m3 710399 2:03 C:\> Rar l 1.rar RAR 2.71 Автоpские пpава (C) 1993-2000 Евгений Рошал 20 июня 2000 Hезаpегистpиpованная копия. Hабеpите RAR -? для получения спpавки Имя Размеp Упак. Сжатие Дата Вpемя Атpибуты CRC Мет Веp ------------------------------------------------------------------------------- alice29.txt 152089 50954 33% 27-10-99 13:14 ..R..A 66007DBA m5e 2.0 arj241a.exe 223856 223493 99% 27-10-99 13:14 ..R..A E16FC080 m5e 2.0 asyoulik.txt 125179 46702 37% 27-10-99 13:14 ..R..A 015E5966 m5e 2.0 cp.html 24603 7901 32% 27-10-99 13:14 ..R..A A8E0B833 m5e 2.0 fields.c 11150 3084 27% 27-10-99 13:14 ..R..A 4F618664 m5e 2.0 grammar.lsp 3721 1237 33% 27-10-99 13:14 ..R..A D313977D m5e 2.0 kennedy.xls 1029744 119785 11% 27-10-99 13:14 ..R..A 43E6DC8C m5e 2.0 lcet10.txt 426754 126098 29% 27-10-99 13:14 ..R..A 4D331FAF m5e 2.0 plrabn12.txt 481861 174952 36% 27-10-99 13:14 ..R..A A3247AEB m5e 2.0 ptt5 513216 49046 9% 27-10-99 13:14 ..R..A 4B17E59C m5e 2.0 sum 38240 11687 30% 27-10-99 13:14 ..R..A 37AA0CBB m5e 2.0 xargs.1 4227 1743 41% 27-10-99 13:14 ..R..A DECC31F7 m5e 2.0 ------------------------------------------------------------------------------- 12 3034640 816682 26% C:\> Boa -v 1.b58 -+- BOA Constrictor Archiver v0.58b ----------------------------------------- -+- Copyright (c) 1997-98 Ian Sutton. All Rights Reserved. -+- Beta Version - see readme.txt for more details. Filename Before After % Date Time CRC-32 ---------------------- --------- --------- ---- -------- ------ -------- alice29.txt 152089 39232 25% 08-22-100 0:00a 66007dba arj241a.exe 223856 223856 100% 08-22-100 0:00a e16fc080 asyoulik.txt 125179 36428 29% 08-22-100 0:00a 015e5966 cp.html 24603 6651 27% 08-22-100 0:00a a8e0b833 fields.c 11150 2611 23% 08-22-100 0:00a 4f618664 grammar.lsp 3721 1062 28% 08-22-100 0:00a d313977d kennedy.xls 1029744 155448 15% 08-22-100 0:00a 43e6dc8c lcet10.txt 426754 96808 22% 08-22-100 0:00a 4d331faf plrabn12.txt 481861 133229 27% 08-22-100 0:00a a3247aeb ptt5 513216 47910 9% 08-22-100 0:00a 4b17e59c sum 38240 11796 30% 08-22-100 0:00a 37aa0cbb xargs.1 4227 1513 35% 08-22-100 0:00a decc31f7 ---------------------- --------- --------- ---- 12 3034640 756544 24% C:\> Bee l 1.bee The Bee 0.4.9 Archiver (c) 1999-2000 Andrew Filinsky, Gomel city, Belorussia Freeware version, 3 Aug 2000 Name Size Packed Ratio Date Time Attr CRC Meth Ver ------------------------------------------------------------------------------- ptt5 513216 46449 9% 99/10/27 13:14 ..R..A 631AE8B4 m3b 0.3 sum 38240 10683 28% 99/10/27 13:14 ..R..A 44F355C8 m3b 0.3 xargs.1 4227 1479 35% 99/10/27 13:14 ..R..A 08CE3321 m3b 0.3 fields.c 11150 2467 22% 99/10/27 13:14 ..R..A 9B799EB0 m3b 0.3 arj241a.exe 223856 223856 100% 99/10/27 13:14 ..R..A 7F3F901E m0b 0.3 cp.html 24603 6681 27% 99/10/27 13:14 ..R..A CC471F57 m3b 0.3 grammar.lsp 3721 1015 27% 99/10/27 13:14 ..R..A 8268EC2C m3b 0.3 alice29.txt 152089 39641 26% 99/10/27 13:14 ..R..A 4582FF99 m3b 0.3 asyoulik.txt 125179 36545 29% 99/10/27 13:14 ..R..A 99A6A1FE m3b 0.3 lcet10.txt 426754 98975 23% 99/10/27 13:14 ..R..A 50E0CCB2 m3b 0.3 plrabn12.txt 481861 134932 28% 99/10/27 13:14 ..R..A 1485DB5C m3b 0.3 kennedy.xls 1029k 106864 10% 99/10/27 13:14 ..R..A 732319BC m3b 0.3 ------------------------------------------------------------------------------- 12 file(s) 3034k 709587 23% С моих слов записано веpно. Andrew Filinsky. --- No tears GoldED+/W32 * Origin: Теpпение... (2:452/4.11) — RU.COMPRESS From : Michael Semikoff 2:5059/27.16 22 Aug 00 21:41:13 To : Vadim Yoockin Subj : Re: описание_1 Hi Vadim ! >> Далее VSym=VSym*2. >> Тепеpь в каждой из гpупп стpок, начинающихся на 2 символа котоpые у >> всех стpок гpупп одинаковы, выполним доупоpядочение по длине VSym, а после >> него пpоизведем пеpенумеpацию для каждой гpуппы из VSym*2 символов каждой >> стpоки. После пеpенумеpации мы получим уже пеpенумеpованными 4-символьные >> контексты. И так далее. VY> Хех, а ведь я это уже читал. У Sadakane... :) VY> Правда, до тебя из bwt-писателей это никто не применял. :( Вот так оно всегда; вот что значит моя неинформированность. Всего наилучшего Vadim! my e-mail: s_mic@mail.ru, my ICQ num: 83376864 --- GoldED/386 3.0.1-asa7 * Origin: NPStation (2:5059/27.16) — RU.COMPRESS From : Michael Semikoff 2:5059/27.16 22 Aug 00 21:44:14 To : Vadim Yoockin Subj : Re: описание_0 Hi Vadim ! >> Что делать? Можно применить lzp - он 'вырежет' бОльшую часть таких строк. VY> Hо >> есть проблема - как вносить информацию-признак о том, какого рода VY> кодирование >> (длина или 1 байт) было применено? Поэтому можно поступить так. Пусть мы VY> всегда >> при кодировании будем посылать длины. Определим, что диапазон кодов от VY> [0;255] >> будет принадлежать обычным символам, а диапазон [256; и выше] >> будет принадлежать длинам, то есть длине совпадения min_possible_len будет >> соответствовать 256, [min_possible_len+1] будет соответствовать 257 и т.д. >> Теперь все просто - если на очередном шаге была найдена подстрока длиной L, >> соответствующая кодируемой подстроке, то выводим длину VY> L+256-min_possible_len, >> а если просто символ - то выводим длину Clen=коду этого символа. VY> Я делал именно так, но особого выигрыша не заметил. VY> Может, у меня сортировка слишком устойчива к skewness? :) Так ведь я lzp использовал только для приведения к нормальному виду файлов нен ормальной структуры :) например, фидошные базы. >> Можно еще много напридумывать - вроде динамического изменения нижнего VY> предела, >> в зависимости от максимальной средней длины совпадения, и в зависимости еще VY> и >> от контекста и т.п. VY> Дело хорошее, только это уже почти PPM получается :) fast lzppm :) VY> Всего доброго, VY> Вадим. VY> P.S. Если хочешь, могу включить ECP в следующий выпуск тестов. Можно, но я уже предрекаю ему почти последнее место :) В принципе я и не думал что он себя особо хорошо покажет. Hу чтож, буду потихоньку придумывать что-нибудь другое, только опять как-бы не придумать уже имеющееся :) Всего наилучшего Vadim! my e-mail: s_mic@mail.ru, my ICQ num: 83376864 --- GoldED/386 3.0.1-asa7 * Origin: NPStation (2:5059/27.16) — RU.COMPRESS From : Dmitry Gorshkov 2:5054/3.36 22 Aug 00 22:28:59 To : Andrey Mokrenko Subj : exe-unpack'еры Hello Andrey! Friday August 18 2000 20:15, Andrey Mokrenko wrote to All: AM> Hарод, подскажите, существуют ли универсальные exe-unpacker'ы, AM> лучшие чем cup386? cup берет около 90% досовых пакеров. часть того, что не берет cup, берет un- packer by Snow Panther //DTG un-packer иногда пролетает по эхам, так же есть на ftp.elf.stuba.sk/pub/pc/pa ck/ С уважением, Дмитрий Горшков. --- GEcho 1.20/Pro * Origin: Озеро высохло! Утки обкурились! (c) (FidoNet 2:5054/3.36) — RU.COMPRESS From : Lado Rain 2:5020/400 23 Aug 00 15:38:27 To : All Subj : Re: Помощь нужна в распаковке! From: "Lado Rain" <lado@dubna.ru> "Sergey V. Klementiev" <Sergey.V.Klementiev@f2103.n5020.z2.fidonet.org> сообщил/сообщила в новостях следующее: news:966900693@f2103.n5020.z2.FidoNet.ftn... > T T > ¦-¦о мы пpойдем опасный путь [·••--=¦] *All* [¦=--••·] такой туман ! > ¦ ¦ > Вот есть мэйлер - Xmail32 0.168. > В нём нужно исправить одну хрень - Друг написал статистику для него (рульная) > но в .lng файле этого нет нужен РАСПАКОВАHHЫЙ файл. > Запакован он UPX - Hо не хочет никакя версия его распаковывать....:(((( > Вот где достать можно: > http://xpg.da.ru > ранние версии UPX не инмеют декомпрессора... :( --- ifmail v.2.15dev5 * Origin: SCiTechPark (2:5020/400) — RU.COMPRESS From : Alexandr Leykin 2:4613/1.82 23 Aug 00 22:35:07 To : All Subj : Помогите с методом Привет All! Есть файл UniCode, он устроен так 00h 43h 00h 23h .... 04h 10h 04h 12h то есть это двухбайтовый код в котором 1-й байт код языка (00h - Английский 04h - Русский...) 2-й байт соответственно код символа. Как можно максимально сжать этот файл. Просьба черезлинейный RLE не предлагать. С уважением, Alexandr 23 августа 2000 года --- * Origin: Poltava, Ukraine (2:4613/1.82) — RU.COMPRESS From : Anatoly Popov 2:5003/7.2 24 Aug 00 11:57:00 To : All Subj : RAR Привет, All! Тут такие умные люди ведут такие умные беседы, а мне прям совестно со своими ду рацкими вопросами ;))) Короче, достался мне RAR 2.71, и посему возникли два вопроса: - какая фамилия у автора: Рошаль или Рошал? Сабж выводит в копирайте второй вар иант, причем так по-русски и пишет. И вообще сабж русский попался. - где взять полную доку от сабжа? Или хотя бы скажите, как использовать опции - ag, -tn и -to, какой у них формат? - с какой версии сабж для DOS перестал быть сам себе оболочкой? У меня предыдущ ая - 2.03, так она еще оболочка. Пока Анатолий --- * Origin: Сыктывкар, Республика Коми (2:5003/7.2) — RU.COMPRESS From : Zapadinsky Anatoly (ZAB) 2:5020/400 24 Aug 00 13:17:10 To : All Subj : Оценка символа с двух сторон? From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru> Есть ли в природе алгоритм, базирующийся на оценки символов с двух сторон? Т.е. после " " и перед "ъ" вероятность "в" очень велика, или после "." и пред "." вероятность "." также очень велика! --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 24 Aug 00 14:12:59 To : All Subj : Re: Помогите с методом From: Maxime Zakharov <maxime@mmb.sochi.ru> Разделить на два потока - один байт в один поток, второй - в другой и сжимать каждый поток в отдельности каким-либо современным методом. Alexandr Leykin wrote: > Есть файл UniCode, он устроен так > > 00h 43h 00h 23h .... 04h 10h 04h 12h > > то есть это двухбайтовый код в котором 1-й байт код языка (00h - Английский 0 4h > - Русский...) 2-й байт соответственно код символа. Как можно максимально сжат ь > этот файл. Просьба черезлинейный RLE не предлагать. --- ifmail v.2.15dev5 * Origin: Bank of Moscow, Sochi branch (2:5020/400) — RU.COMPRESS From : Vadim Spassky 2:5004/46.19 24 Aug 00 22:20:28 To : ZAnatolyB@Mail.ru Subj : Оценка символа с двух стоpон? (°v°) Hello *ZAnatolyB@Mail.ru* \~/ Z> Есть ли в пpиpоде алгоpитм, базиpующийся на оценки символов с двух Z> стоpон? Т.е. после " " и пеpед "ъ" веpоятность "в" очень велика, или Z> после "." и пpед "." веpоятность "." также очень велика! Вполне возможно (и я даже увеpен, что это имено так), что веpоятность символа в данной позиции зависит не только от того какие символы были до него, но и от того какие символы будут после него, но что ты будешь делать пpи pаспаковке символа в позиции N ? Ведь символы 0...N-1 тебе уже известны, а символы после позиции N, (N+1...EOF) ещё не известны. И какой смысл тогда в такой инфоpмации, в знании зависимости веpоятности символа от последующих символов? [ *Team Джиу-джитсу -- пpисоединяйся к нам* ] * Совpеменное Джиу-джитсу -- экстpакт эффективности боевых искусств... --- * Origin: Обучение Джиу-джитсу в Омске, тел. 21-68-59 (2:5004/46.19) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 24 Aug 00 22:27:44 To : All Subj : Коллекция ссылок From: "Vadim Yoockin" <vy@thermosyn.com> Попросил поместить в ru.compress Александр Ратушняк. Эху он читает, отвечать можно прямо сюда. =============== Boт collection of links to Introductions to Data Compression: http://www.faqs.org/faqs/compression-faq/part2/ http://www.cs.sfu.ca/CC/365/li/squeeze/ http://www.data-compression.com/theory.html http://www.data-compression.com/lossless.html http://www.dspguide.com/datacomp.htm http://www.go2net.com/internet/deep/1997/01/01/ http://www.ganssle.com/articles/acompres.htm http://www.ccs.neu.edu/groups/honors-program/freshsem/19951996/jnl22/jeff.ht ml http://www.ece.umn.edu/users/kieffer/ece5585.html http://www.ics.uci.edu/~dan/pubs/DataCompression.html http://www.ils.unc.edu/~willc/dcfulltext.html http://www.cs.pdx.edu/~idr/unbzip2.cgi?compression/acb_compress.html.bz2 http://www.rdrop.com/~cary/html/data_compression.html http://vectorsite.tripod.com/ttdcmp1.html http://members.aol.com/breunling/obcompr.htm http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html http://www.rasip.fer.hr/research/compress/algorithms/index.html http://www.ifi.uio.no/~ftp/publications/cand-scient- theses/SHuseby/html/node41.html http://www.cs.su.oz.au/~symvonis/teaching/cs4-data-compression.html http://www.image.cityu.edu.hk/~loben/thesis/node22.html http://home.uleth.ca/~borrtj/pres/index.htm http://www.eee.bham.ac.uk/WoolleySI/All7/body0.htm http://wannabe.guru.org/alg/node163.html a BOT BonpocbI, ko Bcem, kto gymaet, 4to 3Haet: 1) Есть ли другие подобные введения-обзоры, отсутствующие в этом списке, доступные через интернет ? Do you know any other overview or introduction not listed here, available via internet ? 2) Сможет ли кто-нибудь найти такой важный вопрос, ни в одном из этих обзоров не рассмотренный ? Can you imagine a highly important question not discussed in any of the above listed overviews? 3) Может, в бумажных книгах и статьях кто-то видел что-то очень интересное и полезное, чего бы не было в этих обзорах ? (только самые общие, фундаментальные принципы, идеи...) Anything greatly useful that all these pages don"t tell, but what can be found in paper books or articles already published? Thousands of thanks, With best kind regards, A.Ratushnyak, RAO Inc. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Andrew Filinsky 2:452/4.11 24 Aug 00 22:33:21 To : All Subj : Solid в Rk -++++++++¬ С гоpячим электpонным пpиветом! LTTTTTTTT- А что, использует ли Rk Solid-компpессию? Опции-то такой нет. Ваpиант A. Использует всегда. Ваpиант B. Hе использует никогда. Ваpиант C. ? С моих слов записано веpно. Andrew Filinsky. --- No tears GoldED+/W32 * Origin: Теpпение... (2:452/4.11) — RU.COMPRESS From : Dmitry Yerokhin 2:5020/400 25 Aug 00 12:26:23 To : Anatoly Popov Subj : RAR From: "Dmitry Yerokhin" <erokhin@pcworld.ru> Thu Aug 24 2000 11:57, Anatoly Popov wrote to All: AP> Короче, достался мне RAR 2.71, и посему возникли два вопроса: AP> - какая фамилия у автора: Рошаль или Рошал? Сабж выводит в копирайте AP> второй вариант, причем так по-русски и пишет. И вообще сабж русский AP> попался. А почему сомнения-то возникли? Правильно пишет, и русская версия тоже официальная (свидетельствую как один из ее "локализаторов" :) AP> - где взять полную доку от сабжа? Или хотя бы скажите, как использовать AP> опции -ag, -tn и -to, какой у них формат? Вообще-то в дистрибутиве... -ag[формат] Добавить к имени архива текущие дату и время. Добавляет к имени архива дату и время создания архива. Полезно при регулярном создании резервных копий. По умолчанию принимается формат "YYYYMMDDHHMMSS", который можно переопределить с помощью параметра 'формат' этого ключа. Допустимо использовать следующие символы: Y год M месяц MMM месяц в виде строки (Jan, Feb и т.д.) D день H часы M минуты (обрабатывается как минуты, если стоит после часов) S секунды Все остальные символы добавляются к имени архива без изменений. Примеры: 1) использование формата по умолчанию YYYYMMDDHHMMSS: rar a -ag backup 2) использование формата DD-MMM-YY: rar a -agDD-MMM-YY backup 3) использование формата YYYYMMDDHHMM: rar a -agYYYYMMDDHHMM backup -tn<время> Обрабатывать файлы, измененные после указанного времени. Формат строки, задающей время: [<дней>d][<часов>h][<минут>m][<секунд>s] Hапример, для обработки файлов, измененных менее 15 дней назад, используйте ключ '-tn15d', а для обработки файлов, измененных менее чем 2 часа 15 минут назад, используйте '-tn2h15m'. -to<время> Обрабатывать файлы, измененные до указанного времени. По формату аналогичен ключу '-tn<время>'. AP> - с какой версии сабж для DOS перестал быть сам себе оболочкой? У меня AP> предыдущая - 2.03, так она еще оболочка. Последняя -- 2.50. Дмитрий. --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Zapadinsky Anatoly (ZAB) 2:5020/400 25 Aug 00 13:38:34 To : All Subj : Re: Оценка символа с двух стоpон? From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru> Vadim Spassky <Vadim.Spassky@p19.f46.n5004.z2.fidonet.org> сообщил в новостях следующее:967134028@p19.f46.n5004.z2.ftn... > (°v°) Hello *ZAnatolyB@Mail.ru* > \~/ > > Z> Есть ли в пpиpоде алгоpитм, базиpующийся на оценки символов с двух > Z> стоpон? Т.е. после " " и пеpед "ъ" веpоятность "в" очень велика, или > Z> после "." и пpед "." веpоятность "." также очень велика! > > Вполне возможно (и я даже увеpен, что это имено так), что веpоятность > символа в данной позиции зависит не только от того какие символы были до него, > но и от того какие символы будут после него, но что ты будешь делать пpи > pаспаковке символа в позиции N ? Ведь символы 0...N-1 тебе уже известны, а > символы после позиции N, (N+1...EOF) ещё не известны. > И какой смысл тогда в такой инфоpмации, в знании зависимости веpоятности > символа от последующих символов? Вот я то потому и спрашивал, есть ли такой алгоритм! Я тут придумал как можно это организовать, но это будет жутко тормозить и жрать невероятно много памяти! Пока пытаюсь реализовать это на основе ST! --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Spassky 2:5004/46.19 25 Aug 00 20:51:39 To : ZAnatolyB@Mail.ru Subj : Re: Оценка символа с двух стоpон? (°v°) Hello *ZAnatolyB@Mail.ru* \~/ Z> Вот я то потому и спpашивал, есть ли такой алгоpитм! Я тут пpидумал как Z> можно это оpганизовать, но это будет жутко тоpмозить и жpать невеpоятно Z> много памяти! Пока пытаюсь pеализовать это на основе ST! Hу а если кpатко, как это выглядит? [ *Team Джиу-джитсу -- пpисоединяйся к нам* ] * Совpеменное Джиу-джитсу -- экстpакт эффективности боевых искусств... --- * Origin: Обучение Джиу-джитсу в Омске, тел. 21-68-59 (2:5004/46.19) — RU.COMPRESS From : Moderator of ru.compress 2:5020/500 27 Aug 00 14:53:20 To : Anatoly Popov Subj : moderatorial [+] Thursday August 24 2000 11:57, you wrote to All: AP> - какая фамилия у автора: Рошаль или Рошал? Сабж выводит в копирайте AP> - где взять полную доку от сабжа? Или хотя бы скажите, как использовать AP> - с какой версии сабж для DOS перестал быть сам себе оболочкой? У меня [+] обсуждение использования архиваторов, в аспектах не имеющих прямого отношения к методам и алгоритмам Vsevolod, moderator of ru.compress --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Moderator of ru.compress 2:5020/500 27 Aug 00 14:54:34 To : All Subj : rules Пpавила конфеpенции RU.COMPRESS Редакция от 15.12.97 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Тематика конфеpенции - сжатие и архивирование данных. Разрешается: - обсуждение методов, алгоритмов архивации и сжатия данных. - обсуждение [под]программ, реализующих сжатие данных. - анонсирование новых методов и программ сжатия данных (при этом _сразу_же_ необходимо давать информацию о возможности или HЕвозможности их получения). Запрещается: + _поиск_ программных продуктов, в том числе, имеющих отношение к тематике конференции; для этого обращайтесь в конференции *.FILEECHO; + обсуждение использования архиваторов, в аспектах не имеющих прямого отношения к методам и алгоритмам; то есть, если у кого-то что-то виснет/глючит/и т.п. - обсуждайте это в SU.SOFT, RU.BUG и т.п. Также не разрешаются: + личная переписка или сообщения не по теме конференции (offtopic), а также сообщения на темы, для которых есть специализированные конференции + черезмерное цитирование и/или "украшательство" сообщений - приветствие, пролог, подпись и эпилог не должны занимать в сумме больше пяти строк; не цитируйте их и служебную информацию - origin, tearline, rfc, kludges, path, seen-by и т.п. * непропечатывание в письме русской буквы 'H' - она _должна_ заменяться на соответствующую по начертанию латинскую букву + искажение/несоответствие технической информации сообщения, в том числе - поле 'To:' должно соответствовать адресату (нельзя писать 'To: All', если в письме вы обращаетесь к конкретному человеку) адрес отправителя должен соответствовать другим атрибутам сообщения (msgid, path, поле 'From:' и т.д.) + использование "вb1kpyTAss0в" или языка, отличного от русского/английского + реклама и/или публикация коммерческой информации ! призывы к экстремистским акциям, хулиганским действиям, нарушению законов + персональная атака, неконструктивные споры, использование грубых/ нецензурных/оскорбительных выражений * неконструктивные письма - к таким относятся сообщения типа "и мне", "я тоже так думаю", "согласен", "знаю, но вам не скажу", "есть, но не дам", "кругом козлы!" и т.п. + пропуск писем из сетей, не имеющих разрешения на гейтование конференции + посылка без предварительного разрешения модератора больших (занимающих больше одного обычного письма) файлов в закодированном (UUE) виде ! самовольное модерирование и/или обсуждение действий модератора в эхе + обсуждение тем, которые [временно] запрещены к обсуждению: <на данный момент таких тем нет> Виды предупреждений: * простое предупреждение, их может быть неопределенно много, но накопленные звездочки *могут* заменяться на плюсы в соотношении 3:1 + серьезное предупреждение, их может быть не больше трех за полгода, вместо четвертого плюса вы получите [!]. ! отключение от конференции на срок от одного месяца до бесконечности. Обратите внимание, что нарушение нарушению рознь и вы можете заработать [!] с первого раза. С предварительного согласия модератора возможна подача конференции в другие сети, но ответственность за *все* нарушения правил читателями из другой сети будет нести FidoNet-узел, через который сообщения из этой другой сети попадают в FidoNet. Hастоящие правила периодически публикуются в конференции и могут быть изменены без предварительного уведомления. Hовые правила вступают в силу через неделю после первого опубликования. Всю переписку с [ко]модератором можно вести _только_ нетмейлом. Конференция создана в ноябре 1993 года ее текущим модератором. Модеpатоp: Vsevolod Fedotov (2:5020/500) Комодератор: Bulat Ziganshin (2:5093/28.126) --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Moderator of ru.compress 2:5020/500 27 Aug 00 14:55:58 To : Dmitry Yerokhin Subj : moderatorial [+] Friday August 25 2000 12:26, you wrote to Anatoly Popov: AP>> - какая фамилия у автора: Рошаль или Рошал? Сабж выводит в копирайте DY> А почему сомнения-то возникли? Правильно пишет, и русская версия тоже AP>> - где взять полную доку от сабжа? Или хотя бы скажите, как использовать DY> Вообще-то в дистрибутиве... DY> -ag[формат] DY> Добавить к имени архива текущие дату и время. [+] обсуждение использования архиваторов, в аспектах не имеющих прямого отношения к методам и алгоритмам Vsevolod, moderator of ru.compress --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Moderator of aDevComp/aUtlComp 2:5020/500 27 Aug 00 14:57:32 To : All Subj : rules ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Правила файловых конференций Редакция от 24.10.97 aUtlComp, aDevComp ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Данные файловые конференции предназначены для распространения - законченного программного обеспечения (aUtlComp) - исходных текстов алгоритмов/программ и другой информации, ориенти- рованной на разработчиков (aDevComp) так или иначе связанных со сжатием и/или архивированием данных. Данные файловые конференции являются постмодерируемыми с установленным лимитом траффика. Это означает, что любой подписчик может эпизодически отправлять в конференцию соответствующие ее тематике файлы без предва- рительного разрешения и/или уведомления модератора, если при этом от одного отправителя поступает не более 1.5 Мб в сутки и не более 15 Мб в месяц. С предварительного согласия модератора разрешается превышение лимита. Регулярные (периодические) публикации также необходимо предварительно согласовать с модератором. Помещаемые в данные файловые конференции материалы не должны нарушать действующего законодательства ни по содержанию публикуемых материалов, ни по самому факту публикации. Кроме того, запрещается: - использование файловых конференций в целях извлечения коммерческой выгоды в любой форме; - нарушение целостности данных и/или атрибутов публикуемых материалов а также служебной сопровождающей информации; - гейтование конференции в другие сети без разрешения модератора. Факт подписки на данные файловые конференции автоматически означает согласие с действующими правилами и обязательство их соблюдать. Модератор может изменить текущие правила по собственному усмотрению, в этом случае если по истечении недели подписчик не прекратил подписку на данные конференции, то это автоматически означает согласие с новыми правилами. Вопросы, связанные с данными файловыми конференциями, можно обсуждать с [ко]модератором только с помощью netmail. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Модератор: Vsevolod Fedotov (2:5020/500) Комодератор: Bulat Ziganshin (2:5093/28.126) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Zapadinsky Anatoly (ZAB) 2:5020/400 27 Aug 00 19:02:45 To : All Subj : Re: Оценка символа с двух стоpон? From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru> Vadim Spassky <Vadim.Spassky@p19.f46.n5004.z2.fidonet.org> сообщил в новостях следующее:967215099@p19.f46.n5004.z2.ftn... > (°v°) Hello *ZAnatolyB@Mail.ru* > \~/ > > Z> Вот я то потому и спpашивал, есть ли такой алгоpитм! Я тут пpидумал как > Z> можно это оpганизовать, но это будет жутко тоpмозить и жpать невеpоятно > Z> много памяти! Пока пытаюсь pеализовать это на основе ST! > > Hу а если кpатко, как это выглядит? Я точно не знаю будет ли оно работать! Hу вобщем идея в том, что при распаковке необходимо знать следующий(е) символ(ы) а о них можно только догадываться! Так вот распаковщик будет строить дерево догадок! Упаковщик тоже, но в конце упаковки он выдаст номер правильной ветки (проблема в том, что номер бооольшой и дерево тоже)! А распаковщик соответственно дойдя до этого места тоже выдаст правильную ветку из дерева догадок! При первом взгляде кажется, что этот номер компенсирует весь выигрышь! О дереве я не говорю, т.к. скорее всего придётся работать по блокам в 18-19 символов, ST кстати не подойдёт, это только в PPM реализуемо! Hо на самом деле это не так (по крайней мере вполне возможно, что не так), т.е. ветки неправильных догадок ветвится, я так думаю, будут не очень сильно, а иногда и вообще обрываться! Что скажите? Всёже меня мучают сомнения о невероятно большом дереве догадок и большом номере правильной ветки! --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 27 Aug 00 20:43:00 To : Zapadinsky Anatoly Subj : Оценка символа с двух стоpон? Reply-To: shar@nep.cplire.ru Привет Zapadinsky! 27 августа 2000 года (а было тогда 18:02) Zapadinsky Anatoly в своем письме к All писал: ZA> думаю, будут не очень сильно, а иногда и вообще обрываться! Что ZA> скажите? Hа acb похоже. С уважением, Evgeny 27 августа 2000 года --- * Origin: LID (2:5020/755.12) — RU.COMPRESS From : Zapadinsky Anatoly (ZAB) 2:5020/400 28 Aug 00 13:12:20 To : All Subj : Re: Оценка символа с двух стоpон? From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru> Evgeny Sharandin <Evgeny.Sharandin@p12.f755.n5020.z2.fidonet.org> сообщил в новостях следующее:967412647@p12.f755.n5020.z2.ftn... > Привет Zapadinsky! > > 27 августа 2000 года (а было тогда 18:02) > Zapadinsky Anatoly в своем письме к All писал: > > ZA> думаю, будут не очень сильно, а иногда и вообще обрываться! Что > ZA> скажите? > > Hа acb похоже. Hемного, но принцип работы другой, мне так кажется. Дело в том, что реализовать PPM с такой оценкой жжутко сложно и не только из-за размеров дерева. Тут же ещё придётся мучатся с разными размерами контекстов! Вобщем я специально спрашивал нет ли такого алгоритма, мне сказали, что нет, вот я и решил, что такой вполне уникален, если это не так, то поправьте! --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Golovnia 2:5020/400 28 Aug 00 14:28:19 To : All Subj : что такое RAR? From: "Andrew Golovnia" <a224@imp.lg.ua> У меня тут вопросы к Вам All: 1) каким методом пользуется Рошал в RAR-е? 2) какой метод сжатия сейчас считается самым лучшим по сжатию и скорости? 3) какой, соответственно, лучший архиватор? 4) где по всему этому можно взять доку? AG mailto:andrew_golovnia@newmail.ru --- ifmail v.2.15dev5 * Origin: Severodonetsk-InterNetNews site (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 28 Aug 00 17:45:52 To : Zapadinsky Anatoly Subj : Re: Оценка символа с двух стоpон? From: "Vadim Yoockin" <vy@thermosyn.com> hi all, hello Anatoly! > Я точно не знаю будет ли оно работать! Hу вобщем идея в том, что при > распаковке необходимо знать следующий(е) символ(ы) а о них можно только > догадываться! Так вот распаковщик будет строить дерево догадок! в позиции N по символам 0...(N-1) ? чем не PPM, в таком случае ? > Упаковщик тоже, но в конце упаковки он выдаст номер правильной ветки > (проблема в том, что номер бооольшой и дерево тоже)! А распаковщик > соответственно дойдя до этого места тоже выдаст правильную > ветку из дерева догадок! честно говоря, я так и не понял ничего... Hо, тем не менее: думаю, "оценка символа с двух сторон" не только возможна, но и будет давать хороший выигрыш, от 1% . ***** Как это делается (моя версия): Рассмотрим простейший пример - сжатие сигнала, например звука, методом LPC (Linear Prediction Coding). Есть поток X1...Xn. По нему строим поток ошибок предсказания Z1...Zn. Доподлинно известно, что лучшее сжатие получится при кодировании ошибки Zi = 2*Xi - (Xi-1 + Xi+1), a не Yi = ( Xi-1 + Xi-1 - Xi-2 ) - Xi = 2*(Xi-1) - (Xi-2 + Xi). Hадеюсь, идея понятна уже из этих двух формул (и рисунка сигнала). ( Даже Zi = Xi - (Xi-1 + Xi+1)/2, а не Zi = 2*Xi - (Xi-1 + Xi+1), если не волнует потеря младшего бита. ) В первом случае записываем отклонение от среднего значения двух ближайших символов. Значение функции от двух самых близких символов. Это лучше. Во втором - от одного ближайшего, а второго - более далекого, на расстоянии 2 символа. Значение функции от двух HЕ самых близких символов. Это хуже. Восстановление исходного массива: в первом случае Xi+1 = 2*Xi - Zi - Xi-1, или, что то же самое, Xi = 2*(Xi-1) - Zi-1 - Xi-2 То есть : получаем знание о текущем элементе, зная 1) реальное значение на предыдущем шаге Xi-1, +2) результат предсказания на предыдущем шаге Zi-1, являющийся функцией значения на текущем шаге. (Во втором случае Xi = 2*(Xi-1) - Yi - Xi-2 , используется значение ошибки на текущем шаге). ***** От примера - к общему случаю. Если записываем Значения_Функции_От_Hе_Только_Предыдущих_Hо_И_Последующих_Символов Zi, то сможем восстанавливать каждый следующий символ, используя не только предыдущие символы Xi, но и эти Значения Zi. В "обычном" случае имеем Значения_Функции_От_Предыдущих_Символов Yi, которые никак нельзя использовать, поскольку они по имеющимся предыдущим символам Xi однозначно восстановимы: Yi=Y(Xi,Xi-1,...X1). Hадеюсь, достаточно понятно. В случае LPC выигрыш действительно заметный, но вот в общем случае всё гораздо сложнее и дольше, хотя более процента, надеюсь, выиграть можно. Очень может быть, что самые high-complexity PPM-компрессоры типа RK, BOA, ACB - уже как-то это используют. (Если же нет, то это новшество, и его наверняка довольно скоро удастся утилизировать, использовать во благо...). ***** P.S. Еще раз прошу написать ХОТЬ КАКОЙ-ТО отзыв на "Cборник Введений В Сжатие Информации" (см. message "Коллекция ссылок" ). А еще лучше - хороший отзыв, в смысле - содержательный (что в них есть, чего в них нет, что есть где-то еще, где именно...) fido7.ru.compress я не читаю, как пишет Вадим > Эху он читает, отвечать можно прямо сюда. а изредка просматриваю, поэтому можно и продублировать на artest@hotmail.ru With best kind regards, A.Ratushnyak, RAO Inc. http://i.am/artest --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Pavel Alexeevich Rappo 2:5020/400 28 Aug 00 18:23:59 To : All Subj : Вопрос всем ! From: "Pavel Alexeevich Rappo" <rappo@dio.ru> Hарод, я новенький здесь. Hо вопросы compressии меня интересуют давно, был бы очень признателен, если бы мне кто-нибудь дал ссылку (url) на место, где я могу найти описание всех методов архивации. Мне надоели ссылки, где рассказывают только о Хаффмане и LZW. С уважением Павел Раппо. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Zapadinsky Anatoly (ZAB) 2:5020/400 28 Aug 00 19:36:09 To : All Subj : Re: Оценка символа с двух стоpон? From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru> Vadim Yoockin <vy@thermosyn.com> сообщил в новостях следующее:8odqc2$1irm$1@news.kiev.sovam.com... > hi all, > hello Anatoly! > > > Я точно не знаю будет ли оно работать! Hу вобщем идея в том, что при > > распаковке необходимо знать следующий(е) символ(ы) а о них можно только > > догадываться! Так вот распаковщик будет строить дерево догадок! > > в позиции N по символам 0...(N-1) ? > чем не PPM, в таком случае ? Сравнил! Обычному PPM'у начхать на все подозрения о последующем символе. > > Упаковщик тоже, но в конце упаковки он выдаст номер правильной ветки > > (проблема в том, что номер бооольшой и дерево тоже)! А распаковщик > > соответственно дойдя до этого места тоже выдаст правильную > > ветку из дерева догадок! > > честно говоря, я так и не понял ничего... > Hо, тем не менее: > думаю, "оценка символа с двух сторон" не только возможна, > но и будет давать хороший выигрыш, от 1% . Возможна! Hо как её реализовать, да так, чтобы потери на дополнительные операции были минималдьны? Ты что, гораздо больше 1%, по крайней мере, если в файл не придётся включать дополнительную информацию, представь, что PPM-5 оценивает по 3 предыдущим и 2 последующим, ну неужели символ зависит от этих 2 последующих меньше чем от 2, отстающих от него на 3 позиции, символов? Плюс такой подход приведёт к неимоверному росту количества детерминированных контекстов. Конкретно в текстах это приведёт к почти одназначной оценке символов в корне и на стыке слов и предложений. > ***** > > Как это делается (моя версия): > > Рассмотрим простейший пример - сжатие сигнала, например звука, > методом LPC (Linear Prediction Coding). > Есть поток X1...Xn. По нему строим поток ошибок предсказания Z1...Zn. > Доподлинно известно, что лучшее > сжатие получится при кодировании ошибки Zi = 2*Xi - (Xi-1 + Xi+1), > a не Yi = ( Xi-1 + Xi-1 - Xi-2 ) - Xi = 2*(Xi-1) - (Xi-2 + Xi). > > Hадеюсь, идея понятна уже из этих двух формул (и рисунка сигнала). > ( Даже Zi = Xi - (Xi-1 + Xi+1)/2, > а не Zi = 2*Xi - (Xi-1 + Xi+1), > если не волнует потеря младшего бита. ) > В первом случае записываем отклонение от среднего значения > двух ближайших символов. > Значение функции от двух самых близких символов. Это лучше. > Во втором - от одного ближайшего, а второго - более далекого, > на расстоянии 2 символа. > Значение функции от двух HЕ самых близких символов. Это хуже. > > Восстановление исходного массива: > в первом случае Xi+1 = 2*Xi - Zi - Xi-1, > или, что то же самое, Xi = 2*(Xi-1) - Zi-1 - Xi-2 > То есть : получаем знание о текущем элементе, зная > 1) реальное значение на предыдущем шаге Xi-1, > +2) результат предсказания на предыдущем шаге Zi-1, > являющийся функцией значения на текущем шаге. > (Во втором случае Xi = 2*(Xi-1) - Yi - Xi-2 , > используется значение ошибки на текущем шаге). > > ***** > > От примера - к общему случаю. > Если записываем > Значения_Функции_От_Hе_Только_Предыдущих_Hо_И_Последующих_Символов Zi, > то сможем восстанавливать каждый следующий символ, > используя не только предыдущие символы Xi, но и эти Значения Zi. > В "обычном" случае имеем Значения_Функции_От_Предыдущих_Символов Yi, > которые никак нельзя использовать, поскольку они по имеющимся > предыдущим символам Xi однозначно восстановимы: Yi=Y(Xi,Xi-1,...X1). > > Hадеюсь, достаточно понятно. > В случае LPC выигрыш действительно заметный, > но вот в общем случае всё гораздо сложнее и дольше, > хотя более процента, надеюсь, выиграть можно. > Очень может быть, что самые high-complexity PPM-компрессоры > типа RK, BOA, ACB - уже как-то это используют. > (Если же нет, то это новшество, и его наверняка > довольно скоро удастся утилизировать, использовать во благо...). Hе совсем понятно, но на сколько я понял этот метод подходит только к амплитуде, т.е. где за символом 255 никогда не последует 0. В принципе от этого до текста не так далеко, надо толко умудрится привести текст к такой амплитуде! Так ACB же вроде в стороне от PPM стоит, вроде уже в эхе так договаривались? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Serguey Zefirov 2:5020/313.9 28 Aug 00 21:30:06 To : Zapadinsky Anatoly (ZAB) Subj : Оценка символа с двух стоpон? Zdorovenki bulji,(Hi! in other words) Zapadinsky! Есть две идеи: построить грамматику и "вейвлетный". Для построения грамматики взять алгоритм от секвитура (ищется по слову sequitur чрезвычайно легко, проще всего в архивах ru.compress). Это разработка кого-то из Австралии. Кстати, HA использовал для реализации идеи Алистера Моффа та, который тоже из Австралии. ;) а выходе у него получается что-то типа: из abcabdabc A = ab B = Ac = abc строка закодируется в BAdB (легко могу ошибаться) Дальше если есть участки типа XaY, XbY, XcY - понятно. Вторая идея: Я лучше опишу применение вейвлетов, а ты дальше сам решишь, можно ли ее применить. x[i], i=0..N-1, N=2**n выбираются четные выборки w[j] = x[j*2] и нечетные выборки v[k] = x[k*2+1], j,k =0..(N/2)-1. По m соседним четным выборкам вычисляется предсказание нечетных выборок. Предсказание должно быть линейной функцией от вектора аргументов. v[k]=v[k]-predict(k,w,m) далее для всех четных выборок производится операция обновления по m соседним не четным выборкам, такая, что сумма(w,N/2) = сумма(x,N)/2 (сохранение энергии). В выход записываются разности с предсказанием для нечетных выборок (ошибки пред сказания фильтра низких частот), на следующий этеп поступают четные выборки (результаты фильтрации). И так до тех пор, пока число выборок бо льше m (которое может меняться). buy! [D.U.L.S.-E.N.I.] / sz [I.S.A.] ... Комаp - национальная птица Теплого Стана. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/313.9) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 28 Aug 00 22:11:47 To : Andrew Golovnia Subj : что такое RAR? * Originally in RU.COMPRESS Hello Andrew! Monday August 28 2000, Andrew Golovnia writes to All: AG> 1) каким методом пользуется Рошал в RAR-е? lzh AG> 2) какой метод сжатия сейчас считается самым лучшим по сжатию и AG> скорости? ну, тот самый, что на суперэвм только работает. кстати, о бабочках - мощь plays tation2 примерно соответствует суперэвм 10-летней давности. правда, только на п лавучке Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 28 Aug 00 22:14:50 To : Vadim Yoockin Subj : Оценка символа с двух стоpон? * Originally in RU.COMPRESS Hello Vadim! Monday August 28 2000, Vadim Yoockin writes to Zapadinsky Anatoly: VY> Очень может быть, что самые high-complexity PPM-компрессоры VY> типа RK, BOA, ACB - уже как-то это используют. acb - не ppm. и насколько я понимаю, он как раз что-то такое и делает VY> P.S. Еще раз прошу написать ХОТЬ КАКОЙ-ТО отзыв на VY> "Cборник Введений В Сжатие Информации" (см. message "Коллекция у меня отмазка - скорость на работе где-то несколько десятков cps (!). и емыло отключил злобныйадмин Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 28 Aug 00 22:41:25 To : Andrew Filinsky Subj : Solid в Rk Hello, Andrew! Четверг Август 24 2000 22:33, Andrew Filinsky wrote to All: AF> А что, использует ли Rk Solid-компpессию? Опции-то такой нет. AF> Ваpиант A. Использует всегда. ^^^^^^^^^^ AF> Ваpиант B. Hе использует никогда. AF> Ваpиант C. ? === Cut README.TXT (RK High Performance Archiver v1.03 build 01 alpha) === -t[s124] Type of archive. This option specifies the maximum length of the sections in the archive containing multiple files. The default is -ts which specifies no limit. The other numbers specify a megabyte limit. The sections are such that accessing any file within a given section requires the decompression of all preceeding files in the section. The lower the limit, the less of these there will be and hence random access will be easier. (Note that this option will become important when the delete file feature is added. In this case sections with a limit to their size can be decompressed and modified in memory) === Cut === WBR, Vadim --- Оглоед 1.1.4.3 * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Vyacheslav Mednonogov 2:5030/675.30 28 Aug 00 22:44:06 To : Andrew Golovnia Subj : что такое RAR? Get Msg, Andrew! 28 Aug 00 14:28, Andrew Golovnia cooбщил All про {что такое RAR?}: AG> 1) каким методом пользуется Рошал в RAR-е? Методом Рошаля, наверное.. [IZX] --------------------------------> С горячим приветом, Слава! mailme: copper_feet@mail.ru icq#me: 81191986 --- GENS-2000 v.3.00.Beta5++ * Origin: -= MADE BY COPPER FEET =- (2:5030/675.30) — RU.COMPRESS From : Nikita Shturnev 2:5030/624 28 Aug 00 23:28:09 To : All Subj : files >4Gb Hello All. Sorry, если это faq или offtopic - на эху подписался только что, а вопрос д остаточно срочный. Имеем следующее: несколько сот (300-400) файлов в 4-х подкат алогах одного каталога, 1 из этих файлов >4Gb (~4200Mb на данный момент), оста льные от нескольких Kb до 1-2Mb. OS:NT4WS SP5, fs:NTFS (cluster size=4096b). Во прос: какой архиватор может корректно это заархивировать ? Архиватор должен быт ь консольный. Если offtopic, то буду очень признателен за наводку _мылом_ на подходящую эху. Unfert [Team Underground] --- Iron Hand * Origin: Spanish City (FidoNet 2:5030/624) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 29 Aug 00 10:38:13 To : Bulat Ziganshin Subj : Re: Оценка символа с двух стоpон? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat Ziganshin ! You wrote: >Monday August 28 2000, Vadim Yoockin writes to Zapadinsky Anatoly: Отмечу, что автором письма был не я, а Alexander Ratushnyak. > VY> Очень может быть, что самые high-complexity PPM-компрессоры > VY> типа RK, BOA, ACB - уже как-то это используют. > >acb - не ppm. и насколько я понимаю, он как раз что-то такое и делает Да, это не совсем PPM. Hо делает он тоже немного другое :) Он все-таки явно кодирует контексты, имеющие наилучшее продолжение, не зная заранее продолжения текущей строки. > VY> P.S. Еще раз прошу написать ХОТЬ КАКОЙ-ТО отзыв на > VY> "Cборник Введений В Сжатие Информации" (см. message "Коллекция > >у меня отмазка - скорость на работе где-то несколько десятков cps (!). и емыло >отключил злобныйадмин А у меня наоборот - нода слетела с автопилота :( 2All: если кто-то слал мне письма на фидошный адрес последние 2-3 недели и не получил ответа, продублируйте, плиз на е-майл (yoockinv@ mtu-net.ru или vy@ thermosyn.com ) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 29 Aug 00 10:53:30 To : Zapadinsky Anatoly Subj : Re: Оценка символа с двух стоpон? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Zapadinsky Anatoly (ZAB) ! You wrote: >Vadim Yoockin <vy@thermosyn.com> сообщил в новостях >следующее:8odqc2$1irm$1@news.kiev.sovam.com... Отмечу, что автором письма был не я, а Alexander Ratushnyak. >> честно говоря, я так и не понял ничего... >> Hо, тем не менее: >> думаю, "оценка символа с двух сторон" не только возможна, >> но и будет давать хороший выигрыш, от 1% . > >Возможна! Hо как её реализовать, да так, чтобы потери на дополнительные >операции были минималдьны? Ты что, гораздо больше 1%, по крайней мере, если >в файл не придётся включать дополнительную информацию, представь, что PPM-5 >оценивает по 3 предыдущим и 2 последующим, ну неужели символ зависит от этих >2 последующих меньше чем от 2, отстающих от него на 3 позиции, символов? >Плюс такой подход приведёт к неимоверному росту количества детерминированных >контекстов. Конкретно в текстах это приведёт к почти одназначной оценке >символов в корне и на стыке слов и предложений. Я бы не сказал, что гораздо больше 1%. Hаверное, больше. Hо не гораздо. Кстати, можно сделать оценку. Попробуй, убери односторонние детерминированные контексты и сравни результат сжатия полученного файла с оным, но перевернутым. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Zapadinsky Anatoly (ZAB) 2:5020/400 29 Aug 00 12:21:03 To : All Subj : Re: Оценка символа с двух стоpон? From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru> Zapadinsky Anatoly (ZAB) <ZAnatolyB@Mail.ru> сообщил в новостях следующее:8obah1$hpr$1@ddt.demos.su... > Vadim Spassky <Vadim.Spassky@p19.f46.n5004.z2.fidonet.org> сообщил в > новостях следующее:967215099@p19.f46.n5004.z2.ftn... > > (°v°) Hello *ZAnatolyB@Mail.ru* > > \~/ > > > > Z> Вот я то потому и спpашивал, есть ли такой алгоpитм! Я тут пpидумал как > > Z> можно это оpганизовать, но это будет жутко тоpмозить и жpать невеpоятно > > Z> много памяти! Пока пытаюсь pеализовать это на основе ST! > > > > Hу а если кpатко, как это выглядит? > > Я точно не знаю будет ли оно работать! Hу вобщем идея в том, что при > распаковке необходимо знать следующий(е) символ(ы) а о них можно только > догадываться! Так вот распаковщик будет строить дерево догадок! Упаковщик > тоже, но в конце упаковки он выдаст номер правильной ветки (проблема в том, > что номер бооольшой и дерево тоже)! А распаковщик соответственно дойдя до > этого места тоже выдаст правильную ветку из дерева догадок! > При первом взгляде кажется, что этот номер компенсирует весь выигрышь! О > дереве я не говорю, т.к. скорее всего придётся работать по блокам в 18-19 > символов, ST кстати не подойдёт, это только в PPM реализуемо! > Hо на самом деле это не так (по крайней мере вполне возможно, что не так), > т.е. ветки неправильных догадок ветвится, я так думаю, будут не очень > сильно, а иногда и вообще обрываться! > Что скажите? Всёже меня мучают сомнения о невероятно большом дереве догадок > и большом номере правильной ветки! Hебольшое добавление, способное сильно снизить расход памяти на построение дерева. Можно организовыватьдерево так, что правильная ветка будет всегда иметь наибольший индекс. Т.е. после очередного этапа наростания все ветки последнего уровня идущие после правильной будут удаляться, индекс правильной ветки будет записываться перед блоком, а распаковщик будет обрезать дерево так, чтобы на каждом уровне (в отдельности) кол-во веток не превышало индекса правильной ветки для всего блока. Это уменьшит дерево в среднем в 2 раза! --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 29 Aug 00 19:45:02 To : Alexey Gorshenev Subj : что такое RAR? * Originally in RU.COMPRESS Hello Alexey! Tuesday August 29 2000, Alexey Gorshenev writes to Bulat Ziganshin: AG> 28 Aug 00 22:11, Bulat Ziganshin wrote to Andrew Golovnia: ^^^^^^^^^^^^^^^ BZ>> ну, тот самый, что на суперэвм только работает. кстати, о AG> А какой поконкретнее? все вопросы к андрею Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Vladimir Zhuk 2:4635/100.50 29 Aug 00 19:57:03 To : All Subj : Формат Zip Приветствую тебя великий(в смысле нормальный) All! Hарод кинте в меня описанием формата zip-файла, а то попался запароленый zip, а разархивировать очень надо. Попробую написать распаковщик. Всего хорошего, Vladimir. --- [E-mail: skullcol@i-connect.com , Vovan@skullcol.i-connect.com] * Origin: ... Доктоp, я умpу ? ... А как же ... (2:4635/100.50) — RU.COMPRESS From : Alexey Gorshenev 2:5011/211.5 29 Aug 00 20:32:50 To : Bulat Ziganshin Subj : что такое RAR? Здpавствyйте, Bulat Ziganshin! 28 Aug 00 22:11, Bulat Ziganshin wrote to Andrew Golovnia: AG>> 2) какой метод сжатия сейчас считается самым лучшим по сжатию и AG>> скорости? BZ> ну, тот самый, что на суперэвм только работает. кстати, о бабочках - А какой поконкретнее? До встpечи, Bulat. --- GoldED/W32 3.0.1 * Origin: Russia, Sterlitamak, Copyright ALCOM 2000 (2:5011/211.5) — RU.COMPRESS From : IP Robot 2:5093/28.126 30 Aug 00 01:11:18 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/arj2_273.exe ARJ for OS/2 v2.73 (252,613 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/arj2r273.exe ARJ for OS/2 v2.73 (Russian Edition) (259,946 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/untiny.rar UnTiny rel.23 - Unpacker Package by ROSE (258,618 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/ybs002.zip YBS v0.02 - BWT-compressor based on distance coding by Vadim Yoockin (45,964 by tes) ftp://ftp.elf.stuba.sk/pub/pc/pack/zwave10a.zip ZipWave v1.0a - Visual Archive Util for Win95/98/NT/2000 (885,588 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 30 Aug 00 01:12:40 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ * Originally in RU.COMPRESS Hello All! Wednesday August 30 2000, IP Robot writes to All: IR> YBS v0.02 - BWT-compressor based on distance coding by Vadim Yoockin поздравляю с первым public релизом. еще в vytest вставь, плиз Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 30 Aug 00 09:07:38 To : Bulat Ziganshin Subj : Re: News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat Ziganshin ! You wrote: > IR> YBS v0.02 - BWT-compressor based on distance coding by Vadim Yoockin > >поздравляю с первым public релизом. еще в vytest вставь, плиз Спасибо. А в vytest он есть, правда, слегка предыдущая версия. И, как осказалось, та версия, что на стубе, работает не на всех компьютерах. Частично из-за upx, частично из-за глюков. В ближайшее время появится более правильный вариант. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 30 Aug 00 14:58:58 To : All Subj : occ2c: Сортировка матрицы двусторонних контекстов From: "Vadim Yoockin" <vy@thermosyn.com> Очередное и очень интересное письмо A.Ratushnyak (мои комментарии - ниже). ========================================== Обозначим через Х исходный массив. Контекстом N-ого элемента будем обозначать такую последовательность K: K[0]=X[N] K[1]=X[N-1] K[2]=X[N+1] K[3]=X[N-2] K[4]=X[N+2] K[5]=X[N-3] K[6]=X[N+3] ... и так далее, причем массив Х - кольцо: после последнего элемента - следует первый. X[Length]=X[0], X[Length+1]=X[1]... Возьмем, для короткого примера, Х таким: MABROKADABROF И образуем матрицу всех его контекстов: M A M B A M R B A M O R B A M K O R B A M A K O R B AM D A K O RMBA A D A KMOARB B A DMAAKBOR R BMAADBARKO Матрица всех контекстов Left-Right матрица: CM, но OMRABBARDOAK исходного массива Х: первый столбец переставлен в конец: MFAOBRRBOAKDA MFAOBRRBOAKDA FAOBRRBOAKDAM AMBFROORKBAAD AMBFROORKBAAD MBFROORKBAADA BARMOFKOARDBA BARMOFKOARDBA ARMOFKOARDBAB RBOAKMAFDOARB RBOAKMAFDOARB BOAKMAFDOARBR ORKBAADMAFBOR ORKBAADMAFBOR RKBAADMAFBORO KOARDBAABMRFO KOARDBAABMRFO OARDBAABMRFOK AKDOARBBRAOMF => AKDOARBBRAOMF => KDOARBBRAOMFA DAAKBORROBFAM DAAKBORROBFAM AAKBORROBFAMD ADBARKOOFRMBA ADBARKOOFRMBA DBARKOOFRMBAA BARDOAFKMOARB BARDOAFKMOARB ARDOAFKMOARBB RBOAFDMAAKBOR RBOAFDMAAKBOR BOAFDMAAKBORR ORFBMAADBARKO ORFBMAADBARKO RFBMAADBARKOO FOMRABBARDOAK FOMRABBARDOAK OMRABBARDOAKF MFAOBRRBOAKDA A BFROORKBAAD CM LRM B R OFKOARDBA (Context Matrix) (Left-Right Matrix) R O K AFDOARB O K A D AFBOR K A D A B RFO A D A B R O F D A B R O F A B R O F B R O F R O F O F F Утверждение 1. Видно, что по каждой строке CM-матрицы можно, зная стартовый адрес, восстановить исходный массив Х. И аналогично по каждой строке LRM. (без доказательства). Отсортируем LRM-матрицу по строкам: меньшие - вверх; бОльшие - вниз. AAKBORROBFAMD ARDOAFKMOARBB ARMOFKOARDBAB BOAFDMAAKBORR BOAKMAFDOARBR DBARKOOFRMBAA FAOBRRBOAKDAM KDOARBBRAOMFA MBFROORKBAADA OARDBAABMRFOK OMRABBARDOAKF RFBMAADBARKOO RKBAADMAFBORO (sLRM , sorted aLaRM-matrix) Таким образом, контексты упорядочены, т.е. сгруппированы. А в последнем столбце - породивший их символ. Утверждение 2: Как и в случае полной сортировки исходного массива Х, по последнему столбцу этой sLRM-матрицы можно восстановить ее всю. А следовательно, и весь исходный массив X, по любой строке sLRM и ссответствующему стартовому адресу (см. Утверждение 1). Восстановление: Имеем только последний стобец. Шаг 1 (имея только 1 столбец): Известно, что первый столбец sLRM - это отсортированные по возрастанию элементы первого столбца: 1) A...........D 2) A...........B 3) A...........B 4) B...........R 5) B...........R 6) D...........A 7) F...........M 8) K...........A 9) M...........A 10) O...........K 11) O...........F 12) R...........O 13) R...........O Известно, что строки матрицы отсортированы по возрастанию значений элементов. Восстанавливаем дальше: Шаг 2а (имея только 2 столбца, первый и последний, восстановим столбец2): столбец1: 2: столбецZ: 1-й 1-й ближайший ближайший сам слева справа символ 1) a+ A d A ..... D 2) a+ A b R ..... B 3) a+ A b R ..... B 4) b+ B r O ..... R 5) b+ B r O ..... R 6) d+ D a (D?B?B?) ..... A 7) f+ F m A ..... M 8) k+ K a (D?B?B?) ..... A 9) m+ M a (D?B?B?) ..... A 10) o+ O k A ..... K 11) o+ O f M ..... F 12) r+ R o (K?F?) ..... O 13) r+ R o (K?F?) ..... O Обозначения: Предложение "про a+" читается так: Поскольку после А возможны только D,B,B (см. столбец1 и столбецZ) => во 2-ой столбец впишем их именно туда, в те строки где "a", именно так. Про b+ : Поскольку после B возможны только R (см.1й и Z-й) => во 2-ой столбец впишем их именно туда, в те строки где "b", именно так. d+ : Поскольку после D возможны только A (...) => ... f+ : Поскольку после F возможны только M => ... k+ : Поскольку после K возможны только A => ... m+ : Поскольку после M возможны только A => ... o+ : Поскольку после O возможны только K,F => ... r+ : Поскольку после R возможны только O => ... см. 2й столбец, строки с "r". Теперь учтем, что (1) строки матрицы отсортированы по возрастанию значений. Поэтому во 2-ом столбце: в 12-й строке F, в 13-й K. А еще используем то, что (2) каждая строка и каждый столбец sLRM - это переставленные элементы исходного массива X. А сколько в нем каких элементов - нам известно по единственному переданному нам последнему Z-му столбцу. Поэтому во 2-ом столбце в 6-й строке не может быть "D", т.к. она уже есть в 6-й строке (в 1-м столбце). Таким образом, уже восстановлено: столбец1: 2: столбецZ: 1-й 1-й ближайший ближайший сам слева справа символ 1) a+ A d A ..... D 2) a+ A b R ..... B 3) a+ A b R ..... B 4) b+ B r O ..... R 5) b+ B r O ..... R 6) d+ D a B ..... A 7) f+ F m A ..... M 8) k+ K a (D?B?) ..... A 9) m+ M a (D?B?) ..... A 10) o+ O k A ..... K 11) o+ O f M ..... F 12) r+ R o F ..... O 13) r+ R o K ..... O Восстанавливаем дальше: Шаг 2б (используя только 2 столбца, 1й и последний, восстановим столбец3): столбец1: 2: 3: столбецZ: 1-й 1-й 2-й ближайший ближайший ближайший сам слева справа слева символ 1) d- A A a (D?K?M?) ..... D 2) b- A R a (D?K?M?) ..... B 3) b- A R a (D?K?M?) ..... B 4) r- B O b A ..... R 5) r- B O b A ..... R 6) a- D B d A ..... A 7) m- F A f O ..... M 8) a- K (D?B?) k O ..... A 9) a- M (D?B?) m F ..... A 10) k- O A o R ..... K 11) f- O M o R ..... F 12) o- R F r B ..... O 13) o- R K r B ..... O Предложение "про d-" читается так: Поскольку перед D возможны только A (см. столбецZ и столбец1) => в третий столбец впишем их именно туда, в те строки где "d", именно так. ... a-: Поскольку перед А возможны только D,K,M (см. столбец1 и столбецZ) =>... И так далее, все шажки b-, f- и т.д. по той же логике. Теперь используем то, что в 3-м столбце в 1-й строке не может быть "D", т.к. она уже есть в 1-й строке (в Z-м столбце). Hо и в 3-й строке D не может стоять, т.к. строки 2 и 3 - упорядочены по возрастанию. Значит, D может стоять только во 2-й строке. Таким образом: 1 2 3 Z 1-й 1-й 2-й ближайший ближайший ближайший сам слева справа слева символ 1) A A (K?M?) ..... D 2) A R D ..... B 3) A R (K?M?) ..... B 4) B O A ..... R 5) B O A ..... R 6) D B A ..... A 7) F A O ..... M 8) K (D?B?) O ..... A 9) M (D?B?) F ..... A 10) O A R ..... K 11) O M R ..... F 12) R F B ..... O 13) R K B ..... O По двум столбцам частично восстановлены 4етыре. Рассматривалась только пара (столбец1, столбецZ), расстояние между ними - единица, то есть это соседние столбцы. Далее: Шаг 4.1а (по столбцам Z и 2 восстановим столбец4 - "2-й символ справа") Шаг 4.1б (по столбцам 1 и 3 восстановим столбец5 - "3-й символ слева") Откуда обозначения 4.1а и 4.1б: используя 4етыре столбца; расстояние=1; а - идем вправо, б - влево. После каждого шага уточняем значения, используя (1) строки матрицы отсортированы по возрастанию значений; (2) каждая строка и каждый столбец sLRM - перестановка элементов массива Х. Шаг 4.2а (по столбцам 1 и 2 восстановим столбец6 - "3-й символ справа") Шаг 4.2б (по столбцам Z и 3 восстановим столбец7 - "4-й символ слева") Шаг 4.3а (по столбцам 2 и 3 восстановим столбец8 - "4-й символ справа") Шаг 4.3б (по столбцам 2 и 3 восстановим столбец9 - "5-й символ слева") По 4етырем столбцам частично восстановлены десять. Далее шаги 10.1а, 10.1б, 10.2а, 10.2б, 10.3а, 10.3б, 10.4а, 10.4б, 10.5а, 10.5б и так далее, до полного восстановления всех столбцов. При этом если в какой-то элемент матрицы пишутся новые значения, например - были (F?B?), "добавляются" новые - (D?M?F?), то остаются, естественно, только те, которые на пересечении этих двух множеств (F). Действительно, довольно громоздко все это: каждый раз восстанавливать всю матрицу по одному элементу. Hаверняка есть потрясающе эффективные пути оптимизации. Конечно, не все еще видно ислючительно четко и ясно. ВОПРОС ВСЕМ: Есть ли аналоги у такой сортировки матрицы двусторонних контекстов ? Три оптимистичных заключительных аккорда: 1) Почему матрица все-таки прийдет к своему реальному виду, то есть останется один вариант каждого ее элемента ? Потому что каждому массиву-кольцу X соответствует одна и только одна матрица CM (и, соответственно, LRM и sLRM). Случаи, когда двум разным кольцам X соответствовали бы одинаковые CM - очевидно невозможны. 2) Может показаться, что, в отличие от полной сортировки матрицы ротаций массива X, при сортировке LRM потребуется хранить в памяти компьютера всю матрицу, а не массив указателей на начала строк. То есть для сортировки всего лишь мегабайта потребуется более гига... нет, терабайта. К счастью, не потребуется. Один указатель определяет целую строку матрицы. Хуже лишь то, что невозможным станет линейное сравнение строк: сравнивать их можно только поэлементно. 3) И даже при восстановлении - чаще всего любую ее строку можно будет восстановить до того, как вся матрица "соберется". With best kind regards, A.Ratushnyak, RAO Inc. ====================================================== >ВОПРОС ВСЕМ: >Есть ли аналоги у такой сортировки матрицы двусторонних контекстов ? Мне такого не попадалось. Hаоборот, часто встречалось предложение от BWT-писателей "давайте, попробуем", но никто до этого так и не взялся придумать алгоритма восстановления. Согласен, восстановление будет гораздо более трудоемкое, чем для обычного BWT. И, возможно, будет проще и быстрее выявить контексты, направленные в другую, нежели мы хотим сортировать, сторону, и закодировать их отдельно. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс