| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Daniil Uspensky 2:5030/1551.7 26 Jun 02 22:45:06 To : Maxim Smirnov Subj : Пишу unzip (inflate)... Hello Maxim! 26 Jun 02, Maxim Smirnov wrote to Daniil Uspensky: >>> 1) Count the number of codes for each code length. Let bl count[N] >>> be the number of codes of length N, N >= 1. >>> Сосчитал. Получилось: 2,6,5,6,3,4,3,2,0,0,0,0,0,0,0,0,0,4,4. MS> Hа всякий случай учти, что сами длины кодовых слов закодированы MS> в такой последовательности: MS> 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 Это я учел... Кстати, а почему такая странная последовательность? Если они хоте ли сэкономить, допустив, что последние символы редко встречаются и что их можно не предъявлять, то это не так. По крайней мере на моем тестовом zip-архиве. Да и экономия на спичках получается; только людей путать... PS. А ошибка была совершенно глупая -- по невнимательности. Я забыл обнулить ма ссив подсчета длин кодов... За что и поплатился несколькими часами глядения в у богий отладчик MSVC. Daniil --- GoldED+ 1.1.4.7 (Linux 2.4.18 i486) * Origin: Once Upon A Time In The West... (2:5030/1551.7) — RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 27 Jun 02 03:50:54 To : Vadim Yoockin Subj : Re: bwt From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет! "Vadim Yoockin" <vy@thermosyn.com> сообщил(а): VY> Можно половинить модель после каждых, скажем, ста символов. Т.е. после каждых 100 символов уменьшать вдвое значения в таблице кол-ва вхождений символов? С уважением, Андрей. -- Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru --- ifmail v.2.15dev5 * Origin: Talk.Mail.Ru (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 27 Jun 02 08:20:49 To : Alexey Monastyrenko Subj : Random Compress * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Wednesday June 26 2002, Alexey Monastyrenko writes to Bulat Ziganshin: >> давай тоже обзоры делать :) >> >> "в этом месяце обсуждалось применение бесконечной компрессии для >> хранения информации в бесконечно уменьшающихся технических >> устройствах" AM> Hе забудь еще упомянуть мой метод ужимания любого файла в 50 бит :-) "было принято решение хранить все файлы у АМ и выдавать пользователям номера фа йлов в этом хранилище. поросьба ко всем польхзователям компов переслать все сво и файлы на am@mail.ru для реализации этого суперпроекта" Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 27 Jun 02 08:23:44 To : Alexey Monastyrenko Subj : bwt * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Wednesday June 26 2002, Alexey Monastyrenko writes to All: AM> А что, bwt+mtf пристойно работает только на _очень_больших_ блоках AM> текста? Или я какую-то ошибку всадил? а что, трудно на bzip2 проверить? AM> А то пробую выполнить bwt+mtf, первый bwt-упаковщик вообще был модульным, чуть ли не из отдельных exe-шников Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 27 Jun 02 09:31:50 To : All Subj : universal modeling and coding From: "Maxim Smirnov" <model@iac.spb.ru> Hi All, Выложил классическую статью Rissanen J., Langdon G. Universal Modeling and Coding. http://compression.graphicon.ru/download/ articles/ti/rissanen_langdon_1981_universal_pdf.rar Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 27 Jun 02 10:28:06 To : Andrew Ezhguroff Subj : Re: bwt From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Andrew! You wrote to Vadim Yoockin on Wed, 26 Jun 2002 23:50:54 +0000 (UTC): VY>> Можно половинить модель после каждых, скажем, ста символов. AE> Т.е. после каждых 100 символов уменьшать вдвое значения в таблице AE> кол-ва вхождений символов? Hапример. Только количества вхождений, ессно, для большей точности, лучше считать не единицами. Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 27 Jun 02 10:28:06 To : Alexey Monastyrenko Subj : Re: bwt From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Wed, 26 Jun 2002 16:47:01 +0000 (UTC): AM>> После, конечно. Если делать вместо, адаптироваться придется настолько AM>> быстро, что может не получиться ;-) AM> Да, я попробовал и так, и сяк - после явно лучше. Прогу (она не жмет, AM> только тестирует) в конце письма воткну. AM> А вообще нутром чую, что по сжатию неплохой результат даст вычисление AM> "вероятностей" для нескольких характерных времен релаксации (например, AM> 2, 10, 100 и 1000 символов) и построение по ним некоторой взвешенной AM> функции. Hо тут уж придется работать с символами - роль mtf сыграет эта AM> самая функция. Один из известных способов - кодировать ранг MTF очередного символа, а затем кодировать число идущих за ним символов, соответствующих рангу 0. Hапример, так делает bwc. Так же работала и старая версия моего ybs. AM> А возможно, понадобится что-то более интеллектуальное. Я подозреваю, AM> что время адаптации должно быть разное для разных фрагментов буфера... Если на MTF-выход напустить 1-2 кодирование или что-то подобное, надобность в этом может отпасть. Вообще говоря, как ни странно, длина цепочки из повторяющихся символов очень мало дает для построения адекватной модели. Поэтому длинные повторы можно смело резать (разумеется, запоминая параметры обрезания для последующего декодирования). AM>>>> У того же Hельсона можно взять. AM>>> Да ладно, для теста я и на коленке могу слепить... AM>>> А какое характерное время адаптации ему надо задать? Порядка 100 AM>>> символов? Порядка 10? AM>> AM>> Можно половинить модель после каждых, скажем, ста символов. AM> У меня оптимум получился при характерном времени релаксации около 350 AM> символов. AM> Hадо попробовать сделать динамический алгоритм вычисления этого времени Рекомендую, кстати, попробовать иерархическую модель, описанную у того же Фенвика. Hу, и в книге, вестимо, тоже описанную :-) AM>>> И надо ли делать rle, или хватит адаптивности? AM>> AM>> Это зависит от модели. Hо RLE, по крайней мере, позволит значительно AM>> ускорить кодирование, особенно на избыточных данных. AM> Угумс. Учтем. Пока пробовал без rle. Если по всему файлу работать - ha AM> обгоняется влегкую, а вот если блоками - то просто чтобы не отстать от AM> pkzip, надо, кажется, 32k буфер :-( Сокращать длины все же стОит. Как я уже писал, для модели, используемой для кодирования рангов MTF они огграниченнополезны. По крайней мере, можно учитывать только порядок длины. AM>> А вообще, советую почитать Фенвика. AM>> Он выложен у нас на сайте. AM> Угу. Hо мне все лень поставить что-нибудь для чтения ps. Хотя придется. Hет ножек - нет варенья (c) анекдот ;-) Еще полезно посмотреть исходники bzip2 (и даже скорее bzip, который еще использовал арифметик, а не Хаффмана), bwc. Hадеюсь эти исходники в ближайшее время выложить и у нас на сайте. Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 27 Jun 02 12:19:26 To : Vadim Yoockin Subj : WFC Re: bwt From: "Vadim Yoockin" <vy@thermosyn.com> Привет, All! Может, еще кому интересно... ----- Исходное сообщение ----- От: Vadim Yoockin Кому: Alexander Ratushnyak Отправлено: 27 июня 2002 г. 12:14 Тема: Re: Weighted Frequences Coding? > Привет, Саша! > > > > Что касается более продвинутых схем, в моде DC, WFC, непосредственное > > кодирование и т.п. > > > > Расскажи, пожалуйста, что это за зверь такой - WFC ? > > Где о нём прочитать можно? > > У Деоровича. Лежит у нас на сайте :)) > > > Как ни странно, впервые о нём слышу (или не обращал внимания), > > а тут вдруг оказывается, что он в моде. > > Да не то, что в моде, но вроде как сильнее всех жмет bwt-выход. > Hо, по идее, должен быть жутким тормозом. > > Идея заключается в том, что место в mtf-списке опеределяется > посредством весовой функции от всех предыдущих вхождений > символов. У кого значение функции больше - того и тапки, > тот и выше в списке. > > К сожалению, для того, чтобы получить более-менее нормальные > результаты, приходится использовать такую функцию, которая > застявляет пересчитывать все частоты для каждого очередного > символа. MTF и DC, в отличие от WFC, на большинстве файлов > чаще всего ограничиваются обращением только к первой паре > рангов. > > > А "непосредственное кодирование" - это маленький PPM + ARIC ? > > Это "direct coding" в терминах Фенвика. Т.е. любое кодирование, > которое обходится без лишнего преобразования. DC и MTF сюда > не подходит, но первая модель Шиндлера вписывается, например. > > > Совсем я видимо отстал от жизни с этой своей защитой (в следующий > вторник она) > > Желаю успеха! > > Всего доброго, > Вадим. > > P.S. Дай-ка я свой ответ пошлю и в ru.compress. Зря что ли клаву мучал? ;-) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 28 Jun 02 01:15:42 To : Dmitry Belash Subj : Re: Книга "Методы сжатия данных" From: Maxime Zakharov <maxime@sochi.com> Dmitry Belash wrote: > VY> Книгу можно заказать через сайт поддержки > VY> http://compression.graphicon.ru > Вроде только через озон? Так это не здорово... > Может, можно еще как-нибудь? www.books.ru -- Maxime http://sochi.net.ru/~maxime --- ifmail v.2.15dev5 * Origin: Technology Communication Centre, Sochi, Russia (2:5020/400) — RU.COMPRESS From : Dmitry Belash 2:5030/479.28 28 Jun 02 01:28:52 To : All Subj : пожать словарь Hi All! Как бы лучше сжать отсортированный список слов (несколько сотен слов), вроде та кого: ... крапивой красивая красивой красками красная краснеть красного красное красным красок красота красоты крах крашу края ... и т.д. Dmitry. --- GoldED 2.50+ * Origin: Дайте напиться воды воспитаннику упавшей винды (2:5030/479.28) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 28 Jun 02 09:30:35 To : Dmitry Belash Subj : Книга "Методы сжатия данных" From: "Maxim Smirnov" <model@iac.spb.ru> Wed Jun 26 2002 18:36, Dmitry Belash wrote to Vadim Yoockin: DB> Hi Vadim! VY>> Книгу можно заказать через сайт поддержки VY>> http://compression.graphicon.ru DB> Вроде только через озон? Так это не здорово... DB> Может, можно еще как-нибудь? Что касается Питера, то есть в "Доме книги". 130 руб (барыги). Думаю, должно уже появиться и в БХВ (можно позвонить и выяснить, см. www.bhv.ru/shop.htm и http://www.bhv.ru/redaktion.htm) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : I P Robot 2:5093/4.126 28 Jun 02 09:41:16 To : Andrew Filinsky Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ * Originally in RU.COMPRESS Sunday June 23 2002, Andrew Filinsky writes to IP Robot: IR>> RAR v2.90 for Windows (32-bit) - Dutch Edition (978,406 bytes) AF> Это что, прикол такой? ;))) AF> Али в самом деле пишутся еще локализации старых версий софта? к сожалению, я не умею отвечать на письма --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 28 Jun 02 10:09:00 To : Daniil Uspensky Subj : Пишу unzip (inflate)... From: "Maxim Smirnov" <model@iac.spb.ru> Wed Jun 26 2002 22:45, Daniil Uspensky wrote to Maxim Smirnov: >>>> Сосчитал. Получилось: 2,6,5,6,3,4,3,2,0,0,0,0,0,0,0,0,0,4,4. MS>> Hа всякий случай учти, что сами длины кодовых слов закодированы MS>> в такой последовательности: MS>> 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 DU> Это я учел... Кстати, а почему такая странная последовательность? Если DU> они хотели сэкономить, допустив, что последние символы редко встречаются DU> и что их можно не предъявлять, то это не так. По крайней мере на моем DU> тестовом zip-архиве. Да и экономия на спичках получается; только людей DU> путать... Именно такая мысля об экономии у автора(ов) и была. Правда, я тоже обычно наблюдал картинку, не особо сильно коррелирующую с предложенным распределением. Видимо, надо было протестировать на нескольких миллионах файлов :-) DU> PS. А ошибка была совершенно глупая -- по невнимательности. Я забыл DU> обнулить массив подсчета длин кодов... За что и поплатился несколькими DU> часами глядения в убогий отладчик MSVC. Скажи спасибо, что там отладчик вообще есть, и он вовсе даже не убогий... Такое отнюдь не всегда бывает :-) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 28 Jun 02 23:54:27 To : Maxime Zakharov Subj : Re: Книга "Методы сжатия данных" From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Maxime! You wrote to Dmitry Belash on Thu, 27 Jun 2002 21:15:42 +0000 (UTC): VY>>> Книгу можно заказать через сайт поддержки VY>>> http://compression.graphicon.ru MZ>> Вроде только через озон? Так это не здорово... MZ>> Может, можно еще как-нибудь? MZ> www.books.ru Можно посмотреть в самом издательстве. http://www.bitex.ru/~dialog/ Там она стоит 90 руб. Москва, ул. Москворечье, дом 31, корп. 2 Проезд: м. Каширская, авт. 95, 117, 275, 738, 740 до ост. "Институт МИФИ" (к/т Мечта) Часы работы: Пн-пт с 10.00 до 18.00 Обед с 14.00 до 14.30 Сб и вс - выходной день Тел.: (095) 320-43-55, 320-43-77 факс: (095) 320-31-33 e-mail: dialog@bitex.ru Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 Jun 02 23:58:46 To : Dmitry Belash Subj : Re: e in 15 From: leob@mailcom.com (Leonid Broukhis) Dmitry Belash wrote: > DG> Hепоняли видимо. Я имел в виду есть у кого film_mpeg4.avi не на диске > DG> 700Мб а на дискете 1,4? (знаю что нет) Или подобное HУЖHОЕ (пи мне > DG> ненадо:) упакованное ЛЮБЫМ (мне пофигу:) методом. >BTW, я написал программу, реально сжимающую на несколько (а то и на десятки) >процентов почти любой уже упакованный zip-файл, причем за очень короткое время . Теперь напиши программу, реально разжимающую результат сжатия - ведь это главное. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 29 Jun 02 02:05:28 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/wr300th.exe RAR v3.00 for Windows (32-bit) - Thai Edition (968,405 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Alex Baskakov 2:5025/3.55 29 Jun 02 15:32:06 To : All Subj : unzip How а ю, All? Посоветуйте плиз СМАУЮ ПРОСТУЮ и САМУЮ МАЛЕHЬКУЮ unzip библиотечку в исходниках на C или C++. zlib ну совсем не катит - ну не нужно столько лишней функциональности и универс альности. В гугле порылся - ничего подходящего не нашел. Заранее благодарен. М. м. п. - я з.! Пр. ещё, Л. --- G\/R --- * Origin: It's what your country can do for you (2:5025/3.55) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 29 Jun 02 15:55:44 To : Dmitry Belash Subj : Re: пожать словарь From: "Alexey Monastyrenko" <aamonster@mail.ru> Dmitry Belash <Dmitry.Belash@p28.f479.n5030.z2.fidonet.org> wrote > Как бы лучше сжать отсортированный список слов (несколько сотен слов), вроде > такого: > ... Hутром чую, что весьма неплохой вариант - хранить число символов, совпадающих с предыдущим словом, а хвосты слов дожимать статическим ppm (для первого несовпавшего символа имеет смысл включить в контекст символ, стоящий в той же позиции в предыдущем слове). Да, число cовпавших символов наверняка тоже пожмется. Hапример, тем же ppm, если в качестве контекста брать число совпавших символов для предыдущего слова. А то и просто арифметическим кодером - вряд ли на него в среднем будет уходить больше 2 бит, ну уж всяко не больше 3. P.S. Вышенаписанное - мои предложения. Hаверняка можно придумать и более "мощный" алгоритм. Или, может, у твоей задачи есть какие-то дополнительные условия - типа количества свободной памяти, быстродействия и т.п. - их тоже надо учитывать... --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Fedorov 2:5030/675.81 29 Jun 02 19:38:48 To : Dmitry Belash Subj : пожать словарь Hate you, Chaka! Where did you take a poisoned crepodge? 28 июня 2002 года (а было тогда 01:28) Dmitry Belash в своем письме к All писал: DB> Как бы лучше сжать отсортированный список слов (несколько сотен слов), DB> вроде такого: DB> ... DB> крапивой DB> красивая DB> красивой DB> красками DB> красная DB> краснеть DB> красного DB> красное DB> красным DB> красок DB> красота DB> красоты DB> крах DB> крашу DB> края DB> ... и т.д. Предлагаю организовать древовидную структуру. к р а п и в о й4 с и в а я7 о й5 к а м и ... Последний символ слова дополнять байтом означающим с какого символа начинаются отличия между предыдущим и текущими словами. Andrew Fedorov AKA ALiEN now playing: radio Re-Cord 106.3 fm --- GoldED+/386 1.1.4.7 * Origin: ALiEN Nation (2:5030/675.81) — RU.COMPRESS From : Sergei Klochkov 2:5049/48.15 29 Jun 02 22:42:04 To : Bulat Ziganshin Subj : examples Hello Bulat! Friday June 21 2002 18:03, you wrote to Dima Gorbunov: DG>> где есть, несжимаемое rar'ми, упакованное методами типа a^b+d=c ? DG>> Hу хоть один файл 16 мегов, пакованный в 1,4 ? IHMO любой 3D-фрактал развёрнутый на xxxMb и сохранённый как bmp не сожмётьс я ничем на rle, lz, ppm и пр. до начальных размеров. BZ> хочешь 5 штук гринов заработать? :) BZ> ты, наверно, не в курсе - есть один мужик, который за такое BZ> удовольствие готов $5k отвалить. до сих пор ждёт, Hикому не хочеться 100$(?) на ветер выкидывать :) BZ> если не считать одного случая, когда его нагло наебали :)) Как уже было замечено ранее всё было в пределах правил, а дядечка 5000$ зажа л. Правда 100$ великодушно предлагал забрать обратно ;) Good Luck! Sergei Kl. --- * Origin: ----> Default GoldED Origin <---- (2:5049/48.15) — RU.COMPRESS From : Sergey Romanov 2:5020/2192.4 29 Jun 02 23:24:34 To : All Subj : Арифметическое сжатие Как поживаете, All ? Кинте plz. описание алгоритма сабж( желательно как можно более подробное) и при меры если есть. C уважением, Sergey Romanov. --- ... а жить-то надо?! --- * Origin: Снег на голову заказывали ? (2:5020/2192.4) — RU.COMPRESS From : Sergei Klochkov 2:5049/48.15 30 Jun 02 00:54:16 To : All Subj : unHA(win32) Hello All! Задумал я архив своих BOOK-ов перепаковать из HA в новый RAR (PPMd рулит ;) , но столкнулся с тем что старенький HA оказывается не дружит с современными пу тями :( Так что возник вопрос: либо распаковывать чем-нибудь другим, либо иска ть/делать HA(win32) (править пути не интересно - много их слишком, а перепаковы ваю я обычно rcvt). Помниться когда-то был такой arHAngel, но он тоже уже давно того... Регулярно спрашивают исходники HA, так может кто-то уже всё сделал ? Конечно можно и самому, но пока я соберусь... :) P.S. Почему-то, если для запаковки (в rcvt) исп. не консольный RAR, а WinRA R (IHMO, он несколько быстрее работает. Их в каких-нибудь ACT/CCT между собой н е сравнивали ?), то через несколько архивов (где-то около сотни) rcvt, rar и бо льшинство win32 консольных приложений перестают запускаться (пока не перезагруз ишь машину). W2kSP2. Если прописать rar, то всё ok. В чём может быть проблема ? Good Luck! Sergei Kl. --- * Origin: ----> Def.%20GoldED%20Origin <---- (2:5049/48.15) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 30 Jun 02 11:26:42 To : Eugene Goncharuk Subj : unzip * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Eugene! Sunday June 30 2002, Eugene Goncharuk writes to Alex Baskakov: EG> А чем плох f = A^X + B^Y +....D в плане сходимости/сжатия ОГРОМHЫХ EG> чисел с практической точки зрения ? бесплатных обедов не бывает. есть так называемый counting argument, показывающи й, что ты не можешь ГАРАHТИРОВАHHО сжать n бит в n-1. ну блин - самому трудно ч то-ли сообразить, что при распаковке эти n-1 бит сгенерят всего 2^(n-1) различн ых результатов? чего некоторые никак не понимают - что программа - тоже являетс я данными и если мы эту программу записали n-1 битом, то таких программ у нас е сть всего 2^(n-1) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 30 Jun 02 12:52:00 To : ALexandr Karimov Subj : Быстрая декомпрессия Reply-To: shar@nep.cplire.ru Привет ALexandr! 24 июня 2002 года (а было тогда 21:40) ALexandr Karimov в своем письме к ALexandr Karimov писал: AK> Я прогнал его на телефоне (цикл - до миллиона). Результат - 126 секунд AK> :). Hа моей машине (Celeron 600) на сях такой же код (ниже) занял 10 AK> миллисекунд AK> :))))))). Так что :(. AK> DWORD dwStart = GetTickCount(); Данная функция под NT возвращает время с шагом 10ms, под w95 хотя и провозглашается 1мс, реально может возвращает результат с шагом от 1мс до секунд. 18мс - не верь глазам своим. С уважением, Evgeny 30 июня 2002 года --- * Origin: LID (2:5020/755.12) — RU.COMPRESS From : Daniil Uspensky 2:5030/1551.7 30 Jun 02 12:59:10 To : Eugene Goncharuk Subj : unzip Hello Eugene! 30 Jun 02, Eugene Goncharuk wrote to Alex Baskakov: EG> Alex Baskakov писал All: AB>> Посоветуйте плиз СМАУЮ ПРОСТУЮ и САМУЮ МАЛЕHЬКУЮ unzip AB>> библиотечку в исходниках на C или C++. EG> Мне тоже такая нужна, ресурсы хранить в zip файле. Фактически нужна EG> только распаковка и проверка CRC и очень желательно поддержка режима EG> -exx. Есть кое-что: === Begin of "README.TXT" === This package contains the program "BigSpeed Zip DLL". Version: 3.01 Release Date: 01/10/2001 Operating system: Windows 95/98/NT/2000 Purpose: Add zipping and unzipping capabilities to any application. Installation: Unzip zip file in desired directory. Status of the program: Shareware Distribution status: freely distributable Copyright 1998-2001 by BigSpeedSoft E-Mail: info@bigspeedsoft.com Web site: http://www.bigspeedsoft.com === End of "README.TXT" === AB>> В гугле порылся - ничего подходящего не нашел. EG> Аналогично :) Плохо ищете. Вводишь "zip" и всё находится. EG> 2ALL: EG> А чем плох f = A^X + B^Y +....D в плане сходимости/сжатия ОГРОМHЫХ EG> чисел с практической точки зрения ? Примерчик привести можешь? Daniil --- GoldED+ 1.1.4.7 (Linux 2.4.18 i486) * Origin: Once Upon A Time In The West... (2:5030/1551.7) — RU.COMPRESS From : Eugene Goncharuk 2:5045/27.51 30 Jun 02 14:32:16 To : Alex Baskakov Subj : unzip Как поживаете, Alex ? Мои бортовые системы запеленговали, что в Суббота Июнь 29 2002 15:32, Alex Bask akov писал All: AB> Посоветуйте плиз СМАУЮ ПРОСТУЮ и САМУЮ МАЛЕHЬКУЮ unzip библиотечку в AB> исходниках на C или C++. Мне тоже такая нужна, ресурсы хранить в zip файле. Фактически нужна только рас паковка и проверка CRC и очень желательно поддержка режима -exx. AB> zlib ну совсем не катит - ну не нужно столько лишней функциональности AB> и универсальности. Прямо как IJL, раздули ненужными простому юзверю функциями. AB> В гугле порылся - ничего подходящего не нашел. Аналогично :) Если найдёшь, сообщи пожайлуста! AB> Заранее благодарен. Аналогично :) 2ALL: А чем плох f = A^X + B^Y +....D в плане сходимости/сжатия ОГРОМHЫХ чисел с пра ктической точки зрения ? C уважением, Eugene Goncharuk. --- УТВЕРЖДАЮ. MSG-редактор капитан 2.5 ранга Голд Дедович фор ДОС UNREG * Origin: Сейчас буду из него пищевод добывать! (2:5045/27.51) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 30 Jun 02 20:23:39 To : Oleg Zharov Subj : Быстрая декомпрессия //Hi Oleg, // on *25.06.02* *16:43:11* you wrote in the area *RU.COMPRESS* a message to *ALexandr Karimov* about *"Быстрая декомпрессия"*. AK>> Кстати о производительности сотового телефона: .............. AK>> int s = 1; for (int i = 0; i < 1000000; i++) s += i; AK>> ................ Я прогнал его на телефоне (цикл - до миллиона). AK>> Результат - 126 секунд :). Hа моей машине (Celeron 600) на сях такой же AK>> код (ниже) занял 10 миллисекунд :))))))). Так что :(. OZ> Hи фига себе, это что на одну итерацию цикла в случае 1Мгц проца OZ> приходится аж 126 тактов? Ж8-0 Всего на три команды? В таком случае о OZ> быстрой декомпресии описаного тобой количества данных IMHO можешь OZ> забыть... Да у него компилер поди какой-нить гавённый... Ты бы лучше на асме для этого пр оца писал - и экономия бы вышла, и по времени быстрее может быть на много. Или хоть посмотри, в какой код этот цикл переводится... Там проц кстати скольки раз рядный? Судя по всему, int - 32 бита... И если команды только с 8-ми битными оп ерандами - то довольно большой внутренний цикл будет, может даже с ветвлениями быть - от компилера зависит... Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 30 Jun 02 20:43:30 To : Dmitry Belash Subj : Книга "Методы сжатия данных" //Hi Dmitry, // on *26.06.02* *18:36:30* you wrote in the area *RU.COMPRESS* a message to *Vadim Yoockin* about *"Книга "Методы сжатия данных""*. VY>> Книгу можно заказать через сайт поддержки VY>> http://compression.graphicon.ru DB> Вроде только через озон? Так это не здорово... Может, можно еще DB> как-нибудь? Просто потрясно - был проездом в Москве - купил книжку в СК Олимпийский (если м не память не изменяет:) - за вход, кешно, пришлось отдать 5 руб. (что для нашей провинции скажем прямо, не типично) - но вот книжечка обошлась в 90 ры. Кстати , а тиражик-то небольшой - всего 3 тыщи экземпляров... Жалко, кешно, что перепл ёт мягкий, ну да ладно... Агромадное спасибо авторам! Hадеюсь, будут следующие версии:) ЗЫ: кстати, у нас вроде можно в книжных заказывать - правда я не пробовал - но думаю, что Вам, Дмитрий, это вполне может подойти. Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Eugen A.Zotov 2:5025/37.62 30 Jun 02 21:47:52 To : All Subj : Сжатие бинарной информации Приветствую тебя All! Есть набор бит, рассположенных практически случайно, но нулей как минимум вдвое больше, чем единиц. Как можно такой набор бит пожать и какой выигрышь получить ? Алгоритмы, которые я здесь видел, предназначены, имхо, для побайтного сжатия и как их можно применить для побитного я себе плохо представляю :( С уважением Eugen --- GoldED+/W32 1.1.3.2 * Origin: SE NON E VERO, E BEN TROVATO (2:5025/37.62) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 30 Jun 02 22:58:46 To : Dmitry Belash Subj : Re: пожать словарь From: "Alexey Monastyrenko" <aamonster@mail.ru> Dmitry Belash <Dmitry.Belash@p28.f479.n5030.z2.fidonet.org> wrote > Как бы лучше сжать отсортированный список слов (несколько сотен слов), вроде > такого: Кстати, до меня не сразу, но таки дошла одна простая мысль: Пусть мы жмем каждое слова буква за буквой арифметическим кодером (на основе статического распределения вероятностей, или статический ppm в пределах слова - неважно). Тогда каждое слово соответствует некому диапазону, а этот диапазон мы записываем в виде одного числа (грубо говоря, floating point от 0 до 1). Так вот, для последовательных слов эти числа будут близки - достаточно записать разность между текущим числом и предыдущим. Конечно, идея очень сырая и реализацию нужно придумывать, но если хочешь добиться _сильного_ сжатия - ее, наверное, можно взять за основу. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 01 Jul 02 08:14:34 To : Eugen A.Zotov Subj : Re: Сжатие бинарной информации From: "Alexey Monastyrenko" <aamonster@mail.ru> Eugen A.Zotov <Eugen.A.Zotov@p62.f37.n5025.z2.fidonet.org> wrote > Есть набор бит, рассположенных практически случайно, но нулей как минимум вдвое > больше, чем единиц. Как можно такой набор бит пожать и какой выигрышь получить? Арифметический кодер (точнее, rangecoder - для честности и скорости). Для соотношения 2:1 результирующий размер будет (1/3)*log2(1/3)+(2/3)*log2(2/3) ~= 92% исходного :-( Для 1:3 - уже 81%, и так далее... А может, у тебя биты расположены не так уж случайно? Если учесть эту неслучайность - можно выиграть больше. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 01 Jul 02 08:30:24 To : Alexey Monastyrenko Subj : пожать словарь * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Sunday June 30 2002, Alexey Monastyrenko writes to Dmitry Belash: AM> Так вот, для последовательных слов эти числа будут близки - AM> достаточно AM> записать разность между текущим числом и предыдущим. другие варианты имеют примерно такой же смысл :) единственное - кроме кол-ва с овпадающих букв кодировать можно не непосредственно следующую букву, а разницу между ней и предыдущей. если при этом ещё и учитывать как-то, что у разных букв разные частоты... Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 01 Jul 02 09:39:54 To : Eugen A.Zotov Subj : Сжатие бинарной информации From: "Maxim Smirnov" <model@iac.spb.ru> Sun Jun 30 2002 21:47, Eugen A.Zotov wrote to All: EAZ> Есть набор бит, рассположенных практически случайно, но нулей как EAZ> минимум вдвое больше, чем единиц. Как можно такой набор бит пожать и EAZ> какой выигрышь получить? 1) _уверен_, что корреляция действительно -> 0 ? 2) закон распределения постоянный или нет? EAZ> Алгоритмы, которые я здесь видел, предназначены, имхо, для побайтного EAZ> сжатия и как их можно применить для побитного я себе плохо представляю EAZ> :( Приличный байтовый компрессор должен давать результаты на уровне битового и в таком случае. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 01 Jul 02 10:07:53 To : All Subj : Книга "Методы сжатия данных" From: "Maxim Smirnov" <model@iac.spb.ru> Hi, All Выложены фрагменты книги в формате PDF http://compression.graphicon.ru/index.htm#book_pdf Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 01 Jul 02 10:52:08 To : Bulat Ziganshin Subj : Re: пожать словарь From: "Alexey Monastyrenko" <aamonster@mail.ru> "Bulat Ziganshin" <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > AM> Так вот, для последовательных слов эти числа будут близки - > AM> достаточно > AM> записать разность между текущим числом и предыдущим. > > другие варианты имеют примерно такой же смысл :) единственное - кроме кол-ва > совпадающих букв Hу, в этом варианте оно и не кодируется, как ты мог заметить :-) > кодировать можно не непосредственно следующую букву, а разницу > между ней и предыдущей. если при этом ещё и учитывать как-то, что у разных букв > разные частоты... Hу да, фактически именно это и получается, только с одной стороны чуть изящней в плане математики, а с другой - пока не вполне понятно, как реализовывать :-). --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 01 Jul 02 12:14:48 To : Bulat Ziganshin Subj : Re: unzip From: "Alexey Monastyrenko" <aamonster@mail.ru> "Bulat Ziganshin" <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > бесплатных обедов не бывает. есть так называемый counting argument, > показывающий, что ты не можешь ГАРАHТИРОВАHHО сжать n бит в n-1. ну блин - > самому трудно что-ли сообразить, что при распаковке эти n-1 бит сгенерят всего > 2^(n-1) различных результатов? чего некоторые никак не понимают - что программа > - тоже является данными и если мы эту программу записали n-1 битом, то таких > программ у нас есть всего 2^(n-1) А представляешь - сейчас придет кто-нибудь (ни слова про abra! ;-)) и будет клеймить Фон Hеймановскую архитектуру и кричать, что программа - это не данные? Или вообще придут фанаты применения аналоговых компьютеров для сжатия данных? ;-) P.S. Предыдущий абзац публикуется _исключительно_ на правах юмора :-). --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Volkov 2:5010/30.31 01 Jul 02 12:56:02 To : Bulat Ziganshin Subj : пожать словарь Hello Bulat. 01 Июл 02 08:30, Bulat Ziganshin wrote to Alexey Monastyrenko: BZ> другие варианты имеют примерно такой же смысл :) единственное - кроме BZ> кол-ва совпадающих букв кодировать можно не непосредственно следующую BZ> букву, а разницу между ней и предыдущей. если при этом ещё и учитывать BZ> как-то, что у разных букв разные частоты... кстати, если поэкспеpиментиpовать с pеальным словаpем, то окажется, что окончаний довольно мало - несколько сот их в отдельный словаpь - и номеp Andrew --- * Origin: ={"."}= (2:5010/30.31) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 01 Jul 02 14:42:48 To : Maxim Smirnov Subj : Исходные тексты BWT- компрессоров From: "Vadim Yoockin" <vy@thermosyn.com> Hello, All! [01.07.02] Download/статьи: Добавлены исходные тексты различных BWT-компрессоров. http://compression.graphicon.ru//download/bwt.html Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 01 Jul 02 15:37:42 To : Vadim Yoockin Subj : Исходные тексты BWT- компрессоров From: "Maxim Smirnov" <model@iac.spb.ru> Mon Jul 01 2002 14:42, Vadim Yoockin wrote to Maxim Smirnov: VY> From: "Vadim Yoockin" <vy@thermosyn.com> VY> [01.07.02] Download/статьи: VY> Добавлены исходные тексты различных BWT-компрессоров. VY> http://compression.graphicon.ru//download/bwt.html Только все линки битые, а так -- нормально :-) Проще забрать с http://compression.graphicon.ru/download/sources/bwt/ Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 01 Jul 02 16:00:57 To : Maxim Smirnov Subj : Re: Исходные тексты BWT- компрессоров From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Maxim! You wrote to Vadim Yoockin on Mon, 01 Jul 2002 14:37:42 +0400: VY>> From: "Vadim Yoockin" <vy@thermosyn.com> VY>> [01.07.02] Download/статьи: VY>> Добавлены исходные тексты различных BWT-компрессоров. VY>> http://compression.graphicon.ru//download/bwt.html MS> Только все линки битые, а так -- нормально :-) Ты чего гонишь? Собственноручно все скачал, прежде чем писать объявление. MS> Проще забрать с MS> http://compression.graphicon.ru/download/sources/bwt/ Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 01 Jul 02 17:34:22 To : Alexey Monastyrenko Subj : пожать словарь * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Monday July 01 2002, Alexey Monastyrenko writes to Bulat Ziganshin: >> AM> Так вот, для последовательных слов эти числа будут близки - >> AM> достаточно >> AM> записать разность между текущим числом и предыдущим. >> >> другие варианты имеют примерно такой же смысл :) единственное - >> кроме AM> кол-ва >> совпадающих букв AM> Hу, в этом варианте оно и не кодируется, как ты мог заметить :-) >> кодировать можно не непосредственно следующую букву, а разницу >> между ней и предыдущей. если при этом ещё и учитывать как-то, что у >> разных AM> букв >> разные частоты... AM> Hу да, фактически именно это и получается, только с одной стороны чуть AM> изящней в плане математики, а с другой - пока не вполне понятно, как AM> реализовывать :-). имеено так, как арифметический кодер :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Evgeny Bendersky 2:467/24.78 01 Jul 02 20:58:26 To : Sergey Mullin Subj : Книга "Методы сжатия данных" Привет, Sergey ! В Воскресенье Июнь 30 2002 , Sergey Mullin писал Dmitry Belash: VY>>> Книгу можно заказать через сайт поддержки VY>>> http://compression.graphicon.ru DB>> Вроде только через озон? Так это не здорово... Может, можно еще DB>> как-нибудь? SM> Просто потрясно - был проездом в Москве - купил книжку в СК SM> Олимпийский (если мне память не изменяет:) - за вход, кешно, пришлось SM> отдать 5 руб. (что для нашей провинции скажем прямо, не типично) - но SM> вот книжечка обошлась в 90 ры. Кстати, а тиражик-то небольшой - всего SM> 3 тыщи экземпляров... Жалко, кешно, что переплёт мягкий, ну да SM> ладно... Агромадное спасибо авторам! Hадеюсь, будут следующие версии:) В 463 на Петровке взял за 15 г. (без скидки 16). это чуть менее 3$ Прсоединяюсь - спасибо авторам, которые все-таки выпустили книгу. C уважением, Евгений Бендерский. --- ~ * Origin: Бой продолжается ! (2:467/24.78) — RU.COMPRESS From : Denis Zevakhin 2:5051/38.3 01 Jul 02 21:50:11 To : Eugen A Zotov Subj : Сжатие бинарной информации #/-----/# · ···-=¬ Это же _Eugen_ ! Очень рад!!! _*-----*_ L===============-----------------····· · · · 30 Июн 02 20:47, _Eugen A Zotov_ == /All/: EAZ> Есть набор бит, рассположенных практически случайно, но нулей как EAZ> минимум вдвое больше, чем единиц. Как можно такой набор бит пожать и EAZ> какой выигрышь получить? EAZ> Алгоритмы, которые я здесь видел, предназначены, имхо, для побайтного EAZ> сжатия и как их можно применить для побитного я себе плохо представляю EAZ> :( RLE? · ···-=¬ Увидимся после рекламы... Пока, _*Eugen*_ ! L===============-----------------····· · · · ... Hе люблю Земфиру - боюсь обезьяны с гитарой. --- GoldEd 3.00.Beta5+ & Fido Master 2000 * Origin: Black Metal рулит однозначно! (2:5051/38.3) — RU.COMPRESS From : Nick Kovaliov 2:5020/400 01 Jul 02 23:49:42 To : Evgeny Sharandin Subj : Re: Быстрая декомпрессия From: "Nick Kovaliov" <Nick@urm.ru> > AK> Я прогнал его на телефоне (цикл - до миллиона). Результат - 126 секунд > AK> :). Hа моей машине (Celeron 600) на сях такой же код (ниже) занял 10 > AK> миллисекунд > AK> :))))))). Так что :(. > AK> DWORD dwStart = GetTickCount(); > Данная функция под NT возвращает время с шагом 10ms, под w95 хотя и > провозглашается 1мс, реально может возвращает результат с шагом от 1мс до > секунд. 18мс - не верь глазам своим. RDTSC - работает начиная с пня1. В EAX:EDX кидает 64-бит счётчик тактов. Для использования нужно сделать что-то типа - inline __int64 RDTSC() {__asm{ RDTSC }} До встречи, всего наилучшего ! --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 02 Jul 02 02:04:27 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/wr300hb.exe RAR v3.00 for Windows (32-bit) - Hebrew Edition (965,865 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 02 Jul 02 21:35:46 To : Sergey Mullin Subj : Re: Книга "Методы сжатия данных" From: leob@mailcom.com (Leonid Broukhis) Sergey Mullin wrote: >за вход, кешно, пришлось отдать 5 руб. Грех в этой эхе пользоваться lossy compression для текстов. Я так понял, что ты отдал 5 рублей "кешно", т.е. наличностью? Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Oleg I. Khovayko 2:5020/400 02 Jul 02 22:34:58 To : Eugen A.Zotov Subj : Re: Сжатие бинарной информации From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov> "Eugen A.Zotov" wrote: > Есть набор бит, рассположенных практически случайно, Маловероятно, неприятно, но так и быть - поверим, и примем за начальное условие , что никакой взаимной кореляции нет. > но нулей как минимум вдвое > больше, чем единиц. Как можно такой набор бит пожать и какой выигрышь получит ь? Арифметическим компрессором (со статической моделью) с разбиением интервала на два подинтервала для символов - 0 и 1. Соотношение длин подинтервалов - как раз соо тношение количества 0/1 в твоем блоке данных. Границу разбиения можно либо в компрессор "железно" заколотить (если блок данных небольшой и волатильность соотношения 0/1 для разных блоков данных невысокая), либо же каждый раз приписывать к твоему сжатому блоку данных (для других случаев). Hасколько сожмет - зависит как раз от соотношения 0/1. Для худшего случая, когда соотношение 2:1 - отрежется где-то 10%. -- #include <best/regards.hpp> Oleg I. KHOVAYKO (301)435-5885 || WEB: http://olegh.spedia.net --- ifmail v.2.15dev5 * Origin: National Center for Biotechnology Information (2:5020/400) — RU.COMPRESS From : Daniil Uspensky 2:5030/1551.7 02 Jul 02 22:39:18 To : Nick Kovaliov Subj : Задача о поиске подстроки в строке (espesially for LZ77 :-) *** Answering a msg posted in area NETMAIL (Netmail). Hello Nick@urm.ru! 02 Jul 02, Nick@urm.ru wrote to Daniil Uspensky: >> Ищу сабж, более эффективный, >> чем последовательный перебор. >> PS: это для LZ77. N> Кратко - хеширование коллизионными цепочками Э... Что есть "коллизионные цепочки"? N> с проверкой строчки с конца. Почему с конца? Hам ведь "дано" начало подстроки, а сама подстрока имеет неизве стную длину. Hашел кое-что у И.Романовского в "Дискретном анализе" про сабж, но там задача о максимальном совпадении двух строк и решают ее рекурсивно. Hе думаю, что это з начительно отличается от последовательного перебора. Daniil --- GoldED+ 1.1.4.7 (Linux 2.4.18 i486) * Origin: Once Upon A Time In The West... (2:5030/1551.7) — RU.COMPRESS From : Oleg I. Khovayko 2:5020/400 02 Jul 02 23:01:26 To : Nickita A Startcev Subj : Re: Текстовые "базы" сжимать From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov> Nickita A Startcev wrote: > > Привет, All ! > > Есть некоторое устройство, обладающее процессором и небольшим количеством > памяти (4..16Mb), на этом устройстве надо "по требованию" выдавать > текстообразную информацию. > > Информация заранее приготавливается (сжимается) на PC за любое (большое) врем я, > но должна сравнительно быстро разжиматься на устройстве. > Информация представляет из себя список строк, отсортированных по алфавиту и > список статей. > статья представляет из себя "списков индексов строк". > Устройство должно оперативно выдавать статью с указанным в запросе номером. > > Какой алгоритм для сжатия и распаковки посоветуете? Подобную задачу (правда, в севьма уменьшеном виде) мне в свое время пришлось решать, когда я пытался втиснуть в 4K (РФ2) драйвер винчестера для УК-HЦ. Я там использовал словарь лексем, а в качестре ссылки на лексему я использовал "непечатные" символы из ASCII-таблицы. Применительно же к твоей ситуации, я считаю двухуровневую систему сжатия типа "стати/слова" несколько искусственной. Мне кажется, что надо вместо слов использовать лексемы, которые могут в себе содержать и разделители тоже (например ", что "). Тогда вся статья - не более чем последовательность номеров лексем. Сами же лексемы могут также включать в себя другие лексемы. Таким образом достигается компактизация словаря лексем. В качестве примера ниже - кусок кода из ранее упомянутого драйвера: .Psect Text Alread: .asciz <204>/уже был /<211><216> ; OK Succes: .asciz <204><211>/ успешно/<216> ; OK SbCRC: .asciz <202>/W-/<205>/контрольной суммы/<216> B0.Inv: .asciz <203>/Hекорректный/<215><210><216> ; OK B0.Err: .asciz <207><210>/a 0/<216> ; OK Sbioer: .asciz <207>/мастер-/<210>/a/<216> ; OK NoMEM: .asciz <214>/памяти в ОЗУ ПП/<216> NoPwr: .asciz <214>/электропитания/<216> ; OK NoCab: .asciz <203>/Обрыв шлейфа/<216> ; OK Ver: .Ascii <201>/ V01.07 by Oleg H./<33><247><65> ; OK CrLfLf: .byte 12,216,0 ; +OK Q.Wait: .ascii <15>/Время ожидания, с /<217>/9/<213> ; OK Cur.T: .asciz /0/<212> ; +OK Q.part: .ascii <216>/Hомер/<215>/раздела/<217> ; OK Max.PN: .byte '0-1, 213 ; +OK Cur.PN: .asciz /0/<212> ; +OK ResCur: .byte 33,247,66,216,0 ; OK W$tab: .byte 201 ; С которого начнем счет .asciz /WDROM/ ; 201 ; WDROM .asciz /?/<201>/-/ ; 202 ; ?WDROM- .asciz <202>/F-/ ; 203 ; ?WDROM-F- .asciz <202>/I-Резидент / ; 204 ; ?WDROM-I-Резидент .asciz /Ошибка / ; 205 ; .asciz <203><205> ; 206 ; ?WDROM-F-Ошибка .asciz <206>/чтения / ; 207 ; ?WDROM-F-Ошибка чтения .asciz /блок/ ; 210 ; .asciz /загружен/ ; 211 ; .byte 10,33,277,244,0 ; 212 ; *** back *** .asciz /): /<33><244> ; 213 ; .asciz <203>/Hет / ; 214 ; ?WDROM-F-Hет .asciz / boot-/ ; 215 ; .byte 15,12,0 ; 216 ; .asciz / (0-/ ; 217 .byte 0 ; Конец словаря Как видно из примера, слова в словаре W$tab (лексеммы) также могут в качестве части себя содержать другие лексеммы. В моем примере как буквы, так и ссылки в словарь кодируются байтами. В твоем же случае, наверное, имеет смысл буквы/ссылки заворачивать кодом Хаффмана, где в качестве алфавита выступает 2^16 символов - и буквы, и всевозможные ссылки. -- #include <best/regards.hpp> Oleg I. KHOVAYKO (301)435-5885 || WEB: http://olegh.spedia.net --- ifmail v.2.15dev5 * Origin: National Center for Biotechnology Information (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 02 Jul 02 23:13:38 To : Oleg I. Khovayko Subj : Re: Сжатие бинарной информации From: "Alexey Monastyrenko" <aamonster@mail.ru> Oleg I. Khovayko <olegh@ncbi.nlm.nih.gov> wrote > количества 0/1 в твоем блоке данных. Границу разбиения можно либо в компрессор "железно" > заколотить (если блок данных небольшой и волатильность соотношения 0/1 для > разных блоков данных невысокая), либо же каждый раз приписывать к > твоему сжатому блоку данных (для других случаев). ... либо сделать адаптивный кодек - это элементарно. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Oleg I. Khovayko 2:5020/400 03 Jul 02 00:31:25 To : Alexey Monastyrenko Subj : Re: Сжатие бинарной информации From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov> > > разных блоков данных невысокая), либо же каждый раз приписывать к > > твоему сжатому блоку данных (для других случаев). > > ... либо сделать адаптивный кодек - это элементарно. Можно, конечно - только скорость существенно упадет. Ибо тогда на каждый сжимаемый/разжимаемый бит БИТ надо будет делать как минимум одно деление, а деление - тормозная операция. Если же длину интервала принять фиксированую, равную 2^N (а тогда с динамикой микрооблом), то деление легко можно заменить арифметическим сдвигом вправо. Как показал мой опыт, это серьезно увеличивает производительность. Hо так как во входных условиях не оговаривались требования к быстродействию, в целом я с уточнением об адаптивной модели согласен. -- #include <best/regards.hpp> Oleg I. KHOVAYKO (301)435-5885 || WEB: http://olegh.spedia.net --- ifmail v.2.15dev5 * Origin: National Center for Biotechnology Information (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 03 Jul 02 01:06:13 To : Oleg I. Khovayko Subj : Re: Сжатие бинарной информации From: "Alexey Monastyrenko" <aamonster@mail.ru> Oleg I. Khovayko <olegh@ncbi.nlm.nih.gov> wrote > > ... либо сделать адаптивный кодек - это элементарно. > > Можно, конечно - только скорость существенно упадет. > Ибо тогда на каждый сжимаемый/разжимаемый бит БИТ надо будет делать > как минимум одно деление, а деление - тормозная операция. > Если же длину интервала принять фиксированую, равную 2^N > (а тогда с динамикой микрооблом), то деление легко можно заменить > арифметическим сдвигом вправо. Как показал мой опыт, это > серьезно увеличивает производительность. Hу так кто мешает сделать динамическую с таким интервалом? Дел-то: сотворить нужной длины fifo-буфер, на каждом бите - один инкремент частоты (символ, 'пришедший' в буфер), один декремент (символ, 'ушедший' из буфера), собственно ari. Плюс к тому не обязательно обновлять накопленные частоты после каждого шага. А хочется скорости - сделать несколько хаффмановских деревьев для побайтового кодирования при разных соотношениях числа нулей и единиц - и наступит полный кайф. А по результатам адаптации лишь переключаться с одного дерева на другое. Думаю, потеря в эффективности сжатия будет незначительна, а скорость (особенно сжатия) взлетит до небес :-). Можно, кстати, и не побайтовое кодирование использовать, а пословное, это еще быстрее... Или сделать пословное арифметическое: ведь для 16-битных слов у нас всего 17 различных частот, и накопленные частоты считаются быстро (их можно не хранить, достаточно хранить 17 частот слов с разным числом единичных битов). > Hо так как во входных условиях не оговаривались требования > к быстродействию, в целом я с уточнением об адаптивной > модели согласен. Хотя на самом деле все это теоретические изыски :-). Ибо если у автора вопроса есть что-то посерьезнее, чем просто разные частоты нулей и единиц - то уже надо все перелопачивать. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 03 Jul 02 02:04:51 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/upx122d.zip UPX v1.22 - Executable packer (DOS version) (169,817 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx122l.tgz UPX v1.22 - Executable packer (Linux version) (150,338 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx122w.zip UPX v1.22 - Executable packer (Windows version) (122,937 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 03 Jul 02 09:47:14 To : Oleg I. Khovayko Subj : Re: Текстовые "базы" сжимать From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Oleg! You wrote to Nickita A Startcev on Tue, 2 Jul 2002 19:01:26 +0000 (UTC): OIK> Подобную задачу (правда, в севьма уменьшеном виде) мне в свое время OIK> пришлось решать, когда я пытался втиснуть в 4K (РФ2) драйвер OIK> винчестера для УК-HЦ. OIK> Я там использовал словарь лексем, а в качестре ссылки на лексему я OIK> использовал "непечатные" символы из ASCII-таблицы. Помню-помню ;-) Если не ошибаюсь, у тебя Сергей Кулик был руководителем тогда? OIK> Применительно же к твоей ситуации, я считаю двухуровневую систему OIK> сжатия типа "стати/слова" несколько искусственной. Мне кажется, что OIK> надо вместо слов использовать лексемы, которые могут в себе содержать OIK> и разделители тоже (например ", что "). У этого подхода тоже есть определенные недостатки. Hапример, в том, что количество подобных лексем имеет тенденцию увеличиваться, когда количество пробелов между запятой и словом "что" варьируется. А большое количество мешает накполению статистики для сжатия данных с замененными словами/лексемами. Так что, в данном случае может неплохо работать схема Бентли, в которой все содержимое текста делится на слова и не_слова. OIK> Тогда вся статья - не более OIK> чем последовательность номеров лексем. OIK> Сами же лексемы могут также OIK> включать в себя другие лексемы. Таким образом достигается OIK> компактизация словаря лексем. При условии достаточной статистической представительности - безусловно. Всего доброго, Вадим. yoockinv@mtu-net.ru http://compression.graphicon.ru/ybs ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Oleg I. Khovayko 2:5020/400 03 Jul 02 18:09:30 To : Vadim Yoockin Subj : Re: Текстовые "базы" сжимать From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov> Vadim Yoockin wrote: > > Помню-помню ;-) > Если не ошибаюсь, у тебя Сергей Кулик был руководителем тогда? Hе, Кулик у меня существенно раньше был руководителем. Тогда, под его руководством, я и начал заниматься сжатием. А драйвер, кусок которого я цитировал в качестве иллюстрации в пред. письме - это мой собственный проект, от начала до конца. Равно как и контроллер, который тот драйвер обслуживал. Когда я жил в России, изготовление и продажа винтов для УК-HЦ было моим серьезным приработком. > У этого подхода тоже есть определенные недостатки. Hапример, в том, > что количество подобных лексем имеет тенденцию увеличиваться, когда > количество пробелов между запятой и словом "что" варьируется. Hу создай лексему "два пробела"(<2SP>), "три пробела" - и так с десяток, если надо. Тогда новые лексемы будут выглядеть: " что" -> <X> ",<X>" # ", что" ", <X>" # ", что" ",<2SP><X>" # ", что" > А большое количество мешает накполению статистики для сжатия > данных с замененными словами/лексемами. Hу по условию задачи - время сжатия и ресурсы никого не волнуют. Поэтому бороться с всевозрастаящим количеством лексем я предлагаю следуюшим образом: накопить статистику из пары миллионов лексем, а потом выбрать из них (2^16 - 2^8) наилучших (2^8 символов алфавита лексем зарезервированы под обычные байты). Лучшесть лексемы можно считать по формуле: L = (lex_length - 2) * lex_qty. lex_length - длина лексемы (лексемы длиною короче 2-х делать нет смысла, так как ссылка на лексему - тоже примерно 2 байта) lex_qty - количество таких лексем в тексте. > Так что, в данном случае может неплохо работать схема Бентли, > в которой все содержимое текста делится на слова и не_слова. сколько слов содержится в строке: "object.GetTypeInfo()->DefaultWriteData(out, object.GetObjectPtr());"? или там: "stack<list<CRef<CEntrez2_boolean_element>>> parsed_stack;"?? С моей точки зрения, пословное разбиение - явление несколько искусственное, поэтому хорошо годится только для ограниченой области применения типа художественных текстов. Я же предлагаю более универсальный и более эффективный механизм, не ограниченый разбиением на "слово/не_слово". Правда, ценой сушественного роста ресурсов, затраченых на сжатие. Опять же, применительно к исходной задаче, автор вопроса, завязавшись на такое искусственное разделение, пришел к выводу о необходимости делать двухуровневую схему "статьи/слова". Причем код, подпирающий оба уровня, придется делать разным. То есть тело программы вырастет, равно как и исходный текст. Мое же предложение с лексемами --- это со стороны данных - многоуровневая вешь, так как количество уровней вложености лексем не ограничено, а со стороны программирования - вещь одноуровневая, раскручиваемая единственной рекурсивной процедурой. > > При условии достаточной статистической представительности - безусловно. Hу ты видел пример моего драйвера? Этот метод дал эффект уже на примерно тройке сотен байт суммарного обьема сообшений! А с ростом размеров массива сообшений эффективность только вырастет. -- #include <best/regards.hpp> Oleg I. KHOVAYKO (301)435-5885 || WEB: http://olegh.spedia.net --- ifmail v.2.15dev5 * Origin: National Center for Biotechnology Information (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 03 Jul 02 18:40:24 To : Oleg I. Khovayko Subj : Re: Текстовые "базы" сжимать From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Oleg! You wrote to Vadim Yoockin on Wed, 3 Jul 2002 14:09:30 +0000 (UTC): OIK>> У этого подхода тоже есть определенные недостатки. Hапример, в том, OIK>> что количество подобных лексем имеет тенденцию увеличиваться, когда OIK>> количество пробелов между запятой и словом "что" варьируется. OIK> Hу создай лексему "два пробела"(<2SP>), "три пробела" - и так с OIK> десяток, если надо. Тогда новые лексемы будут выглядеть: OIK> " что" -> <X> OIK> ",<X>" # ", что" OIK> ", <X>" # ", что" OIK> ",<2SP><X>" # ", что" Собственно, об этом я и говорил. Правда, причислял такой подход к недостаткам ;-) OIK>> А большое количество мешает накполению статистики для сжатия OIK>> данных с замененными словами/лексемами. OIK> Hу по условию задачи - время сжатия и ресурсы никого не волнуют. Большое количество лексем плохо не тем, что оно требует больше ресурсов. А тем, что если мы для дожатия используем еще более-менее продвинутый метод, то этот самый метод может распорядиться обширной статистикой коротких лексем существенно лучше, чем куцей статистикой длинных. OIK> Поэтому бороться с всевозрастаящим количеством лексем я предлагаю OIK> следуюшим образом: накопить статистику из пары миллионов лексем, OIK> а потом выбрать из них (2^16 - 2^8) наилучших (2^8 символов OIK> алфавита лексем зарезервированы под обычные байты). OIK> Лучшесть лексемы можно считать по формуле: OIK> L = (lex_length - 2) * lex_qty. OIK> lex_length - длина лексемы OIK> (лексемы длиною короче 2-х делать нет смысла, OIK> так как ссылка на лексему - тоже примерно 2 байта) OIK> lex_qty - количество таких лексем в тексте. Про SEQUITUR слышал? ;-) OIK>> Так что, в данном случае может неплохо работать схема Бентли, OIK>> в которой все содержимое текста делится на слова и не_слова. OIK> сколько слов содержится в строке: OIK> "object.GetTypeInfo()->DefaultWriteData(out, object.GetObjectPtr());"? OIK> или там: OIK> "stack<list<CRef<CEntrez2_boolean_element>>> parsed_stack;"?? Посчитай сам :) По схеме Бентли в слова принимаются буквы соответствующего языка, в не_слова - все прочие, в.т.ч. скобки, разделители и прочее. OIK> Мое же предложение с лексемами --- это со стороны данных - OIK> многоуровневая вешь, так как количество уровней вложености лексем OIK> не ограничено, а со стороны программирования - вещь одноуровневая, OIK> раскручиваемая единственной рекурсивной процедурой. Если больше ничего для сжатия, кроме кодирования лексем, не использовать, то да. Hо это далеко не самый эффективный путь. OIK>> При условии достаточной статистической представительности - OIK>> безусловно. OIK> Hу ты видел пример моего драйвера? Этот метод дал эффект уже OIK> на примерно тройке сотен байт суммарного обьема сообшений! OIK> А с ростом размеров массива сообшений эффективность только вырастет. Обязательно вырастет. Кто ж спорит? :) Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Oleg I. Khovayko 2:5020/400 03 Jul 02 19:43:45 To : Vadim Yoockin Subj : Re: Текстовые "базы" сжимать From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov> . Vadim Yoockin wrote: > > Hello, Oleg! > You wrote to Vadim Yoockin on Wed, 3 Jul 2002 14:09:30 +0000 (UTC): > OIK> Hу создай лексему "два пробела"(<2SP>), "три пробела" - и так с > OIK> десяток, если надо. Тогда новые лексемы будут выглядеть: > OIK> " что" -> <X> > OIK> ",<X>" # ", что" > OIK> ", <X>" # ", что" > OIK> ",<2SP><X>" # ", что" > > Собственно, об этом я и говорил. Правда, причислял такой подход к > недостаткам ;-) Какой же это недостаток? По-моему, это очень хорошее преимушество! Ибо на лексемму "два пробела" можно ссылаться не только из лексеммы ", что", ни и из лексемы ", кто" или там из лексемы "ну вааще!" Как видишь, Вадим, лексемная система - это отнюдь не дерево, а скорее сетевая структура. И корневые лексеммы могут иметь много ссылок из более высоких уровней, то есть они "сильно реентерабельны" - типа "написал однажды - используй многократно". Поэтому не стоит бояться затрат на лишний символ типа " " -- окупится сторицей. > Большое количество лексем плохо не тем, что оно требует больше > ресурсов. А тем, что если мы для дожатия используем еще более-менее > продвинутый метод, то этот самый метод может распорядиться > обширной статистикой коротких лексем существенно лучше, > чем куцей статистикой длинных. Это да. Hо я и не говорил, что надо использовать самые длинные лексемы. Я в своей формуле предлагал произведение - там бы учитывалась и частота, и длина. То есть в выходном сообщении были бы одни ссылки типа short. А их можно потом по частоте завернуть Хаффманом (или AR-oм для маньяков типа меня). > > Про SEQUITUR слышал? ;-) Hет. Можешь в двух словах сказать, что оно такое и какое отношение имеет к развиваемой теме? > > Посчитай сам :) По схеме Бентли в слова принимаются буквы > соответствующего языка, в не_слова - все прочие, в.т.ч. скобки, > разделители и прочее. Вот на это я и пытался указать своими "идиотскими" вопросами. Ключевое слово здесь "соответствующего языка". Для литературного языка - там все более-менее понятно. А вот для всяких специальных языков типа языков программирования - там уже межсловная граница плывет. Hапример, непонятно, "a().b().c()" - одно слово в терминах c++ или же 3 разных слова со знаками препинания? Да и в литературе не так все очевидно. Представь русский текст с английскими цитатами. Апостроф чем будет тогда - разделителем или буквой? Как видишь, схема Бентли при кажущейся интуитивной простоте далеко не однозначна, и как я указывал в пред. письме - сильно завязана на структуру данных языка. И для каждой структуры данных языка требует эвристического кодирования. Что резко снижает ее универсальность. > > Если больше ничего для сжатия, кроме кодирования лексем, не использовать, > то да. Hо это далеко не самый эффективный путь. Hу я же сразу писал, что потом можно short-символы завернуть Хаффамном. При этом и сжатие будет хорошим, и разжатие - быстрым и с прямым доступом. -- #include <best/regards.hpp> Oleg I. KHOVAYKO (301)435-5885 || WEB: http://olegh.spedia.net --- ifmail v.2.15dev5 * Origin: National Center for Biotechnology Information (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 03 Jul 02 20:29:07 To : Vadim Yoockin Subj : Re: Текстовые "базы" сжимать From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Про SEQUITUR слышал? ;-) Кроме sequitur, есть еще один забавный алгоритм, который, в отличие от sequitur, смотрит на весь текст сразу, и итеративно заменяет наиболее часто встречающуюся пару токенов на новый токен, пока не останется ни одной повторяющейся пары токенов. Как этот алгоритм называется, я, к сожалению, забыл. Что-то типа double, но не double. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Alex Baskakov 2:5025/3.55 03 Jul 02 23:24:50 To : Daniil Uspensky Subj : unzip How а ю, Daniil? 30 Июн 02 12:59, Daniil Uspensky -> Eugene Goncharuk: AB>>> Посоветуйте плиз СМАУЮ ПРОСТУЮ и САМУЮ МАЛЕHЬКУЮ unzip AB>>> библиотечку в исходниках на C или C++. EG>> Мне тоже такая нужна, ресурсы хранить в zip файле. Фактически нужна EG>> только распаковка и проверка CRC и очень желательно поддержка режима EG>> -exx. DU> Есть кое-что: DU> This package contains the program "BigSpeed Zip DLL". Прежде чем отвечать хотя бы читай вопрос. AB>>> В гугле порылся - ничего подходящего не нашел. EG>> Аналогично :) DU> Плохо ищете. Вводишь "zip" и всё находится. Действительно. Hаходится ВСЁ zip. Пр. ещё, Л. --- G\/R --- * Origin: Bash the fash (2:5025/3.55)
Предыдущий блок Следующий блок Вернуться в индекс