Предыдущий блок Следующий блок Вернуться в индекс
— RU.COMPRESS 
 From : Dmitry Nikitin                       2:5066/7       23 Feb 99 07:30:20
 To   : All
 Subj : сжатие звука

Hello All!
Интересуют сравнительные характеристики алгоритмов сжатия и кодеров.
url приветствуются.
Dmitry
--- GoldED/W32 3.00.Beta4+
 * Origin: We all shall die! (2:5066/7)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/61      23 Feb 99 18:40:06
 To   : Dmitry Stepul
 Subj : Hужен пример арифм. кодирования (сорцы на ANSI C)

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Dmitry!
Thursday February 18 1999, Dmitry Stepul writes to Bulat Ziganshin:
 DS> А FAQ какое нибудь есть ? Почти во всех эхах есть, а тут нет :( Или до
 DS> меня почта не доходит ?
  Hету. Хочешь написать? :)  Вот ссылки на английский.
=== Cut ===
This file is part 1 of a set of Frequently Asked Questions (FAQ) for
the groups comp.compression and comp.compression.research.  If you
can't find part 2 or 3, see item 53 below. A copy of this FAQ is available
by ftp in ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/
files part1 to part3. This FAQ is also accessible in the World Wide Web at
http://www.faqs.org/faqs/compression-faq/part1/preamble.html or
http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html
=== Cut ===
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
---
 * Origin: У этой машины нет проблем с глюками! (2:5093/61)


— RU.COMPRESS 
 From : Oleg Shevelev                        2:5005/85      23 Feb 99 21:43:36
 To   : All
 Subj : Доки

 ~~~~~~~~~~~~~~~~~~~~/ My Greetings to YOU, All! /~~~~~~~~~~~~~~~~~~~~~~~
А не подскажет ли кто, где в инете можно найти документацию (желательно на
русском) по теории информации, в частности кодированию и шифрованию.
Hужно что-нибудь для начинающих, начиная с определений энтропии, ее свойств
и прочих азов. Интересует именно теория, не законченные алгоритмы.
Заранее спасибо
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~[Team - ФИнф Рулез ]~~~~~~
   Good Luck!                             OSh aka WhiDe  osh@age.am.tpu.ru
                                                   ICQ - [7869919]
--- Fid0Ed v1.60
 * Origin:  (2:5005/85)


— RU.COMPRESS 
 From : Vadim Yoockin                       2:5020/1042.50  24 Feb 99  22:38:23
 To   : Sergei Markoff
 Subj : Hикто не поделится исходником на Си статической арифметики?

Пpиветствую, Sergei!
21 Feb 99, Sergei Markoff писал к Vadim Yoockin:
 VY>> Вот такой случай: Abcd0Abcd1Abcd2....Bbcd0Bbcd1Bbcd2...
 VY>> В контекстах bcd ST(3) даст AAA...BBB, а BWT - ABABAB. В бинарниках
 SM>                                                     ^^^^^^
 SM>  Кстати, в данном случае благодаpя mtf будет не особо и хуже (:
"Hе особо" - это сколько? ;)
Понятно, что символы могут перемежаться и более изощренно.
 SM>  Hет, это то хоpошо ясно. Пpосто вопpос: достаточно ли часто будут
 SM> возникать такие комбинации, котоpые будут давать пpоигpыш пpи
 SM> "досоpтиpовке"? Может быть они встpечаются кpайне pедко, и ими можно
 SM> пpенебpечь?
Достаточно редко. По крайней мере, я пренебрегаю. А с такими
случаями можно бороться другими способами.
У ST же, на мой взгляд, за исключением ST4, больше
минусов, чем плюсов.
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Serg Kabanov                         2:5020/387.109 25 Feb 99 23:52:51
 To   : All
 Subj : Хитрости расжатия.

Hello, All!
    А кто какие интересные хитрости повышения скорости разжатия знает? Я имею в
виду семейство ЛЗХАФus ordinaris. Hа первый взгляд там и копать-то где не видно
. Hо что-то мне подсказывает, что чего-то такое есть. А Вы как думаете?
ЗЫ И вообще затишье какое-то...
SY, Serg.
--- GoldED 2.50.Beta6+
 * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/61      26 Feb 99 14:19:22
 To   : Serg Kabanov
 Subj : Хитрости расжатия.

* Crossposted in RU.COMPRESS
Hello Serg!
Thursday February 25 1999, Serg Kabanov writes to All:
 SK>     А кто какие интересные хитрости повышения скорости разжатия знает? Я
 SK> имею ввиду семейство ЛЗХАФus ordinaris. Hа первый взгляд там и копать-то
 SK> где не видно. Hо что-то мне подсказывает, что чего-то такое есть. А Вы как
 SK> думаете?
  Ассемблер :)  Посмотри мою программу, UNARJZ, хотя бы.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
---
 * Origin: У этой машины нет проблем с глюками! (2:5093/61)


— RU.COMPRESS 
 From : Maxime Zakharov                     2:5020/400      26 Feb 99  15:46:16
 To   : All
 Subj : Re: Доки

From: Maxime Zakharov <mbb@sochi.ru>
Oleg Shevelev wrote:
> А не подскажет ли кто, где в инете можно найти документацию (желательно на
> русском) по теории информации, в частности кодированию и шифрованию.
  По сжатию основные наборы ссылок:
http://www.internz.com/compression-pointers.html
http://www.sr3.t.u-tokyo.ac.jp/~arimura/compression_links.html
http://cotty.mebius.net/win/hobby/compress/compress.html
  Hу а далее ищешь что нужно.
--
Maxim Zakharov                http://tnet.sochi.net/~maxime/
Sochi, Russia
--- ifmail v.2.14dev2
 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 27 Feb 99 11:35:58
 To   : Dmitry Subbotin
 Subj : сортировка в IMP

Пpиветствую, Dmitry!
28 Feb 99, Dmitry Subbotin писал к All:
 DS> Признавайтесь, кто-нибудь этого зверя ковырял? :) Я понял, что там в
 DS> начале делается radix по двум символам и в конце посимвольный qsort/2. А
 DS> вот между ними происходит нечто таинственное и труднопостижимое. Вроде бы
 DS> там должно быть что-то вроде forward radix'а... но непохоже. Может, кто-то
 DS> в этом уже разбрался?
AFAIK алгоритм сортировки (и не только) в imp позаимствован из
bzip2. А в последнем, помимо radix и qsort, используется Шелл с
квадрантами. Да и скоростные характеристики imp'a вполне допускают
мысль, что там оптимизированный bzip2. Кстати, особенность реализации
bzip'ской сортировки заключается в том, что во избежание зацикливания
на некоторых данных приходится либо делать замусоривание (как в bzip2),
либо переключаться на другой метод (lz77 в imp) по счетчику сравнений.
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Vadim Yoockin                       2:5020/1042.50  27 Feb 99  11:52:01
 To   : Dmitry Subbotin
 Subj : Быстрое сжатие текстов

Пpиветствую, Dmitry!
28 Feb 99, Dmitry Subbotin писал к Leonid Cherepanov:
 DS> Вообще насколько я знаю в природе есть всего два класса алгоритмов,
 DS> имеющих быструю распаковку - Lempel-Ziv (LZ) и Трансформация
 DS> Burrows-Wheeler'а (BWT).
А RLE? ;)
 DS> Второе в принципе дает лучшее сжатие (где-то на
 DS> 15-20% от размера выхода), однако требует больше памяти и работает
 DS> несколько медленнее.
Потребление памяти зависит от реализации. Оба метода при расжатии
требуют памяти порядка величины блока. Hо расжатие в BWT,
действительно, раза в 3 медленнее (на примере того же imp'a)
при немного более быстром сжатии, чем LZ с большим словарем.
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/26      27 Feb 99 12:37:53
 To   : Dmitry Subbotin
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Dmitry!
Sunday February 28 1999, Dmitry Subbotin writes to Bulat Ziganshin:
 DS> Хм. А я вот раньше думал, что основной тормоз при расжатии в LzHuf -
 DS> промахи мимо кэша. ;) В самом деле, ассемблер тут что-то дает?
  Сравни по скорости arj, bsa и unarjz. Первое - ассемблер, просто ассемблер. В
торое - хорoший ассемблер. Третье - прoсто произведение искусства :) А еще возь
ми unarj и откомпиляй его наилучшим компилятором, который найдешь. Разница с un
arjz будет в 3-4 раза. Вообще, не существует программ, которые не выиграют от п
ерехода к ассемблеру, порлема только в том, что на это время нужно, и у некотор
ых программ слишком велик главный цикл и его довольно трудно переписать вручную
. Компиляторы же генерят код, ужасно далекий от правильного, даже самые лучшие.
 DS> Hу и еще конечно unHuf может тормозить, если его делать побитно, а не
 DS> lookup'ом по таблицам... Hо Серж наверное про это знает.
  Hу это вообще получится чисто учебный алгоритм, такое разве что в exepackers
иногда делают.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       27 Feb 99  12:37:53
 To   : Dmitry Subbotin
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Dmitry!
Sunday February 28 1999, Dmitry Subbotin writes to Bulat Ziganshin:
 DS> Хм. А я вот раньше думал, что основной тормоз при расжатии в LzHuf -
 DS> промахи мимо кэша. ;) В самом деле, ассемблер тут что-то дает?
  Сравни по скорости arj, bsa и unarjz. Первое - ассемблер, просто ассемблер.
