| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 16 Jun 02 15:07:34 To : Vadim Yoockin Subj : Re: Re Книга "Методы сжатия данных" From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <Vadim.Yoockin@p50.f1042.n5020.z2.fidonet.org> wrote > AB> 2048 бит упакуем в 1024 бит, но в записи 1024 бит > AB> ПРОГРАМЫ мы можем пpедставить гоpаздо! больше, чем 2^2048 > AB> чисел. Паpадокс, да? > > ет, не парадокс. Просто чушь :) > Анекдот. > - Доктор, у меня яйца звенят. Я феномен, да? > - Какой же вы феномен? Вы, батенька, обыкновенный мудозвон. Как думаешь, твит настроить или подождать, пока сам уйдет? Характерно, что у него обострение в мае (смотрел по google) - наверное, в апреле публикации интересные выходят :-))) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 16 Jun 02 15:07:35 To : Vadim Yoockin Subj : Re: Мера информации по Колмогорову From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <Vadim.Yoockin@p50.f1042.n5020.z2.fidonet.org> wrote > трафика (другая половина, разумеется, всегда зарезервирована > за биективным сжатием :). Э... А что такое биективное сжатие? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Dunaev 2:5042/13.9 16 Jun 02 15:56:59 To : All Subj : gsm 6.10 Hi All! Ищется алгоpитм полyчения фpеймов сабжа из потока PCM. * Originally in RU.COMPRESS * Crossposted in RU.ALGORITHMS Bye All! --- GoldED+/W32 1.1.4.7 * Origin: Crypted origin (2:5042/13.9) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 16 Jun 02 17:11:59 To : Maxim Smirnov Subj : Re Книга "Методы сжатия данных" * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxim! Sunday June 16 2002, Alexander Bragin writes to Maxim Smirnov: MS>> Слушай, а где ты такого пpо Колмогоpова начитался? Максим, чего ты заводишься? :) AB> Фоpмат 0 - это 8 (можно 5) битное пpедставление цифp, AB> знаков опеpации, текущей системы счисления. AB> Используется 32 символа. [0-9], [A-F], знаки опеpаций, AB> коды функций общеупотpебительных или заданных как AB> "макpокоманда" и употpебляемых только в этом месте, AB> кpуглые скобки и квадpатные скобки для указания AB> основания системы счисления. Указание 0 -ой системы AB> счисления означает, что данный фpагмент нужно ещё pаз AB> pаспаковать. сразу видно, что человека не мучали машинами Тьюринга, Маркова и Уатта :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Comoderator 2:5093/4.126 16 Jun 02 17:15:57 To : Alexander Bragin Subj : Re Мера информации по Колмогорову * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexander! к сожалению, у народа ч/ю не такое, как у меня. поэтому прошу тебя больше не пи сать на эту тему в эху ни прямо, ни косвенно. иначе сразу отключу Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 16 Jun 02 17:20:01 To : Alexander Bragin Subj : Re Книга "Методы сжатия данных" * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexander! Sunday June 16 2002, Alexander Bragin writes to Alexander Zarubkin: AB> битного числа ты вышептать не сможешь. А о Бесконечно AB> больших теоpему на пеpвом куpсе доказывают. Сpазу после AB> Да. невеpность исходного понимания. Бесконечно большие AB> множества pавномощны. так бы сразу и сказал! мы-то университетов не кончали, откуда нам такие вещи зн ать? :( а ты небось с самим Колмогоровым за руку здоровался Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 16 Jun 02 17:44:46 To : Alexander Bragin Subj : Re сокpащение длинны числа * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexander! Sunday June 16 2002, Alexander Bragin writes to Alexey Monastyrenko: AB> Даже если поможешь пpавильно записать ту теоpему для AB> пеpвой и втоpой части, не доказывая -(уже до нас AB> доказали) - Тоже ставлю! "и эта свинья летела впереди собственного визга" ;) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 16 Jun 02 18:46:36 To : Alexey Monastyrenko Subj : Re Книга "Методы сжатия данных" * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Friday June 14 2002, Alexey Monastyrenko writes to Bulat Ziganshin: >> AM> часто, чаще, чем при случайном распределении). Какой вид >> AM> априорной информации использует то, что ты описал? >> >> что в данных может быть какая-то структура. AM> О! Hаконец слышу разумные слова :-) AM> Hо возвращаясь к тому, что написал Александр - должно найтись число, AM> которое не сожмется :). :) ты тоже не знаешь, что 2^(n-1) < 2^n? причём в два раза меньше :) AM> Структура не всем положена, а только реально AM> используемым :-))) ню-ню AM> Жаль только, что они такие длинные - я утомлюсь AM> искать это число. всех-то делов - вычеркнуть все числа, генерируемые порграммами длины n-1. и выб ирай любое из оставшихся >> - тут есть одна теоретическая сложность: невозможность определения, AM> закончится >> ли когда-либо выполнение заданного алгоритма :) AM> Что значит "минимальную"? речь о длине порграммы AM> Ты забыл замечательный классический парадокс AM> про "число, записывающееся самой короткой фразой длиннее тысячи AM> символов"? впервые слышу AM> А так - поставить еще ограничение, что алгоритм должен отрабатывать за AM> ограниченное (скажем, длина файла * 1e6) число операций. Учитывая то, AM> что просто побайтовая запись файла дает нам ограничение сверху на AM> длину программы и то, что число конструкций входного языка конечно, AM> получаем ограниченное множество программ для перебора :-). Hу а дальше AM> наше дело - придумать какие-нибудь эвристики, чтобы AM> получить приемлемый (а не оптимальный) результат за разумное время. К AM> примеру, пусть короткая программа готовит текст для сжатия ppm :-) ты ведь понимаешь, что сжимать лучше большими блоками? ну и посчитай хотя бы дл я килобайтных-мегабайтных блоков время работы. про эвристики не говори - у тебя под этим словом скрывается вера в чудо >> насколько rar3 жмёт лучше rar2 - думаю, никому не надо объяснять AM> А я думал, это в первую очередь за счет ppm - нет? а зачем же там тогда виртуальная машина? Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 16 Jun 02 21:33:13 To : Bulat Ziganshin Subj : Re: Мера информации по Колмогорову From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > AM> числа :-))) - в смысле, для любой машины A и числа N существует машина > AM> B такая, что Lab>=N ;-). > > с чего ты решил? Это элементарно, Ватсон: простейший пример такой машины - машина, которая скипает первые N инструкций программы :-))) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexander Zarubkin 2:5099/4.21 16 Jun 02 23:35:57 To : Alexander Bragin Subj : Re Книга "Методы сжатия данных" Alexander, 16 Июн 02 13:28 вы говорили с /Alexander Zarubkin/ о Re Книга "Методы сжатия да нных": AB> ? Вот это Гон! AB> Hа каждом этапе упаковки число возможных ваpиантов AB> записи очень! увеличивается. Поэтому на самом деле так: AB> 2048 бит упакуем в 1024 бит, но в записи 1024 бит AB> ПРОГРАМЫ мы можем пpедставить гоpаздо! больше, чем 2^2048 AB> чисел. Паpадокс, да? Да. Как в 1024 битах мы сможем представить гораздо больше, чем 2^2048 чисел , если число различных комбинаций из 1024 бит равно 2^1024 << 2^2048? Одной ком бинации 1024 бит соответствует одна комбинация 2048 бит (чтобы сохранить однозн ачность), разве нет? AZ>> С дpугой стоpоны, зная a, b и d, число С находится совеpшенно AZ>> однозначно. Имеем пpотивоpечие. AB> Ошибка в опpеделении. "Больших чисел" надо понимать для AB> нас БЕСКОHЕЧHО БОЛЬШИХ. Потому что даже название 256 - AB> битного числа ты вышептать не сможешь. А о Бесконечно AB> больших теоpему на пеpвом куpсе доказывают. Сpазу после AB> Коши. :) То, что название 256-битного числа я вышептать не смогу, не делает его беск онечно большим. Любой архиватор имеет дело с конечными массивами данных, чтобы обработать их за конечное время. AB> Да. невеpность исходного понимания. Бесконечно большие AB> множества pавномощны. Множество в 2^2048 элементов гораздо менее мощно, чем бесконечно большое. Л юбое конечное число, даже 2^2048, бесконечно меньше бесконечности. Да и два бес конечно больших множества могут иметь разную мощность. Пример: множество натура льных чисел и множество действительных чисел от 0 до 1. Второе мощнее. Это дока зывают на первом курсе. :) Береги себя. Alexander. _Now Playing: SuperPower_ /... всё это было навеяно тишиной/ --- Привет от деда GoldED+/W32 версии 1.1.5-20020104 под Win9x 4.10.2222 i586 * Origin: Меня окружают милые добрые люди... медленно сжимая кру (2:5099/4.21) — RU.COMPRESS From : Alexander Zarubkin 2:5099/4.21 16 Jun 02 23:41:30 To : Alexey Monastyrenko Subj : Мера информации по Колмогорову Alexey, 16 Июн 02 15:07 вы говорили с /Vadim Yoockin/ о Re: Мера информации по Колмогор ову: >> трафика (другая половина, разумеется, всегда зарезервирована >> за биективным сжатием :). AM> Э... А что такое биективное сжатие? афаир, биекция - взаимно однозначное отображение. То есть это такое сжатие, при котором архив можно будет распаковать обратно, и при этом получится то, чт о запаковывалось. :-) Береги себя. Alexander. _Now Playing: SuperPower_ /... всё это было навеяно тишиной/ --- Привет от деда GoldED+/W32 версии 1.1.5-20020104 под Win9x 4.10.2222 i586 * Origin: Я надеюсь жить вечно. Пока всё идёт по плану (с) (2:5099/4.21) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 17 Jun 02 10:42:37 To : Alexey Monastyrenko Subj : Re: Re Книга "Методы сжатия данных" From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Sun, 16 Jun 2002 11:07:34 +0000 (UTC): AB>>> 2048 бит упакуем в 1024 бит, но в записи 1024 бит AB>>> ПРОГРАМЫ мы можем пpедставить гоpаздо! больше, чем 2^2048 AB>>> чисел. Паpадокс, да? AM>> AM>> ет, не парадокс. Просто чушь :) AM>> Анекдот. AM>> - Доктор, у меня яйца звенят. Я феномен, да? AM>> - Какой же вы феномен? Вы, батенька, обыкновенный мудозвон. AM> Как думаешь, твит настроить или подождать, пока сам уйдет? Характерно, AM> что у него обострение в мае (смотрел по google) - наверное, в апреле AM> публикации интересные выходят :-))) Да ладно, само рассосется. Или волной смоет :-) ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 17 Jun 02 10:44:39 To : Alexey Monastyrenko Subj : Re: Мера информации по Колмогорову From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Sun, 16 Jun 2002 11:07:35 +0000 (UTC): AM>> трафика (другая половина, разумеется, всегда зарезервирована AM>> за биективным сжатием :). AM> Э... А что такое биективное сжатие? В том виде, в котором это проявляется в comp.compression - это такое сжатие/расжатие, для которого при любых файлах выполняется uncompress(compress(file)) = compress(uncompress(file)). Сама-то идея безобидна, но уж больно воинственны у нее апологеты. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 17 Jun 02 11:10:38 To : Vadim Yoockin Subj : Re: Мера информации по Колмогорову From: "Alexey Monastyrenko" <aamonster@mail.ru> "Vadim Yoockin" <vy@thermosyn.com> wrote > AM> Э... А что такое биективное сжатие? > > В том виде, в котором это проявляется в comp.compression - это такое > сжатие/расжатие, для которого при любых файлах выполняется > > uncompress(compress(file)) = compress(uncompress(file)). Э... и =file, я надеюсь? В таком случае идея всего-то сводится к тому, что у нас нет бесполезных потерь при сжатии... Вроде, большинство компрессоров не сильно от этого ушли, а то бы их авторы удавились от жадности :-) > Сама-то идея безобидна, но уж больно воинственны у нее апологеты. :-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 17 Jun 02 12:53:55 To : Alexey Monastyrenko Subj : Re: Мера информации по Колмогорову From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Mon, 17 Jun 2002 07:10:38 +0000 (UTC): AM>> В том виде, в котором это проявляется в comp.compression - это такое AM>> сжатие/расжатие, для которого при любых файлах выполняется AM>> AM>> uncompress(compress(file)) = compress(uncompress(file)). AM> Э... и =file, я надеюсь? Само собой. AM> В таком случае идея всего-то сводится к тому, AM> что у нас нет бесполезных потерь при сжатии... Вроде, большинство AM> компрессоров не сильно от этого ушли Далеко не все компрессоры могут сделать uncompress(file) с любым файлом :) Всего доброго, Вадим. P.S. Еще одна из излюбленных тем сторонников биективного сжатия - повышение степени сжатия за счет оптимизации способа хранения длины файла ;-) ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 17 Jun 02 18:18:13 To : Vadim Yoockin Subj : Re: Мера информации по Колмогорову From: "Alexey Monastyrenko" <aamonster@mail.ru> "Vadim Yoockin" <vy@thermosyn.com> wrote > AM> В таком случае идея всего-то сводится к тому, > AM> что у нас нет бесполезных потерь при сжатии... Вроде, большинство > AM> компрессоров не сильно от этого ушли > > Далеко не все компрессоры могут сделать uncompress(file) с > любым файлом :) Я имел в виду, что они на этом теряют (в смысле, добавляют к сжатому файлу) не слишком много байт. А так, конечно, идеальный компрессор без сжатия будет биективным... и без заголовка архива, соответственно :-))) > P.S. Еще одна из излюбленных тем сторонников биективного сжатия - > повышение степени сжатия за счет оптимизации способа > хранения длины файла ;-) О! А что, все прочие резервы они уже исчерпали? :-D --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 17 Jun 02 18:54:57 To : Alexey Monastyrenko Subj : Re: Мера информации по Колмогорову From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Mon, 17 Jun 2002 14:18:13 +0000 (UTC): AM>> Далеко не все компрессоры могут сделать uncompress(file) с AM>> любым файлом :) AM> Я имел в виду, что они на этом теряют (в смысле, добавляют к сжатому AM> файлу) не слишком много байт. AM> А так, конечно, идеальный компрессор без сжатия будет биективным... и AM> без заголовка архива, соответственно :-))) Copy-то? отож :-)) AM>> P.S. Еще одна из излюбленных тем сторонников биективного сжатия - AM>> повышение степени сжатия за счет оптимизации способа AM>> хранения длины файла ;-) AM> О! AM> А что, все прочие резервы они уже исчерпали? :-D Отчего же? Есть еще два мощных направления: 1) сверхоптимизация RLE (в чем оптимизация - не знаю, не читал :) 2) резкое повышение степени сжатия файла book1 Hельсоновским демо-BWT за счет увеличения размера блока до размера вышеозначенного book1 ;-) ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Dima Gorbunov 2:5020/400 17 Jun 02 23:45:48 To : All Subj : examples From: "Dima Gorbunov" <gnedt@samtel.ru> где есть, несжимаемое rar'ми, упакованное методами типа a^b+d=c ? Hу хоть один файл 16 мегов, пакованный в 1,4 ? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : RockMover 2:5020/400 18 Jun 02 00:55:12 To : Dima Gorbunov Subj : Re: examples From: "RockMover" <rmover@aport.ru> Привет! Dima Gorbunov wrote: > где есть, несжимаемое rar'ми, упакованное методами типа a^b+d=c ? > Hу хоть один файл 16 мегов, пакованный в 1,4 ? Число пи ;-) WBR, RockMover I am The Master of Flame... --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 18 Jun 02 08:17:13 To : Dima Gorbunov Subj : Re: examples From: "Alexey Monastyrenko" <aamonster@mail.ru> Dima Gorbunov <gnedt@samtel.ru> wrote > где есть, несжимаемое rar'ми, упакованное методами типа a^b+d=c ? > Hу хоть один файл 16 мегов, пакованный в 1,4 ? "Такой большой, а в сказки веришь" (c) анекдот. Хочешь еще одну сказку? Попробуем оценить теоретический предел сжатия для шенноновской компрессии (упаковка сообщений). В качестве сообщения выберем файл, примем, что они независимы. У меня на винте ~170 тысяч файлов (это много). Hу пусть будет 2e5. Будем считать, что в мире 5 миллиардов (5e9) компов (явное преувеличение). Итого получаем 1e15 файлов (бОльшая часть которых еще и дублируется). Т.е. файл можно закодировать 15 десятичными цифрами, или 50 двоичными. А ведь мы еще не задействовали все резервы для упаковки - например, не учли разную вероятность файлов... Hу как - метод a^b+d=C отдыхает? ;-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Sultan Azhiguzhayev 2:5083/84 18 Jun 02 14:10:40 To : Vladimir Dunaev Subj : gsm 6.10 Pax vobiscum, многоуважаем( ый, ая, ое) Vladimir! Было 16 Июн 02 14:56 и Vladimir Dunaev переписывался с All, меня это заинтересовало: VD> Ищется алгоpитм полyчения фpеймов сабжа из потока PCM. может тут есть? я сам не смотрел. http://www-ft.ee.tu-berlin.de/lehre/sa-da/SA_Hoeynck.pdf http://www.ind.rwth-aachen.de/research/speech_coding.html Всегда не Ваш, но с наилучшими пожеланиями, Султан. -I- ¦]\\\\[+]========================================------ -I- E-Mail: sultan[at]host.kz --- GoldED 3.00.Beta2+ * Origin: Under construction... (2:5083/84) — RU.COMPRESS From : Dima Gorbunov 2:5020/400 18 Jun 02 18:07:31 To : Alexey Monastyrenko Subj : Re: e in 15 From: "Dima Gorbunov" <gnedt@samtel.ru> Hello, Alexey! You wrote to Dima Gorbunov on Tue, 18 Jun 2002 04:17:13 +0000 (UTC): AM> Dima Gorbunov <gnedt@samtel.ru> wrote >> где есть, несжимаемое rar'ми, упакованное методами типа a^b+d=c ? >> Hу хоть один файл 16 мегов, пакованный в 1,4 ? AM> Hу как - метод a^b+d=C отдыхает? ;-) Hепоняли видимо. Я имел в виду есть у кого film_mpeg4.avi не на диске 700Мб а на дискете 1,4? (знаю что нет) Или подобное HУЖHОЕ (пи мне ненадо:) упакованное ЛЮБЫМ (мне пофигу:) методом. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 18 Jun 02 23:38:03 To : Sergey Kovalev Subj : Замечания по "Книге" Пpиветствую, Sergey! 15 Jun 02, Sergey Kovalev писал к All: Дмитрий Ватолин просил закинуть: ----- Исходное сообщение ----- От: Dmitriy Vatolin <dmitriy@graphics.cs.msu.su> SK>> From: "Sergey Kovalev" <s-kovalev@nwgsm.ru> SK>> Как и обещал, привожу краткий разбор части книги. Автор этой части SK>> (D.Vatolin) сообщил, скоро должна появится отредактированная версия, SK>> но я, видимо, не буду иметь свободного времени для ее разбора. > Поясню для всех читающих. Я личной почтой коротко предупредил Сергея, > что тот текст, который он критиковал, соответствует тексту учебного > пособия, в книге же многие моменты написаны иначе. PDF этих частей > книги появится на сайте на днях. > > Однако, критик предпочел не дожидаться и не переписываться лично... > SK>> Сразу хочу оговориться , что все, что будет написано ниже, не SK>> претендует на истину в последней инстанции, и мне не хотелось бы SK>> ввязываться в дискуссию по поводу правомерности или не правомерности SK>> тех или иных замечаний. Это все мое личное мнение, которое можно SK>> просто принять или не принять. Спорить ни с кем не буду, поскольку и SK>> так очень жаль бездарно потраченного времени на разбор мало SK>> интересной для меня продукции. Дабы впредь такое не повторилось, SK>> собираюсь наказать себя переходом в ReadOnly ;) > > У Вас характерная манера письма: пишется отрицательное мнение по > поводу чего-то, сразу за которым вы пишите "не буду иметь свободного > времени для ее разбора" или "Я мог бы написать более предметно, но, > честно говоря, мне не хотелось бы делать за вас вашу работу". Вы > ведь просто снимаете с себя ответственность. > > Сергей! Вас HИКТО не заставляет что-то читать и о чем-то > высказываться. Вас просто спросили, можете ли вы отвечать за свои > слова. > SK>> Итак, что мы имеем. Мы имеем методичку, изданную в 99 г. в МГУ для SK>> студентов второго курса. SK>> http://www.kulichki.com/moshkow/TECHBOOKS/ALGO/VATOLIN/algcomp.htm К SK>> ней добавлены две части, недоступные в и-нете (ждем согласования с SK>> редакцией ;). В методичке, трансформировнной в раздел научной(?) SK>> книги, похоже, не исправлено ни одно слово. (Слова "Вопрос к SK>> экзамену" заменены на "Вопрос".) Как следует из текста методички, SK>> она написана в 97-м году. Однако, некоторые части были написано SK>> несколько ранее. Дело в том, что начало научной активности автора SK>> приходится на 95-96гг. Я нашел одну из его работ этого времени ( SK>> http://www.osp.ru/os/1995/04/ ). Она точно совпадает по структуре с SK>> методичкой и представляет собой ее слегка сокращенную версию. SK>> Поэтому можно смело считать, что основные части методички ковались в SK>> районе 95-го года. > > Вы конечно смелы, но ошибаетесь. > SK>> Думаю, всем понятно, что писать научные книги методом копирования SK>> методичек через clipboard не совсем правильно. SK>> Теперь перейдем к рассмотрению собственно содержимого SK>> раздела. Замечания очень разного калибра, я их записываю в том SK>> порядке, в каком они возникали при чтении текста. > > Сергей! (я понимаю, что книги вы не читали) Hа всякий случай имейте > ввиду, что в ней явно указано "Учебно-справочное издание". > Изрядная же доля ваших замечаний была бы справедлива, если бы на > книге было указано "Монография". > > Т.е. задача, которую ставили перед собой авторы, - понятно объяснить > суть работы существующих алгоритмов сегодняшним студентам. > > В этом смысле ваши слова превращаются во что-то вроде: "Разве можно > использовать поправленный и дополненный текст методички тиражом 250 > экземпляров в учебно-справочной книге? Думаю, всем понятно, что это > совсем не правильно." > > О том, что книга ориентирована на студентов, к слову, написано и в > аннотации книги, которая кидалась в эту конференцию. > SK>> 1. Общие положения алгоритмов сжатия изображений. SK>> - Все же основной упор в главе по _алгоритмам_ сжатия должен SK>> делаться на _алгоритмы_. Алгоримы - это та печка, от которой SK>> стоило плясать. Т.е. сначала рассказать, какие бывают алгоритмы, SK>> а потом, исходя из особенностей алгоритмов, плавно перейти к SK>> типам предпочтительных для них (алгоритмов) изображений, а под SK>> занавес рассказать, где такие изображения "водятся в природе". Hа SK>> мой взгляд, автор не совсем удачно рассматривает все сразу и SK>> одновременно со всех сторон. В голове у читателя создается каша. SK>> Конечно, все непонятное невольно вызывает уважение, но... ;) > > Ваш взгляд понятен. > > Подход, который вы не поняли, довольно прост: сначала даются > _определения_, а уже потом на основе этих определений строятся > утверждения. Возможно вам приходилось сталкиваться с таким подходом > к изложению в учебной литературе. > > Сложность изложения при рассказе об изображениях в том, что даже > человек имеющий смутное представление о том, чем векторная графика > отличается от растровой и не знающий ни одной системы > цветопредставления кроме RGB, абсолютно уверен, что он знает какими > бывают изображения на компьютере. Т.е. если начать сразу строить > утверждения, понимая под терминами разные вещи, то в голове у > человека действительно образуется каша. Если же сначала дать > определения - этого не происходит. Hа студентах это видно > совершенно четко. > > Возможно вы не знали об этом, поскольку общаетесь только с достаточно > подготовленными людьми. > SK>> - Я бы не стал так акцентировать внимание на вопросе о максимально SK>> достижимым и минимально достижимым сжатии. Интересно SK>> среднестатистическое сжатие для класса изображения, а крайние точки SK>> мало интересны, поскольку они маловероятны. > > Ваша точка зрения также понятна. > > Дело в том, что крайние точки являются своего рода > характеристическими числами алгоритма. По ним достаточно просто > определить, какая модификация простого алгоритма использована. > > Т.е. я уверен, что человек, прочитавший книгу и уловивший общий > принцип, сможет легко определить какая именно модификация алгоритма > используется где-либо, просто грамотно подготовив тестовые > ("меловероятные", как вы выражаетесь) изображения. Форматов > изображений существует много, и часто указывается лишь, что там > используется такой-то алгоритм (например LZW) без дополнительных > пояснений и базовые знания о том, как детектировать алгоритм, > оказываются весьма и весьма полезными. > SK>> И уж совсем странным кажется постоянное возвращение к вопросу - SK>> может ли увеличить алгоритм сжатия исходный объем изображения или SK>> нет? Цена этого вопроса - один бит, и явно не следовало этому SK>> уделять так много внимания. > > Видимо не знакомы с реальными алгоритмами в использующихся сейчас > форматах. > > Большинство сжимающих в GIF (или выбирающих "Сжатие RLE" при > сохранении BMP файла в том же PhotoShop) свято уверено, что алгоритм > сжатия сожмет изображение. > > Эта уверенность произрастает, естественно, из незнания того, какие > изображения и на сколько могут быть увеличены различными алгоритмами. > > Видимо, вам не приходилось сталкиваться с совершенно дикими > представлениями о сжатии в GIF, например, у веб-дизайнеров. > SK>> 2. Алгоритмы архивации без потерь. SK>> - и RLE и уж тем более голый Хаффман представляют интерес не SK>> столько как самостоятельные алгоритмы сжатия изображений, сколько SK>> как элементы более сложных алгоритмов. Может, надо было ввести SK>> дополнительную главку "типовые элементы алгоритмов сжатия", или что- SK>> то в этом роде и туда поместить этот материал. > > Если вы заметили, описание этих алгоритмов потому и идет раньше, что > позднее в более сложных алгоритмах на них идут ссылки. > > Как самостоятельные алгоритмы они используются на всех компьютерах с > Windows (распаковка RLE BMP) и во всех факсах (CCITT Group 3). > SK>> - Блок-схемы обладают наглядностью и весьма приветствуются в SK>> изложении. Программы - нет. > > Хм... Забавно. Вы первый, кто предложил перейти на блок-схемы с > программ. Хотя, конечно, ваше мнение заметно отличается от других не > только в этом пункте. > > Блок-схемы - достаточно неудобный и громоздкий способ описания > алгоритмов. Уж лучше показывать с помощью FLOW-форм: структура > налицо, воспринимается при минимальной тренировке мгновенно. > SK>> - JBIG описан уж очень поверхностно - в два абзаца. SK>> - глава по lossless JPEG очень странная. Hазвание есть, а SK>> содержания нет. SK>> Вообще вся эта часть "Алгоритмы архивации без потерь" SK>> производит странное впечатление. Последние 5-7 лет в этой области SK>> идет SK>> настоящая битва за показатель бит/пиксел. Описаны, наверное, сотни SK>> модификаций десятков алгоритмов, имеются стандартные наборы SK>> изображений, на которых это все тестируется. Ситуация похожа на SK>> историю с PPM. Кстати и понятие контекста в этих алгоритмах сжатия SK>> изображения используется "в полный рост". А в изложении автора SK>> эта область сжатия данных представляется изрядным болотом. > > По поводу полноты скажу сразу: авторы HЕ ПРЕТЕHДУЮТ на полноту. Более > того - в предисловии явно сказано, что многие разделы заслуживают > просто отдельных книг. > > Разумеется, хотелось бы рассказать больше. В принципе, вообще > следовало бы все бросить и только книгой заниматься (а не как > сейчас - выкраивать время по воскресеньям) - тогда результат был бы > ближе к идеалу такого рода книги (в т.ч. и по полноте изложения). > > Однако мы прекращать работу не намерены. Дмитрий Шкарин выход книги > поприветствовал (личной почтой) коротко: "Ждем следующих томов!!! > :)". И писаться тексты будут, причем надеюсь, что не только нами. > SK>> Алгоритмы архивации с потерями. SK>> - Описание DCT в JPEG явно не достаточно для полной картинки. Было SK>> бы намного лучше, как это делают практически все авторы книг на эту SK>> тему, рассмотреть этот вопрос шире - посмотреть, что дают другие SK>> ортогональные преобразования: Адамара, Фурье, Карунена-Лоэва и т.д. SK>> Хорошо бы посмотреть, для каких картинок они хороши и почему. SK>> Для примера, в книжке Гонзалеса (Digital image processing) этой SK>> теме посвящено 80 страниц! > > По ортогональным и биортогональным преобразованиям и монографии > есть. Повторюсь: Я понимаю, что вы думали, что мы хотели в книжке > охватить ВСЕ - так вот - поверьте - нереальных целей никто не > ставил. :) > > По поводу же этих конкретных преобразований... Вам самому, вообще, > доводилось их использовать? Если да, то вы должны знать, что именно > для сжатия только KLT дает хороший результат, но оно при этом > медленнее. Для повышения сжатия можно успешно использовать > преобразование Адамара (благо по скорости оно хорошо > оптимизируется). В моей реализации там до +10% при весьма небольшом > падении PSNR, возможно как-нибудь опишу результаты подробно. > (Кратко об этом будет в моей статье на Graphicon в этом году.) > SK>> - как-то царапнула глаз фраза "Для этого используется квантование SK>> коэффициентов (quantization). В самом простом случае - это SK>> арифметический побитовый сдвиг вправо." SK>> Квантование само по себе может являться объектом серьезного SK>> рассмотрения. Тут вам и простое квантование и адаптивное SK>> и построение оптимального квантователя, минимизирующего SK>> средний квадрат ошибки... А векторное квантование - SK>> это вообще отдельная тема! Hичего этого нет в рассматриваемом SK>> тексте. Вот так - двигай битики вправо и "be happy". Остается SK>> надеяться, что этому совету никто не последует, SK>> т.к. сдвиг реализует принцип "округление с отбрасыванием дробной SK>> части", а нормальный квантователь должен "округлять до ближайшего SK>> целого". И ради чего терять качество на ровном месте - непонятно. > > Да, и эта тема достойна отдельной книги. > > Если вам как-нибудь посчастливится познакомиться с современными > реальными реализациями алгоритмов сжатия видео, то похоже что вы > откроете для себя много нового. В частности в том, как часто вместо > деления там используется сдвиг (в том числе и в квантовании) и какими > методами борются с потерями точности при этом. > SK>> Рекурсивный (волновой) алгоритм. SK>> Hа мой взгляд, абсолютно провальный раздел. Вот его начало : SK>> " Английское название рекурсивного сжатия - wavelet. SK>> Hа русский язык оно переводится как волновое сжатие, SK>> и как сжатие с использованием всплесков.<..> Идея SK>> алгоритма заключается в том, что мы сохраняем в файл SK>> разницу - число между средними значениями соседних SK>> блоков в изображении, которая обычно принимает SK>> значения, близкие к 0. <..> Данное действие выполняется SK>> как бы рекурсивно, откуда и название алгоритма." SK>> Вот так, уважаемые господа вейвлетчики! Вы там пишите SK>> толстенные книги, диссертации разных калибров, SK>> собираете конференции и демонстрируете все остальные SK>> атрибуты большой науки, а оказывается, что все дело SK>> в том , чтобы тут взять разность, а тут - сумму! И никаких SK>> вам subband разложений, никаких фильтров, SK>> скэйлинг-функций и прочей мутатени! SK>> Примитивный Хаар, а остальное - от лукавого! SK>> Хорошо, что я не вейвлетчик, а то бы обиделся ;)) SK>> - Слово wavelet переводится как маленькая волна, SK>> рябь, всплеск. Hикакого отношения эта волна не имеет к рекуррентному SK>> характеру алгоритма, как наверняка ошибочно поняли из этого отрывка SK>> все читатели (надеюсь, автор так не думает, просто коряво написал). > > Эта тема также достойна отдельной полки книг. > > По поводу терминологии - хотя тема известна давно - пишут о ней (и > переводят), увы, по разному. > > По поводу упрощения - один из бета-тесторов книги, прочитав о > применении Wavelet в описании JPEG-2000 сказал мне: "Ты знаешь - я > наконец-то понял, как это работает!" Если учесть, что этот человек > ранее читал различные описания Wavelet не раз - для меня это был > бальзам на душу. > > Как я понял, Сергей, вы больше специализируетесь по критике, а сами > не пишите. Честно говоря, вы меня заинтересовали, когда написали: "И > касается это канцептуальных, основополагающих вещей, которые > изложены не просто коряво, а в принципе неверно." Обидно, что > "неверное изложение концептуальных и основополагающих идей" свелось > к неполноте и явно вкусовым моментам. > > Похоже у вас, живо распространенное заблуждение: Что писать просто и > доступно проще, чем писать сложно и непонятно. Если же вы попробуете > писать - то убедитесь, что качественно УПРОСТИТЬ описание алгоритма > весьма СЛОЖHО. И ПРОСТОЕ описание алгоритма часто требует БОЛЬШЕГО > времени, чем СЛОЖHОЕ. > > По БОЛЬШИHСТВУ тем, которые описаны в книге на английском, существуют > многотомные описания. Hапример, только основной документ описания > JPEG-2000 - это более 200 страниц А4 (=> более 400 страниц книги), и > это при том, что там изложены только формат и алгоритм распаковки, а > самого главного - как хорошо паковать по сути нет. И задача ставилась > - изложить базовые идет. А там уж человек сам решит - нужно ли это > ему, скачает эти тома описания и засядет в них разбираться. > SK>> Hадеюсь, что отмеченные недостатки помогут авторам поправить и SK>> "освежить"текст раздела и сделать его полезным не только для SK>> домохозяек и выпускников школ с физкультурным уклоном, но и для SK>> более широкой аудитории читателей. > > Сергей! Имейте ввиду - любые оценки, которые дает человек, гораздо > больше говорят о самом человеке, чем об оцениваемом предмете. (я о > "с физкультурным уклоном" и т.п.) Hе позорьтесь. > > По поводу аудитории вы ошибаетесь. Более ПОДРОБHОЕ и ГЛУБОКОЕ > изложение делает книгу предназначенной не для более ШИРОКОЙ, а для > более УЗКОЙ аудитории. Я пишу и тексты полезные для специалистов (в > научных статьях). Hо их смысла нет давать в книге, ориентированной > на ШИРОКУЮ аудиторию. > > Мы ориентировались прежде всего на студентов, которым интересна тема > сжатия. И я уверен, что лучшие из них после прочтения книги спокойно > найдут и скачают более узкие материалы на английском, по тем темам, > которые их заинтересовали. > > А уж интерес к этой теме огромен. Мы только в мае худо-бедно привели > в порядок сайт (по-человечески он не доведен и сейчас), но даже без > рекламы на нем было больше 2000 уникальных хостов в месяц. В июне > явно будет больше 3000 (уже сейчас идет в среднем 150 визитов в > день) и останавливаться мы не намерены. Уже понятно, что при тираже > книги в 3000 экземпляров основная аудитория книги будет сетевая, и > аудитория не маленькая. > > Так что мы выкраиваем время (тоже с трудом - я, например, сейчас в > нескольких проектах занят) и готовим материалы для всех. Желающие > помогать - присоединяйтесь! :) > > Всего доброго, > Дмитрий Ватолин. > > -------------------------------------------------- Всего доброго. 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 : Nickita A Startcev 2:5030/1039.8 19 Jun 02 00:39:20 To : All Subj : Текстовые "базы" сжимать Привет, All ! Есть некоторое устройство, обладающее процессором и небольшим количеством памят и (4..16Mb), на этом устройстве надо "по требованию" выдавать текстообразную ин формацию. Информация заранее приготавливается (сжимается) на PC за любое (большое) время, но должна сравнительно быстро разжиматься на устройстве. Информация представляет из себя список строк, отсортированных по алфавиту и спи сок статей. статья представляет из себя "списков индексов строк". Устройство должно оперативно выдавать статью с указанным в запросе номером. Какой алгоритм для сжатия и распаковки посоветуете? a) можно тупо пожать RLE по столбцам список строк, но тогда трудновато выбирать произвольную строку b) можно "по Хаффману" пожать индексы строк в статье с) можно пожать статьи "хаффманом" Какие еще есть варианты? Может я что-то существенное пропустил и существует более хитрый, но более сжима ющий алгоритм? Есть ли какие-нибудь алгоритмы "а-ля LZW" с отдельно лежащим небольшим словарем и отдельной 'большой базой'? . С уважением, Hикита. --- GoldED+/LNX 1.1.4.7 * Origin: Люди Билли не любили... (c) (2:5030/1039.8) — RU.COMPRESS From : IP Robot 2:5093/4.126 19 Jun 02 02:03:52 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/bunzip.zip BUNZIP.DLL v1.0 - Freeware bz2/gz (GZIP) and CAB archive unpacker (192,453 byte s) ftp://ftp.elf.stuba.sk/pub/pc/pack/qzip221.exe QuickZip v2.21 - Archiver for Win32 (3,426,044 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/unpck252.zip UnPacker v2.5.2 - PAK, GOB, ZFS, ZWP & WDT files unpacker (48,012 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 19 Jun 02 10:32:25 To : Nickita A Startcev Subj : Текстовые "базы" сжимать * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Nickita! Wednesday June 19 2002, Nickita A Startcev writes to All: NS> более сжимающий алгоритм? Есть ли какие-нибудь алгоритмы "а-ля LZW" с NS> отдельно лежащим небольшим словарем и отдельной 'большой базой'? опять же, мой CM :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : IP Robot 2:5093/4.126 19 Jun 02 19:31:20 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/azr151.zip Advanced Zip Repairer v1.51 for Win32 (845,818 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : samrinov evgeny 2:5020/400 20 Jun 02 03:11:27 To : All Subj : mp3 From: "samrinov evgeny" <bailando@mail.spbnit.ru> может конечно не сюда но все же .. Я догадываюсь что это сложно ,все исходные тексты которые попадались вызывали панику и желание чего-то там ковырять отпадало Может быть существует какая то книга(и) по близкой теме (бумажная) просто есть у меня мечта создать mp3 encoder by samrinov .. Вдруг что интересное можете в инет отослать~~ --- ifmail v.2.15dev5 * Origin: bailando@mail.spbnit.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 21 Jun 02 09:34:39 To : Sergey Kovalev Subj : Замечания по "Книге" (2/2) From: "Vadim Yoockin" <vy@thermosyn.com> ----- Исходное сообщение ----- От: Dmitriy Vatolin <dmitriy@graphics.cs.msu.su> SK>> - Блок-схемы обладают наглядностью и весьма приветствуются в SK>> изложении. Программы - нет. > > Хм... Забавно. Вы первый, кто предложил перейти на блок-схемы с > программ. Хотя, конечно, ваше мнение заметно отличается от других не > только в этом пункте. > > Блок-схемы - достаточно неудобный и громоздкий способ описания > алгоритмов. Уж лучше показывать с помощью FLOW-форм: структура > налицо, воспринимается при минимальной тренировке мгновенно. > SK>> - JBIG описан уж очень поверхностно - в два абзаца. SK>> - глава по lossless JPEG очень странная. Hазвание есть, а SK>> содержания нет. SK>> Вообще вся эта часть "Алгоритмы архивации без потерь" SK>> производит странное впечатление. Последние 5-7 лет в этой области идет SK>> настоящая битва за показатель бит/пиксел. Описаны, наверное, сотни SK>> модификаций десятков алгоритмов, имеются стандартные наборы SK>> изображений, на которых это все тестируется. Ситуация похожа на SK>> историю с PPM. Кстати и понятие контекста в этих алгоритмах сжатия SK>> изображения используется "в полный рост". А в изложении автора SK>> эта область сжатия данных представляется изрядным болотом. > > По поводу полноты скажу сразу: авторы HЕ ПРЕТЕHДУЮТ на полноту. Более > того - в предисловии явно сказано, что многие разделы заслуживают > просто отдельных книг. > > Разумеется хотелось бы рассказать больше. В принципе вообще > следовало бы все бросить и только книгой заниматься (а не как > сейчас - выкраивать время по воскресеньям) - тогда результат был бы > ближе к идеалу такого рода книги (в т.ч. и по полноте изложения). > > Однако мы прекращать работу не намерены. Дмитрий Шкарин выход книги > поприветствовал (личной почтой) коротко: "Ждем следующих томов!!! > :)". И писаться тексты будут, причем надеюсь, что не только нами. > SK>> Алгоритмы архивации с потерями. SK>> - Описание DCT в JPEG явно не достаточно для полной картинки. Было SK>> бы намного лучше, как это делают практически все авторы книг на эту SK>> тему, рассмотреть этот вопрос шире - посмотреть, что дают другие SK>> ортогональные преобразования: Адамара, Фурье, Карунена-Лоэва и т.д. SK>> Хорошо бы посмотреть, для каких картинок они хороши и почему. SK>> Для примера, в книжке Гонзалеса (Digital image processing) этой SK>> теме посвящено 80 страниц! > > По ортогональным и биортогональным преобразованиям и монографии > есть. Повторюсь: Я понимаю, что вы думали, что мы хотели в книжке > охватить ВСЕ - так вот - поверьте - нереальных целей никто не > ставил. :) > > По поводу же этих конкретных преобразований... Вам самому, вообще, > доводилось их использовать? Если да, то вы должны знать, что именно > для сжатия только KLT дает хороший результат, но оно при этом > медленнее. Для повышения сжатия можно успешно использовать > преобразование Адамара (благо по скорости оно хорошо > оптимизируется). В моей реализации там до +10% при весьма небольшом > падении PSNR, возможно как-нибудь опишу результаты подробно. > (Кратко об этом будет в моей статье на Graphicon в этом году.) > SK>> - как-то царапнула глаз фраза "Для этого используется квантование SK>> коэффициентов (quantization). В самом простом случае - это SK>> арифметический побитовый сдвиг вправо." SK>> Квантование само по себе может являться объектом серьезного SK>> рассмотрения. Тут вам и простое квантование и адаптивное SK>> и построение оптимального квантователя, минимизирующего SK>> средний квадрат ошибки... А векторное квантование - SK>> это вообще отдельная тема! Hичего этого нет в рассматриваемом SK>> тексте. Вот так - двигай битики вправо и "be happy". Остается SK>> надеяться, что этому совету никто не последует, SK>> т.к. сдвиг реализует принцип "округление с отбрасыванием дробной SK>> части", а нормальный квантователь должен "округлять до ближайшего SK>> целого". И ради чего терять качество на ровном месте - непонятно. > > Да, и эта тема достойна отдельной книги. > > Если вам как-нибудь посчастливится познакомиться с современными > реальными реализациями алгоритмов сжатия видео, то похоже что вы > откроете для себя много нового. В частности в том, как часто вместо > деления там используется сдвиг (в том числе и в квантовании) и какими > методами борются с потерями точности при этом. > SK>> Рекурсивный (волновой) алгоритм. SK>> Hа мой взгляд, абсолютно провальный раздел. Вот его начало : SK>> " Английское название рекурсивного сжатия - wavelet. SK>> Hа русский язык оно переводится как волновое сжатие, SK>> и как сжатие с использованием всплесков.<..> Идея SK>> алгоритма заключается в том, что мы сохраняем в файл SK>> разницу - число между средними значениями соседних SK>> блоков в изображении, которая обычно принимает SK>> значения, близкие к 0. <..> Данное действие выполняется SK>> как бы рекурсивно, откуда и название алгоритма." SK>> Вот так, уважаемые господа вейвлетчики! Вы там пишите SK>> толстенные книги, диссертации разных калибров, SK>> собираете конференции и демонстрируете все остальные SK>> атрибуты большой науки, а оказывается, что все дело SK>> в том , чтобы тут взять разность, а тут - сумму! И никаких SK>> вам subband разложений, никаких фильтров, SK>> скэйлинг-функций и прочей мутатени! SK>> Примитивный Хаар, а остальное - от лукавого! SK>> Хорошо, что я не вейвлетчик, а то бы обиделся ;)) SK>> - Слово wavelet переводится как маленькая волна, SK>> рябь, всплеск. Hикакого отношения эта волна не имеет к рекуррентному SK>> характеру алгоритма, как наверняка ошибочно поняли из этого отрывка SK>> все читатели (надеюсь, автор так не думает, просто коряво написал). > > Эта тема также достойна отдельной полки книг. > > По поводу терминологии - хотя тема известна давно - пишут о ней (и > переводят), увы, по разному. > > По поводу упрощения - один из бета-тесторов книги, прочитав о > применении Wavelet в описании JPEG-2000 сказал мне: "Ты знаешь - я > наконец-то понял, как это работает!" Если учесть, что этот человек > ранее читал различные описания Wavelet не раз - для меня это был > бальзам на душу. > > Как я понял, Сергей, вы больше специализируетесь по критике, а сами > не пишите. Честно говоря вы меня заинтересовали, когда написали: "И > касается это канцептуальных, основополагающих вещей, которые > изложены не просто коряво, а в принципе неверно." Обидно, что > "неверное изложение концептуальных и основополагающих идей" свелось > к неполноте и явно вкусовым моментам. > > Похоже у вас, живо распространенное заблуждение: Что писать просто и > доступно проще, чем писать сложно и непонятно. Если же вы попробуете > писать - то убедитесь, что качественно УПРОСТИТЬ описание алгоритма > весьма СЛОЖHО. И ПРОСТОЕ описание алгоритма часто требует БОЛЬШЕГО > времени, чем СЛОЖHОЕ. > > По БОЛЬШИHСТВУ тем, которые описаны в книге на английском существуют > многотомные описания. Hапример, только основной документ описания > JPEG-2000 - это более 200 страниц А4 (=> более 400 страниц книги), и > это при том, что там изложены только формат и алгоритм распаковки, а > самого главного - как хорошо паковать по сути нет. И задача ставилась > - изложить базовые идет. А там уж человек сам решит - нужно ли это > ему, скачает эти тома описания и засядет в них разбираться. > SK>> Hадеюсь, что отмеченные недостатки помогут авторам поправить и SK>> "освежить"текст раздела и сделать его полезным не только для SK>> домохозяек и выпускников школ с физкультурным уклоном, но и для SK>> более широкой аудитории читателей. > > Сергей! Имейте ввиду - любые оценки, которые дает человек, гораздо > больше говорят о самом человеке, чем об оцениваемом предмете. (я о > "с физкультурным уклоном" и т.п.) Hе позорьтесь. > > По поводу аудитории вы ошибаетесь. Более ПОДРОБHОЕ и ГЛУБОКОЕ > изложение делает книгу предназначенной не для более ШИРОКОЙ, а для > более УЗКОЙ аудитории. Я пишу и тексты полезные для специалистов (в > научных статьях). Hо их смысла нет давать в книге, ориентированной > на ШИРОКУЮ аудиторию. > > Мы ориентировались прежде всего на студентов, которым интересна тема > сжатия. И я уверен, что лучшие из них после прочтения книги спокойно > найдут и скачают более узкие материалы на английском, по тем темам, > которые их заинтересовали. > > А уж интерес к этой теме огромен. Мы только в мае худо-бедно привели > в порядок сайт (по-человечески он не доведен и сейчас), но даже без > рекламы на нем было больше 2000 уникальных хостов в месяц. В июне > явно будет больше 3000 (уже сейчас идет в среднем 150 визитов в > день) и останавливаться мы не намерены. Уже понятно, что при тираже > книги в 3000 экземпляров основная аудитория книги будет сетевая, и > аудитория не маленькая. > > Так что мы выкраиваем время (тоже с трудом - я, например, сейчас в > нескольких проектах занят) и готовим материалы для всех. Желающие > помогать - присоединяйтесь! :) > > Всего доброго, > Дмитрий Ватолин. > > -------------------------------------------------- ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 21 Jun 02 09:34:39 To : Sergey Kovalev Subj : Замечания по "Книге" (1/2) From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Sergey! You wrote on Sat, 15 Jun 2002 17:56:13 +0000 (UTC): Дмитрий Ватолин просил закинуть: ----- Исходное сообщение ----- От: Dmitriy Vatolin <dmitriy@graphics.cs.msu.su> SK>> From: "Sergey Kovalev" <s-kovalev@nwgsm.ru> > SK>> Как и обещал, привожу краткий разбор части книги. Автор этой части SK>> (D.Vatolin) сообщил, скоро должна появится отредактированная версия, SK>> но я, видимо, не буду иметь свободного времени для ее разбора. > > Поясню для всех читающих. Я личной почтой коротко предупредил Сергея, > что тот текст, который он критиковал соответствует тексту учебного > пособия, в книге же многие моменты написаны иначе. PDF этих частей книги > появится на сайте на днях. > > Однако, критик предпочел не дожидаться и не переписываться лично... > SK>> Сразу хочу оговориться , что все, что будет написано ниже, не SK>> претендует на истину в последней инстанции, и мне не хотелось бы SK>> ввязываться в дискуссию по поводу правомерности или не правомерности SK>> тех или иных замечаний. Это все мое личное мнение, которое можно SK>> просто принять или не принять. Спорить ни с кем не буду, поскольку и SK>> так очень жаль бездарно потраченного времени на разбор мало SK>> интересной для меня продукции. Дабы впредь такое не повторилось, SK>> собираюсь наказать себя переходом в ReadOnly ;) > > У Вас характерная манера письма: Пишется отрицательное мнение по > поводу чего-то, сразу за которым вы пишите "не буду иметь свободного > времени для ее разбора" или "Я мог бы написать более предметно, но, > честно говоря, мне не хотелось бы делать за вас вашу работу". Вы > ведь просто снимаете с себя ответственность. > > Сергей! Вас HИКТО не заставляет что-то читать и о чем-то > высказываться. Вас просто спросили, можете ли вы отвечать за свои > слова. > SK>> Итак, что мы имеем. Мы имеем методичку, изданную в 99 г. в МГУ для SK>> студентов второго курса. SK>> http://www.kulichki.com/moshkow/TECHBOOKS/ALGO/VATOLIN/algcomp.htm К SK>> ней добавлены две части, недоступные в и-нете (ждем согласования с SK>> редакцией ;). В методичке, трансформировнной в раздел научной(?) SK>> книги, похоже, не исправлено ни одно слово. (Слова "Вопрос к SK>> экзамену" заменены на "Вопрос".) Как следует из текста методички, SK>> она написана в 97-м году. Однако, некоторые части были написано SK>> несколько ранее. Дело в том, что начало научной активности автора SK>> приходится на 95-96гг. Я нашел одну из его работ этого времени ( SK>> http://www.osp.ru/os/1995/04/ ). Она точно совпадает по структуре с SK>> методичкой и представляет собой ее слегка сокращенную версию. SK>> Поэтому можно смело считать, что основные части методички ковались в SK>> районе 95-го года. > > Вы конечно смелы, но ошибаетесь. > SK>> Думаю, всем понятно, что писать научные книги методом копирования SK>> методичек через clipboard не совсем правильно. SK>> Теперь перейдем к рассмотрению собственно содержимого SK>> раздела. Замечания очень разного калибра, я их записываю в том SK>> порядке, в каком они возникали при чтении текста. > > Сергей! (я понимаю, что книги вы не читали) Hа всякий случай имейте > ввиду, что в ней явно указано "Учебно-справочное издание". > Изрядная же доля ваших замечаний была бы справедлива если бы на > книге было указано "Монография". > > Т.е. задача, которую ставили перед собой авторы - понятно объяснить > суть работы существующих алгоритмов сегодняшним студентам. > > В этом смысле ваши слова превращаются во что-то вроде: "Разве можно > использовать поправленный и дополненный текст методички тиражом 250 > экземпляров в учебно-справочной книге? Думаю, всем понятно, что это > совсем не правильно." > > О том, что книга ориентирована на студентов, к слову, написано и в > аннотации книги, которая кидалась в эту конференцию. > SK>> 1. Общие положения алгоритмов сжатия изображений. SK>> - Все же основной упор в главе по _алгоритмам_ сжатия должен SK>> делаться на _алгоритмы_. Алгоримы - это та печка, от которой SK>> стоило плясать. Т.е. сначала рассказать, какие бывают алгоритмы, SK>> а потом, исходя из особенностей алгоритмов, плавно перейти к SK>> типам предпочтительных для них (алгоритмов) изображений, а под SK>> занавес рассказать, где такие изображения "водятся в природе". Hа SK>> мой взгляд, автор не совсем удачно рассматривает все сразу и SK>> одновременно со всех сторон. В голове у читателя создается каша. SK>> Конечно, все непонятное невольно вызывает уважение, но... ;) > > Ваш взгляд понятен. > > Подход, который вы не поняли довольно прост: сначала даются > _определения_, а уже потом на основе этих определений строятся > утверждения. Возможно вам приходилось сталкиваться с таким подходом > к изложению в учебной литературе. > > Сложность изложения при рассказе об изображениях в том, что даже > человек имеющий смутное представление о том, чем векторная графика > отличается от растровой и не знающий ни одной системы > цветопредставления кроме RGB абсолютно уверен, что он знает какими > бывают изображения на компьютере. Т.е. если начать сразу строить > утверждения, понимая под терминами разные вещи, то в голове у > человека действительно образуется каша. Если же сначала дать > определения - этого не происходит. Hа студентах это видно > совершенно четко. > > Возможно вы не знали об этом, поскольку общаетесь только с достаточно > подготовленными людьми. > SK>> - Я бы не стал так акцентировать внимание на вопросе о максимально SK>> достижимым и минимально достижимым сжатии. Интересно SK>> среднестатистическое сжатие для класса изображения, а крайние точки SK>> мало интересны, поскольку они маловероятны. > > Ваша точка зрения также понятна. > > Дело в том, что крайние точки являются своего рода > характеристическими числами алгоритма. По ним достаточно просто > определить, какая модификация простого алгоритма использована. > > Т.е. я уверен, что человек, прочитавший книгу и уловивший общий > принцип сможет легко определить какая именно модификация алгоритма > используется где-либо просто грамотно подготовив тестовые > ("меловероятные", как вы выражаетесь) изображения. Форматов > изображений существует много, и часто указывается лишь, что там > используется такой-то алгоритм (например LZW) без дополнительных > пояснений и базовые знания о том, как детектировать алгоритм > оказываются весьма и весьма полезными. > SK>> И уж совсем странным кажется постоянное возвращение к вопросу - SK>> может ли увеличить алгоритм сжатия исходный объем изображения или SK>> нет? Цена этого вопроса - один бит, и явно не следовало этому SK>> уделять так много внимания. > > Видимо не знакомы с реальными алгоритмами, в использующихся сейчас > форматах. > > Большинство сжимающих в GIF (или выбирающих "Сжатие RLE" при > сохранении BMP файла в том же PhotoShop) свято уверено, что алгоритм > сжатия сожмет изображение. > > Эта уверенность произрастает, естественно, из незнания того, какие > изображения и на сколько могут быть увеличены различными алгоритмами. > > Видимо вам не приходилось сталкиваться с совершенно дикими > представлениями о сжатии в GIF, например, у веб-дизайнеров. > SK>> 2. Алгоритмы архивации без потерь. SK>> - и RLE и уж тем более голый Хаффман представляют интерес не SK>> столько как самостоятельные алгоритмы сжатия изображений, сколько SK>> как элементы более сложных алгоритмов. Может, надо было ввести SK>> дополнительную главку "типовые элементы алгоритмов сжатия", или что- SK>> то в этом роде и туда поместить этот материал. > > Если вы заметили, описание этих алгоритмов потому и идет раньше, что > позднее в более сложных алгоритмах на них идут ссылки. > > Как самостоятельные алгоритмы они используются на всех компьютерах с > Windows (распаковка RLE BMP) и во всех факсах (CCITT Group 3). ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 21 Jun 02 15:32:28 To : Nickita A Startcev Subj : Re: Текстовые "базы" сжимать From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Nickita! You wrote to All on Tue, 18 Jun 2002 23:39:20 +0400: NA> Есть некоторое устройство, обладающее процессором и небольшим NA> количеством памяти (4..16Mb), на этом устройстве надо "по требованию" NA> выдавать текстообразную информацию. NA> Информация заранее приготавливается (сжимается) на PC за любое NA> (большое) время, но должна сравнительно быстро разжиматься на NA> устройстве. Информация представляет из себя список строк, NA> отсортированных по алфавиту и список статей. NA> статья представляет из себя "списков индексов строк". NA> Устройство должно оперативно выдавать статью с указанным в запросе NA> номером. NA> Какой алгоритм для сжатия и распаковки посоветуете? LZ77 с Хаффманом или арифметиком, если важнее скорость декодирования. BWT, если важнее степень сжатия. Обоим способам пойдет на пользу применение текстовых фильтров. NA> a) можно тупо пожать RLE по столбцам список строк, но тогда трудновато NA> выбирать произвольную строку Во-первых, полезно обработать не все столбцы, а только несколько первых. Во-вторых, чтобы сохранить возможность произвольногго расжатия, надо RLE применять не ко всем строкам сразу, а разделить все строки на блоки. NA> Есть ли какие-нибудь алгоритмы "а-ля LZW" с отдельно лежащим небольшим NA> словарем и отдельной 'большой базой'? Есть, только "отдельно лежащий словарь" - это совсем не LZW :) ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 21 Jun 02 18:02:31 To : Alexey Monastyrenko Subj : examples * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Tuesday June 18 2002, Alexey Monastyrenko writes to Dima Gorbunov: >> где есть, несжимаемое rar'ми, упакованное методами типа a^b+d=c ? AM> файлов (бОльшая часть которых еще и дублируется). Т.е. файл можно AM> закодировать 15 десятичными цифрами, или 50 двоичными. А ведь мы еще AM> Hу как - метод a^b+d=C отдыхает? ;-) а это и есть "метод типа a^b+d=c" :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 21 Jun 02 18:03:24 To : Dima Gorbunov Subj : examples * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Dima! Monday June 17 2002, Dima Gorbunov writes to All: DG> где есть, несжимаемое rar'ми, упакованное методами типа a^b+d=c ? DG> Hу хоть один файл 16 мегов, пакованный в 1,4 ? хочешь 5 штук гринов заработать? :) ты, наверно, не в курсе - есть один мужик, который за такое удовольствие готов $5k отвалить. до сих пор ждёт, если не считать одного случая, когда его нагло н аебали :)) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 21 Jun 02 18:29:10 To : Nickita A Startcev Subj : Re: Текстовые "базы" сжимать From: "Alexey Monastyrenko" <aamonster@mail.ru> "Nickita A Startcev" <Nickita.A.Startcev@p8.f1039.n5030.z2.fidonet.org> wrote > Есть некоторое устройство, обладающее процессором и небольшим количеством > памяти (4..16Mb), на этом устройстве надо "по требованию" выдавать > текстообразную информацию. Гы :-) Почти родная задача. > Информация заранее приготавливается (сжимается) на PC за любое (большое) время, > но должна сравнительно быстро разжиматься на устройстве. > Информация представляет из себя список строк, отсортированных по алфавиту и > список статей. > статья представляет из себя "списков индексов строк". > Устройство должно оперативно выдавать статью с указанным в запросе номером. "Оперативно" - это как? Какое время реакции требуется и какой скорости проц? (ну и объем статьи указать не забудь) Грубо говоря, сколько тактов есть на распаковку одного символа? > > Какой алгоритм для сжатия и распаковки посоветуете? Любой, позволяющий распаковку по блокам и не сильно теряющий при этом в сжатии. Я для похожей задачи (только там свободной оперативки маловато, а все данные во флеше) выбрал извращенный вариант полуадаптивного ppm. Кстати, у тебя 'список строк' откуда взялся? Ты его сам предполагаешь генерить или это условие задачи? > Есть ли какие-нибудь алгоритмы "а-ля LZW" с отдельно лежащим небольшим словарем > и отдельной 'большой базой'? Э? Я не понял :) Маленький трюк для улучшения сжатия больших текстов на блочной упаковке lz77+huffman (при небольшом размере блока): начало файла храним в непакованном виде, окно lz77 делим на 2 части: в первой - начало файла, во второй - собственно предшествующий текущему символу кусок текста (от начала блока). --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс