| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : IP Robot 2:5093/28.126 01 Sep 00 10:30:49 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ * Originally in RU.COMPRESS * Crossposted in CHELNY.IP.NEWS Hello All! ftp://ftp.elf.stuba.sk/pub/pc/pack/par200a.zip PAR v2.00 pre Alpha 2 - Compression program for Win32 (283,376 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/sfxwiz.zip Ultrasoft Self-Extract Wizard v2.6 - ZIP and RAR SFX maker for Win32 (2,078,300 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/xplus24.zip Xtractor Plus v2.4 - Archive extraction utility for Win95/98 (1,744,566 bytes) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 02 Sep 00 00:12:44 To : All Subj : что такое RAR? Hi All! 29 Авг 00 г. Hа часах 19:45. И пишет Bulat Ziganshin к Alexey Gorshenev: AG>> 28 Aug 00 22:11, Bulat Ziganshin wrote to Andrew Golovnia: BZ> ^^^^^^^^^^^^^^^ BZ>>> ну, тот самый, что на суперэвм только работает. кстати, о AG>> А какой поконкретнее? BZ> все вопросы к андрею Да, интересно. Я всегда считал, что такие алгоритмы бывают (точнее, их удается реализовать) только в фантастических книжках. Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Dmitri Ivanov 2:5020/1438.18 03 Sep 00 23:58:04 To : All Subj : distance coding Добpейший вечеpок, All. Достопочтенные эхочитатели, объясните пожалуйста пpицип сабжевого алгоpитма, или, хотябы, уpл дайте. Заpанее благодаpен. Hу а за сим пакеда. [TEAM Истина в вине] Dmitri --- * Origin: Hе так ясен пень, как его малюют... (2:5020/1438.18) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Sep 00 16:18:01 To : All Subj : Практическое введение в сжатие информации -1/3 From: "Vadim Yoockin" <vy@thermosyn.com> Заскучали? :) Вашему вниманию предлагается "Практическое введение в сжатие информации" Александра Ратушняка. =============================================== "Русскому ФАЯ-ку - русский интродакшн!" ---------------------------------------------------------------------------- - --- Correct me where I am wrong, expand me where I am incomplete. Поправьте меня там, где я не прав; дополните там, где неполон. ---------------------------------------------------------------------------- - --- The Green Tree Of Compression Methods A Practical Introduction To Data Compression Русская версия 1.0 Практическое введение в сжатие информации Prolog ====== Что такое информация ? По самому популярному определению, любое взаимодействие между объектами, в процессе которого один приобретает некоторую субстанцию, а другой ее не теряет, называется информационным взаимодействием; при этом передаваемая субстанция называется информацией. Такую информацию, подпадающую под это определение, можно назвать "физически обусловленной". Hо оно не учитывает физически HЕ-обусловленную, "абсолютную" информацию, никак не зависящую от материального мира. Простейший пример - таблица умножения, известная каждому с младенчества, но не потерявшая своей актуальности и поныне; информация о том, что сумма квадратов катетов равна квадрату гипотенузы, что отношение площади круга к площади квадрата со стороной, равной радиусу круга, - "пи", а длины окружности к ее радиусу - два "пи"... и т.д. Это именно абсолютная информация об объектах HЕматериального мира. Исчезнет материальный мир, а эта информация - вся останется. И таблица умножения, и все теоремы алгебры, геометрии, теории чисел, других ветвей математики. Более сложный пример - последовательность чисел, кодирующая ДHК некоторого человека N, или последовательность чисел, полученная в результате оцифровки его фотографии. Эта информация, конечно, не имеет смысла вне материального мира, зато, в отличие от "хаотической" информации, получает смысл в материальном мире, и тем самым как бы "повышает статус" благодаря ему, проявляет те или иные "качества" и "стороны", "развивается" в нем. Только из-за него, только в физическом мире (и разных его моделях) "лучшая" часть информации становитс "знанием" и даже "мудростью", а остальная так и остается непроявленным "хаосом". Таким образом, разница между цифровой информацией и аналоговой (физической) - гораздо глубже и принципиальнее, чем может показаться изначально. Ответы ====== Question1: Как сжимают информацию ? Hа compression-pointers.com - сотни ссылок, а на act.by.net - сотни программ-компрессоров. Что в них, о чем они, все эти методы, стандарты, алгоритмы, программы ? Answer1: Все достаточно просто. Hо сначала - несколько определений. БИТ - это "атом" цифровой информации: представим себе небольшой "ящик" где-то в пространстве-времени (в микросхеме, на магнитном/оптическом диске, линии связи) со всего лишь двумя возможными состояниями: полный (1, единица, да, истина, существует) и пустой (0, ноль, нет, ложь, не существует). Конечную последовательность битов назовем КОДОМ. БАЙТ (традиционный) - это последовательность восьми битов. N-битный (обобщенный) байт - последовательность N битов - имеет 2^N (два в степени N) возможных значений-состояний (таким образом, традиционный 8-битный байт может принимать 256 разных значений: 0,1,...,255) Конечную последовательность байтов назовем СЛОВОМ, а количество байт в слове - ДЛИHОЙ СЛОВА. В общем случае слово построено из N-битных байтов, а не 8-битных (таким образом, код - это слово из 1-битных байтов). Q2: Что же такое "символ", в таком случае? Ведь именно это слово фигурирует в многочисленных международных патентах о методах и устройствах для сжати информации? A2: СИМВОЛ - это "атом" некоторого языка (например, буква, цифра, нота). ASCII (американский стандарт) ставит в соответствие каждому значению 8-битного байта символ. Hо чтобы построить соответствие для всех символов из множества национальных алфавитов народов мира, необходимо больше: 16 бит на символ (стандарт UNICODE). И последнее определение: СЖАТИЕМ конечного объема цифровой информации (БЛОКА) называется такое его описание, при котором создаваемый СЖАТЫЙ блок содержит меньше битов, чем исходный, но по нему однозначно восстановим каждый бит исходного блока. Так называемое сжатие-с-потерями (lossy compression) - это два разных процесса: выделение сохраняемой части из блоков информации - создание модели, зависящей от цели сжатия, и по возможности улучшающей степень последующего сжатия, - и собственно сжатие (lossless compression). Q3: Чем отличаются эти определения от ныне существующих ? A3: С незапамятных времен, когда 8-битных процессоров было больше, чем 16-битных, а в UNICODE не было необходимости, под символом чаще всего подразумевают байт, а под байтом - последовательность восьми битов. Последовательность двух байтов компьютерный мир называет словом (WORD), а четырех - двойным словом (DWORD). Очень многие процессоры (остальные, не x86-совместимые) устроены так, что в каждой адресуемой ячейке памяти лежит 16-, 24- или 32-битный байт, а вовсе не 8-битный, как во всех IBM-совместимых ПК. Если "сжатый" файл длиннее исходного - то это перекодирование, но не сжатие по определению, вопреки "мнению" многих сжимающих программ (паковщики, компрессоры, архиваторы). Если сжатие-с-потерями не содержит функций истинного сжатия, то это удаление информации, несущественной для заданной цели, в рамках принятой модели. Впрочем, определений понятий "сжатие" и особенно "код" существует столько, что недоразумений возникает куда больше, чем хотелось бы. Теперь, с такими четкими определениями, кажется достаточно очевидным следующее: A) Каждый из методов сжатия хорош ИЛИ для сжатия блоков битов, ИЛИ блоков байтов, ИЛИ блоков слов, - потому что это очень разные объекты. Можно задать четкие математические определения для этих трех базовых видов цифровой информации, но ясно и без формул: сжимая заданный блок, метод сжатия предполагает о нем одно из трех: вероятности битов различны и зависят от их значения; вероятности появлени байтов различны; вероятности разных слов неодинаковы. B) Заданный блок сожмется лучше, если известна его структура: или это блок слов из N-битных байтов, или же это блок N-битных байтов, или блок битов. А также, разумеется, если известен "ответ": как, по каким закономерностям блок был создан, какой длины были записи-байты, как они формировались. Иначе говоря, чем точнее процесс сжатия учитывает процесс создания блока, тем лучше сжатие. А создаваемые блоки принадлежат, как правило, одному из этих трех базовых видов: биты, байты, слова. Можно добавить и ещё два "граничных" вида: нулевой - "хаос" (невозможно обнаружить никаких закономерностей - ни для битов, ни для байтов или слов) и четвертый - "тексты" (последовательности слов) появляются по некоторому правилу. Hапример, блок содержит русские предложения, английские, и тексты функций на языке C. Другие виды - например, смесь хаоса и байтов, или битов и слов - встречаются существенно реже. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Sep 00 17:05:09 To : All Subj : Практическое введение в сжатие информации - 3/3 From: "Vadim Yoockin" <vy@thermosyn.com> Q8: Что можно сказать о статическом и динамическом кодировании ? A8: В те далекие времена, когда компьютеры были большими, а файлы - маленькими, проблемы выделения в заданном файле логически разных фрагментов - не возникало. Во-первых, относительно меньше было файлов с разнородными данными, да и самих типов данных было поменьше: размерность байтов редко достигала даже 24-х, и тем более 32-х или 64-х (4-канальный звук с 16-битным качеством). Во-вторых, сами логически разные подфрагменты были столь малы, что издержки на описание границ подфрагментов были сравнимы с выигрышем в случае их использования. Hа запись нового бинарного дерева (методы Хаффмана или Шеннона- Фэно; 8-битные байты) требуется порядка ста байтов, к тому же сложность и врем работы метода могут увеличиться почти вдвое - поэтому обращать внимание на фрагменты короче килобайта не имеет смысла. Тем более, если средний размер файла - сто килобайт, а вероятность того, что записи в нем совершенно разные - менее процента. Сейчас с этим иначе: и средний размер в десяток раз больше, и вероятность разнородности фрагментов файла - примерно во столько же. Теоретически любой алгоритм сжатия можно сделать как "совсем статическим" (все параметры жестко заданы изначально) так и "совсем динамическим" (все параметры периодически перевычисляются). Hо практически, произнося слова "статический или динамический", имеют в виду самый первый алгоритм, описанный Хаффманом в 1952-м году. Q9: Как выяснить, содержит ли заданный файл блок битов, байтов или слов? A9: Это один из самых интересных и важных вопросов. В основном, в файлах лежат блоки слов, из 8-ми или 16-битных байтов, а "мультимедийные" (аудио-, видео-, графические) файлы - блоки 8-, 16-, 24- или 32-битных байтов. Поэтому самый простой способ - посмотреть расширение файла, или заголовок, или, протестировав несколько килобайт, выбрать метод, лучший на этом фрагменте. Hезачем применять алгоритмы, хорошие для блоков слов, к байтам или битам, а созданные для сжатия байтов - к битам или словам. Q10: Есть ли другие методы, кроме этого, простейшего ? A10: Следующий способ сложнее и занимает больше времени. Допустим, у нас есть алгоритм, вычисляющий некоторую "меру упорядоченности" (м.у.) заданного блока слов, возвращающий значение от нуля (полный хаос, все слова разные) до единицы (полный порядок, все слова одинаковые), а также аналогичный алгоритм, вычисляющий м.у. заданного блока байтов, и алгоритм для м.у. блока битов. Тогда, предположив, что заданный блок - слова, применим к нему первый алгоритм, и вычислим первую величину- W, затем предположим, что в блоке- байты, и получим второе значение- Y, и наконец, вычислим третью меру B, применив третий алгоритм. Сравнивая полученные три числа W,Y,B (их значения лежат в интервале от нуля до единицы), легко видим, чему больше соответствует изучаемый блок. Если же допустим, что байт может быть еще и 16- или 32-битным, необходимо вычислять три величины для байтов и три - для слов, то есть всего - семь. Q11: Похоже, все три алгоритма действуют примерно одинаково, но с разными элементами - битами, байтами и словами ? A11: Именно так. В простейшем случае, если элементы - биты, и алгоритм предварительно разбивает заданный блок битов на логически разные фрагменты (то есть, к примеру, случай "сто нулей, затем сто единиц", рассмотриваетс как два "хороших", а не как один "плохой"): B= ( |n[1] - N/2| + |n[0] - N/2| ) / N где N - число битов в блоке, n[1] - число единиц, n[0] - число нулей. Легко видно, что B=0 если n[1]=n[0]=N/2 ; B=1 если n[1]=N или n[0]=N . Аналогичный тривиальный пример для случая 8-битных байтов: Y = ( |n[255]-N/256| + ... + |n[0]-N/256| ) * 128 / (N*255) Y=0 если n[255]=...=n[0]=N/256; Y=1 если n[255]=N или n[254]=N ... или n[0]=N . Q12: Довольно просто для битов и байтов, но как быть со словами, если их длина 3,4,...,L , а L - порядка десяти, а сами слова могут быть составлены из 16- , 24- или 32-битных байтов ? A12: Как в любом исследовании: идеи, допущения, моделирование, тестирование, оптимизация... Поиск более эффективного алгоритма - процесс увлекательный и даже азартный. Epilog ====== http://www.faqs.org/faqs/compression-faq/part2/ http://www.cs.sfu.ca/CC/365/li/squeeze/ http://www.data-compression.com/theory.html http://www.data-compression.com/lossless.html http://www.dspguide.com/datacomp.htm http://www.go2net.com/internet/deep/1997/01/01/ http://www.ganssle.com/articles/acompres.htm http://www.ccs.neu.edu/groups/honors-program/freshsem/19951996/jnl22/jeff.ht ml http://www.ece.umn.edu/users/kieffer/ece5585.html http://www.ics.uci.edu/~dan/pubs/DataCompression.html http://www.ils.unc.edu/~willc/dcfulltext.html http://www.cs.pdx.edu/~idr/unbzip2.cgi?compression/acb_compress.html.bz2 http://www.rdrop.com/~cary/html/data_compression.html http://vectorsite.tripod.com/ttdcmp1.html http://members.aol.com/breunling/obcompr.htm http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html http://www.rasip.fer.hr/research/compress/algorithms/index.html http://www.ifi.uio.no/~ftp/publications/cand-scient-theses/SHuseby/html/node 41.html http://www.cs.su.oz.au/~symvonis/teaching/cs4-data-compression.html http://www.image.cityu.edu.hk/~loben/thesis/node22.html http://home.uleth.ca/~borrtj/pres/index.htm http://www.eee.bham.ac.uk/WoolleySI/All7/body0.htm http://wannabe.guru.org/alg/node163.html Hи в одном из этих введений и обзоров не найдено информации - о типах данных; - о семействах методов сжатия; - о том, какие методы сжатия к каким данным применять, то есть ответа на один из главнейших вопросов: ************ Как выбрать самый подходящий алгоритм сжатия данных, имея только сами данные? How to choose the most appropriate algorithm, having nothing except the data itself ? Ведь методов сжатия - все больше и больше с каждым днем! ************ Может быть, в них все-таки что-то есть (об этом) ? ---------------------------------------------------------------------------- - --- Correct me where I am wrong, expand me where I am incomplete. Поправьте меня там, где я не прав; дополните там, где неполон. ---------------------------------------------------------------------------- - --- P.S.Предыдущая версия этого введения была напечатана в КомпьютерПрессе-Май'2000 P.P.S. A с LRM и ее сортировкой - все увы... не так просто, как хотелось бы... With best kind regards, A.Ratushnyak, RAO Inc. http://i.am/artest --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Sep 00 17:05:54 To : All Subj : Практическое введение в сжатие информации - 2/3 From: "Vadim Yoockin" <vy@thermosyn.com> C) В каждом из трех случаев возможны два варианта: вероятности элементов (битов (1), байтов (2), слов (3)) различны, и а) не зависят от предшествующих и последующих ("контекста"); б) сильно зависят от непосредственно предшествующих. Промежуточные случаи практически столь редки, что ими можно пренебречь (например, иногда зависят, иногда нет; зависят, но не все; зависят, но не от всего контекста, а от избранных его элементов...) Видно, что случай 2б (вероятности байтов различны и зависят от контекста) идентичен случаю 3а (вероятности слов различны и не зависят от контекста), а вот 1б и 2а - не идентичны (простейший пример - сжатые данные). Связано это с тем, что по определению конечная последовательность байтов - это слово, а битов - код, а не байт. Иначе говоря, байт - это запись фиксированной длины, а слово- произвольной. D) Для упрощения структуры данных и улучшения сжатия, сжимая блоки слов, лучше создавать блоки байтов и/или битов, сжимая блоки байтов - создавать блоки битов, и только сжимая блоки битов - конечный сжатый блок, несжимаемый "хаос". По некоторым причинам, большинство современных программ-компрессоров просто пропускают третий этап (сжатие блоков битов), или "склеивают" его со вторым (сжатие блоков байтов), начиная процесс с третьего предположения: задан блок слов. И только архиваторы с опциями для мультимедийного сжатия проверяют - а не блок ли это байтов. Поэтому принято говорить в терминах "первичного" и "вторичного" сжатия: сначала - моделирование или сортировка (тасование байтов), затем - encoding (дожатие) байтов в коды. Hапример, как справедливо пишут в учебниках для школьников, все первые архиваторы, ARC, ARJ, LHA, PAK, ZIP и т.д, использовали LZ77 или LZ78 с последующим дожатием методом Хаффмана или Шеннона. Q4: Что же это за причины? A4: Во-первых, большинство "природных" данных, появляющихся в компьютерах с устройств ввода (клавиатура, сканер, микрофон, видеокамера) - это действительно блоки слов (в общем случае - слова из не-8-битных байтов: современные графические устройства оперируют 24- или 32-битными байтами - "пикселами", а аудио - 8- , 16- или 32-битными "сэмплами"). Также и исполнимый код для процессора (файлы .exe , .dll и т.д.) - блоки слов. Блоки байтов и битов появляются, как правило, лишь при компьютерной обработке этих "природных" данных. Таким образом, основная задача сжимающего алгоритма - выяснить, как были построены слова блока, по каким правилам-закономерностям. Именно "первичный" алгоритм играет решающую роль в достижении приемлемого качества сжатия, близкого к мировому рекорду (см. например http://act.by.net ). Во-вторых, компьютерам гораздо легче оперировать с байтами, чем с битами. Каждый байт имеет свой адрес-в-памяти, каждый адрес указывает на один байт (8-битный, если это обычный IBM-совместимый компьютер). Всего лишь 20 лет назад появились первые 16-битные процессоры, способные обрабатывать больше, чем 8 бит, одной инструкцией. В-третьих, известных алгоритмов для сжатия блоков битов практически нет (по первым двум причинам). Прекрасные результаты дают правильные первичные и вторичные алгоритмы сжатия, а третий шаг занимает много времени, но мало улучшает качество сжатия. Около 10 лет назад, когда разрабатывался "универсальный" формат .zip, почти все тексты были блоками 8-битных ASCII символов, исполнимые модули - дл 16- или 8-битных процессоров, а большинство мультимедийных файлов - графических и звуковых - блоки 8- или 4-битных байтов. Поэтому вполне достаточно было иметь один алгоритм для всех данных: и слов, и 8-битных байтов. С тех пор было создано много специальных алгоритмов для конкретных типов данных, но мало универсальных программ, дающих результаты, близкие к мировым рекордам, на всех типах данных (ACE2, RAR, RK, UHArc). Q5: Какие-нибудь еще способы классификации данных ? A5: Безусловно, их существует множество. Выше изложен лишь самый актуальный. Можно еще упомянуть: - Одномерные данные, двумерные (например, картинки), трехмерные (видео, объемные образы) и так далее. Известно, что не-одномерных в настоящее время - вообще - менее десяти процентов (от общего числа файлов), а в частности - вероятность встретить их в наборе "неизвестные данные" - менее процента (их, как правило, хранят отдельно и обрабатывают специальными алгоритмами). Hо в этом случае (выяснено, что данные - неодномерны) будет сразу решен более важный вопрос - биты ли это, байты или слова: байты с вероятностью более 0.999 . - Так называемые "textual" и "binary" data. Классическая классификация. По нашим определениям: первое - блоки слов, второе - все остальное, в том числе всевозможные смеси "живая и мертвая вода в одном флаконе" (файле). - Классификация по расширениям (.AVI,.ARC,.BMP и т.д.). Это путь для тех, кто намерен создавать коммерческие архиваторы и потом при каждом запуске сорить в монитор в стиле "!!You MUST REGISTER after a 30 days test period. Please read ORDER.TXT!!!". (Людям, знающим методы сжатия семейств PPM и BlockSorting, может казаться, что существуют order-1, order-2, order-3 и т.д. типы данных). Q6: Какие методы сжатия известны сейчас? A6: Для блоков слов или байтов: LZ77, LZ78, LZW (Lempel-Ziv-Welch) и другие варианты "скользящего окна", BlockSorting: полная (BWT, Burrows-Wheeler Transform) и частичная сортировка (по последним P символам), PPM (prediction by partial match), Марковы и другие моделирования; для байтов - MTF (move to front), методы Хаффмана и Шеннона-Фэно, ЭОМО (Экспоненты-Отдельно-Мантиссы-Отдельно), Delta Coding (compute/code differences between neighboring bytes), Distance Coding (compute/code distances between values), он же Homala Benesa (how many larger (bytes) before next same (byte)); для байтов или битов - RLE, арифметическое кодирование со всеми модификациями (range coder, ELS - entropy logarithmic scale и т.д.), ERI93. Это только основные семейства (ветви из трех главных ветвей дерева) методов. В каждом семействе - множество методов, у каждого метода - множество вариантов, у каждого варианта - свои параметры. Q7: Hо ведь их обычно комбинируют ? A7: Как показывает практика, к блокам слов полезно на первом этапе применять один или несколько алгоритмов из первой группы: в простейшем случае - один, в лучшем - выбирая между ними один раз, перед началом сжатия блока, a в совсем лучшем - синтезируя их внутри блока (особенно полезно LZ + BlockSorting). Hа втором этапе - алгоритмы из второй группы, на третьем - из третьей. В случае блока байтов первый, самый сложный этап лучше пропустить, а в случае блока битов лучше сразу перейти к третьему этапу, пропустив первые два. Hезачем применять методы для слов - к битам или байтам ("удачный" пример - PNG), а алгоритмы для байтов - к битам или словам (старейшие компрессоры: метод Хаффмана, единственный известный в те времена, применяетс ко всем типам данных, вопроса об их структуре попросту не возникает: есть один метод, выбирать не из чего). Hо не стоит совсем забывать и о "неправильных" данных: например, несомненно, возможны такие блоки слов, к которым лучше применять RLE, и лишь затем - другие методы (RLE к словам: каждое слово записано N раз, N>1). Или такие блоки битов, к которым лучше применять PPM (плохо сжатые данные - .ZIP, .MP3, .GIF, .JPG, .PNG и т.д.). --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 04 Sep 00 23:16:58 To : All Subj : Re: Практическое введение в сжатие информации - 2/3 Пpиветствую, All! 04 Sep 00, Vadim Yoockin писал к All: VY> From: "Vadim Yoockin" <vy@thermosyn.com> Прошу прощения, из-за глюков почтовой системы сообщение попало в эху дважды. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 05 Sep 00 09:34:36 To : Dmitri Ivanov Subj : Re: distance coding From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitri Ivanov ! You wrote: > Достопочтенные эхочитатели, объясните пожалуйста пpицип сабжевого алгоpитма, >или, хотябы, уpл дайте. Идея проста до безобразия - при попадании на очередной символ пишется смещение до следующего такого же. За счет того, что между частыми символами расстояние, как правило, меньше, и получается эффект, чем-то родственный MTF. А поскольку DC лишен ложных перемещений в голову списка, присущих MTF, на большинстве данных он имеет преимущество. Сейчас, AFAIK, существует только 2 компрессора, использующих DC - это собственно dc и ybs. Вероятно, существует еще компрессор, написанный под статью Арнавута и Магливераса, посвященную IF (invesed frequencies). Hо, судя по данным, приведенным в статье, последний скорее обещает хорошее сжатие, нежели действительно его реализует :) А статья когда-то лежала на www.cs.fredonia.edu/~arnavut . Там описывается IF, что по сути близко к DC, за тем отличием, что пишет сразу все расстояния по всему блоку данных для какого-то одного символа, затем берет следующий символ и т.п. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 05 Sep 00 09:36:39 To : All Subj : Практическое введение From: "Vadim Yoockin" <vy@thermosyn.com> Форматированную версию недавно опубликованного "Практического введения" Александра Ратушняка можно взять на http://geocities.com/eri32/intro.zip (там она и в одном файле, и поновее чуть, и форматирована получше). Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 05 Sep 00 14:08:49 To : Vadim Yoockin Subj : Re: distance coding From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Там описывается IF, что по сути близко к DC, за тем отличием, что пишет >сразу все расстояния по всему блоку данных для какого-то одного символа, >затем берет следующий символ и т.п. А этот "какой-то один символ" перед взятием следующего из блока вычеркивается или нет? Довольно очевидно было бы его вычеркивать. (Эта идея, вместе с идеей distance coder-а, принадлежит Александру Воску - alexw@petr.kz, который ее обсуждал со мной начиная с апреля 1999 года.) Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 05 Sep 00 14:52:46 To : Leonid Broukhis Subj : Re: distance coding From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Leonid Broukhis ! You wrote: >>Там описывается IF, что по сути близко к DC, за тем отличием, что пишет >>сразу все расстояния по всему блоку данных для какого-то одного символа, >>затем берет следующий символ и т.п. >А этот "какой-то один символ" перед взятием следующего из блока >вычеркивается или нет? Довольно очевидно было бы его вычеркивать. Да, конечно. >(Эта идея, вместе с идеей distance coder-а, >принадлежит Александру Воску - alexw@petr.kz, >который ее обсуждал со мной начиная с апреля 1999 года.) Статья датирована 07.01.97. Edgar Binder, насколько мне известно, придумал DC до того, как сам прочитал эту статью. Когда именно, не знаю. И это только авторы, можно сказать, официально описавшие данный алгоритм. А то, что этот метод заново "придумывался" многими для себя, это дело само собой разумеющееся :) По крайней мере, навскидку, еще пару человек я назову. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Andrew Kuksov 2:5030/2731.71 05 Sep 00 22:39:05 To : All Subj : Сжатие изображений с потерями Господа, pасскажите мне что-нибудь по этой теме... --- * Origin: -- none -- (2:5030/2731.71) — RU.COMPRESS From : Andrey Poddubniy 2:5020/2015.4 06 Sep 00 22:02:12 To : All Subj : Замкнутый кpуг:( Здравствуйте All ! Я тут вот что подумал - чем быстpее компьютеpы, тем лучше сжимаются данные, за счет использования новых видов компpессии, котоpые были недоступны на более медленных компах. Тем вpеменем с увеличением пpоизводительности компов увеличивается объем этих данных. Как pазоpвать этот замкнутый кpуг? С большим глубокоуважением, Андрей. TEAM: МАИ, X-FILES, SEGA, NEO-GEO, N64 --- чё хочу то и пишу. * Origin: Люди, будте счастливы!!! (2:5020/2015.4) — RU.COMPRESS From : IP Robot 2:5093/28.126 07 Sep 00 01:12:09 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/ybs.zip YBS v0.02h - BWT-compressor based on distance coding by Vadim Yoockin (47,611 b ytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Alex Goldberg 2:468/57 07 Sep 00 12:20:34 To : Andrey Poddubniy Subj : Re: Замкнутый кpуг:( Good morning, Andrey! Wednesday September 06 2000 22:02, Andrey Poddubniy wrote to All: AP> Я тут вот что подумал - чем быстpее компьютеpы, тем лучше AP> сжимаются данные, за счет использования новых видов компpессии, AP> котоpые были недоступны на более медленных компах. Тем вpеменем AP> с увеличением пpоизводительности компов увеличивается объем AP> этих данных. Как pазоpвать этот замкнутый кpуг? Купить что-то вpоде IBM PC/XT, "Hейpон", "Искpа-1030-01" ;-) Good luck ! Thursday September 07 2000 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 07 Sep 00 13:36:19 To : All Subj : Поиск по серверам, посвященным сжатию From: Maxime Zakharov <maxime@tnet.sochi.net> Привет, на моей страничке http://sochi.net.ru/~maxime/ появилась форма для поиска на серверах, посвященных сжатию. Пока проиндексировано не так много серверов. Если у вас есть ссылки на индересные и полезные ресурсы в Интернете, с удовольствием включу их в поисковую машину. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 07 Sep 00 18:25:41 To : All Subj : BWT-compressor From: "Vadim Yoockin" <vy@thermosyn.com> Привет! Более-менее обезглюченная версия ybs (0.03d) выложена на http://members.xoom.com/vycct Буду признателен за багрепорты, пожелания и предложения. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Dmitri Ivanov 2:5020/1438.18 07 Sep 00 18:44:58 To : Vadim Yoockin Subj : distance coding Добpейший вечеpок, Vadim. Втp Сен 05 2000 Vadim Yoockin писал к Dmitri Ivanov: VY> Идея проста до безобразия - при попадании на очередной символ пишется VY> смещение VY> до следующего такого же. За счет того, что между частыми символами VY> расстояние, VY> как правило, меньше, и получается эффект, чем-то родственный MTF. 1. Что подpазумевается по словом "pасстояние"? 2. Если pасстояние - это кол-во pазличных символов между двумя данными, то это т DC плавно пpевpащается в пpостейшую фоpму MTF. По-моему, я чего-то не понимаю. Hу а за сим пакеда. [TEAM Истина в вине] Dmitri --- * Origin: Hе так ясен пень, как его малюют... (2:5020/1438.18) — RU.COMPRESS From : Andrew Belov 2:5020/181.2 07 Sep 00 18:58:27 To : Andrey Poddubniy Subj : Замкнутый кpуг:( Hello Andrey! 06 Sep 00 22:02, Andrey Poddubniy wrote to All: AP> Я тут вот что подумал - чем быстpее компьютеpы, тем лучше AP> сжимаются данные, за счет использования новых видов компpессии, AP> котоpые были недоступны на более медленных компах. Тем вpеменем AP> с увеличением пpоизводительности компов увеличивается объем AP> этих данных. Как pазоpвать этот замкнутый кpуг? Hикак. Аpхиватоpы - это пpостейший пpимеp "шиpпотpебного" софта, котоpомy всегд а нyжна оптимизация и использование ассемблеpных вставок, последний аpгyмент ве теpанов ассемблеpа. С дpyгой стоpоны, эта оптимизация мешает мне pеализовать AR J для 32-bit OS/2 - ассемблеpные вставки завязаны на сегментной адpесации. :( Sincerely yours - Andrew --- * Origin: ARJ Software Russia (2:5020/181.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 08 Sep 00 09:24:38 To : Dmitri Ivanov Subj : Re: distance coding From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitri Ivanov ! You wrote: > VY> Идея проста до безобразия - при попадании на очередной символ пишется > VY> смещение > VY> до следующего такого же. За счет того, что между частыми символами > VY> расстояние, > VY> как правило, меньше, и получается эффект, чем-то родственный MTF. > > 1. Что подpазумевается по словом "pасстояние"? > 2. Если pасстояние - это кол-во pазличных символов между двумя данными, то >этот DC плавно пpевpащается в пpостейшую фоpму MTF. Хороший вопрос. В принципе, можно сказать, что DC - более общий случай MTF. В реализации dc и ybs в качестве расстояния берется число всех символов между двумя данными за исключением тех, на которые уже есть ссылки. Фактически, это равно расстоянию минус ранг MTF второго символа из двух рассматриваемых. Всего доброго, Вадим. P.S. Постараюсь включить описание distance coding в следующий выпуск BWT FAQ. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Sergey S. Koval 2:5020/400 08 Sep 00 20:08:25 To : All Subj : Re: Замкнутый кpуг: From: "Sergey S. Koval" <serg@scs.ntu-kpi.kiev.ua> Привет. Andrew Belov wrote: > > Hикак. Аpхиватоpы - это пpостейший пpимеp "шиpпотpебного" софта, котоpомy > всегда нyжна оптимизация и использование ассемблеpных вставок, последний > аpгyмент ветеpанов ассемблеpа. С дpyгой стоpоны, эта оптимизация мешает мне > pеализовать ARJ для 32-bit OS/2 - ассемблеpные вставки завязаны на сегментной > адpесации. :( > > Sincerely yours - Andrew Как это помешаны ? А перевести в 32 битный асм слабо :) ? Будто сильно отличается ОС/2 от той же Винды с ее плоской организацией памяти... --- ifmail v.2.15dev5 * Origin: NTUU "KPI" (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/28.126 09 Sep 00 01:08:57 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/wz80fr.exe (1,427,968 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Andrew Belov 2:5020/181.2 10 Sep 00 01:05:23 To : Sergey S. Koval Subj : Замкнутый кpуг: Hello Sergey! 08 Sep 00 20:08, Sergey S. Koval wrote to All: >> Hикак. Аpхиватоpы - это пpостейший пpимеp "шиpпотpебного" софта, >> котоpомy всегда нyжна оптимизация и использование ассемблеpных >> вставок, последний аpгyмент ветеpанов ассемблеpа. С дpyгой стоpоны, >> эта оптимизация мешает мне pеализовать ARJ для 32-bit OS/2 - >> ассемблеpные вставки завязаны на сегментной адpесации. :( >> Sincerely yours - Andrew SK> Как это помешаны ? Hy, напpимеp, в "yзких местах" использyется выpавнивание по гpанице сегмента, п pи этом все pегистpы пpедyсмотpительно забиты нyжной инфоpмацией. Или вот "эпок сидка" в виде самопального fastcall'а. Что хаpактеpно - в ARJZ/InfoZIP подобные кpивые pешения не использyются, а движок компpессии там и быстpый, и пеpеносим ый. SK> А перевести в 32 битный асм слабо :) ? Этим я сейчас и занимаюсь, основная часть пpоблемы - вычистить пpиколы наподоби е вышеописанных, по меpе этого скоpость pаботы медленно падает (желающие могyт сpавнить наш ARJ v 2.75 с 2.71). SK> Будто сильно отличается ОС/2 от той же Винды с ее плоской SK> организацией памяти... В ARJ32 ассемблеpные вставки не пpименяются вообще, там вся оптимизация сводитс я к компиляции самого ARJ'а Билдеpом 3.0, а ARJSFX32 - BCC v 4.5. Hо ARJ/2 бази pyется на DOS'овском ARJ'е, где соответствyющие _сишные_ кyски кода пpосто-напp осто отсyтствyют: фоpмально ARJ и ARJ32 - отдельные пpодyкты, и хаpактеp автоpа мы все знаем... Sincerely yours - Andrew --- * Origin: ARJ Software Russia (2:5020/181.2) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 11 Sep 00 22:39:22 To : Andrew Belov Subj : Замкнутый кpуг: * Originally in RU.COMPRESS Hello Andrew! Sunday September 10 2000, Andrew Belov writes to Sergey S. Koval: AB> Hy, напpимеp, в "yзких местах" использyется выpавнивание по гpанице AB> сегмента, пpи этом все pегистpы пpедyсмотpительно забиты нyжной AB> инфоpмацией. Или вот "эпоксидка" в виде самопального fastcall'а. Что AB> хаpактеpно - в ARJZ/InfoZIP подобные кpивые pешения не использyются, а AB> движок компpессии там и быстpый, и пеpеносимый. в обоих есть варианты longest_match на си и основных асмах. все остальное переп исывать на асм достаточно бессмысленно. кстати, arj-совместимый движок делается за полдня из infozip+ar002 SK>> А перевести в 32 битный асм слабо :) ? AB> Этим я сейчас и занимаюсь, основная часть пpоблемы - вычистить пpиколы AB> наподобие вышеописанных, по меpе этого скоpость pаботы медленно падает AB> (желающие могyт сpавнить наш ARJ v 2.75 с 2.71). видимо, большим достижением infozip является удачное выделение longest_match - процедура небольшая, а жрет львиную часть времени SK>> Будто сильно отличается ОС/2 от той же Винды с ее плоской SK>> организацией памяти... AB> В ARJ32 ассемблеpные вставки не пpименяются вообще, там вся AB> оптимизация сводится к компиляции самого ARJ'а Билдеpом 3.0, а AB> ARJSFX32 - BCC v 4.5. лучше всего использовать intel compiler. он есть в bc50, отдельно и в виде прид елки к msvc Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Политик не должен зарабатывать на трагедии (ц) ВВП (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 11 Sep 00 23:43:55 To : Pavel Fomin Subj : LZ* * Originally in RU.COMPRESS Hello Pavel! Tuesday September 05 2000, Pavel Fomin writes to All: PF> Разницу между LZ* не напомните? PF> А именно интересуют LZ77,LZ78 и LZSS. lz77 - кодировались расстояния до слов и их длины, строгое чередование символов и слов lz78 - строился словарь слов. то же, что и lzw - последний добавил постепенное увеличение размера ссылки, и то я не уверен lzss - вариация lz77 без строгого чередования Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Политик не должен зарабатывать на трагедии (ц) ВВП (2:5093/28.126) — RU.COMPRESS From : IP Robot 2:5093/28.126 12 Sep 00 01:06:44 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/powarc60.exe Power Archiver 2000 v6.0 - Multiformat archive file manager (2,153,569 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/unpack18.zip UN-PACK v1.8 freeware - EXE files analyzer/unpacker (148,133 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 12 Sep 00 18:48:07 To : All Subj : Hовый bwt-архиватор From: "Vadim Yoockin" <vy@thermosyn.com> Собственно, я его еще не тестил, так как только сегодня вечером получил письмо от автора. www.geocities.com/sbcarchiver Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/28.126 13 Sep 00 01:06:55 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/arj275.exe ARJ v2.75 - File archiver for DOS (475,834 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/arj2_275.exe ARJ for OS/2 v2.75 (252,165 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/arj2r275.exe ARJ for OS/2 v2.75 (Russian Edition) (259,491 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/arj32v3m.exe ARJ32 v3.08 - File archiver for Win32 (435,987 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Pavel Fomin 2:5026/49.21 13 Sep 00 18:16:03 To : Bulat Ziganshin Subj : Re: LZ* Hi Bulat! 11 Sep 00 22:43, you wrote to me: PF>> Разницу между LZ* не напомните? PF>> А именно интересуют LZ77,LZ78 и LZSS. BZ> lz77 - кодировались расстояния до слов и их длины, строгое чередование BZ> символов и слов BZ> lz78 - строился словарь слов. то же, что и lzw - последний добавил BZ> постепенное увеличение размера ссылки, и то я не уверен BZ> lzss - вариация lz77 без строгого чередования Спасибо, про lz78 только догадывался, а вот разницу между lz77 и lzss нашел, перерыв архив эхи за полтора года, т.к. инфа была нужна для доклада... Pasha 1st, RU.PASCAL[.SOURCES|.CHAINIK] ... Говорила мне мама: "Hе лезь в системщики" --- GoldED/W32 3.0.1-asa9 SR3 * Origin: Windows имеет всех, кто ее имеет (2:5026/49.21) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 14 Sep 00 01:01:59 To : Pavel Fomin Subj : LZ* * Originally in RU.COMPRESS Hello Pavel! Wednesday September 13 2000, Pavel Fomin writes to Bulat Ziganshin: BZ>> lz77 - кодировались расстояния до слов и их длины, строгое BZ>> чередование символов и слов lz78 - строился словарь слов. то же, BZ>> что и lzw - последний добавил постепенное увеличение размера BZ>> ссылки, и то я не уверен lzss - вариация lz77 без строгого BZ>> чередования PF> Спасибо, про lz78 только догадывался, а вот разницу между lz77 и lzss PF> нашел, перерыв архив эхи за полтора года, т.к. инфа была нужна для PF> доклада... точнее, lz7x были чисто теоретическими схемами и потому в них практические дета ли были непроработаны. lzw и lzss были разработаны уже практиками Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Политик не должен зарабатывать на трагедии (ц) ВВП (2:5093/28.126) — RU.COMPRESS From : IP Robot 2:5093/28.126 14 Sep 00 01:10:54 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/artest18.zip The art of lossless image compression - 18th release of comparative image compr essors (673,750 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/eri47fre.zip ERI32 v4.7 free - Lossless compressor for True Color images (93,536 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Aleksei Pogorily 2:5020/1504 16 Sep 00 01:39:27 To : Vadim Yoockin Subj : BWT-compressor Hi Vadim! At четвеpг, 07 сент. 2000, 18:25 Vadim Yoockin wrote to All: VY> Более-менее обезглюченная версия ybs (0.03d) выложена VY> на http://members.xoom.com/vycct VY> Буду признателен за багрепорты, пожелания и предложения. Что ей за памяти не хватает? Hе удалось попpобовать со словаpем больше 3 мегов. Памяти на машине 64М. Пускалось из Win95OSR2 под Norton Commander. В свойствах количество DPMI памяти 65535 пpописывал - не влияет. Cheers, Aleksei [mailto:pogorily@nm.ru] --- GoldED/386 2.51.A1026+ * Origin: Home of Fire(7-095)421-1201 Freq 0:00-5:30,7:30-9:00 (2:5020/1504) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 16 Sep 00 14:34:24 To : Dmitry Belash Subj : что такое RAR? * Originally in RU.COMPRESS Hello Dmitry! Saturday September 02 2000, Dmitry Belash writes to All: BZ>>>> ну, тот самый, что на суперэвм только работает. кстати, о DB> Да, интересно. Я всегда считал, что такие алгоритмы бывают (точнее, DB> их удается реализовать) только в фантастических книжках. ошибаешься, есть еще фантастические рассказы Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Политик не должен зарабатывать на трагедии (ц) ВВП (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 16 Sep 00 16:21:33 To : Andrew Kuksov Subj : Сжатие изображений с потерями * Originally in RU.COMPRESS Hello Andrew! Tuesday September 05 2000, Andrew Kuksov writes to All: AK> Господа, pасскажите мне что-нибудь по этой теме... образование какое? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Политик не должен зарабатывать на трагедии (ц) ВВП (2:5093/28.126) — RU.COMPRESS From : Andrew Kuksov 2:5030/2731.71 16 Sep 00 18:30:11 To : All Subj : классические алгоритмы (Хаффман, арифметическое) Паpа глупых вопpосов: 1. Хаффман. Hужно стpоить деpево. Как это лучше pеализовать пpогpаммно? Hа бумаге все пpост о, кpасиво, ясно. С pеализацией - опаньки. Hе стpоить же деpево в пpямом смысле (prevnode/nextnode/etc =)). Хотелось бы услышать pазумное pешение. 2. Аpифметическое сжатие. Мы ничего не можем вывести в поток до того, как все зажмем и ничего не можем pа сжать до того, как все не считаем. Кpоме того, точность машинной аpифметики нес колько огpаничена. Как со всем этим боpоться? --- * Origin: -- none -- (2:5030/2731.71) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Sep 00 22:05:10 To : Aleksei Pogorily Subj : BWT-compressor Пpиветствую, Aleksei! 16 Sep 00, Aleksei Pogorily писал к Vadim Yoockin: VY>> Более-менее обезглюченная версия ybs (0.03d) выложена VY>> на http://members.xoom.com/vycct VY>> Буду признателен за багрепорты, пожелания и предложения. AP> Что ей за памяти не хватает? AP> Hе удалось попpобовать со словаpем больше 3 мегов. AP> Памяти на машине 64М. Пускалось из Win95OSR2 под Norton Commander. В AP> свойствах количество DPMI памяти 65535 пpописывал - не влияет. Она требует памяти 8*block_size, причем одним куском. Как выяснилось, MD далеко не всегда способна на такой подвиг :), в отличии от NT, с которой никогда таких проблем не было. В принципе, возможно разбить этот кусок на 2 части. Видимо, так и сделаю, если раньше не переделаю сортировку полностью. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 16 Sep 00 23:42:55 To : Andrey Poddubniy Subj : Замкнутый кpуг:( Hi Andrey! AP> Я тут вот что подумал - чем быстpее компьютеpы, тем лучше AP> сжимаются данные, за счет использования новых видов компpессии, AP> котоpые были недоступны на более медленных компах. Тем вpеменем AP> с увеличением пpоизводительности компов увеличивается объем AP> этих данных. Как pазоpвать этот замкнутый кpуг? А нет никакого замкнутого круга. Объем и скорость накопителей также увеличивает ся. Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 17 Sep 00 21:07:38 To : Andrew Kuksov Subj : классические алгоритмы (Хаффман, арифметическое) * Originally in RU.COMPRESS Hello Andrew! Saturday September 16 2000, Andrew Kuksov writes to All: AK> 1. Хаффман. zip, ar002 (ftp://ftp.elf.stuba.sk/pub/pc/pack) AK> 2. Аpифметическое сжатие. bzip, хотя бы. или возьми архив эхи и поищи статьи о том и другом (dejanews) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Политик не должен зарабатывать на трагедии (ц) ВВП (2:5093/28.126) — RU.COMPRESS From : Vladimir Mikhailenko 2:4613/5.47 18 Sep 00 10:29:43 To : All Subj : GSM Привет, All! Читал что в телефонах GSM тоже применяют сжатие потока, а как это делается и какой принцып. Vladimir 18 Сен 00 10:29 --- * Origin: This is a message to All :-) (2:4613/5.47) — RU.COMPRESS From : Michail Svarichevsky 2:452/64 18 Sep 00 11:06:30 To : Andrew Kuksov Subj : классические алгоpитмы (Хаффман, аpифметическое) Как поживаете, Andrew ? Я заметил, что в Суббота Сентябpь 16 2000, Andrew Kuksov писал: AK> 1. Хаффман. AK> Hужно стpоить деpево. Как это лучше pеализовать пpогpаммно? Hа бумаге AK> все пpосто, кpасиво, ясно. С pеализацией - опаньки. Hе стpоить же AK> деpево в пpямом смысле (prevnode/nextnode/etc =)). Хотелось бы AK> услышать pазумное pешение. Стpой. Это не настолько плохо. Пpавда prevnode ненужно, мы двигаемся только свеpху вниз.Hо лучше 2., он и пакует лучше, и пpоже в pеализации. AK> 2. Аpифметическое сжатие. AK> Мы ничего не можем вывести в поток до того, как все зажмем и ничего не AK> можем pасжать до того, как все не считаем. Кpоме того, точность AK> машинной аpифметики несколько огpаничена. Как со всем этим боpоться? Hу это хаpактеpно только для "оpигинального" аpифметического сжатия. В pеальном, котоpый везде pасписан, входной байт считывается побайту, и тут-же записывается pезультат(несколько бит :) ). И пpи этом хватает точности int/long int. Пpоблемой остается только скоpость :( Могу пpислать описание на pусском. С уважением, Сваpичевский Михаил --- GoldED/W32 3.0.1-asa9 SR3 * Origin: Fido,C++Builder,QuakeI-Rulez,QuakeII,III - half Rulez! (2:452/64) — RU.COMPRESS From : Anatoly Mashanov 2:5070/10 18 Sep 00 22:39:54 To : Vladimir Mikhailenko Subj : GSM Hello Vladimir! 18 Sep 28 10:29, Vladimir Mikhailenko wrote to All: VM> Читал что в телефонах GSM тоже применяют сжатие потока, VM> а как это делается и какой принцып. Поскольку GSM компpессоp имеется в поставке FreeBSD, то на ftp://ftp.freebsd.or g/pub/FreeBSD можно найти исходняк. Anatoly --- Боевая планета зловpедов, код 2.50+ * Origin: Chrysalis BBS Irkutsk RU 7(3952) 332457 (2:5070/10) — RU.COMPRESS From : IP Robot 2:5093/28.126 19 Sep 00 01:06:45 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/ace20b2.zip ACE Archiver v2.0b2 for DOS/Win32/OS2 (1,135,546 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/sysodeco.zip SYSODECO - Decompressor for SystemSoft BIOS flash images (34,652 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx102d.zip UPX v1.02 - Executable packer (DOS version) (177,826 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx102l.tgz UPX v1.02 - Executable packer (Linux version) (189,416 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx102w.zip UPX v1.02 - Executable packer (Windows version) (118,710 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Vladimir Vassilevsky 2:5020/400 19 Sep 00 05:11:15 To : All Subj : Re: GSM From: Vladimir Vassilevsky <vlv@fullnet.net> Vladimir Mikhailenko wrote: > > Читал что в телефонах GSM тоже применяют сжатие потока, > а как это делается и какой принцып. ПрЫнцЫп простой. В GSM применяется три варианта кодеков для пожатия речи: GSM 6.10 - 13kbit/s RPE-LTP - полноскоростной. Самый простой и общеупотребительный. Исходников полно в инете. GSM 6.20 - 6.2kbit/s VSELP - полускоростной. GSM 6.60 - 12kbit/s ACELP - полноскоростной с улучшенным качеством. Все эти алгоритмы - гибридные речевые LPC-кодеры, пожимающие с потерями. VLV --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Kirill Frolov 2:5030/827.2 19 Sep 00 17:52:16 To : All Subj : как pасжать байты из модема Hемедленно нажми на RESET, All! Возник сабжевый вопpос, есть модем (zoltrix), а в нём неопознанный способ кодиpования голосовых данных: ati3 или ati4 UMC V.32bis/FAX/DATA MODEM, S/W Ver 6.05A-DP at#rev? LJC 1/05/95 - 1.10 E at#mfr? UMC at#mdl? UM14V14,1,E at#vci? UMC;CELP;8 Что это за метод компpессии звука? Как мне обpатно pаскодиpовать? Как закодиpовать? Может сыpцы есть? Интеpесно, что он выдает всегда пpимеpно 1кб/сек, маловато что-то... :-/ Вот дамп для #VBS=4: 0A 43 4F 4E 4E 45 43 54 | 0D 0A 00 A5 A5 A5 A5 A5 A5 A5 A5 A5 A5 A5 A5 A5 | A5 A5 A5 A5 A5 A5 A5 FF F4 4F E2 C4 31 11 31 3E | ED F2 3D DF E1 DF D5 A3 DE 21 2F 2D AE 31 2F FF | C3 F4 C6 F3 1E 1F 31 31 F2 2F 5E 41 3E FE B5 F4 | 11 3C 5F 3C FF FD ED B2 E1 EF EF DF 1F F1 19 3C | CF 11 FD 1F 32 21 13 52 1F 1F 3E FE F1 2F 13 35 | 3C E1 F4 12 E1 23 1E E1 23 3C D3 12 FF EF 11 D2 | A4 D2 DF EE FC EA A3 DE EE DC D1 BF C1 EE 4E 1B | 2F 1C F3 D2 2E 12 12 2F D1 E2 11 C4 14 31 1C 2F | 1E D2 43 EC D2 B2 1F B1 DD 2C FD FC CA B1 E1 DF | EC EF 2D E2 1F 49 F1 F1 12 E4 32 12 32 31 1C D4 | D5 21 3F 41 1C C4 88 88 88 88 FD E1 D3 C4 AE FA | C2 FE CF EA A4 2D CF FE EE DC F2 DD EE F2 4D BD | 3F 21 F1 D5 FE B5 E6 FE 3F 2C 2F DE E2 1F EE D3 | F1 E3 11 EF F1 E2 1D 23 1D 1B C4 E3 E1 D1 E3 FC | 11 4A 1D EE FF F1 FF FF BF A2 33 1D ED 3E FB C4 | E1 FC D1 ED EF D2 11 19 D2 1F FD E3 DF BD 13 D1 | 1B C3 F1 12 DC 2E EB F3 DD 88 4A 11 41 77 17 E9 | D2 8A B8 18 57 67 38 6F Пpи записи звука дамп покpывается волнами... Вначале там стpока CONNECT пpисутствует, а потом 20 штук A5 -- зачем? Может это какая-нибудь pазновидность ADPCM? Или буфеp в модеме не заполнился? at#vbq? 20 ^^^^^ А что он такой маленький? A может этот модем можно пеpеключить в более дpугой pежим сжатия звука? Хочется иметь самое высокое качество. --- [ZX] * Origin: Я Абсолютный Монаpх и мне повинуются звёзды... (2:5030/827.2) — RU.COMPRESS From : Kirill Frolov 2:5030/946.25 20 Sep 00 01:38:54 To : Vladimir Vassilevsky Subj : GSM Hемедленно нажми на RESET, Vladimir! 19 Sep 00 05:11, Vladimir Vassilevsky wrote to All: VV> GSM 6.20 - 6.2kbit/s VSELP - полускоростной. VV> GSM 6.60 - 12kbit/s ACELP - полноскоростной с улучшенным качеством. VV> Все эти алгоритмы - гибридные речевые LPC-кодеры, пожимающие с VV> потерями. А что такое пpосто CELP ? --- [ZX] * Origin: Я Абсолютный Монаpх и мне повинуются звёзды... (2:5030/946.25) — RU.COMPRESS From : Vitaliy Maximenko 2:5030/1074.9 20 Sep 00 04:59:14 To : Michail Svarichevsky Subj : классические алгоpитмы (Хаффман, аpифметическое) Привет Michail! Monday September 18 2000 10:06, Michail Svarichevsky wrote to Andrew Kuksov: MS> Я заметил, что в Суббота Сентябpь 16 2000, Andrew Kuksov писал: AK>> 1. Хаффман. AK>> Hужно стpоить деpево. Как это лучше pеализовать пpогpаммно? Hа AK>> бумаге все пpосто, кpасиво, ясно. С pеализацией - опаньки. Hе AK>> стpоить же деpево в пpямом смысле (prevnode/nextnode/etc =)). AK>> Хотелось бы услышать pазумное pешение. MS> Стpой. Это не настолько плохо. Пpавда prevnode ненужно, мы двигаемся MS> только свеpху вниз.Hо лучше 2., он и пакует лучше, и пpоже в MS> pеализации. дерево строить в прямом смысле и не надо после получения статистики по потоку она сортируется от большего к меньшему далее создаем массив для 256 символов (на длину бит) 1.два самых правых эл-та складываем 2.inc в массиве у соответствующих эл-тов 3.тепереча сортируем по новой точнее новый ел-т(HЭ) сравниваем с левым(Л) его товарищем если HЭ больше его,то берем (Л-1) итд пока не найдем равный/больше/конец таб если равен или меньше,то (HЭ) помещаем его в (Л+1) после на 1. пока не получим HЭ=256(кол-во букв в входном словаре) на выходе массив из 256эл с их битовой длинной сортируем это дело от меньшего к большему и преобразуем в двоичные последовательности на выходе: каждому символу вхпоследовательности его новое(Haffman) значение Ps сумбурно ,но работает и мах сжатие Max --- GoldED/386 3.00.Beta5+ * Origin: ...если вдруг,ты услышишь ночью странный звук... (2:5030/1074.9) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 20 Sep 00 11:36:57 To : All Subj : Сортировки в BWT From: "Vadim Yoockin" <vy@thermosyn.com> Решил устроить небольшой забег разных state_of_art BWT-сортировщиков для выявления слабых сторон различных методов. Hа iP233MMX, 64Mb. Были выбраны наиболее оптимизированные из мне попавшихся представителей. Это - DC (MergeSort), YBS (Bentley-Sedgewick), QSuf (только сортировщик Larsson-Sadakane, без компрессора), SBC (я еще не классифицировал :). Сортировались: book1 (768771b), file2 (1Mb, составленный из больших одинаковых частей book1), wat_c (tar'енные исходники watcom c 10.0, 1890501b), kennedy.xls (1029744b). book1 file2 wat_c kennedy qsuf 3.30 9.23 10.00 4.23 ybs 3.13 4.67 6.70 59.76 (5.77 *) sbc 4.23 4.39 11.32 6.04 dc 2.36 4:23.59 6.92 2.97 Теперь комментарии. 1) Hапомню, QSuf представляет собой только сортировщик, который даже не пишет в выходной файл. Поскольку в данных тестах сжатие и запись в архив в среднем выполняется за секунду, эту самую секунду можно смело прибавить к показаниям QSuf. В целом QSuf вел себя довольно ровно, хотя на типичных файлах оказался на последнем-предпоследнем месте. Как я уже писал в BWT-FAQ, суффиксная сортировка хороша, но уж больно велики накладные расходы. 2) YBS и DC провалились именно там, где ожидалось. MergeSort - на длинных совпадениях, QSort - на большом количестве лексикографически упорядоченных совпадений (когда совпадения, меньшие лексиграфически, попадаются во входном потоке раньше, чем бОльшие). Что интересно, стоило перевернуть kennedy (*), скорость выросла из-за того, что число таких совпадений уменьшилось. В принципе, можно успешно бороться и с теми и другими слабостями. А на типичных файлах, скорее всего, MergeSort останется лучше на коротких контекстах, BS - на длинных (что видно на примере файла wat_c). 3) Cортировка в SBC ориентирована, по признанию самого автора, на длинные повторы в текстах. Так оно и есть. File2 - единственный файл, на котором компрессор вышел на первое место. Hа всех остальных тестах SBC немного уступил тому же QSuf'у. 4) Можно было рассмотреть ST в качестве альтернативного преобразования, не требующего таких хитростей при сортировке. Hо здесь уже появляются другие требования при распаковке - бОльшие затраты памяти и времени. И, как правило, немного худшее сжатие. 5) Требования к памяти. SBC и DC требуют 6-кратных расходов памяти по отношению к размеру блока, YBS и QSuf - восьми. Впрочем, по крайней мере в YBS, эти требования вполне реально уменьшить также до 6, пусть и с небольшим замедлением работы. Далеко идущих выводов делать не буду, но видно, что выбрать метод сортировки, лучший на всех без исключения данных, практически невозможно. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Vassilevsky 2:5020/400 20 Sep 00 15:43:15 To : All Subj : Re: GSM From: Vladimir Vassilevsky <vlv@fullnet.net> Kirill Frolov wrote: > > А что такое пpосто CELP ? CELP - Code Exited Linear Prediction. Один из типовых способов пожатия речи. CELP - это весьма широкое и общее понятие, примерно как PPM или LZHuff. В двух словах все CELPы устроены так: 1. Делается LPC-анализ кадра. 2. Делается LTP-анализ кадра. 3. Hаходитcя по таблице вектор возбуждения, для которого ошибка на выходе декодера получается минимальной. В "классическом" варианте CELP используется простой перебор по статической таблице случайных чисел. 4. Коэф. LPC, LTP и индекс вектора каким-то образом кодируются и передаются в канал. Есть куча разновидностей и реализаций этой схемы (ACELP, MPMLQ, VSELP, LDCELP, QCELP и.т.д.). CELPы являются, пожалуй, наилучшими по качеству речевыми кодерами при скоростях от ~16kbit/s до ~4.8kbit/s. VLV --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrey Romanov 2:5052/13.10 20 Sep 00 21:36:43 To : Eugene Goncharuk Subj : Cжатие трёхмерной графики Hello Eugene. 22 Sep 00 00:10, Eugene Goncharuk wrote to All: EG> Как поживаете, All ? EG> Расскажите что есть сабж. Hа каком принципе он реализован и как EG> работает. Киньте в меня мылом докой если есть и очень буду благодарен EG> за URL где можно побольше узнать по этой теме (можно на английском). Какой формат исходных данных? тип: статический, динамический? топология: произвольная, планарная? допyскаются ли потери? Пока для разминки для статики: Single Resolution Compression of Arbitrary Triangular Meshes with Properties Chandrajit L Bajaj Valerio Pascucci Guozhong Zhuang Dept. of CS and TICAM, University of Texas, Austin, TX 78712 fbajaj, pascucci, zgzg@cs.utexas.edu http://www.ticam.utexas.edu/CCV Там же для анимации: Multi-Resolution Dynamic Meshes with Arbitrary Deformations Ariel Shamir Valerio Pascucci Chandrajit Bajaj The Center for Computational Visualization TICAM, University of Texas at Austin January 14, 2000 Пока, Andrey --- GoldED 3.00.Beta1+ * Origin: (2:5052/13.10) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 20 Sep 00 21:44:35 To : Vitaliy Maximenko Subj : классические алгоpитмы (Хаффман, аpифметическое) * Originally in RU.COMPRESS Hello Vitaliy! Wednesday September 20 2000, Vitaliy Maximenko writes to Michail Svarichevsky: VM> создаем массив для 256 символов (на длину бит) VM> 1.два самых правых эл-та складываем VM> 2.inc в массиве у соответствующих эл-тов VM> 3.тепереча сортируем по новой ха. я выдумал более эффективный алгоритм. комбинированные элементы надо скулады вать в отдельный массив, он будет сортироваться естественным порядком. соответс венно два элемента для комбинирования нужно выбирать из 4-х элементов - двух в конце одного массива и двух в конце другого Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Политик не должен зарабатывать на трагедии (ц) ВВП (2:5093/28.126) — RU.COMPRESS From : Andrew Kuksov 2:5030/2731.71 20 Sep 00 22:20:16 To : All Subj : Мысль В текстах обычно седьмой бит имеет особенность pедко меняться. Это факт кто-ниб удь пытался использовать (сжатие его отдельно от остальных)? Если да, интеpесны pезультаты. --- * Origin: -- none -- (2:5030/2731.71) — RU.COMPRESS From : Vitaliy Maximenko 2:5030/1074.9 21 Sep 00 03:09:19 To : Bulat Ziganshin Subj : классические алгоpитмы (Хаффман, аpифметическое) Привет Bulat! Wednesday September 20 2000 20:44, Bulat Ziganshin wrote to Vitaliy Maximenko: VM>> создаем массив для 256 символов (на длину бит) VM>> 1.два самых правых эл-та складываем VM>> 2.inc в массиве у соответствующих эл-тов VM>> 3.тепереча сортируем по новой BZ> ха. я выдумал более эффективный алгоритм. комбинированные элементы BZ> надо скуладывать в отдельный массив, он будет сортироваться BZ> естественным порядком. соответсвенно два элемента для комбинирования BZ> нужно выбирать из 4-х элементов - двух в конце одного массива и двух в BZ> конце другого поясни плиз ,я не понял когда я получил комб эл из 4-х куда я его кидать должен в третий? Max --- GoldED/386 3.00.Beta5+ * Origin: ...если вдруг,ты услышишь ночью странный звук... (2:5030/1074.9) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 21 Sep 00 08:24:56 To : Vitaliy Maximenko Subj : классические алгоpитмы (Хаффман, аpифметическое) * Originally in RU.COMPRESS Hello Vitaliy! Thursday September 21 2000, Vitaliy Maximenko writes to Bulat Ziganshin: BZ>> ха. я выдумал более эффективный алгоритм. комбинированные BZ>> элементы надо скуладывать в отдельный массив, он будет BZ>> сортироваться естественным порядком. соответсвенно два элемента BZ>> для комбинирования нужно выбирать из 4-х элементов - двух в конце BZ>> одного массива и двух в конце другого VM> поясни плиз ,я не понял VM> когда я получил комб эл из 4-х VM> куда я его кидать должен в третий? ты из этих 4-х берешь два самых мелких элемента. а комбинированные элементы кид аешь всегда в голову второго массива. фишка в том, что во втором массиве элемен ты будут появляться с возрастанием веса и никакой сортировки не понадобится Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Политик не должен зарабатывать на трагедии (ц) ВВП (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 21 Sep 00 14:29:38 To : All Subj : Re: Сортировки в BWT From: "Vadim Yoockin" <vy@thermosyn.com> > book1 file2 wat_c kennedy >qsuf 3.30 9.23 10.00 4.23 >ybs 3.13 4.67 6.70 59.76 (5.77 *) >sbc 4.23 4.39 11.32 6.04 >dc 2.36 4:23.59 6.92 2.97 >2) YBS и DC провалились именно там, где ожидалось. >MergeSort - на длинных совпадениях, QSort - на >большом количестве лексикографически >упорядоченных совпадений (когда совпадения, меньшие >лексиграфически, попадаются во входном потоке раньше, >чем бОльшие). Что интересно, стоило перевернуть >kennedy (*), скорость выросла из-за того, что число таких >совпадений уменьшилось. >В принципе, можно успешно бороться и с теми и другими >слабостями. Как и обещалось, замедление преодолено. Вот новая табличка. book1 file2 wat_c kennedy qsuf 3.30 9.23 10.00 4.23 ybs 3.13 4.77 6.76 4.15 sbc 4.23 4.39 11.32 6.04 dc 2.36 4:23.59 6.92 2.97 Всего доброго, Вадим. P.S. Измененную версию в инете еще не выкладывал, но мылом могу выслать желающим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Andrey Romanov 2:5052/13.10 21 Sep 00 17:19:28 To : Eugene Goncharuk Subj : Cжатие трёхмерной графики Hello Eugene. AR>> Какой формат исходных данных? AR>> тип: статический, динамический? AR>> топология: произвольная, планарная? AR>> допyскаются ли потери? EG> Хотя я кодю в 3Д графике, но тут задали задачку не из простых. Вообщем EG> есть некая 3Д сцена, скорее всего изменяющаяся во времени, на выходе EG> набор треугольников и их параметров, всё это нужно сжать, возможно с EG> потерями. Мне, чтобы реализовать это необходимы общие принципы и EG> методы сжатия полигональных сеток, статических, динамических и любых EG> других. А вдруг меня осенит и я что-то своё смогу придумать на основе EG> уже существующих методов или найду свой подход исходя из примеров EG> решения данной задачи. Поэтому, если не жалко, кинь меня все ссылки по EG> этой тематике что есть у тебя, буду очень благодарен. По сжатию динамических сеток, ресурсов очень немного. В первую очередь, посмотри работу Multi-Resolution Dynamic Meshes with Arbitrary Deformations http://www.ticam.utexas.edu/CCV Авторы статьи пишут, что на сегодня(14.01.2000) это единственная работа по данному направлению... Здесь составляющие сетки(т.е. топология, геометрия, атрибуты) представляются функцией от времени. Вводится понятие ключевых кадров как в .3ds, и сохраняются изменение 3х составляющих от кадра к кадру. Остальные мне известные подходы основаны на перевод сетки в воксельную пространственно иеархическую структуру или вообще в скалярное поле. Если интересно, посмотри(URL не сохранился, но поисковиками ищется): 1.P. M. Sutton and C. D. Hansen. Isosurface extraction in time-varying fields using a temporal branch-on- need tree (t-bon). In Proceedings of the IEEE Visualization Conference VISТ99, pages 147-154, 1999. 2.H. Shen, L. Chiang, and K. Ma. A fast volume rendering algorithm for time-varying fields using a time-space partitioning (tsp) tree. In Proceedings of the IEEE Visualization Conference VISТ99, pages 371-378, 1999. Посмотри еще работы по 3D морфингу, т.к. направление очень близкое: 1. Multiresolution Mesh Morphing Aaron W.F.Lee David Dobkin Wim Sweldensz Peter Schreder www.aaron-lee.com 2. Feature-Based Volume Metamorphosis Apostolos Lerios, Chase D. Garfinkle, Marc Levoy \Lambda Computer Science Department Stanford University www-graphics.stanford.edu/~levoy По сжатию статических сеток : Есть несколько работ на www.ticam.utexas.edu(см. прошлое письмо) На research.micrisoft.com/~hoppe: 1. M. Eck, T. DeRose, T. Duchamp, T. Hoppe, H. Lounsbery, and W. Stuetzle. Multiresolution analysis of arbitrary meshes. In ACM Computer Graphics Proceedings, SIGGRAPHТ95, pages 173Ц180, 1995. 2. Effective implementation of Progressive meshes. На www.aaron-lee.com: 1. MAPS 2. Displaced Subdivision Surfaces Работа Lounsberry на ftp://cs.washington.edu/pub/graphics/TR931005b.ps.Z Вообще тут литературы тонны, лучше смотри в работах главу 'Related/Previos Works', и иди по ссылкам. Если будут конкретные вопросы, могу проконсультировать мылом. Пока, Andrey --- GoldED 3.00.Beta1+ * Origin: (2:5052/13.10) — RU.COMPRESS From : Eugene Goncharuk 2:5045/27.51 21 Sep 00 23:11:18 To : All Subj : Cжатие трёхмерной графики Как поживаете, All ? C уважением, Eugene Goncharuk. --- УТВЕРЖДАЮ. MSG-редактор капитан 2.5 ранга Голд Дедович фор ДОС UNREG * Origin: Интурист хорошо говорит! (2:5045/27.51) — RU.COMPRESS From : Eugene Goncharuk 2:5045/27.51 22 Sep 00 00:10:04 To : All Subj : Cжатие трёхмерной графики Как поживаете, All ? Расскажите что есть сабж. Hа каком принципе он реализован и как работает. Киньте в меня мылом докой если есть и очень буду благодарен за URL где можно по больше узнать по этой теме (можно на английском). C уважением, Eugene Goncharuk. --- УТВЕРЖДАЮ. MSG-редактор капитан 2.5 ранга Голд Дедович фор ДОС UNREG * Origin: Винамп заткнулся. Свет погас. В который раз......... (2:5045/27.51) — RU.COMPRESS From : Kirill Frolov 2:5030/946.25 22 Sep 00 10:27:12 To : Vladimir Vassilevsky Subj : GSM Hемедленно нажми на RESET, Vladimir! 20 Sep 00 15:43, Vladimir Vassilevsky wrote to All: VV> Есть куча разновидностей и реализаций этой схемы (ACELP, MPMLQ, VV> VSELP, VV> LDCELP, QCELP и.т.д.). CELPы являются, пожалуй, наилучшими по VV> качеству VV> речевыми кодерами при скоростях от ~16kbit/s до ~4.8kbit/s. А как узнать, какой у меня CELP в модеме? Имея дамп сжатых данных pазобpаться можно? Модем ещё говоpит "UMC;CELP;8", но это навеpное ни о чём не говоpит... :-( Мне нужно его pаскодиpовать для начала... --- [ZX] * Origin: Я Абсолютный Монаpх и мне повинуются звёзды... (2:5030/946.25)
Предыдущий блок Следующий блок Вернуться в индекс