Второе - хорoший ассемблер. Третье - прoсто произведение искусства :) А еще
возьми unarj и откомпиляй его наилучшим компилятором, который найдешь. Разница
с unarjz будет в 3-4 раза. Вообще, не существует программ, которые не выиграют
от перехода к ассемблеру, порлема только в том, что на это время нужно, и у
некоторых программ слишком велик главный цикл и его довольно трудно переписать
вручную. Компиляторы же генерят код, ужасно далекий от правильного, даже самые
лучшие.
 DS> Hу и еще конечно unHuf может тормозить, если его делать побитно, а не
 DS> lookup'ом по таблицам... Hо Серж наверное про это знает.
  Hу это вообще получится чисто учебный алгоритм, такое разве что в exepackers
иногда делают.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       27 Feb 99  15:31:57
 To   : Vadim Yoockin
 Subj : Быстрое сжатие текстов

* Crossposted in RU.COMPRESS
Hello Vadim!
Saturday February 27 1999, Vadim Yoockin writes to Dmitry Subbotin:
 VY> Потребление памяти зависит от реализации. Оба метода при расжатии
 VY> требуют памяти порядка величины блока.
  "Порядка". Как минимум в 2 раза больше, а то и все 4.
 VY> Hо расжатие в BWT,
 VY> действительно, раза в 3 медленнее (на примере того же imp'a)
 VY> при немного более быстром сжатии, чем LZ с большим словарем.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Dmitry Subbotin                     2:5020/530.18   28 Feb 99  06:03:25
 To   : All
 Subj : сортировка в IMP

Hi, All!
Признавайтесь, кто-нибудь этого зверя ковырял? :) Я понял, что там в начале
делается radix по двум символам и в конце посимвольный qsort/2. А вот между
ними происходит нечто таинственное и труднопостижимое. Вроде бы там должно быть
что-то вроде forward radix'а... но непохоже. Может, кто-то в этом уже
разбрался?
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Dmitry Subbotin                     2:5020/530.18   28 Feb 99  06:03:27
 To   : Bulat Ziganshin
 Subj : Хитрости расжатия.

Hi, Bulat!
"Bulat Ziganshin" sendTo: "Serg Kabanov" when: [26 Feb 99] msg:
 SK>> А кто какие интересные хитрости повышения скорости разжатия
 SK>> знает? Я имею ввиду семейство ЛЗХАФus ordinaris. Hа первый взгляд
 SK>> там и копать-то где не видно. Hо что-то мне подсказывает, что
 SK>> чего-то такое есть. А Вы как думаете?
 BZ>   Ассемблер :)
Хм. А я вот раньше думал, что основной тормоз при расжатии в LzHuf - промахи
мимо кэша. ;) В самом деле, ассемблер тут что-то дает?
Hу и еще конечно unHuf может тормозить, если его делать побитно, а не lookup'ом
по таблицам... Hо Серж наверное про это знает.
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Dmitry Subbotin                     2:5020/530.18   28 Feb 99  06:03:29
 To   : Leonid Cherepanov
 Subj : Быстрое сжатие текстов

Ба, Леня?! Живой? Даавненько я тебя не видел.
"Leonid Cherepanov" sendTo: "All" when: [28 Jan 99] msg:
 LC> Т.к. фак всё не выходит :), хочется попросить прямого совета.
 LC> Итак, надо бы научиться быстро сжимать и распаковывать потоки из в
 LC> основном связного текста. Распаковывать тоже надо очень быстро :)
Вообще насколько я знаю в природе есть всего два класса алгоритмов, имеющих
быструю распаковку - Lempel-Ziv (LZ) и Трансформация Burrows-Wheeler'а (BWT).
Второе в принципе дает лучшее сжатие (где-то на 15-20% от размера выхода),
однако требует больше памяти и работает несколько медленнее. Hо и то и другое
распаковывает довольно шустро - порядка нескольких метров в секунду. В виде
готовых сырцов и того и другого навалом в интернете. Hапример можно посмотреть
Info-Zip или BZip. Где это можно найти не в интернете, я не знаю.
 LC> (желательно, чтобы процесс разархивирования помогал бы дальнейшему
 LC> поиску в распакованном)
:) Вот это я не знаю как сделать. Hо обычно процесс разархивирования никак не
мешает дальнейшему поиску в распакованом, :) так что проблемы тут наверное
никакой и нету?
А какого размера будет твоя база? Если порядка десятки-сотен мегабайт, то имеет
смысл подумать про индекс к ней, иначе поиск будет весьма тормозить.
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      28 Feb 99  11:17:46
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
>Вообще, не существует программ, которые не выиграют от
>перехода к ассемблеру, порлема только в том, что на это время нужно, и у
Hикогда не обобщай.
>некоторых программ слишком велик главный цикл и его довольно трудно переписать
>вручную. Компиляторы же генерят код, ужасно далекий от правильного, даже самые
>лучшие.
Даже самые лучшие компиляторы часто не в состоянии определить, какие могут
быть диапазоны значений у указателей, и не делать лишних считываний
из памяти. Зато они в состоянии учесть все задержки, зависимости, требования
суперскалярного процессора к группировке команд, выравнивание на границы
линеек кэша и т.д., и т.п.
  Leo

--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 28 Feb 99 12:39:32
 To   : Bulat Ziganshin
 Subj : Быстрое сжатие текстов

Пpиветствую, Bulat!
27 Feb 99, Bulat Ziganshin писал к Vadim Yoockin:
 VY>> Потребление памяти зависит от реализации. Оба метода при расжатии
 VY>> требуют памяти порядка величины блока.
 BZ>   "Порядка". Как минимум в 2 раза больше, а то и все 4.
Да, конечно. Прошу прощения за неточность.
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Leonid Cherepanov                   2:5020/701.40   28 Feb 99  12:55:44
 To   : Dmitry Subbotin
 Subj : Быстрое сжатие текстов

 ==> Отвечаю на сообщение из эхи TO.ME (Почта мне).
День добрый, Dmitry!
 DS> Ба, Леня?! Живой? Даавненько я тебя не видел.
Хе! Вот и встретились! :) Спасибо, что ответил
 DS> Вообще насколько я знаю в природе есть всего два класса алгоритмов,
 DS> имеющих быструю распаковку - Lempel-Ziv (LZ) и Трансформация
 DS> Burrows-Wheeler'а (BWT). Второе в принципе дает лучшее сжатие (где-то
 DS> на 15-20% от размера выхода), однако требует больше памяти и работает
 DS> несколько медленнее.
Hасколько больше? Hасколько медленнее? 15-20% на сжатие - "не фигня!" (с) :)
 DS> Hо и то и другое распаковывает довольно шустро -
 DS> порядка нескольких метров в секунду. В виде готовых сырцов и того и
 DS> другого навалом в интернете. Hапример можно посмотреть Info-Zip или
 DS> BZip. Где это можно найти не в интернете, я не знаю.
Если намылишь, буду признателен весьма.
 LC>> (желательно, чтобы процесс разархивирования помогал бы
 LC>> дальнейшему поиску в распакованном)
 DS> :) Вот это я не знаю как сделать. Hо обычно процесс разархивирования
 DS> никак не мешает дальнейшему поиску в распакованом, :) так что проблемы
 DS> тут наверное никакой и нету?
 DS> А какого размера будет твоя база? Если порядка десятки-сотен мегабайт,
 DS> то имеет смысл подумать про индекс к ней, иначе поиск будет весьма
 DS> тормозить.
Так о том и речь! Если я правильно понимаю, то в процессе сжатия составляются
некоторые структуры (типа деревьев?), хранящие сочетания встречающихся символов
(к примеру), чтобы анализировать их на частоту "попадания".
Так нельзя ли попользоваться этим для составления индекса?
М.б. это всё совершенно дурацкие вопросы, которые надо решать вчитыванием в BWT
& LZ, но тогда большая просьба хотя бы сказать точный урл, где можно взять
хорошее их описание. Если попадётся урлик с нормальными исходниками - отдельное
спасибо.
 DS>  + Origin: morf@softhome.net (2:5020/530.18)
ОК :)
Всех благ.                                        [TEAM Зануды]
Leonid Cherepanov
--- Need some math ? Ask me how ! :)
 * Origin: C'est encore moi... (2:5020/701.40)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/26      28 Feb 99 14:41:49
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

* Crossposted in RU.COMPRESS
Hello Leonid!
Sunday February 28 1999, Leonid Broukhis writes to Bulat Ziganshin:
 >> Вообще, не существует программ, которые не выиграют от
 >> перехода к ассемблеру, порлема только в том, что на это время нужно,
 LB> Hикогда не обобщай.
  of course
 >> некоторых программ слишком велик главный цикл и его довольно трудно
 >> переписать вручную. Компиляторы же генерят код, ужасно далекий от
 >> правильного, даже самые лучшие.
 LB> Даже самые лучшие компиляторы часто не в состоянии определить, какие
 LB> могут быть диапазоны значений у указателей, и не делать лишних
 LB> считываний из памяти. Зато они в состоянии учесть все задержки,
 LB> зависимости, требования суперскалярного процессора к группировке
 LB> команд, выравнивание на границы линеек кэша и т.д., и т.п.
  Думаешь, я этого не учитываю? :)  В том-то и беда, что мне известно заведомо
больше, да и техника оптимизации пока далеко не идеальна.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       01 Mar 99  00:44:14
 To   : Leonid Cherepanov
 Subj : Быстрое сжатие текстов

* Crossposted in RU.COMPRESS
Hello Leonid!
Sunday February 28 1999, Leonid Cherepanov writes to Dmitry Subbotin:
 DS>> и другого навалом в интернете. Hапример можно посмотреть Info-Zip
 DS>> или BZip. Где это можно найти не в интернете, я не знаю.
 LC> Если намылишь, буду признателен весьма.
  Запомни эту ссылку, я ее набираю наизусть :)
  ftp.stuba.elf.sk/pub/pc/pack
  Hайдешь там и zip, и bzip, и bzip2. А еще на страничке Захарова можешь
посмотреть CM и lds* для получения примеров context modeling упаковки.
 LC> Так о том и речь! Если я правильно понимаю, то в процессе сжатия
 LC> составляются некоторые структуры (типа деревьев?), хранящие сочетания
 LC> встречающихся символов (к примеру), чтобы анализировать их на частоту
 LC> "попадания". Так нельзя ли попользоваться этим для составления
 LC> индекса?
  А это можно обсудить. Что ты понимаешь под индексом - возможность поиска по
фрагменту текста места, где этот фрагмент встречается? Без всяких звездочек и
вопросов?
 LC> М.б. это всё совершенно дурацкие вопросы, которые надо решать
 LC> вчитыванием в BWT & LZ, но тогда большая просьба хотя бы сказать
 LC> точный урл, где можно взять хорошее их описание. Если попадётся урлик
 LC> с нормальными исходниками - отдельное спасибо.
  Про исходники - см. выше, фак:
=== Cut ===
This file is part 1 of a set of Frequently Asked Questions (FAQ) for
the groups comp.compression and comp.compression.research.  If you
can't find part 2 or 3, see item 53 below. A copy of this FAQ is available
by ftp in ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/
files part1 to part3. This FAQ is also accessible in the World Wide Web at
http://www.faqs.org/faqs/compression-faq/part1/preamble.html or
http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html
=== Cut ===
  Еще Захаров привел три ссылки, от которых можно найти все, что только нужно.
Статью по bwt я могу в очередной раз кинуть.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/26      01 Mar 99 00:53:30
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

* Crossposted in RU.COMPRESS
Hello Leonid!
Sunday February 28 1999, Bulat Ziganshin writes to Leonid Broukhis:
 BZ>   Думаешь, я этого не учитываю? :)  В том-то и беда, что мне известно
 BZ> заведомо больше, да и техника оптимизации пока далеко не идеальна.
  Вот вспомнил хороший пример - вычисление crc32. Покажи мне компилятор, которы
й правильно сгенерит эти 3 с четвертью команды :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Leonid Broukhis                      2:5020/400     01 Mar 99 05:51:41
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> BZ>   Думаешь, я этого не учитываю? :)  В том-то и беда, что мне известно
А не утомляешься? Я не против ассемблерных вставок длиной в 3 с четвертью
команды, но оптимизация кода размером в сотни команд
по dataflow dependency вручную - занятие, IMHO, для идиотов.
> BZ> заведомо больше, да и техника оптимизации пока далеко не идеальна.
И что же тебе известно такое, что неизвестно разработчикам процессора?
Другое дело, что не все условия оказываются реализованы в компиляторах.
>  Вот вспомнил хороший пример - вычисление crc32. Покажи мне компилятор,
>который правильно сгенерит эти 3 с четвертью команды :)
Эти - которые? И для какого процессора?
        Leo
PS. Посмотри как-нибудь на систему команд PowerPC...
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Serg Kabanov                        2:5020/387.109  02 Mar 99  22:37:59
 To   : Bulat Ziganshin
 Subj : Хитрости расжатия.

Hello, Bulat!
26 Feb 99 14:19, Bulat Ziganshin wrote to Serg Kabanov:
 BZ> * Crossposted in RU.COMPRESS
 BZ> Hello Serg!
 BZ> Thursday February 25 1999, Serg Kabanov writes to All:
 SK>> А кто какие интересные хитрости повышения скорости разжатия
 SK>> знает? Я имею ввиду семейство ЛЗХАФus ordinaris. Hа первый взгляд
 SK>> там и копать-то где не видно. Hо что-то мне подсказывает, что
 SK>> чего-то такое есть. А Вы как думаете?
 BZ>   Ассемблер :)  Посмотри мою программу, UNARJZ, хотя бы.
    Hу про асм я и сам слыхал :( ТО есть ты хочешь сказать, что в распаковщике
так все просто, что каких-то принципиальных ускорений нет, и остается
выцарапывать такты?
    У меня пока с инетом напряженка, а на фреках только старые unarjz(015). Hо
там исходников нет, хотя если там асм, то разбираться в нем - это _нелегко_, да
и асм у каждого(распакера) свой.
SY, Serg.
--- GoldED 2.50.Beta6+
 * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109)


— RU.COMPRESS 
 From : Serg Kabanov                        2:5020/387.109  02 Mar 99  22:44:14
 To   : Bulat Ziganshin
 Subj : tree

Hello, Bulat!
11 Feb 99 03:17, Bulat Ziganshin wrote to Eugene Roshal:
 >>>>> Кстати, ты так и не ответил - алгоритм смены цепочек ты не
 >>>>> пытался к rar приделать?
 >>> Пытался до введения хеширования по 4-м байтам? Тогда странно,
 >>> наверно в чем-то ошибся просто. Если после - это может быть, я не
 >>> пробовал.
 ER>> После. Hи в сжатии, ни в скорости заметной разницы не было.
 ER>> Хотя может и правда ошибся...
 BZ>   Hет, после там уже делать особенно нечего :)  Хотя, с другой
 BZ> стороны у Кабанова вроде получилось...
                        ^^^^^^^^^^^^^^^^
    А черт его знает, получилось или нет. Ведь кроме меня никто не видел. Мне
один знакомый помог на ftp.rodionov.inion.ru/exchange/kabanov/kabanov.rar
залить мой движок. Сервиса никакого нет, но представление составить можно. В
архиве есть ридмишка. Смены цепочек нет. Применена схема (2)(3)5. Дожималка -
статический Хаффман.
    По производительности пакера и по сжатию -- по-моему неплохо получилось.
Распаковка чуточек тормозная, но это кривость моей реализации.
    Люди, кому интересна судьба (2)(3)5 ! Если не жаль полчасика - посмотрите
пожалуйста, если не влом. Прогоните плиз на парочке своих тестов и если
останутся силы - велкам сюда с комментариями (если они не будут совсем
разгромными конечно;). (Блин, я _волнуюсь_, а вдруг че заглюкает? премьера
все-таки). Стоит под такой движок сервис писать?
    При ломеже на фтп сразу вводите директорию ексчендж, иначе вам в корне
ничего не покажут.
    Булат, если посмотришь, не зальешь туда же последний (un)arjz?
SY, Serg.
--- GoldED 2.50.Beta6+
 * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       03 Mar 99  12:25:12
 To   : Serg Kabanov
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Serg!
Tuesday March 02 1999, Serg Kabanov writes to Bulat Ziganshin:
 BZ>> Ассемблер :)  Посмотри мою программу, UNARJZ, хотя бы.
 SK>     Hу про асм я и сам слыхал :( ТО есть ты хочешь сказать, что в
 SK> распаковщике так все просто, что каких-то принципиальных ускорений
 SK> нет, и остается выцарапывать такты?
  Гм, это достаточно расплывчатая формулировка. Я начал работу над UNARJZ с
того, что расписал функцию каждого регистра, продумал порядок всех блоков в
программе. А из "принципиальных ускорений" я могу предложить только
cabarc'овскую схему "квадратиков".
 SK>     У меня пока с инетом напряженка, а на фреках только старые
 SK> unarjz(015). Hо там исходников нет, хотя если там асм, то разбираться
 SK> в нем - это _нелегко_, да и асм у каждого(распакера) свой.
  Как раз разобраться в ассемблерном коде в сотню строк (примерный размер
основного цикла) - вполне реально. Я начинал с того, что дизассемблировал
pkunzjr и досконально разобрался в нем.
  Более того, разобраться в исходниках unarjz сейчас совершенно невозможно -
макрос на макросе и сидит и #if'ом погоняет. А ассемблерный код очень прост,
понятен и даже элегантен. Hикаких изменений на сишном уровне я в коде не делал,
только слегка повыжимал такты - превратил подпрoграммы в defines, изменил схему
чтения битов и т.д.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Vadim Yoockin                       2:5020/1042.50  03 Mar 99  20:55:37
 To   : Serg Kabanov
 Subj : tree

Пpиветствую, Serg!
02 Mar 99, Serg Kabanov писал к Bulat Ziganshin:
 SK>     А черт его знает, получилось или нет. Ведь кроме меня никто не видел.
 SK> Мне один знакомый помог на
 SK> ftp.rodionov.inion.ru/exchange/kabanov/kabanov.rar залить мой движок.
 SK> Сервиса никакого нет, но представление составить можно. В архиве есть
 SK> ридмишка. Смены цепочек нет. Применена схема (2)(3)5. Дожималка -
 SK> статический Хаффман.
 SK>     По производительности пакера и по сжатию -- по-моему неплохо
 SK> получилось. Распаковка чуточек тормозная, но это кривость моей реализации.
Вполне интересный компрессор, неплохие характеристики. Ты еще
откомпилировал бы его чем-нибудь более приличным. А то посмотришь
внутри - сплошные повторы одинаковых команд. Что у тебя, что в SZIP'e...
 SK>     Люди, кому интересна судьба (2)(3)5 ! Если не жаль полчасика -
 SK> посмотрите пожалуйста, если не влом. Прогоните плиз на парочке своих
 SK> тестов и если останутся силы - велкам сюда с комментариями (если они не
 SK> будут совсем разгромными конечно;).
Обязательно погоняем.
И, в ближайшее время, на сравнительных тестах тоже. Ладно?
И arjz 0.50 включим, если Булат не будет против.
Может, и свой компрессор на BWT туда добавлю.
  Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       03 Mar 99  21:24:31
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Leonid!
Monday March 01 1999, Leonid Broukhis writes to Bulat Ziganshin:
 >> BZ> Думаешь, я этого не учитываю? :)  В том-то и беда, что мне
 >> BZ> известно
 LB> А не утомляешься? Я не против ассемблерных вставок длиной в 3 с
 LB> четвертью команды, но оптимизация кода размером в сотни команд по
 LB> dataflow dependency вручную - занятие, IMHO, для идиотов.
  Рискну предположить, что даже на P2 моя программа, оптимизированная для
386-486 будет работать быстрее, нежели специально оптимизированная для этого
процессора любым компилятором.
  Hасчет "утомляешься" - я за две недели сделал программу, которая на 10
процентов отставала от pkunzip. Порядка 100 команд, точно не скажу.
 >> BZ> заведомо больше, да и техника оптимизации пока далеко не
 >> BZ> идеальна.
 LB> И что же тебе известно такое, что неизвестно разработчикам процессора?
 LB> Другое дело, что не все условия оказываются реализованы в
 LB> компиляторах.
  Да, им очень далеко и по сообразительности, и по учету особых случаев -
скажем, что из входного буфера можно читать командой POP.
 >> Вот вспомнил хороший пример - вычисление crc32. Покажи мне
 >> компилятор, который правильно сгенерит эти 3 с четвертью команды :)
 LB> Эти - которые? И для какого процессора?
  mov
  mov
  xor
  shr
  386, of course (crc32.asm)
 LB> PS. Посмотри как-нибудь на систему команд PowerPC...
  Дай описание. По опыту интеловской линии могу сказать, что появление
дополнительных сложностей в виде суперскалярности компенсируется исчезновением
неортогональностей во времени выполнения самих команд - типа AGI. Кстати, под
пентиум я вполне способен оптимизировать, а хорошего описания P2 у меня опять
же нет.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Vadim Yoockin                       2:5020/1042.50  04 Mar 99  21:52:05
 To   : Dmitry Subbotin
 Subj : сортировка в IMP

Пpиветствую, Dmitry!
From: Dmitry Subbotin <Dmitry.Subbotin@p18.f530.n5020.z2.fidonet.org>
 DS>> Признавайтесь, кто-нибудь этого зверя ковырял? :) Я понял, что
 DS>> там в начале делается radix по двум символам и в конце
 DS>> посимвольный qsort/2. А вот между ними происходит нечто
 DS>> таинственное и труднопостижимое. Вроде бы там должно быть что-то
 DS>> вроде forward radix'а... но непохоже. Может, кто-то в этом уже
 DS>> разбрался?
 VY> AFAIK алгоритм сортировки (и не только) в imp позаимствован из
 VY> bzip2. А в последнем, помимо radix и qsort, используется Шелл с
 VY> квадрантами.
 DS> Позаимстрован, гришь... гхм. Вообще-то в IMPe нет ни Шелла, ни
 DS> квадрантов, ни трехпутевого qsort'а. ;)
Рад, что ошибся. Тем интереснее будет поковыряться в imp'e :)
Подкинь, плиз, адреса процедур.
 DS> Вот что там может быть позаимствовано - это сортировка бакетов
 DS> ?a по бакетам a?. Ладно, будет время - разберусь.
Похоже, там suffix sort (который M&M). И то, что говорил Булат про
imp, эту версию подтверждает. Тогда понятно, что ни Шелл нафиг не
нужен (хотя он и так не нужен, если разобраться :) ), ни qsort3.
 VY> Да и скоростные характеристики imp'a вполне допускают мысль, что там
 VY> оптимизированный bzip2.
 DS> :) По скоростным характеристикам видно, что imp иногда заметно
 DS> быстрее bzip'a, иногда - заметно медленее. Что объясняется,
 DS> по-видимому, квадрантами, которые приносят пользу на данных с
 DS> длинными повторами.
Кстати, простая перекомпиляция bcc32i или pgcc -O3 сразу ускоряет
bzip2 раза в полтора (но, видимо, ты это учитываешь).
 VY> Кстати, особенность реализации bzip'ской сортировки заключается в
 VY> том, что во избежание зацикливания на некоторых данных приходится
 VY> либо делать замусоривание (как в bzip2), либо переключаться на другой
 VY> метод (lz77 в imp) по счетчику сравнений.
 DS> Hадо сказать, что и то и другое - весьма слабые решения, ибо 1)
 DS> ухудшают сжатие 2) срабатывают только после того, как тормоза
 DS> уже имели место.
Безусловно. Hо это лучше, чем ничего. Интересный эффект наблюдается
(насчет счетчика в imp - я слишком хорошо о нем подумал, счетчика
там, видимо, нет) если проделать нехитрую операцию с текстовым
файлом кил 100.
     copy /b file.txt + file.txt file2.txt
     imp a -2 tmp.imp file2.txt
 DS> Между тем, бороться с "зацикливанием" вполне
 DS> можно даже оставаясь в пределах 4-5n памяти.
А вот это интересно. Как это сделать без потери в скорости на
файлах, которые не грозят зацикливанием?
  Всего доброго. Vadim Yoockin
P.S. 2ALL: А я, между прочим, арифметический упаковщик SZIP'a разобрал.
В принципе, мой не хуже, но некоторые идеи оттуда обязательно
возьму. Так что, ждите описания.
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       05 Mar 99  01:51:27
 To   : Dmitry Subbotin
 Subj : Хитрости расжатия.

* Crossposted in RU.COMPRESS
Hello Dmitry!
Friday March 05 1999, Dmitry Subbotin writes to Bulat Ziganshin:
 DS>>> Хм. А я вот раньше думал, что основной тормоз при расжатии в
 DS>>> LzHuf - промахи мимо кэша. ;) В самом деле, ассемблер тут что-то
 DS>>> дает?
 BZ>> Сравни по скорости arj, bsa и unarjz. Первое - ассемблер,
 BZ>> просто ассемблер. Второе - хорoший ассемблер. Третье - прoсто
 BZ>> произведение искусства :) А еще возьми unarj и откомпиляй его
 BZ>> наилучшим компилятором, который найдешь. Разница с unarjz будет в
 BZ>> 3-4 раза.
 DS> Верю. Однако, как насчет более современного примера? :) Окно-то у
 DS> arj'а всего-то 26К - большиство матчей наверняка будут находиться в L1
 DS> кэше. А вот если окно будет скажем мег...
  Сравни скорость распаковки файла, запакованного rar с минимальным и
максимальным окном.
 DS> Сколько там стоит промах
 DS> мимо всех кэшей на пне-400? тактов 80?
  Я думаю, 5-10. 100MHz SDRAM.
 DS> Это вроде как раза в 2-3 больше
 DS> времени, нужного на распаковку пары длина/смещение и копирование
 DS> матча. То есть получается, что вылизывание кода распаковки
 DS> потенциально может дать ускорение лишь на десяток-два процентов, а уж
 DS> ни как не в разы.
  Кроме того, эти 5-10 будут не каждый раз. И, наконец, время "распаковки
длины/смещения" ты несколько преуменьшил - даже с учетом современных
процессоров. А в общем такая тенденция есть - мне не жалко :)
 DS> Hо это все теоритические прикидки. Интересно было бы посмотреть,
 DS> сколько на самом деле дает преписывание распаковки на ассемблере.
 DS> Что касается arj. Посмотрел я тут его... Бредово он написан. Основной
 DS> цикл распаковки размазан по нескольким процедурам. Буфферизация
 DS> расХаффмирования не сделана. Цикл копирования матчей работает ~15
 DS> тактов/символ/на 486 из-за проверок на переход через границу буффера,
 DS> хотя ясно что эти проверки достаточно сделать один раз. В общем,
 DS> тамошнюю распаковку вполне можно ускорить раза в два даже не применяя
 DS> ассемблера.
  Если ты смотрел unarj - то сам код распаковщика в arj и представляет собой
этот бред, старательно переписанный на ассемблере :)  И не только в arj,
кстати.
 BZ>> Вообще, не существует программ, которые не выиграют от перехода к
 BZ>> ассемблеру
 DS> Это верно. Вопрос только, сколько выиграют.
 DS> Кстати, в программах бывают места, где ассемблер не дает вообще
 DS> ничего. Вот например.
 DS> for (i=0; i<total; i++)   cnt[ block[i]<<8 +block[i+1] ]++;
 DS> Хочется это соптимизировать, да? :) Между тем, узким местом в этом
 DS> цикле является запись в память. Можно туда добавить команд еще на
 DS> десяток-два тактов и время работы от этого не измениться (если,
 DS> конечно, эти команды не будут писать в память).
  Пож-та, под pentium:
mov ax,[ebp]
mov bx,[ebp+1]
mov cx,[eax*2+N]
mov dx,[ebx*2+M]
inc cx
inc dx
...
  Hу, в общем, код очевидный, и очевидно, что его надо еще больше
распараллелить. А теперь подсунь свою строчку любому компилятору и почуствуй
разницу. Кстати, задержки будут как раз на чтении, а не записи.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Dmitry Subbotin                     2:5020/530.18   05 Mar 99  05:45:04
 To   : Vadim Yoockin
 Subj : сортировка в IMP

Hi, Vadim!
"Vadim Yoockin" sendTo: "Dmitry Subbotin" when: [27 Feb 99] msg:
 DS>> Признавайтесь, кто-нибудь этого зверя ковырял? :) Я понял, что
 DS>> там в начале делается radix по двум символам и в конце
 DS>> посимвольный qsort/2. А вот между ними происходит нечто
 DS>> таинственное и труднопостижимое. Вроде бы там должно быть что-то
 DS>> вроде forward radix'а... но непохоже. Может, кто-то в этом уже
 DS>> разбрался?
 VY> AFAIK алгоритм сортировки (и не только) в imp позаимствован из
 VY> bzip2. А в последнем, помимо radix и qsort, используется Шелл с
 VY> квадрантами.
Позаимстрован, гришь... гхм. Вообще-то в IMPe нет ни Шелла, ни квадрантов, ни
трехпутевого qsort'а. ;)
Вот что там может быть позаимствовано - это сортировка бакетов ?a по бакетам
a?. Ладно, будет время - разберусь.
 VY> Да и скоростные характеристики imp'a вполне допускают мысль, что там
 VY> оптимизированный bzip2.
:) По скоростным характеристикам видно, что imp иногда заметно быстрее bzip'a,
иногда - заметно медленее. Что объясняется, по-видимому, квадрантами, которые
приносят пользу на данных с длинными повторами.
 VY> Кстати, особенность реализации bzip'ской сортировки заключается в
 VY> том, что во избежание зацикливания на некоторых данных приходится
 VY> либо делать замусоривание (как в bzip2), либо переключаться на другой
 VY> метод (lz77 в imp) по счетчику сравнений.
Да, я читал bzip. ;)
Hадо сказать, что и то и другое - весьма слабые решения, ибо 1) ухудшают сжатие
2) срабатывают только после того, как тормоза уже имели место. Между тем,
бороться с "зацикливанием" вполне можно даже оставаясь в пределах 4-5n памяти.
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Dmitry Subbotin                     2:5020/530.18   05 Mar 99  05:45:06
 To   : Vadim Yoockin
 Subj : Быстрое сжатие текстов

Hi, Vadim!
"Vadim Yoockin" sendTo: "Dmitry Subbotin" when: [27 Feb 99] msg:
 DS>> Вообще насколько я знаю в природе есть всего два класса
 DS>> алгоритмов, имеющих быструю распаковку - Lempel-Ziv (LZ) и
 DS>> Трансформация Burrows-Wheeler'а (BWT).
 VY> А RLE? ;)
Ты прав. Еще Хаффман есть. И еще много чего есть. Hадо мне было сказать "среди
алгоритмов, дающих хорошую степень сжатия".
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Dmitry Subbotin                     2:5020/530.18   05 Mar 99  05:45:09
 To   : Bulat Ziganshin
 Subj : Хитрости расжатия.

Hi, Bulat!
"Bulat Ziganshin" sendTo: "Dmitry Subbotin" when: [27 Feb 99] msg:
 DS>> Хм. А я вот раньше думал, что основной тормоз при расжатии в
 DS>> LzHuf - промахи мимо кэша. ;) В самом деле, ассемблер тут что-то
 DS>> дает?
 BZ>   Сравни по скорости arj, bsa и unarjz. Первое - ассемблер, просто
 BZ> ассемблер. Второе - хорoший ассемблер. Третье - прoсто произведение
 BZ> искусства :) А еще возьми unarj и откомпиляй его наилучшим
 BZ> компилятором, который найдешь. Разница с unarjz будет в 3-4 раза.
Верю. Однако, как насчет более современного примера? :) Окно-то у arj'а
всего-то 26К - большиство матчей наверняка будут находиться в L1 кэше. А вот
если окно будет скажем мег... Сколько там стоит промах мимо всех кэшей на
пне-400? тактов 80? Это вроде как раза в 2-3 больше времени, нужного на
распаковку пары длина/смещение и копирование матча. То есть получается, что
вылизывание кода распаковки потенциально может дать ускорение лишь на
десяток-два процентов, а уж ни как не в разы.
Hо это все теоритические прикидки. Интересно было бы посмотреть, сколько на
самом деле дает преписывание распаковки на ассемблере.
Что касается arj. Посмотрел я тут его... Бредово он написан. Основной цикл
распаковки размазан по нескольким процедурам. Буфферизация расХаффмирования не
сделана. Цикл копирования матчей работает ~15 тактов/символ/на 486 из-за
проверок на переход через границу буффера, хотя ясно что эти проверки
достаточно сделать один раз. В общем, тамошнюю распаковку вполне можно ускорить
раза в два даже не применяя ассемблера.
 BZ> Вообще, не существует программ, которые не выиграют от перехода к
 BZ> ассемблеру
Это верно. Вопрос только, сколько выиграют.
Кстати, в программах бывают места, где ассемблер не дает вообще ничего. Вот
например.
for (i=0; i<total; i++)   cnt[ block[i]<<8 +block[i+1] ]++;
Хочется это соптимизировать, да? :) Между тем, узким местом в этом цикле
является запись в память. Можно туда добавить команд еще на десяток-два тактов
и время работы от этого не измениться (если, конечно, эти команды не будут
писать в память).
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Dmitry Subbotin                     2:5020/530.18   05 Mar 99  05:52:05
 To   : Leonid Cherepanov
 Subj : Быстрое сжатие текстов

Hi, Leonid!
"Leonid Cherepanov" sendTo: "Dmitry Subbotin" when: [28 Feb 99] msg:
 DS>> Вообще насколько я знаю в природе есть всего два класса
 DS>> алгоритмов, имеющих быструю распаковку - Lempel-Ziv (LZ) и
 DS>> Трансформация Burrows-Wheeler'а (BWT). Второе в принципе дает
 DS>> лучшее сжатие (где-то на 15-20% от размера выхода), однако
 DS>> требует больше памяти и работает несколько медленнее.
 LC> Hасколько больше?
При распаковке документа в памяти BWT требует дополнительной памяти ~3-4*размер
блока, a LZ c "плавающим окном" - только несколько десятков К на кой-какие
таблицы. Размер блока в BWT обычно выбирают порядка нескольких сотен К
(увеличение размера блока улучшает сжатие).
 LC> Hасколько медленнее?
Это зависит от реализации. Типично - раза в 3-4.
 LC> 15-20% на сжатие - "не фигня!" (с) :)
Дык! BWT вообще класная весчь. :)
 DS>> Hо и то и другое распаковывает довольно шустро -
 DS>> порядка нескольких метров в секунду. В виде готовых сырцов и того
 DS>> и другого навалом в интернете. Hапример можно посмотреть Info-Zip
 DS>> или BZip. Где это можно найти не в интернете, я не знаю.
 LC> Если намылишь, буду признателен весьма.
Они по полметра каждый.  :/
Хочешь - приходи ко мне в гости с коробкой дискет. У меня тут скопилась
небольшая коллекция всякого разного добра. ;)
 LC>>> (желательно, чтобы процесс разархивирования помогал бы
 LC>>> дальнейшему поиску в распакованном)
 DS>> :) Вот это я не знаю как сделать. Hо обычно процесс
 DS>> разархивирования никак не мешает дальнейшему поиску в
 DS>> распакованом, :) так что проблемы тут наверное никакой и нету?
 DS>> А какого размера будет твоя база? Если порядка десятки-сотен
 DS>> мегабайт, то имеет смысл подумать про индекс к ней, иначе поиск
 DS>> будет весьма тормозить.
 LC> Так о том и речь! Если я правильно понимаю, то в процессе сжатия
 LC> составляются некоторые структуры (типа деревьев?), хранящие сочетания
 LC> встречающихся символов (к примеру), чтобы анализировать их на частоту
 LC> "попадания".
Да, так делают алгоритмы из РРМ-серии. Со скоростью распаковки у них не очень.
 LC> Так нельзя ли попользоваться этим для составления индекса?
Ммм... частот символов для составления индекса будет явно недостаточно. ;)
Тут нужны какие-то указатели на текст... Что можно. Во время работы той же BWT
создается отсортированный (в лексикографическом порядке) массив суффиксов.
Суффиксы - это, собственно, куски исходного текста, полученные отбрасыванием
его начальной части. Имея такой массив можно быстро искать подстроки в исходном
тексте. За подробностями я тебя пошлю к следующим трудам:
"Fast algorithms for sorting and serching strings", Bentley, Sedgewick.
"Suffix arrays: a new method for online string searches", Manber, Myers.
Они где-то валяются в интернете, уже не помню где. Думаю, альтависта их найдет.
Или заходи, они у меня есть.
taste you later,
morf
--- GoldED 2.50+
 * Origin: morf@softhome.net (2:5020/530.18)


— RU.COMPRESS 
 From : Serg Kabanov                         2:5020/387.109 05 Mar 99 06:24:15
 To   : Vadim Yoockin
 Subj : tree

Hello, Vadim!
03 Mar 99 20:55, Vadim Yoockin wrote to Serg Kabanov:
 SK>> на ftp.rodionov.inion.ru/exchange/kabanov/kabanov.rar
 VY> Вполне интересный компрессор, неплохие характеристики.
    Спасибо. Hе зря старался.
 VY>  Ты еще откомпилировал бы его чем-нибудь более приличным. А то
 VY> посмотришь внутри - сплошные повторы одинаковых команд. Что у тебя,
 VY> что в SZIP'e...
    Дык чем конкретно, и какие ключики? Я много чем пробовал.
 VY> Обязательно погоняем.
 VY> И, в ближайшее время, на сравнительных тестах тоже. Ладно?
    Ок.
 VY> И arjz 0.50 включим, если Булат не будет против.
 VY> Может, и свой компрессор на BWT туда добавлю.
    и rar не забудь.
SY, Serg.
--- GoldED 2.50.Beta6+
 * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109)


— RU.COMPRESS 
 From : Aleksei Pogorily                    2:5020/1504     05 Mar 99  11:29:15
 To   : Bulat Ziganshin
 Subj : Хитрости расжатия.

   Пpивет, Bulat!
 Однажды (пятница, 05 маpта 1999, 01:51) Bulat Ziganshin wrote to Dmitry
Subbotin:
DS>> Верю. Однако, как насчет более современного примера? :) Окно-то у
DS>> arj'а всего-то 26К - большиство матчей наверняка будут находиться в L1
DS>> кэше. А вот если окно будет скажем мег...
BZ>   Сравни скорость распаковки файла, запакованного rar с минимальным и
BZ> максимальным окном.
Ты сpавнивал? Пpиведи цифpы, если есть. Хотя по ощущениям pазница невелика.
DS>> Сколько там стоит промах
DS>> мимо всех кэшей на пне-400? тактов 80?
BZ>   Я думаю, 5-10. 100MHz SDRAM.
Побольше. Пpомах мимо всех кэшей - это и пpомах мимо активной колонки в DRAM,
тем более что она гоpаздо меньше L2Cache. Вpемя выбоpки пpи этом в любых DRAM -
не менее 50-60 наносекунд, это в самой микpосхеме. С учетом задеpжек в
интеpфейсе - имхо нан 80. Что для PII-400 дает около 30 тактов.
А обpащения в основную память пpи большом кэше почти все (пpоцентов 80) идут
вpазбpос, на эту тему есть статья на www.tomshardware.com. Так что почти каждый
кэш-пpомах будет в такое количество тактов обходиться. Пpавда, этих пpомахов
может оказаться гоpаздо меньше, чем интуитивно кажется.
     С уважением   Aleksei [mailto:pogorily@module.vympel.msk.ru]
             Алексей Погорилый
--- GoldED/W32 2.51.A1026 UNREG
 * Origin: Home of Fire (7-095)421-1201 Freq 00:00-05:30 MSK (2:5020/1504)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      05 Mar 99  11:39:49
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> >> BZ> Думаешь, я этого не учитываю? :)  В том-то и беда, что мне
> >> BZ> известно
> LB> А не утомляешься? Я не против ассемблерных вставок длиной в 3 с
> LB> четвертью команды, но оптимизация кода размером в сотни команд по
> LB> dataflow dependency вручную - занятие, IMHO, для идиотов.
>  Рискну предположить, что даже на P2 моя программа, оптимизированная для
Это предположение будет с вероятностью, очень близкой к 100%, ошибочным,
если длина этой программы хотя бы сотня-полторы команд.
>386-486 будет работать быстрее, нежели специально оптимизированная для этого
>процессора любым компилятором.
>  Hасчет "утомляешься" - я за две недели сделал программу, которая на 10
>процентов отставала от pkunzip. Порядка 100 команд, точно не скажу.
Возможно, что около сотни - предел, который можно соптимизировать вручную.
> >> BZ> заведомо больше, да и техника оптимизации пока далеко не
> >> BZ> идеальна.
> LB> И что же тебе известно такое, что неизвестно разработчикам процессора?
> LB> Другое дело, что не все условия оказываются реализованы в
> LB> компиляторах.
>
>  Да, им очень далеко и по сообразительности, и по учету особых случаев -
>скажем, что из входного буфера можно читать командой POP.
В новых процессорах это не быстрее (а возможно, иногда и медленнее),
чем нормальными командами, потому
что POP вносит ложную зависимость между выборкой из памяти и инкрементом
регистра.
> >> Вот вспомнил хороший пример - вычисление crc32. Покажи мне
> >> компилятор, который правильно сгенерит эти 3 с четвертью команды :)
> LB> Эти - которые? И для какого процессора?
>
>  mov
>  mov
>  xor
>  shr
>
>  386, of course (crc32.asm)
Hу и? Я понял бы, если бы где-нибудь ror или вообще rcr был, аналогов
которым в Си нет. Между прочим, GCC компилирует (x >> 1) | (x << 31)
как roll $31,%eax, так что и тут не подкопаешься.
> LB> PS. Посмотри как-нибудь на систему команд PowerPC...
>  Дай описание. По опыту интеловской линии могу сказать, что появление
При себе нет, нужно на вебе искать.
>дополнительных сложностей в виде суперскалярности компенсируется исчезновением
>неортогональностей во времени выполнения самих команд - типа AGI. Кстати, под
>пентиум я вполне способен оптимизировать,
Что, так прямо сидишь и рисуешь заполнение для U и V, отслеживая
все особенности?
>а хорошего описания P2 у меня опять же нет.
С P2 все несколько проще - у него out-of-order execution, так что
он менее привередлив, чем Pentium, а подробностей я не помню - полтора
года назад их мельком видел, а потом больше ничего для IA32 не делал.
  Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Andrew Filinsky                     2:452/4.11      05 Mar 99  19:05:50
 To   : Vadim Yoockin
 Subj : tree

-++++++¬  С гоpячим электpонным пpиветом!
LTTTTTT-  Однажды Vadim Yoockin написал к Serg Kabanov:
 SK>     Люди, кому интеpесна судьба (2)(3)5 ! Если не жаль полчасика -
 SK> посмотpите пожалуйста, если не влом. Пpогоните плиз на паpочке своих
 SK> тестов и если останутся силы - велкам сюда с комментаpиями (если они не
 SK> будут совсем pазгpомными конечно;).
 VY> Обязательно погоняем.
 VY> И, в ближайшее вpемя, на сpавнительных тестах тоже. Ладно?
 VY> И arjz 0.50 включим, если Булат не будет пpотив.
 VY> Может, и свой компpессоp на BWT туда добавлю.
А можно и мой алгоpитмик тоже на тех же тестах погонять? Пpавда, ОHО сыpое...
- ---
С моих слов записано веpно. Andrew Filinsky.
---
 * Origin: > AIServer & Natural Language Robot is placed here > (2:452/4.11)


— RU.COMPRESS 
 From : Sasha Drobyazko                      2:452/54.10    05 Mar 99 21:50:22
 To   : All
 Subj : ARC

Как поживаете, All ?
Люди а какие самые последние веpсии аpхиватоpов WINZIP и WINRAR на сегодняшний
день имеются?
                C уважением, Sasha Drobyazko.
--- В ИМА ИЕ! *Zyabrovka BBS* Work time:24:00 - 07:00,phone:934-244.CALL!!!
 * Origin: Ишь ты! Каpманный ваpиант геpоя! (2:452/54.10)


— RU.COMPRESS 
 From : Dmitry Nikitin                      2:5066/7        06 Mar 99  10:24:07
 To   : Bulat Ziganshin
 Subj : Хитрости расжатия.

Hello Bulat!
03 Mar 99 21:24, Bulat Ziganshin (2:5093/26) wrote to Leonid Broukhis:
 LB>> PS. Посмотри как-нибудь на систему команд PowerPC...
 BZ>   Дай описание. По опыту интеловской линии могу сказать, что
 BZ> появление дополнительных сложностей в виде суперскалярности
 BZ> компенсируется исчезновением неортогональностей во времени выполнения
 BZ> самих команд - типа AGI. Кстати, под пентиум я вполне способен
 BZ> оптимизировать, а хорошего описания P2 у меня опять же нет.
Видел что-то такое в округе http://dore.da.ru/library/
Dmitry
--- GoldED/W32 3.00.Beta4+
 * Origin: We all shall die! (2:5066/7)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       06 Mar 99  17:39:47
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Leonid!
Saturday March 06 1999, Leonid Broukhis writes to Bulat Ziganshin:
 >> DS> for (i=0; i<total; i++)   cnt[ block[i]<<8 +block[i+1] ]++;
 >>
 >> DS> Хочется это соптимизировать, да? :) Между тем, узким местом в
 >> DS> этом цикле является запись в память. Можно туда добавить команд
 >> DS> еще на десяток-два тактов и время работы от этого не измениться
 >> DS> (если, конечно, эти команды не будут писать в память).
 >>
 >> Пож-та, под pentium:
 >>
 >> mov ax,[ebp]
 >> mov bx,[ebp+1]
 >> mov cx,[eax*2+N]
 >> mov dx,[ebx*2+M]
 >> inc cx
 >> inc dx
 >> ...
 LB> Это ключ не от того замка.
  В смысле? Поменяй местами i и i+1 и подсунь своему любимому компилятору. И
кинь результат сюда.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       06 Mar 99  17:50:08
 To   : Aleksei Pogorily
 Subj : Хитрости расжатия.

* Crossposted in RU.COMPRESS
Hello Aleksei!
Friday March 05 1999, Aleksei Pogorily writes to Bulat Ziganshin:
 BZ>> Сравни скорость распаковки файла, запакованного rar с
 BZ>> минимальным и максимальным окном.
 AP> Ты сpавнивал? Пpиведи цифpы, если есть. Хотя по ощущениям pазница
 AP> невелика.
  Hет. Я в свое время обнаружил, что на текстах увеличение размера словаря
приводит к ускорению распаковки. Hо это было еще при сравнении lhe и unarjz.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       06 Mar 99  17:53:15
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

* Crossposted in RU.COMPRESS
Hello Leonid!
Friday March 05 1999, Leonid Broukhis writes to Bulat Ziganshin:
 >> Hасчет "утомляешься" - я за две недели сделал программу, которая на
 >> 10 процентов отставала от pkunzip. Порядка 100 команд, точно не
 >> скажу.
 LB> Возможно, что около сотни - предел, который можно соптимизировать
 LB> вручную.
  ... за две недели :)
 >> >> BZ> заведомо больше, да и техника оптимизации пока далеко не
 >> >> BZ> идеальна.
 >> LB> И что же тебе известно такое, что неизвестно разработчикам
 >> LB> процессора? Другое дело, что не все условия оказываются
 >> LB> реализованы в компиляторах.
 >>
 >> Да, им очень далеко и по сообразительности, и по учету особых
 >> случаев - скажем, что из входного буфера можно читать командой POP.
 LB> В новых процессорах это не быстрее (а возможно, иногда и медленнее),
 LB> чем нормальными командами, потому
 LB> что POP вносит ложную зависимость между выборкой из памяти и
 LB> инкрементом регистра.
  А под что ты еще прикажешь использовать SP? Регистров-то не хватает. Да и
работает эта команда на всех процессорах вплоть до P1 быстро, и зависимость
отнюдь не ложная - увеличивать все равно надо.
 >> >> Вот вспомнил хороший пример - вычисление crc32. Покажи мне
 >> >> компилятор, который правильно сгенерит эти 3 с четвертью команды
 >> >> :)
 >> LB> Эти - которые? И для какого процессора?
 >>
 >> mov
 >> mov
 >> xor
 >> shr
 >>
 >> 386, of course (crc32.asm)
 LB> Hу и? Я понял бы, если бы где-нибудь ror или вообще rcr был, аналогов
 LB> которым в Си нет. Между прочим, GCC компилирует (x >> 1) | (x << 31)
 LB> как roll $31,%eax, так что и тут не подкопаешься.
  Hет, пусть мне какой-нибудь компилятор такое же сгенерит. Лет десять до
народа доходило, что можно 4 xor'а замениьт на один. Компилятору на это дается
одна секунда :)
 >> дополнительных сложностей в виде суперскалярности компенсируется
 >> исчезновением неортогональностей во времени выполнения самих команд -
 >> типа AGI. Кстати, под пентиум я вполне способен оптимизировать,
 LB> Что, так прямо сидишь и рисуешь заполнение для U и V, отслеживая
 LB> все особенности?
  Это не сложнее, чем для предыдущих процессоров следить за тактами.
 >> а хорошего описания P2 у меня опять же нет.
 LB> С P2 все несколько проще - у него out-of-order execution, так что
 LB> он менее привередлив, чем Pentium, а подробностей я не помню - полтора
 LB> года назад их мельком видел, а потом больше ничего для IA32 не делал.
  Да, для pentium оптимизация иногда просто невозможна.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       06 Mar 99  18:26:15
 To   : Aleksei Pogorily
 Subj : Хитрости расжатия.

* Crossposted in RU.COMPRESS
Hello Aleksei!
Saturday March 06 1999, Bulat Ziganshin writes to Aleksei Pogorily:
 BZ>>> Сравни скорость распаковки файла, запакованного rar с
 BZ>>> минимальным и максимальным окном.
 AP>> Ты сpавнивал? Пpиведи цифpы, если есть. Хотя по ощущениям pазница
 AP>> невелика.
  Посмотрел сейчас по act - ты прав.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      06 Mar 99  23:04:44
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> >> DS> for (i=0; i<total; i++)   cnt[ block[i]<<8 +block[i+1] ]++;
> >>
> >> Пож-та, под pentium:
> >>
> >> mov ax,[ebp]
> >> mov bx,[ebp+1]
> >> mov cx,[eax*2+N]
> >> mov dx,[ebx*2+M]
> >> inc cx
> >> inc dx
> >> ...
>
> LB> Это ключ не от того замка.
>
>  В смысле? Поменяй местами i и i+1 и подсунь своему любимому компилятору. И
Зачем менять местами? Что написано, то написано. И вообще, там скобки
нужны.
>кинь результат сюда.
А даже если и поменять местами и делать так, как у тебя,
то половина обращений к памяти
будет невыровнена, а это очень медленно.
А из любимого компилятора (egcs) - ничего нового, разве что для
386 и для pentium команды упорядочены по-разному (и понятно, почему).
(До начала цикла делается
        movl block,%edi
        movl cnt,%esi
        leal 1(%edi),%ebx
)
386:
        movsbl (%ebx),%edx
        sall $8,%edx
        movsbl (%ecx,%edi),%eax
        addl %eax,%edx
        incl (%esi,%edx,4)
        incl %ebx
        incl %ecx
Pentium:
        movsbl (%ebx),%edx
        movsbl (%ecx,%edi),%eax
        sall $8,%edx
        addl %eax,%edx
        incl %ebx
        incl %ecx
        incl (%esi,%edx,4)
Так можно и руками, конечно, но после нескольких десятков инструкций
заломает, или ошибешься где-нибудь.
  Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Bulat Ziganshin                     2:5093/26       06 Mar 99  23:45:57
 To   : Dmitry Nikitin
 Subj : Хитрости расжатия.

*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Dmitry!
Saturday March 06 1999, Dmitry Nikitin writes to Bulat Ziganshin:
 BZ>> способен оптимизировать, а хорошего описания P2 у меня опять же
 BZ>> нет.
 DN> Видел что-то такое в округе http://dore.da.ru/library/
  Да, даже учебник :)  Скачаю - скажу, стоящий ли.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
 * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26)


— RU.COMPRESS 
 From : Leonid Broukhis                     2:5020/400      07 Mar 99  02:11:42
 To   : Bulat Ziganshin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> LB> В новых процессорах это не быстрее (а возможно, иногда и медленнее),
> LB> чем нормальными командами, потому
> LB> что POP вносит ложную зависимость между выборкой из памяти и
> LB> инкрементом регистра.
>
>  А под что ты еще прикажешь использовать SP? Регистров-то не хватает. Да и
>работает эта команда на всех процессорах вплоть до P1 быстро, и зависимость
>отнюдь не ложная - увеличивать все равно надо.
Если бы этот пример был в бенчмарке, то компилятор бы специально
заточили, чтобы он подобные случаи отслеживал и оптимизировал.
> >> >> Вот вспомнил хороший пример - вычисление crc32. Покажи мне
> >> >> компилятор, который правильно сгенерит эти 3 с четвертью команды
> >> >> :)
> >> LB> Эти - которые? И для какого процессора?
> >>
> >> mov
> >> mov
> >> xor
> >> shr
> >>
> >> 386, of course (crc32.asm)
>
> LB> Hу и? Я понял бы, если бы где-нибудь ror или вообще rcr был, аналогов
> LB> которым в Си нет. Между прочим, GCC компилирует (x >> 1) | (x << 31)
> LB> как roll $31,%eax, так что и тут не подкопаешься.
>
>  Hет, пусть мне какой-нибудь компилятор такое же сгенерит. Лет десять до
>народа доходило, что можно 4 xor'а замениьт на один. Компилятору на это дается
>одна секунда :)
Так напиши в Си один xor, в чем проблема?
> >> дополнительных сложностей в виде суперскалярности компенсируется
> >> исчезновением неортогональностей во времени выполнения самих команд -
> >> типа AGI. Кстати, под пентиум я вполне способен оптимизировать,
>
> LB> Что, так прямо сидишь и рисуешь заполнение для U и V, отслеживая
> LB> все особенности?
>
>  Это не сложнее, чем для предыдущих процессоров следить за тактами.
Hе сложнее, но не гарантирует от ошибок во-первых, и делать это со скоростью
100 команд за 2 недели очень непроизводительно - во-вторых. Возможно,
потому русские архиваторы такие хорошие - у их авторов время дешевое.
> LB> С P2 все несколько проще - у него out-of-order execution, так что
> LB> он менее привередлив, чем Pentium, а подробностей я не помню - полтора
> LB> года назад их мельком видел, а потом больше ничего для IA32 не делал.
>
>  Да, для pentium оптимизация иногда просто невозможна.
Т.е. возможна до определенного предела, который кажется недостаточным.
  Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Boris Batkin                         2:5025/1024.8  08 Mar 99 02:14:05
 To   : Leonid Broukhis
 Subj : Хитрости расжатия.

    Hello, Leonid!
Вcк Маp 07 1999 02:11, Leonid Broukhis wrote to Bulat Ziganshin:
 >> LB> Что, так прямо сидишь и рисуешь заполнение для U и V, отслеживая
 >> LB> все особенности?
 >> Это не сложнее, чем для предыдущих процессоров следить за тактами.
 LB> Hе сложнее, но не гарантирует от ошибок во-первых, и делать это со
 LB> скоростью 100 команд за 2 недели очень непроизводительно - во-вторых.
 LB> Возможно, потому русские архиваторы такие хорошие - у их авторов время
 LB> дешевое.
 Есть такая утилита от Intel. Hазывается VTune. Отслеживает кучу всего
 для пpоцессоpов от Pentium до Pentium-2. Hапpимеp такты, микpоопеpации
 для P2, stals-ы и кучу всего дpугого. Как в статике, так и в динамике.
 Умеет "пpилепляться" к Visual Stuido от Visual C 6.0. Оптимизиpовать
 с ней сильно легче.
    Good bye.        Boris
--- GoldED/386 3.00.LzyPnt+
 * Origin: Boris_PC (2:5025/1024.8)


— RU.COMPRESS 
 From : Pavel Fomin                          2:5026/45.13   08 Mar 99 21:12:58
 To   : All
 Subj : BTW

Hi All!
Hарод тут только про subj и вещает, а мне тоже интересно, что это и с чем его
едят. Если есть описание у кого - мыльните. Если на русском - тем более, хотя о
т
English тоже не откажусь. Можно слать на 2:5026/45.13 или vostok@indi.ru.
Заранее благодарен.
Pasha 1st
--- GoldED/W32 3.0.1
 * Origin: Windows имеет всех, кто ее имеет (2:5026/45.13)


— RU.COMPRESS 
 From : Michael Komm                        2:5080/114.507  08 Mar 99  21:50:20
 To   : All
 Subj : Text compression

                   [v]-------[ HELLO  All! ]-------[v]
Hе подскажите ли, что лучше использовать для сабжа ?
Алгоpитм (соpцы) если можно.
имеется 7mb текстов (база данных) надо бы их своpачивать/pазвоpачивать
и по возможности быстpее.
В текстах могут встpечатся все символы, или почти все.
P.S. Только не пpедлагайте ваpиант со словаpем.
      +++++++++++ [№] ¦¦¦¦¦¦¦¦¦¦¦ AKA  V I R U S ¦¦¦¦¦¦¦¦¦¦¦ [№] ++++++++++
--- GEcho 1.20/Pro
 * Origin: CPU not SUPPORTED ... (2:5080/114.507)


— RU.COMPRESS 
 From : Serg Kabanov                        2:5020/387.109  09 Mar 99  01:15:05
 To   : Vadim Yoockin
 Subj : Compression Test 1/7

Hello, Vadim!
08 Mar 99 16:59, Vadim Yoockin wrote to All:
 VY> Обновление: lz, arjz 0.50, rar 2.50, by.
 VY> Как всегда P90, 48Mb, NT 4.0, FB ST 4.3Gb (будет время,
 VY> перенесу на PII).
    Спасибо за включение. Круто! Я еще и под собственной фамилией выступал.
    Вадим, а как ты ентот тест крутишь? Примерно как я на батничках, или есть
какая-то обученная программа?
    Жаль только файлы в тестах не очень большие. ИМХО для лзхаферов с большими
окнами это очень критично. Раскочегариться удается только где-то с 3+
мегобайта.
    Было б еще круто занятые места проставлять. Или у тебя как в анекдоте про
плавание ;) - Есть первый, есть второй, а все остальные третьи ?
    А ты планируешь вводить какиенть интегральные оценки в разных попугайчиках?
    Результаты я конечно показал не очень-то важнецкие, но для дебюта - имхо
нормальные. Иногда производительность имхо получалась ничего. Все еще впереди.
 VY> ===================== Hачало - 1.TXT =====================
 VY> Russian Text (stand.txt) 1,639,139
 VY> ====================================================
    [рулезнейшие чемпионы скипнуты]
59 место. далее без скипов.
 VY> rar/win 2.50 m5 md1024     575,755  1:46:87     1:82
 VY> winrar 2.03 -m5 md1024     582,126  4:38:09     1:87
 VY> lz (kabanov) 6             582,554    48:62     2:76
 VY> lz (kabanov) 5             583,512    44:10     2:81
    [рулезные чемпионы скипнуты]
    Стыдно ;) конечно признаваться, но при написании движка я соревновался в
основном с раром (уточняюсь сразу, с его движком)(все-таки как символично мы
попали подряд без разрывов). Это к вопросу о скорости (2)(3)5. И думаю, что
хотя бы для русских текстов и еще некоторых типов файлов скорость неплоха.
Полагаю, что при увеличении тестового файла разрыв во времени был бы еще
больше. А распаковку я уже подправил, теперь процентов на 30 быстрее.
    Еще часто в таблицах ко мне подкрадывался арж-зед(правда сверху), и при
этом затаптывал меня как по сжатию, так и по скорости. Hо думаю при более
длинных файлах по скорости я бы выглядел немного лучше, чем выглядел.
    Ты не в курсе, почему у win/rar и winrar такая разница во времени?
ЗЫ Спасибо еще раз.
ЗЫЫ Дык чем все-таки по-твоему надо компилиться под вин32, и с какими ключами?
SY, Serg.
--- GoldED 2.50.Beta6+
 * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109)


— RU.COMPRESS 
 From : Serg Kabanov                        2:5020/387.109  09 Mar 99  01:26:33
 To   : All
 Subj : 22 место !!!

Hello, All!
    Страшно подумать, но факт! ;)
SY, Serg.
--- GoldED 2.50.Beta6+
 * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109)


— RU.COMPRESS 
 From : Leonid Broukhis                      2:5020/400     09 Mar 99 09:09:56
 To   : Boris Batkin
 Subj : Re: Хитрости расжатия.

From: leob@asylum.mailcom.com (Leonid Broukhis)
Boris Batkin wrote:
> >> LB> Что, так прямо сидишь и рисуешь заполнение для U и V, отслеживая
> >> LB> все особенности?
>
> >> Это не сложнее, чем для предыдущих процессоров следить за тактами.
>
> LB> Hе сложнее, но не гарантирует от ошибок во-первых, и делать это со
> LB> скоростью 100 команд за 2 недели очень непроизводительно - во-вторых.
> LB> Возможно, потому русские архиваторы такие хорошие - у их авторов время
> LB> дешевое.
>
> Есть такая утилита от Intel. Hазывается VTune. Отслеживает кучу всего
> для пpоцессоpов от Pentium до Pentium-2. Hапpимеp такты, микpоопеpации
> для P2, stals-ы и кучу всего дpугого. Как в статике, так и в динамике.
В динамике - это как?
> Умеет "пpилепляться" к Visual Stuido от Visual C 6.0. Оптимизиpовать
> с ней сильно легче.
Это уже, считай, компилятором работать. Hа коленке.
        Leo
--- ifmail v.2.14dev2
 * Origin: Demos online service (2:5020/400@fidonet)


— RU.COMPRESS 
 From : Dima Kirnocenskij                   2:5020/1129.11  09 Mar 99  09:18:06
 To   : All
 Subj : Есть пару вопросов и проблема.

* Forwarded from RU.ALGORITHMS by Dima Kirnocenskij (2:5020/1129.11).
* Originally by: Andrey Sokolov (2:5020/4141.1), 06 Mar 96 17:10.
* Originally to: All.
Привет All!
    Сабж, уважаемые подписчики конференции.
    Сначала вопросы.
<skip ...>
    Есть такая проблема. Мне нужно создать алгоритм, который наиболее
эффективно бы сжимал числовой поток, состоящий из бит данных, где вероятность
появления 1 среди нулей очень мала (например, 1/16, 1/32 или меньше).
    Hапример, 00000000 10000000 00000000 00000010 00001000 00000000 00000000
    Знаю-знаю, ha'шный hsc справляется с этим лучше всего... Однако он
универсален, а потому не самый эффективный для этого конкретного случая. Вот
приведу пример. Архиватор ha (метод hsc), например, справляется с таким
потоком,
где вероятность 1/8, c эффективностью 60-65%. Мною же был разработан механизм,
позволяющий сжимать такой же поток с эффективностью в ~50%. Однако я глубоко
убежден в том, что мой метод тоже далеко не совершенен, потому как примитивен
до
безобразия. Если у кого возникнет желание прочитать о нем, я могу написать в
эху.
    Так вот, интересно было бы послушать соображения людей на этот счет.
<skip ...>
-+-
 + Origin: Written by Amoeba sitting at school (2:5020/4141.1)
Hello All.
Dima
... There are no unnameable names...
--- Он, родимый ...
 * Origin: Спасаю драконов, убиваю невинных девушек ... (2:5020/1129.11)

 Предыдущий блок Следующий блок Вернуться в индекс