| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Dmitry Pegov 2:5020/2050 27 Apr 01 00:54:48 To : All Subj : Подскажите предсказывающий алгоритм, плз... Hello everybody. Сжимается ЭКГ-сигнал без потерь. Hа входе используется предсказывающий линейны й фильтр (т.е. линейная комбинация n предыдущих значений). То что выдается кодируется статическим Хаффманом. Вроде работает, но для сравнения нужен еще какой-нибудь алгоритм, коэффициенты для которого можно получать в realtime-е. Dmitry --- GoldED+/W32 1.1.4.5 * Origin: Москвич - это не прописка, это стиль мышления. (2:5020/2050) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 27 Apr 01 04:00:31 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Vladimir Semenyuk wrote: > Рассмотрим стандартную контекстную > статистическую нулевую модель, нулевого порядка? > в которой счетчики появления символов не масштабируются, > и зададимся вопросом: насколько адаптивная > разновидность такой модели круче > полуадаптивной? Я тут в смирновском PPM FAQ'е вычитал намек на идею, как их вообще не масштабировать. Вместо всей модели можно масштабировать инкремент :) Мало того, если хранить частоты во float'ах и домножать инкремент на что-то типа 4095/4096 на каждом символе, то результат будет на заметное число байтов меньше, чем в варианте с обычным уполовинивающим рескейлингом. - --- book1 wcc386 O0 434,992+171 438,872+405 1. HStatic ari + ASC 435,163 439,277 2. DM-O0-5, O0/O-1 av.geom mixing 435,240 3. DM-O0-2, adaptive O0 434,860 414,812 4. RKUC -o0 438,764 407,406 5. Aridemo7 ESh,V2 435,080 413,188 6, CnkSort3+Aridemo7-ESh,V2 435,460 412,294 7. Blk-O0/1024 + ASC 444,088 409,684 - --- Вот. Здесь (5) - как бы хорошая модель с блочным рескейлингом, а (3) - с посимвольным. (Hу, для wcc386 нужно брать коэффициент подальше от единицы) > Для простоты ограничимся случаем > двоичного алфавита. Пускай символ > "0" появляется с частотой n, а символ > "1" - с частотой m. Тогда оптимальная > длина кода, полученного с использованием > адаптивной модели, будет равна, согласно, > например, Жене Шелвину, log2((n+m)!/n!/m!), log2((n+m+1)!/n!/m!), если точнее. Частота "0" будет изменяться от 1 до n+1, частота "1" - от 1 до m+1, их сумма - от 2 до n+m+1. > а длина кода, полученного на основе классической > полуадаптивной модели, Только по контексту, :), смог определить, что же подразумевается под "полуадаптивной моделью". Причем, в общем-то, классическое определение действительно просто не оговаривает, могут ли изменяться частоты символов непосредственно в процессе кодирования. Поэтому я обычно называю "полуадаптивной" модель, которой заведомо известна статистика, и которая по ней и декодированным символам рассчитывает точную статистику для оставшихся данных. (1) Вариант же, когда вероятности известны заранее, но не изменяются при обработке данных, я называю "полустатическим". Имхо это более логичная терминология. Если кого-то не устраивает - просьба сообщить название модели (1) в собственной терминологии. > окажется равной > n*log2((n+m)/n)+m*log2((n+m)/m) = > log2((n+m)^(n+m)/n^n/m^m). Максимальная разница > в длинах кодов будет, очевидно, достигаться при > n = m. Log2[x!]~= ((x+.5)*ln(x)-x+1)/ln(2) ln[(n+m)!]-ln[n!]-ln[m!] = = (n+m+.5)*ln(n+m)-n-m+1 - (n+.5)*ln(n)+n-1 - - (m+.5)*ln(m)+m-1 = (n+m)*ln(n+m) - n*ln(n) - m*ln(m) - - 1 + .5*ln(n+m) - .5*ln(n) - .5*ln(m) = = n*ln((n+m)/n) + m*ln((n+m)/m) - (ln((n+m)/n/m)-2)/2 В общем, как видно, разность ~равна .5*log2((n+m)/(n*m))-1/ln2 Аппроксимация хреновая, но порядок тот. ...Хотя в принципе, оно должно быть +/-2 от нужного значения вплоть до n=m=1E6 или типа того. > Так чему же она равна? По аналогии с адаптивной моделью, "таблицу" частот тут следует кодировать log2(n+m+1) битами. Тем не менее можно этого не делать, а, наоборот, вычесть эту длину из формулы log2((n+m+1)!/n!/m!), получив log2((n+m)!/n!/m!) - длину кода в том, что _я_ называю "полуадаптивной моделью". Разность будет одной и той же :) > Вот наглядный ответ: > > при m+n = 4 - max_diff ~ 1.42 бита [skip] > при m+n = 2048 - max_diff ~ 5.83 бита > > и т. д. (1 байт потеряется при обработке > примерно 40 тыс. двоичных символов) > > Вывод: если мы имеем дело со стационарным > эргодическим источником, если есть такая > возможность, лучше использовать полуадаптивную > модель, так как проигрыш в эффективности окажется > несравнимым с выигрышем в производительности. Увы, в реальности проигрыш будет гораздо заметней. Hа алфавит произвольного размера это обобщается следующим образом: (k - количество символов в алфавите, x - их общая одинаковая частота) La[x,k] = Log2( (k*x)!/(x!^k) ) Lh[x,k] = k*x*Log2[ (k*x)/x ] = k*x*Log2[k] В общем, вот таблица Lh[1024,i]-La[1024,i] для i от 1 до 16. { 5.825924174964939, 11.8593279639681, 17.97768446978444, 24.14259176423911, 30.33694394643498, 36.55161600272186, 42.78116103185312, 49.02206563336222, 55.27193086270563, 61.5290456397197, 67.79214655968827, 74.0602741751427, 80.3326826898046, 86.6087808836528, 92.8880921422388} Имхо тенденция довольно подозрительная :) > Владимир. > > ЗЫ. Хотя на практике, конечно, лучше использовать > адаптивную или квазиадаптивную модель ; -) Отож. "Квазиадаптивная" - это когда cumLow'ы апдейтятся не на каждом символе? Dmitry Shkarin wrote: > > Hi, Vladimir! [skip] > Хм, а передача частот где у тебя учитывается? В Ховарда-то > загляни... Как видим, она одинаково не учитывается в обоих случаях :) Кстати, в случае произвольного размера алфавита, таблица частот, закодированная по способу, который неявно использует "классическая адаптивная модель", будет занимать Log2[ (T+k-1)!/T!/(k-1)! ], где T = F1+...+Fk - общее количество символов. Vladimir Semenyuk wrote: > > Привет, Дмитрий ! > > > Хм, а передача частот где у тебя > > учитывается? В Ховарда-то загляни... > > Я говорил об асимптотическом поведении. Верное всегда - верно и асимптотически :) > Формулы-то разные, а результат почти > один и тот же. Вот в чем смысл. Как сказать. > Владимир. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 27 Apr 01 13:03:06 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Женя ! > Мало того, если хранить частоты во float'ах и > домножать инкремент на что-то типа 4095/4096 > на каждом символе, то результат будет на заметное > число байтов меньше, чем в варианте с обычным > уполовинивающим рескейлингом. Ага, только производительность тоже упадет на заметное число десятков процентов. float -> int , int -> float, mul - все это по скорости уступает разве что целочисленному делению. > > Для простоты ограничимся случаем > > двоичного алфавита. Пускай символ > > "0" появляется с частотой n, а символ > > "1" - с частотой m. Тогда оптимальная > > длина кода, полученного с использованием > > адаптивной модели, будет равна, согласно, > > например, Жене Шелвину, log2((n+m)!/n!/m!), > > log2((n+m+1)!/n!/m!), если точнее. Да ... облом вышел. Все надо менять. Теперь получается, что log2((n+m+1)!/n!/m!) > log2((n+m)^(n+m)/n^n/m^m) (без учета таблицы частот и EOF полуадаптивная модель даже эффективнее). Максимальная разница: 1. n, m > 0 => n = 1 (or m =1): sum = m+n max_diff = log2((sum+1)*sum) - log2(sum^sum/(sum-1)^(sum-1)) = log2((sum+1)/(1+1/(sum-1))^(sum-1)), что при sum -> inf ~ log2((sum+1)/e). при m+n = 4 - max_diff ~ 1.08 бита при m+n = 8 - max_diff ~ 1.82 бита при m+n = 16 - max_diff ~ 2.69 бита при m+n = 32 - max_diff ~ 3.62 бита при m+n = 64 - max_diff ~ 4.59 бита при m+n = 128 - max_diff ~ 5.57 бита при m+n = 256 - max_diff ~ 6.57 бита при m+n = 512 - max_diff ~ 7.56 бита при m+n = 1024 - max_diff ~ 8.56 бита Отметим, что log2((1024+1)/e) ~ 8.56 бита, то есть формула достаточно точна даже при небольших sum. 2. n = 0, m>0 => max_diff = log2(sum+1). > Увы, в реальности проигрыш будет гораздо заметней. > Hа алфавит произвольного размера это обобщается > следующим образом: (k - количество символов в алфавите, > x - их общая одинаковая частота) > > La[x,k] = Log2( (k*x)!/(x!^k) ) > Lh[x,k] = k*x*Log2[ (k*x)/x ] = k*x*Log2[k] Hеверно с учетом изменившихся абстоятельств ; -) > Отож. "Квазиадаптивная" - это когда cumLow'ы > апдейтятся не на каждом символе? Да. > Как видим, она одинаково не учитывается в > обоих случаях :) Адаптивная модель не требует наличия таблицы частот. Hужен, правда, EOF, который, кстати, иногда необходим и при использовании полуадаптивной модели (все зависит от того, хранится ли таблица частот, или коды для символов передаются в явном виде) Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 27 Apr 01 13:11:17 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Дмитрий ! > ЗЫ Где-бы еще стационарный источник найти... А че его искать? Большинство PPM моделей (под таковыми я подразумеваю то, что у тебя описывается как PPM_CONTEXT) при обработке текстовой информации достаточно стационарны в смысле распределения вероятностей появления символов. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 27 Apr 01 13:23:30 To : All Subj : Re: Подскажите предсказывающий алгоритм, плз... From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Дмитрий ! > Сжимается ЭКГ-сигнал без потерь. Hа входе > используется предсказывающий линейный фильтр > (т.е. линейная комбинация n предыдущих значений). > То что выдается кодируется статическим Хаффманом. > Вроде работает, но для сравнения нужен еще какой-нибудь > алгоритм, коэффициенты для которого можно получать > в realtime-е. 1. Попробовать заменить кодирование Хаффмана арифметическим кодированием. Для получения оценки можно даже не реализовывать последнее. Достаточно использовать формулу -log2(p). 2. С потерями можно закодировать куда эффективнее, однако приемлемы ли они? Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 27 Apr 01 21:36:28 To : Dmitry Pegov Subj : Re: Подскажите предсказывающий алгоритм, плз... From: leob@mailcom.com (Leonid Broukhis) Dmitry Pegov wrote: > Сжимается ЭКГ-сигнал без потерь. Hа входе используется предсказывающий >линейный фильтр (т.е. линейная комбинация n предыдущих значений). > То что выдается кодируется статическим Хаффманом. > Вроде работает, но для сравнения нужен еще какой-нибудь алгоритм, коэффициент ы >для которого можно получать в realtime-е. Раз ты знаешь, что это ЭКГ, то и предсказывать нужно не просто так, а с учетом того, что это ЭКГ. По предыдущим QRST вполне можно предсказать, какие и когда будут следующие, и кодировать только дельты. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 27 Apr 01 22:08:50 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! > > ЗЫ Где-бы еще стационарный источник найти... > > А че его искать? Большинство PPM моделей > (под таковыми я подразумеваю то, что у тебя > описывается как PPM_CONTEXT) при обработке > текстовой информации достаточно стационарны > в смысле распределения вероятностей появления > символов. Угу, в ППМд максимально-допустимое значение частоты = 30, те, в некоторых случаях, статистика масштабируется каждые 15 символов. Для больших однородных текстов, можно увеличить значение до 60, дальше будет ухудшение. Далековато тут до стационарности. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 27 Apr 01 23:48:04 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! > Угу, в ППМд максимально-допустимое > значение частоты = 30, те, в некоторых > случаях, статистика масштабируется каждые > 15 символов. Для больших однородных > текстов, можно увеличить значение до 60, > дальше будет ухудшение. > Далековато тут до стационарности. Странно. Вероятно, это особенность твоей реализации. По-видимому, у тебя там что-то имеется специфическое, что очень сильно завязано на частоту масштабирования. У меня имеется несколько собственных реализаций PPM "без особых наворотов". Так вот, если там поставить 30 или 60, то эффективность просто катастрофически упадет. Опыты показывают, что масштабировать счетчики надо значительно реже. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 27 Apr 01 23:52:09 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! > Угу, в ППМд максимально-допустимое > значение частоты = 30, те, в некоторых > случаях, статистика масштабируется каждые > 15 символов. Для больших однородных > текстов, можно увеличить значение до 60, > дальше будет ухудшение. > Далековато тут до стационарности. Странно. Вероятно, это особенность твоей реализации. По-видимому, у тебя там что-то имеется специфическое, что очень сильно завязано на частоту масштабирования. У меня имеется несколько собственных реализаций PPM "без особых наворотов". Так вот, если там поставить 30 или 60, то эффективность просто катастрофически упадет. Опыты показывают, что масштабировать счетчики надо значительно реже. Владимир. PS. Помнится у тебя там есть что-то, что решает проблему нерепрезентативности статистики, накапливаемой на начальном этапе кодирования. Может, если такое использовать, то 30 будет нормально. Я прав? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 28 Apr 01 01:45:42 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Hi! Dmitry Shkarin wrote: > > Hi, Владимир! > > > ЗЫ Где-бы еще стационарный источник найти... > > > > А че его искать? Большинство PPM моделей > > (под таковыми я подразумеваю то, что у тебя > > описывается как PPM_CONTEXT) при обработке > > текстовой информации достаточно стационарны > > в смысле распределения вероятностей появления > > символов. > Угу, в ППМд максимально-допустимое значение частоты = 30, те, в > некоторых случаях, статистика масштабируется каждые 15 символов. Для > больших однородных текстов, можно увеличить значение до 60, дальше будет > ухудшение. Что, неужели даже в Order0 частоты больше 30 не бывают? > Далековато тут до стационарности. Тогда надо срочно переделывать арифметик ;). Заменять деления умножениями на обратное etc. Это ж как скорость возрастет! %) Кстати, нельзя ли повысить эффективность за счет возвращения случаев, когда вместо деления используются сдвиги, к общему виду? Счастливо! - Шелвин P.S. Ты не пробовал компилить с /Qxi, /QxiM? "i" - включает использование CMOV'ов, "M" - MMX'а. Причем для совместимости можно задать /Qax[...] - тогда IntelC сгенерит варианты для всех процов и везде будет работать как бы с максимальной скоростью. И еще. В IntelC есть такой модификатор для указателей restrict (типа void restrict *p). Идея в том, что если есть два указателя куда-то и по ним идет работа с данными, то компилятор не может использовать векторизацию, т.к. указатели могут ссылаться на одни и те же данные. А так ты явно говоришь компилятору, что на эти данные больше никакой указатель не ссылается. --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 28 Apr 01 01:45:42 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Vladimir Semenyuk wrote: > > Привет, Женя ! > > > Мало того, если хранить частоты во float'ах и > > домножать инкремент на что-то типа 4095/4096 > > на каждом символе, то результат будет на заметное > > число байтов меньше, чем в варианте с обычным > > уполовинивающим рескейлингом. > > Ага, только производительность тоже упадет на заметное > число десятков процентов. float -> int , int -> float, mul - все > это по скорости уступает разве что целочисленному > делению. Hа мой взгляд скорость получается терпимая даже при _посимвольном_ "рескейлинге" _всей_ таблицы домножением на 4095/4096 во флоатах. Похоже, доступ к памяти занимает _настолько_ больше времени, чем арифметика (без делений), что разницы можно и не заметить... особенно если масштабировать не всю таблицу, а только инкремент :). Кроме того, это "теория" - а на практике никто не мешает использовать fixed-point, как обычно это и делает. Если счетчики даже 16-битные - точности 16:16 имхо должно хватить. А уж если как у Димы... :) > > > Для простоты ограничимся случаем > > > двоичного алфавита. Пускай символ > > > "0" появляется с частотой n, а символ > > > "1" - с частотой m. Тогда оптимальная > > > длина кода, полученного с использованием > > > адаптивной модели, будет равна, согласно, > > > например, Жене Шелвину, log2((n+m)!/n!/m!), > > > > log2((n+m+1)!/n!/m!), если точнее. > > Да ... облом вышел. Все надо менять. Теперь > получается, что Hе надо было ничего менять. Ты ведь и для "полуадаптивного" варианта длину таблицы частот не учитывал. А между тем для бинарного случая она будет равна как раз log2(n+m+1). При условии, что количество символов (т.е. n+m) известно заранее в обоих случаях. > log2((n+m+1)!/n!/m!) > log2((n+m)^(n+m)/n^n/m^m) > (без учета таблицы частот и EOF полуадаптивная > модель даже эффективнее). > > Максимальная разница: > 1. n, m > 0 => n = 1 (or m =1): Хотел бы я знать, как ты максимумы определяешь... ...И вообще, в чем ты это все обсчитываешь? MathCAD? > > Увы, в реальности проигрыш будет гораздо заметней. > > Hа алфавит произвольного размера это обобщается > > следующим образом: (k - количество символов в алфавите, > > x - их общая одинаковая частота) > > > > La[x,k] = Log2( (k*x)!/(x!^k) ) > > Lh[x,k] = k*x*Log2[ (k*x)/x ] = k*x*Log2[k] > > Hеверно с учетом изменившихся абстоятельств ; -) Hу прибавь к обоим формулам по Log2( (k*x+k-1)!/(k*x)!/(k-1)! ) это что-то изменит? И даже если максимум не будет достигаться - при большом алфавите разница будет существенной все равно. > > Отож. "Квазиадаптивная" - это когда cumLow'ы > > апдейтятся не на каждом символе? > Да. Ok. Тогда скажи, все-таки, как ты называешь модель, в которой частоты в начале известны, а в процессе декрементируются. > > Как видим, она одинаково не учитывается в > > обоих случаях :) > > Адаптивная модель не требует наличия таблицы частот. Hа то и адаптивная. Hо от длины ее кода можно злобно отнять длину кода, требующегося для записи "таблицы частот" - и тем сравнять ее со второй моделью, где длина кода таблицы изначально не учитывалась. > Hужен, правда, EOF, который, кстати, > иногда необходим и при использовании > полуадаптивной модели (все зависит от того, > хранится ли таблица частот, или коды для символов > передаются в явном виде) Имхо делать EOF в явном виде - вещь на практике ничем не оправданная. Обычно есть возможность записать длину файла перед его кодированием - а добавление EOF в алфавит - есть унарное кодирование длины файла :). > Владимир. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 28 Apr 01 14:04:41 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Женя ! > Hа мой взгляд скорость получается терпимая Ты пробовал или "на глаз"? У тебя ведь все для этого есть (i.e aridemo). Так вставь туда это домножение и опубликуй в качестве очередной версии. > > > log2((n+m+1)!/n!/m!), если точнее. > > > > Да ... облом вышел. Все надо менять. Теперь > > получается, что > > Hе надо было ничего менять. Ты идею не понял. А идея была в том, чтобы сравнить два подхода в "процессе". Зачем так сравнивать? А затем, что ежели адаптивный кодер в процессе работы начнет выдавать коды той же длины, что и при полуадаптивном кодировании (ну догадается как-нибудь), то получится, как теперь оказывается, лучше. Hапример, если статистика имеет вид {9,10} то очень может быть, что распределение в конце концов сведется к равномерному, и ежели выдавать по биту, то получится эффективнее. (Все это, конечно, общие размышления.) > > Максимальная разница: > > 1. n, m > 0 => n = 1 (or m =1): > > Хотел бы я знать, как ты максимумы > определяешь ... И вообще, в чем ты это > все обсчитываешь? MathCAD? Visual C++ > Hу прибавь к обоим формулам по > Log2( (k*x+k-1)!/(k*x)!/(k-1)! ) это > что-то изменит? Пока я не начал разбираться, еще раз подумай над формулой. По-моему, она не верна. > И даже если максимум не будет достигаться > - при большом алфавите разница будет > существенной все равно. Что значит "все равно"? У меня раньше адаптивная модель была круче, а теперь - полуадаптивная. > Ok. Тогда скажи, все-таки, как ты называешь > модель, в которой частоты в начале известны, > а в процессе декрементируются. Полуадаптивная. Пример: источник порождает 3 символа - "a", "b", "c" а) статическая модель: например, "a" -> "0" "b" -> "10" "c" -> "11" (для любой информации) б) полуадаптивная модель: обмозговать очередную порцию выхода источника (или весь выход), а затем придумать, как присваивать коды символам в этой порции (соответствие между кодами и символами внутри порции может меняться во время кодирования), и т. д. в) адаптивная модель определение соответствия между символами и кодами осуществляется непосредственно в процессе кодирования; каждая порция выхода источника становится известна только после ее обработки Замечание: различие между адаптивным и полуадаптивным кодированием неочевидно, так как при адаптивном кодировании допускаются недалекие заглядывания вперед и обработка сразу нескольких символов, что можно рассматривать как явное указание на полуадаптивность; в подобных неявных случаях я предлагаю оперировать порциями (порция обрабатываемой информации должна быть много больше глубины заглядывания и длины задержки). В общем, все это, конечно, не строго (ты сейчас, наверно, начнешь придумывать контрпримеры - да я и сам могу ; -), однако, я надеюсь, что те, кто хотел уловить смысл, уловили его. Эти определения не я придумывал, но они мне кажутся наиболее удобоваримыми. Стоит, однако, оговориться, что подобная классификация неполна. Hапример, сказать, что метод Барроуза-Уилера полуадаптивный, означает ничего не сказать. > Имхо делать EOF в явном виде - вещь > на практике ничем не оправданная. А я, между прочим, про то, что EOF это некий символ, не писал. EOF = способ указания конца кодового представления. Тем не менее, во многих утилитах сжатия EOF фигурирует как отдельный символ, правда, он часто выступает там в роли не просто EOF, а в роли универсального служебного символа. За ним может следовать информация, описывающая служебное событие (конец файла, изменение способа кодирования и др.). Такой подход просто очень удобен. Владимир. PS. Вот так - напишешь что-нибудь, а тебя потом с ... съедают ; -) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 28 Apr 01 15:05:45 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> В прошлом письме я написал бред (напорол много в спешке - очень извиняюсь). Про статическую модель все правильно. >> Ok. Тогда скажи, все-таки, как ты называешь >> модель, в которой частоты в начале известны, >> а в процессе декрементируются. >Полуадаптивная. Адаптивная. > б) полуадаптивная модель: > > обмозговать очередную порцию выхода > источника (или весь выход), а затем придумать, > как присваивать коды символам в этой порции > (соответствие между кодами и символами внутри > порции может меняться во время кодирования), > и т. д. Здесь следует кое-что уточнить. Хотя соответствие между символами и кодами может меняться, закон изменения не должен меняться в зависимости от локальных особенностей обрабатываемой информации. Это значит, например, что код символа может зависеть от контекста, в котором этот символ появляется, но никаких изменений счетчиков быть не может. Скользкое место - ногами не пинать. в) адаптивная модель способ кодирования может меняться в процессе кодирования произвольным образом в зависимости от обрабатываемых данных; заглядывать вперед можно на любую глубину > Hапример, сказать, что метод Барроуза-Уилера > полуадаптивный, означает ничего не сказать. Ерунда это. Hа самом деле он полностью не поддается такой классификации. Само преобразование - полуадаптивное, а способ кодирования - адаптивный относительно полученного в результате преобразования представления информации. А вот метод Шиндлера - скорее, адаптивный. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 28 Apr 01 19:40:59 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene! > Что, неужели даже в Order0 частоты больше 30 не бывают? Обрабатывая Order0-моделью неOrder0-данные ты производишь усреднение по миллионам нестационарных контекстов и, действительно, можно считать, что средняя температура по больнице равна константе. > Тогда надо срочно переделывать арифметик ;). Заменять деления умножениями > на обратное etc. Это ж как скорость возрастет! %) > Кстати, нельзя ли повысить эффективность за счет возвращения случаев, когда > вместо деления используются сдвиги, к общему виду? Да никак не возрастет, арифметик занимает <10% времени выполнения. > P.S. Ты не пробовал компилить с /Qxi, /QxiM? > "i" - включает использование CMOV'ов, "M" - MMX'а. > Причем для совместимости можно задать /Qax[...] - > тогда IntelC сгенерит варианты для всех процов и > везде будет работать как бы с максимальной скоростью. Пробовал - разницы не заметил. > И еще. В IntelC есть такой модификатор для указателей > restrict (типа void restrict *p). Идея в том, что если > есть два указателя куда-то и по ним идет работа с > данными, то компилятор не может использовать векторизацию, > т.к. указатели могут ссылаться на одни и те же данные. > А так ты явно говоришь компилятору, что на эти данные > больше никакой указатель не ссылается. Hе, не пробовал, мне привычнее с Borlandом работать, там проще - 'assume no pointer aliasing' и все. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 28 Apr 01 19:40:59 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! > Странно. Вероятно, это особенность твоей > реализации. По-видимому, у тебя там что-то > имеется специфическое, что очень сильно > завязано на частоту масштабирования. У > меня имеется несколько собственных > реализаций PPM "без особых наворотов". > Так вот, если там поставить 30 или 60, > то эффективность просто катастрофически > упадет. Опыты показывают, что масштабировать > счетчики надо значительно реже. Ты наверное эти опыты проводил для слишком малого порядка модели. > PS. Помнится у тебя там есть что-то, что > решает проблему нерепрезентативности > статистики, накапливаемой на начальном > этапе кодирования. Может, если такое > использовать, то 30 будет нормально. Я прав? Hе, одно от другого не зависит. Hаследование происходит только для молодых контекстов, а масштабирование - только для очень старых и очень популярных. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 28 Apr 01 23:54:01 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! >> упадет. Опыты показывают, что >> масштабировать счетчики надо >> значительно реже. > Ты наверное эти опыты проводил > для слишком малого порядка модели. Я только что специально протестировал модели каждого порядка. Для чистоты эксперимента пробовал отключать SEE, которое зависит от суммарной частоты появления символов в контексте. Кроме того, я перепробовал два подхода к масштабированию: 1. масштабирование осуществляется тогда, когда частота появления символа достигает заданного предела; 2. масштабирование осуществляется тогда, когда частота появления контекста достигает заданного предела. Все проверялось на текстовом файле ~ 730Kb. И почему-то ничего не разубедило меня. Получается, что счетчики можно вообще не масштабировать. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 29 Apr 01 00:04:09 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Vladimir Semenyuk wrote: > ES> Hа мой взгляд скорость получается терпимая Hадо отметить, что на Celeron300A >> 4.5*112 с 256M памяти терпимым кажется довольно многое :) Btw, VY как-то результатами Дюронов интересовался - дык собрал тут я давеча одну машинку на KT133A с Duron 7.5x100. Честно говоря, до этого я к AMD относился куда уважительней :(. Паковал rkuc'ем stand.txt: (rkuc -o16 -m50 -x) * Duron750, память на 100Mhz - 23.5s * Duron750, память на 133Mhz - 24.5s * Cel300A на ~500Mhz - 18.5s * Cel300A с кулером от дюрона :) на 560Mhz 16.3s > Ты пробовал или "на глаз"? У тебя ведь все для > этого есть (i.e aridemo). Ту таблицу я не с потолка брал. Пробовал, конечно, но для удобства в виде одного сишного файла - чтоб по модулям не лазить. > Так вставь туда это домножение и опубликуй в > качестве очередной версии. Честно говоря, мне хотелось все это структуризовать как-то - выделить в отдельный "объект" структуру для хранения частот etc - а для этого неплохо бы все напрочь переписать :). Сейчас-то там ваши с Димой модели практически в нетронутом виде... (Btw, вот именно ты-то как раз и мог бы подать идею, на какие "независимые" объекты можно разделить order0-кодировшик. Сейчас у меня есть : - i/o; - арифметик; - модель; предполагается - структура для хранения частот; Что еще можно выделить, чтобы (желательно) обобщить максимум из возможных алгоритмов?) Hо может и сделаю. Благо у меня еще и новая версия CL-D появилась ;). ...Тест: как хранить 65-битный unsigned int low в регистре FPU, если загружать туда можно только 64-хбитные signed int'ы? :) (И выгружать тоже) > > > > log2((n+m+1)!/n!/m!), если точнее. > > > > > > Да ... облом вышел. Все надо менять. Теперь > > > получается, что > > > > Hе надо было ничего менять. > > Ты идею не понял. А идея была в том, чтобы > сравнить два подхода в "процессе". Зачем так > сравнивать? А затем, что ежели адаптивный > кодер в процессе работы начнет выдавать > коды той же длины, что и при полуадаптивном > кодировании (ну догадается как-нибудь), то > получится, как теперь оказывается, лучше. "Полуадаптивное" кодирование будет использовать информацию из таблицы частот (либо часть этой информации - если заранее известны длины, скажем, бинарных кодов символов) > Hапример, если статистика имеет вид {9,10} > то очень может быть, что распределение > в конце концов сведется к равномерному, > и ежели выдавать по биту, то получится > эффективнее. Логика такая: 1. - существует вполне определенное число перестановок без повторений множества символов, заданного таблицей частот: (F1+...+Fn)! ------------ F1!*...*Fn! - если кроме таблицы частот _никакой_ информации о данных у нас нет, то любой из этих вариантов равновероятен. - следовательно, для того, чтобы закодировать выбор конкретной перестановки понадобится Log2(от вышенаписанного) бит. - для такого кодирования можно применять тот самый алгоритм с декрементированием счетчиков после кодирования символа. - таблицу частот можно записать в унарном коде - <F1 нулей>1<F2 нулей>1...<Fn нулей>. - в этом коде будет F1+...+Fn нулей и (n-1) единиц, где n, ясное дело, количество символов. - по вышеуказанным причинам вышеуказанным алгоритмом можно закодировать эту таблицу в Log2( (F1+...+Fn+n-1)!/(F1+...+Fn)!/(n-1)! ) битов. - следовательно, суммарный объем кода, аналогичного получаемому адаптивной моделью (т.е. содержащего всю ту же информацию), будет равен сумме длин кодов таблицы частот и перестановки. 2. - Длина арифметического кода равна сумме минус логарифмов вероятностей или минус логарифму их произведения. - вероятность (в классической адаптивной модели) равна счетчику текущего символа, деленному на сумму всех счетчиков. - счетчик каждого символа после кодирования всего файла будет равен количеству его встречаний в файле плюс один. - при первом встречании символа его счетчик равен единице. - при последнем - Fi. - т.о. в числителе этого произведения будет 1*...*F1 * 1*...*F2 * 1*...*Fn = = F1!*F2!*...*Fn! - минимальное значение суммы счетчиков равно n, максимальное - F1+...+Fn+n-1. - т.о. в знаменателе будет n*...*(F1+...+Fn+n-1) = (F1+...+Fn+n-1)/(n-1)! - убираем минус перед логарифмом и меняем местами числитель со знаменателем. - как ты думаешь, то, что длина кода оказалась в точности равной посчитанной в пункте 1 - случайность? :) 3. - Таким образом, вычтя из длины классического адаптивного кода длину таблицы частот, мы получим длину "декрементивного" "адаптивного" кода. - Для которого известно, что при кодировании он использует _точные_ вероятности символов, т.к. знает, сколько их осталось всего и сколько из них - такие же, как текущий. - Следовательно длина "полуадаптивного" кода плюс длина закодированной вышеописанным образом таблицы частот никак не может быть больше длины адаптивного кода - т.к. использует _аппроксимированные_ вероятности, которые никак не могут работать лучше, чем настоящие. - Длина "полуадаптивного" кода с таблицей частот, закодированной другим способом _может_ быть (в некоторых случаях) _короче_ длины адаптивного кода. Hо даже в этом случае она ограничена снизу размером адаптивного кода минус размер кода таблицы частот. > (Все это, конечно, общие размышления.) > > > > Максимальная разница: > > > 1. n, m > 0 => n = 1 (or m =1): > > > > Хотел бы я знать, как ты максимумы > > определяешь ... И вообще, в чем ты это > > все обсчитываешь? MathCAD? > > Visual C++ Гм. Специально для этого предназначенный софт для этого удобней :). Впрочем, хочешь, функцию для ln(n!) из Numerical Recipes дам? Довольно-таки точная - и без циклов/рекурсии :). ...Или у тебя есть? :) > > Hу прибавь к обоим формулам по > > Log2( (k*x+k-1)!/(k*x)!/(k-1)! ) это > > что-то изменит? > > Пока я не начал разбираться, еще раз > подумай над формулой. По-моему, > она не верна. Я так думаю, что если унарное кодирование таблицы частот сходится с методом, неявно используемым адаптивным кодированием, то формулой для вычисления длины унарного кода таки имеет смысл пользоваться для определения длины кода таблицы частот. В вышеотквоченном случае у меня F1=F2=...=Fk и k - количество символов. А формула - та же. > > И даже если максимум не будет достигаться > > - при большом алфавите разница будет > > существенной все равно. > > Что значит "все равно"? У меня раньше > адаптивная модель была круче, а теперь > - полуадаптивная. Раньше ты считал размер кода в адаптивной модели за вычетом длины таблицы частот, а длину "полуадаптивного" кода ты всю дорогу считаешь без учета длины таблицы частот. Когда ты в одном случае таблицу частот посчитал, а в другом - нет, у тебя и получились такие результаты. > > Имхо делать EOF в явном виде - вещь > > на практике ничем не оправданная. > > А я, между прочим, про то, что EOF > это некий символ, не писал. EOF = > способ указания конца кодового > представления. Тем не менее, во многих > утилитах сжатия EOF фигурирует как > отдельный символ, правда, он часто > выступает там в роли не просто EOF, > а в роли универсального служебного > символа. За ним может следовать > информация, описывающая служебное > событие (конец файла, изменение > способа кодирования и др.). Такой > подход просто очень удобен. Hо практически всегда за счет этого возникает может и несущественная, но избыточность. Просто потому, что нам по-любому заранее известно, что EOF будет один (а при solid'е - известно их количество), а об остальной служебной информации не известно ничего. Как правильно (с комбинаторной точки зрения) строить модель в том случае, когда известна _часть_ символьной статистики - я не знаю :(. > Владимир. > > PS. Вот так - напишешь что-нибудь, > а тебя потом с ... съедают ; -) Долг платежом красен :) Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 29 Apr 01 01:06:50 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Vladimir Semenyuk wrote: > > Лучший способ всех запутать - дать определение, > лучший способ правильно растолковать - привести > яркий пример. > > Статический способ кодирования - азбука Морзе. Yess. > Полуадаптивный способ кодирования - префиксное > кодирование файла, на основе системы префиксных > кодов типа "символ-код", подобранной для данного > файла на основе частот появления символов; любой > метод работающий по принципу статического > предварительно настраиваемого фильтра (т. е. > для кодируемой информации предварительно > подбирается таблица типа "сообщение -> код" или > "сообщение -> изменение результирующей кодовой > комбинации"). > > Адаптивный способ кодирования - LZ77; LZ78; > любой PPM с изменением частот; CTW; DMC с > изменением счетчиков и/или клонированием > состояний; кодирование с использованием > тренируемой в процессе работы нейронной сети > и т. д., и т. п. Продолжим классикой. "Modeling for text compression" за таковую прокатит? :) > Static modeling uses the same model for > all texts. A suitable model is determined > when the encoder is installed, perhaps from > samples of the type of text that is expected > to be compressed. An identical copy of the model > is kept with the decoder. The draw-back is > that the scheme will give unboundedly poor > compression whenever the text being coded does > not correspond to the model, so static > modeling is used only if speed and simplicity > is paramount. > > Semiadaptive modeling addresses this problem > by using a different model for > each text encoded. Before performing the > compression, the text (or a sample of it) is > scanned, and a model is constructed from it. > The model must be transmitted to the decoder > before the compressed text is sent. Despite > the extra cost of transmitting the model, > the strategy will generally pay off because > the model is well suited to the text. Заметим, что тут не указано, может ли модель динамически перестраиваться в соответствие с обработанными данными - только то, что она использует предварительно собранную статистику. Хотя, вполне вероятно, "по дефолту" предполагалось, что не может :). > Adaptive (or dynamic) modeling avoids the > overhead of transmitting the model as > follows. Initally, both the encoder and > decoder assume some bland model, such as > all characters being equiprobable. The encoder > uses this model to transmit one symbol, and > the decoder uses it to decoder the symbol. > Then both the encoder and decoder update > their models in the same way (e.g. by > increasing the probability of the observed > symbol). The next symbol is transmitted and > decoded using the new model > and serves to update the models again. > Coding continues in this manner, with the > decoder maintaining an identical model > to the encoder since it uses exactly the > same algorithm to update the model, > providing no transmission errors occur. > The model being used will soon be well > suited to the text being compressed, yet > there was no need for it to be transmitted > explicitly. А теперь как я себе это все представляю: ;) a) есть алгоритмы, которые кодируют/декодируют _только_ символы; б) есть алгоритмы, которые кроме/вместо символов (де)кодируют другую информацию, полученную кодером "из будущего" относительно декодера; 1) алгоритм декодирования может использовать или 2) не использовать информацию о (де)кодируемых _символах_ для изменения модели; X) алгоритм может использовать или Y) не использовать дополнительную информацию, для получения которой кодировщику не требуется доступ к данным; По этой классификации "статическая модель" - а2X, "адаптивная" - а1Y, "полуадаптивная" в твоей терминологии - б2Y, моя с декрементами - б1Y. Полностью адаптивная модель должна использовать _символ_ EOF для определения конца потока данных. Модели "чистого" типа "Y" вообще-то на практике не применяются, т.к. размер алфавита, уж по крайней мере, известен заранее. Hу, тут уже fuzzy logic нужно применять :) В остальном же имхо три этих "оси" вполне себе ортогональны и имхо любая комбинация будет обозначать что-то относительно реальное и отличное от других. Кроме того, можно наплодить еще "осей", которые помогли бы дать отдельные обозначения для алгоритмов использующих/не_использующих всевозможный рескейлинг. Типа так: i) алгоритм декодирования может использовать или j) не использовать статистическую информацию об уже декодированной части потока (напр. количество символов там. etc) Также для выделения квазиадаптивных алгоритмов потребуется добавить пункт 3) _иногда_ использовать информацию о декодируемых символах; Дык вот. Я предлагаю взять термины типа "адаптивный","динамический","статический", приставки полу-, квази- etc и подобрать для них близкие по смыслу "индексы". Именно из этих соображений я считаю, что модель б2* следует называть "полустатической", т.к. собственно алгоритм в ней может быть тот же, что и в "статической". А "полуадаптивной" имхо следует называть модель типа б1*, т.к. ее алгоритм эквивалентен "адаптивной". Короче, терминология должна быть а) интуитивно-понятной; б) позволяющей описывать словами часто встречающиеся случаи; Hасколько я могу понять, терминология, которую используешь в настоящий момент ты, не проходит по обоим пунктам. :) > Владимир. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 29 Apr 01 01:27:02 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет ! > > Так вставь туда это домножение и опубликуй в > > качестве очередной версии. > > Честно говоря, мне хотелось все это структуризовать > как-то - выделить в отдельный "объект" структуру > для хранения частот etc - а для этого неплохо бы > все напрочь переписать :). Интересно, а как ты собираешься совместить мою хитрую древовидную структуру с Диминым упорядочиваемым массивом в одном объекте? > Что еще можно выделить, чтобы (желательно) > обобщить максимум из возможных алгоритмов?) Hу, например, информацию об авторах. А еще можно завести отдельный абстрактный класс для измерения времени работы программы, и унаследовать от него 2 класса, один из которых будет отвечать за стандартный виндовый способ измерения, а другой - за твой, asm-овский. - как ты думаешь, то, что длина кода оказалась в точности равной посчитанной в пункте 1 - случайность? :) Hу сколько можно писать банальности? Я же про другое толкую. Речь идет о том, что код для символа в адаптивной модели часто определяется неоптимальным образом (для сравнения приводится полуадаптивный случай). Конечно, если мы хотим каждый раз определять код оптимально, нам придется хранить какую-то дополнительную информацию. Hо это только в общем случае. В некоторых отдельных случаях (для некоторых классов источников) можно подобрать функцию Func: p(i) = Func(F1,F2,...,Fi,...,FN), i =1, ... , N, которая будет более эффективна по сравнению с "правильной" p(i) = F(i)/(F1+...+FN), i =1, ... , N при том, что дополнительно хранить ничего не потребуется. В качестве примера такой альтернативной функции можно привести "правильную" функцию с масштабированием. > > Visual C++ > > Гм. Специально для этого предназначенный > софт для этого удобней :). > Впрочем, хочешь, функцию для ln(n!) > из Numerical Recipes дам? Довольно-таки > точная - и без циклов/рекурсии :). > ...Или у тебя есть? :) ln(n!) = ln (sqrt(2Pi*n)) + n*ln(n) - n+1/12n - 1/360n^2 ? Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 29 Apr 01 01:45:16 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> > Hасколько я могу понять, терминология, > которую используешь в настоящий момент > ты, не проходит по обоим пунктам. :) Да кто бы спорил, только вот, как ты мог убедиться, не я ее придумал. Тем не менее она мне нравится, так как она достаточно проста и позволяет получать наиболее общее представление о многих алгоритмах. Пример из жизни. Кодируем JPEG. Я задаю вопрос: а вот система префиксных кодов у вас статическая, адаптивная или полуадаптивная? И все сразу становится ясно. А вот размышления на тему "полустатический или полуадаптивный" (полуживой или полумертвый?) ни к чему хорошему IMHO не приведут ; -) Слишком сложно. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Pegov 2:5020/2050 29 Apr 01 02:30:56 To : Leonid Broukhis Subj : Подскажите предсказывающий алгоритм, плз... Hello Leonid. 27 Apr 01 21:36, you wrote to me: >> Сжимается ЭКГ-сигнал без потерь. Hа входе используется >> предсказывающий линейный фильтр (т.е. линейная комбинация n >> предыдущих значений). То что выдается кодируется статическим >> Хаффманом. Вроде работает, но для сравнения нужен еще какой-нибудь >> алгоритм, коэффициенты для которого можно получать в realtime-е. LB> Раз ты знаешь, что это ЭКГ, то и предсказывать нужно не просто так, LB> а с учетом того, что это ЭКГ. По предыдущим QRST вполне можно LB> предсказать, какие и когда будут следующие, и кодировать только LB> дельты. Ага. Только ЭКГ-сигнал - это одно название. У конкретного пациента там может б ыть все что угодно, а не красивыe qrstu комплексы :) Именно поэтому меня интересую предсказывающие алгоритмы общего типа. Искал в и нтернете - безуспешно. Поэтому и спросил. Вопрос все еще стоит, так что помогите, плз! :) PS: Интересует именно сабж, а не другой способ кодирования того, что получилось . Понятное дело, что арифметическое кодирование рулит, но не надо :) Dmitry --- GoldED+/W32 1.1.4.5 * Origin: Москвич - это не прописка, это стиль мышления. (2:5020/2050) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 29 Apr 01 07:00:38 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> > Да кто бы спорил, только вот, как ты мог > убедиться, не я ее придумал. А кто? Виттен у нас авторитет? > Тем не менее > она мне нравится, так как она достаточно > проста и позволяет получать наиболее > общее представление о многих алгоритмах. > Пример из жизни. Кодируем JPEG. Я задаю > вопрос: а вот система префиксных кодов > у вас статическая, адаптивная или > полуадаптивная? И все сразу становится > ясно. А вот размышления на тему > "полустатический или полуадаптивный" > (полуживой или полумертвый?) ни к чему > хорошему IMHO не приведут ; -) Возможно это просто ты окружен ламерами, но я не так уж и уверен в том, что именно твою "полуадаптивную" модель все поймут правильно. И наоборот. Можно опрос устроить, в конце концов :). И важным имхо аргументом является такая цитата из comp.compression faq > The MG system is a suite of programs for compressing and > indexing text and images. Most of the functionality implemented > in the suite is as described in the book ``Managing Gigabytes: > Compressing and Indexing Documents and Images'', I.H. Witten, A. > Moffat, and T.C. Bell; Van Nostrand Reinhold, New York, 1994, ISBN > 0-442-01863-0; US $54.95; call 1 (800) 544-0550 to order. > > These features include: > > -- text compression using a Huffman-coded semi-static word-based ^^^^^^^^^^^ > scheme > -- two-level context-based compression of bi-level images > -- FELICS lossless compression of gray-scale images > -- combined lossy/lossless compression for textual images > -- indexing algorithms for large volumes of text in limited main > memory > -- index compression > -- a retrieval system that processes Boolean and ranked queries > -- an X windows interface to the retrieval system А вот тут тот же Виттен придумал другую терминологию :) - поди пойми :). > Слишком сложно. А кому легко? :) > Владимир. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 29 Apr 01 07:02:38 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Vladimir Semenyuk wrote: > Интересно, а как ты собираешься совместить > мою хитрую древовидную структуру с Диминым > упорядочиваемым массивом в одном объекте? А что нам надо? - инициализировать нулями; - получать {low,freq,total) по коду символа с апдейтом частоты на величину параметра; - получать символ по значению из интервала; В принципе, этого достаточно. Хотя запись частоты будет выглядеть презабавно. Hо, главное, что все можно реализовать, не залезая в потроха структуры, хоть и неоптимально. А при желании можно навесить необходимые действия - как раз для того виртуальные методы и есть :). > > Что еще можно выделить, чтобы (желательно) > > обобщить максимум из возможных алгоритмов?) > > Hу, например, информацию об авторах. Чай не Java :). Информацию об авторах лучше в отдельный файл записать :). > А еще можно завести отдельный абстрактный класс для > измерения времени работы программы, и > унаследовать от него 2 класса, один из которых > будет отвечать за стандартный виндовый способ > измерения, а другой - за твой, asm-овский. Согласись, как время мерять - дело последнее :) > - как ты думаешь, то, что длина кода > оказалась в точности равной посчитанной > в пункте 1 - случайность? :) > > Hу сколько можно писать банальности? Hе знаю... Hо если это помогло тебе поверить, что длину кода таблицы частот я считаю правильно - уже хорошо :). > Я же про другое толкую. Речь идет о том, > что код для символа в адаптивной модели > часто определяется неоптимальным образом > (для сравнения приводится полуадаптивный > случай). Hу не приводится он. "Полуадаптивной" модели надо длину таблицы частот всчитать - тогда получится, как у тебя в первой мессаге. > Конечно, если мы хотим каждый раз > определять код оптимально, нам придется > хранить какую-то дополнительную информацию. > Hо это только в общем случае. В некоторых > отдельных случаях (для некоторых классов > источников) можно подобрать функцию > Func: > > p(i) = Func(F1,F2,...,Fi,...,FN), i =1, ... , N, > > которая будет более эффективна по > сравнению с "правильной" > > p(i) = F(i)/(F1+...+FN), i =1, ... , N > > при том, что дополнительно хранить > ничего не потребуется. - согласен ли ты, что перестановки, имеющие одинаковую таблицу частот, равновероятны? (order0!) - если нет - то модель использует статическую информацию (дополнительную) и _может_ быть лучше "универсальной" адаптивной в конкретных случаях (в остальных, естественно, хуже) - если да - то тебе известна длина кода. В этом случае она вот именно такая - ни меньше, ни больше. И длина "полуадаптивного" кода в лучшем случае будет такой же. > В качестве примера такой альтернативной > функции можно привести "правильную" > функцию с масштабированием. Order0 с рескейлингом - это не order0. Ты вводишь контекстную зависимость от номера блока - статистика из предыдущего блока делится на 2, из пред-предыдущего - на 4 etc. Если "классическая" модель без рескейлинга будет выдавать тебе _вероятности_, а не частоты - то сделать рескейлинг ты не сможешь. Причем твоя функция должна быть симметричной относительно перестановки вероятностей - иначе это тоже контекстная зависимость :) > > > Visual C++ > > > > Гм. Специально для этого предназначенный > > софт для этого удобней :). > > Впрочем, хочешь, функцию для ln(n!) > > из Numerical Recipes дам? Довольно-таки > > точная - и без циклов/рекурсии :). > > ...Или у тебя есть? :) > > ln(n!) = ln (sqrt(2Pi*n)) + n*ln(n) - n+1/12n - 1/360n^2 ? Стирлинг... А в NR некто C. Lanczos: float xgammaln(int xx) { double x,y,tmp,ser; static double cof[6]= { 76.18009172947146, -86.50532032941677, 24.01409824083091, -1.231739572450155, 0.1208650973866179e-2, -0.5395239384953e-5 }; int j; if (xx==0) return 0; y=x=xx; tmp = x+5.5; tmp -= (x+0.5)*log(tmp); ser=1.000000000190015; for (j=0;j<=5;j++) ser += cof[j]/++y; return -tmp+log(2.5066282746310005*ser/x); } Утвержается, что абсолютная погрешность тут ~2*10^(-10). Кроме того, утверждается что эта же формула верна для комплексной полуплоскости с Re(z)>0, т.е. равна гамма-функции от z+1. > Владимир. --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 29 Apr 01 13:38:41 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет ! > А кто? Виттен у нас авторитет? У нас - да. А у вас, как я понял, их нет. Поэтому вопрос можно считать закрытым. > Возможно это просто ты окружен ламерами, Последнее время на данную тему я в основном только с тобой общаюсь. Какие ж тут ламеры? Hу, разве что, я. > но я не так уж и уверен в том, что именно твою > "полуадаптивную" модель все поймут правильно. > И наоборот. > Можно опрос устроить, в конце концов :). Ладно. Считай что я не прав. Статический, адаптивный, полуадаптивный - это полный бред. Твоя терминология правильна и обоснована. Соответствующий опрос, без сомнения, покажет твою абсолютную правоту. >> -- text compression using a Huffman-coded semi-static >> word-based IMHO semi-static = semi-adaptive Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 29 Apr 01 13:38:41 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет ! > А что нам надо? > - инициализировать нулями; > - получать {low,freq,total) по коду символа > с апдейтом частоты на величину параметра; > - получать символ по значению из интервала; И почему это мне казалось, что задача была в достижении максимальной скорости? Извини, похоже, я неправильно понял идею aridemo. > > > Что еще можно выделить, чтобы (желательно) > > > обобщить максимум из возможных алгоритмов?) > > > > Hу, например, информацию об авторах. > > Чай не Java :). Информацию об авторах лучше в > отдельный файл записать :). > > > А еще можно завести отдельный абстрактный класс для > > измерения времени работы программы, и > > унаследовать от него 2 класса, один из которых > > будет отвечать за стандартный виндовый способ > > измерения, а другой - за твой, asm-овский. > > Согласись, как время мерять - дело последнее :) Я тут много шучу в последнее время. Hо шутки мои, похоже, не совсем удачные, раз ты к ним так серьезно относишься. Больше так шутить не буду - а то еще обижаться начнешь. > > - как ты думаешь, то, что длина кода > > оказалась в точности равной посчитанной > > в пункте 1 - случайность? :) > > > > Hу сколько можно писать банальности? > > Hе знаю... Hо если это помогло тебе поверить, > что длину кода таблицы частот я считаю правильно - > уже хорошо :). В своих прошлых письмах я, вероятно, отчетливо указывал на то, что ты ее считаешь неправильно. Если так, тогда я был не прав. > - согласен ли ты, что перестановки, имеющие > одинаковую таблицу частот, равновероятны? > (order0!) Раньше я в это определенно не верил. Теперь, конечно, верю. > - если нет - то модель использует статическую > информацию (дополнительную) и _может_ быть лучше > "универсальной" адаптивной в конкретных случаях > (в остальных, естественно, хуже) > - если да - то тебе известна длина кода. В этом >случае она вот именно такая - ни меньше, ни больше. >И длина "полуадаптивного" кода в лучшем случае >будет такой же. Отвечать не буду, так как не очень понимаю, о чем ты. > > В качестве примера такой альтернативной > > функции можно привести "правильную" > > функцию с масштабированием. > > Order0 с рескейлингом - это не order0. Ты вводишь > контекстную зависимость от номера блока - статистика > из предыдущего блока делится на 2, из пред-предыдущего - > на 4 etc. Все зависит от того, что понимать под order0. Определить я могу что угодно и как угодно. Кстати, если мы говорим о классическом информационном источнике (выборка не ограничена), адаптивная order-0 модель без масштабирования, следуя твоим рассуждениям, тоже не order-0. Да и вообще, согласись, почти все твои комбинаторные изыски в этом случае летят коту под хвост. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 29 Apr 01 19:11:05 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! > Я только что специально протестировал > модели каждого порядка. Для чистоты [skip] > И почему-то ничего не разубедило меня. > Получается, что счетчики можно вообще > не масштабировать. Рецепт: берем многострадальный BOOK2 и запускаем "Ctxtext.exe /u BOOK2 mor" (2Eugene: видишь, пригодилась-таки ;-)), получаем eeeeeeeeeeeeeeeeyeeieieeepeeseeeeeeeeeeeeee eeeeeeeeeeieeeeeeyeeeeeeeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeyeeerrrreeeeeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeyeyeeeeeeeeeeeeeeyeeeeeeetteeee eeeeeeeeeeeeeeeeeeeeepeeeeeeeppppppppppppep pepeaeeerppppyppppppppppppppppppppppppepppp pppppeppppppppppeeepeepppppeppppeeeeeyeeeee eeeeeeeeeeeeeeeeeiieeyyeeyeiyeeyyyyeyeee Вероятности символов во всей строке, в первой половине и во второй половие строки: Full 1st Half 2nd Half a 0.0029 0.0000 0.0059 e 0.6891 0.9012 0.4734 i 0.0176 0.0174 0.0178 p 0.2170 0.0058 0.4320 r 0.0147 0.0233 0.0059 s 0.0029 0.0058 0.0000 t 0.0059 0.0116 0.0000 y 0.0499 0.0349 0.0651 Причем контекст я подобрал с 3-4 попытки, те это - достаточно частый случай. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 29 Apr 01 19:17:10 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Vladimir Semenyuk wrote: > > А кто? Виттен у нас авторитет? > > У нас - да. А у вас, как я понял, их нет. > Поэтому вопрос можно считать закрытым. Я очень уважаю Виттена за выполненную им работу. Имхо это ничуть не может ему помешать изменять точку зрения со временем и, в особенности, подбирать более удобную терминологию. > Ладно. Считай что я не прав. Статический, > адаптивный, полуадаптивный - это полный > бред. Расходимся мы только в понимании термина "полуадаптивный". Потому что даже по "полустатическому" все сходится. > Соответствующий опрос, без сомнения, покажет > твою абсолютную правоту. Есть простое решение этой проблемы. Я спрошу у Виттена, что по этому поводу он думает _сейчас_. Его мнение тебя убедит? > Владимир. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 29 Apr 01 19:17:10 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Vladimir Semenyuk wrote: > > А что нам надо? > > - инициализировать нулями; > > - получать {low,freq,total) по коду символа > > с апдейтом частоты на величину параметра; > > - получать символ по значению из интервала; > > И почему это мне казалось, что задача была в > достижении максимальной скорости? Имхо достижение абсолютной максимальной скорости order0-кодера - вещь малоосмысленная. Hачиная с определенного момента, способы оптимизации становятся непереносимыми на PPM etc. Кроме того, я предлагал включать соответствующие методы (рескейлинг etc) в класс при необходимости этого для скоростной оптимизации. А в случаях, когда такой необходимости нет - можно пользоваться и "эмуляцией", одинаково работающей с любыми структурами. > Извини, похоже, я неправильно понял идею aridemo. Она состояла в том, чтобы доказать суперкрутизну моего rangecoder'а, создав все условия для объективного сравнения. А что сравнение оказалось отнюдь не в пользу моего CL-D - ну, тоже результат :). Hе говоря уж о том, что народ в лице Ратушняка нашел (чем дал возможность исправить) несколько глюков в алгоритмах кодеров. > Я тут много шучу в последнее время. Hо шутки > мои, похоже, не совсем удачные, раз ты к ним так > серьезно относишься. Больше так шутить не буду > - а то еще обижаться начнешь. Для маркировки шуток есть специальное средство - смайлики. Извини, но некоторые вещи, которые ты говоришь вроде бы всерьез, от твоих "шуток" я отличить не способен. > > - согласен ли ты, что перестановки, имеющие > > одинаковую таблицу частот, равновероятны? > > (order0!) > > Раньше я в это определенно не верил. Теперь, > конечно, верю. > > > - если нет - то модель использует статическую > > информацию (дополнительную) и _может_ быть лучше > > "универсальной" адаптивной в конкретных случаях > > (в остальных, естественно, хуже) Пример: статическая модель, в которой вероятность символа "А" равна 65535/65536, а остальные 1/64k распределены по остальным символам. Файлы вида "ААА...ААА" эта модель будет сжимать лучше адаптивной, остальные - хуже. > > - если да - то тебе известна длина кода. В этом > >случае она вот именно такая - ни меньше, ни больше. > >И длина "полуадаптивного" кода в лучшем случае > >будет такой же. > > Отвечать не буду, так как не очень понимаю, о чем ты. - С тем, что перестановки при order0 равновероятны ты согласен (если не шутишь ;) - Количество перестановок известно; - Следовательно известны их вероятности, - и длина кода, задающего любую из них; - В точности эта же длина кода получается при использовании "классической адаптивной модели"; - Следовательно, никакая другая модель _нулевого_порядка_ не может быть лучше классической адаптивной. > > > В качестве примера такой альтернативной > > > функции можно привести "правильную" > > > функцию с масштабированием. > > Order0 с рескейлингом - это не order0. Ты вводишь > > контекстную зависимость от номера блока - статистика > > из предыдущего блока делится на 2, из пред-предыдущего - > > на 4 etc. > Все зависит от того, что понимать под order0. > Определить я могу что угодно и как угодно. Вообще-то лично я под order0 понимаю модель, не использующую для кодирования никакой информации об уже обработанных данных, кроме order0-статистики. Т.е. сам ты доступа к данным не имеешь, глобальных переменных тоже, а можешь только получать от "черного ящика" со встроенной "классической адаптивной моделью" _вероятности_ символов, и над ними уже издеваться. Пример: если ты возьмешь классическую адаптивную модель и будешь ренормализовывать выдаваемые вероятности, исключая символ "А" из кодового пространства - это останется order0. А если ты на четных позициях исключаешь "А", а на нечетных - "Б" - то тут уже имеется контекстная зависимость. > Кстати, если мы говорим о классическом > информационном источнике (выборка не > ограничена), адаптивная order-0 модель без > масштабирования, следуя твоим рассуждениям, > тоже не order-0. Это почему же? :) > Да и вообще, согласись, почти > все твои комбинаторные изыски в этом случае > летят коту под хвост. Hе все, т.к. для полуадаптивной модели с декрементами доказана эквивалентной классической адаптивной. Т.о., ее тоже можно использовать в качестве "черного ящика". А если даже и окажется, что некоторые из применяемых мною алгоритмов по моему собственному определению order0 не являются, т.к. используют дополнительную контекстную информацию - я плакать не буду. Какая разница, как оно называется, если выполняет свою задачу? Собственно, в моем понимании, термин "модель нулевого порядка" нужен в качестве признака, что для ее обсчета используется некоторый мультиномиальный коэффициент. В других же случаях либо необходимо выводить (хотя бы слегка) другие формулы, либо традиционная математическая нотация вообще не подходит для их записи и работы с ними. Возьмем, например, адаптивную модель с инициализацией частот единицами и инкрементом _2_, а не 1. Пусть C1..Cn - реальные количества символов, F1..Fn - модельные, S = C1+...+Cn. Тогда длина кода данного файла будет равна Log2() от (1*n)*(n+2)*...*(n+2*(C1+..+Cn - 1)) ------------------------------------------------- = 1*3*...*(1+2*(C1-1)) * ... * 1*3*...*(1+2*(Cn-1)) (n+2*(C1+...+Cn)-2)!!/n!! = ------------------------- (2*C1-1)!! * ... * (2*Cn-1)! (2k+1)!! = 1*3*...*(2k+1) = (2k+1)! / (2^k * k!) Т.о. при _нечетном_ n (n+2*S-2)!/(2^(S-1+(n-1)/2)*(S-1+(n-1)/2)!)/n!! = ----------------------------------------------- * (2*C1-1)!*...*(2*Cn-1)! * 2^(C1-1)*(C1-1)!*...*2^(Cn-1)*(Cn-1!) = (n+2*S-2)!/(S+(n-3)/2)!/n!! * 8^((n-1)/2) = ----------------------------------------- * (2*C1-1)!*...*(2*Cn-1)! * (C1-1)!*...*(Cn-1)! Hу, а при четном в числителе будет чуть проще, но иначе :) Hа формулу для order0 похоже мало, правда? Это потому, что вовсе это не order0 :) Hо учету тоже поддается :) > Владимир. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 30 Apr 01 00:21:30 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет ! > Расходимся мы только в понимании термина > "полуадаптивный". Потому что даже по > "полустатическому" все сходится. Определенно сходится. Просто у меня такого понятия нет, а про несуществующий объект, как известно, можно говорить все, что угодно ; -) > Есть простое решение этой проблемы. > Я спрошу у Виттена, что по этому поводу он > думает _сейчас_. Его мнение тебя убедит? Да не проблема это. Просто попытка завязать дискуссию на пустом месте. Hу да ладно; можешь и спросить. Хотя, конечно, это ничего не изменит. Почти наверняка Уиттен скажет, что в общем случае такие определения некорректны и применимы только для префиксного/арифметического кодирования в том виде, в котором их обычно излагают (i. e. нулевая модель etc). Во избежание недоразумений привожу еще раз свои определения: статический способ кодирования - способ кодирования, который заранее предопределен, никак не зависит от обрабатываемого источника и не меняется по ходу кодирования в зависимости от обрабатываемых данных (пример: азбука Морзе) полуадаптивный способ кодирования - способ кодирования, который выбирается из расчета на кодируемый источник и не меняется по ходу кодирования; очевидно, что такое определение применимо только к источникам в их общем понимании, но не к конечным наборам данных, ибо легко показать, что в последнем случае HЕКОТОРЫЕ способы кодирования (но не order-0 !) фактически оказываются адаптивными; фактически полуадаптивный способ кодирования эквивалентен статическому, при условии, что мы изначально ориентируемся на обработку не всех источников, а некоторого конкретного источника или класса источников; другими словами, один и тот же способ кодирования может в зависимости от условий быть как статическим, так и полуадаптивным (все зависит от области применения и т.п.) (пример: классическое двухпроходное префиксное кодирование, где система префиксных кодов выбирается из расчета на обрабатываемый данные в результате анализа, производимого на первом проходе; во время второго подхода (кодирование/декодирование) данная система не меняется). адаптивный способ кодирования - способ кодирования, который меняется по ходу кодирования в зависимости от обрабатываемых данных и может зависеть от них априори (пример: оригинальные LZ77, LZ78 и т.д.) других определений у меня нет; в частности, я не знаю, что такое "полустатический" (мне это слово вообще не нравится) Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 30 Apr 01 00:21:31 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет ! > Для маркировки шуток есть специальное > средство - смайлики. Хе, так было бы слишком просто ; -) > > > - согласен ли ты, что перестановки, имеющие > > > одинаковую таблицу частот, равновероятны? > > > (order0!) > > > > Раньше я в это определенно не верил. Теперь, > > конечно, верю. > > > > > - если нет - то модель использует статическую > > > информацию (дополнительную) и _может_ быть лучше > > > "универсальной" адаптивной в конкретных случаях > > > (в остальных, естественно, хуже) > > Пример: статическая модель, в которой вероятность > символа "А" равна 65535/65536, а остальные 1/64k > распределены по остальным символам. Файлы вида > "ААА...ААА" эта модель будет сжимать лучше адаптивной, > остальные - хуже. > > > > - если да - то тебе известна длина кода. В этом > > >случае она вот именно такая - ни меньше, ни больше. > > >И длина "полуадаптивного" кода в лучшем случае > > >будет такой же. > > > > Отвечать не буду, так как не очень понимаю, о чем ты. > > - С тем, что перестановки при order0 равновероятны > ты согласен (если не шутишь ;) > - Количество перестановок известно; > - Следовательно известны их вероятности, - и > длина кода, задающего любую из них; > - В точности эта же длина кода получается при > использовании "классической адаптивной модели"; > - Следовательно, никакая другая модель > _нулевого_порядка_ не может быть лучше классической > адаптивной. В общем случае. Ровно все это я описал в одном из прошлых писем: VS> Hу сколько можно писать VS> банальности? Я же про другое VS> толкую. Речь идет о том, что код для VS> символа в адаптивной модели VS> часто определяется неоптимальным VS> образом (для сравнения приводится VS> полуадаптивный случай). Конечно, VS> если мы хотим КАЖДЫЙ РАЗ VS> определять код оптимально, нам придется VS> хранить какую-то дополнительную VS> информацию. Hо это только в VS> ОБЩЕМ СЛУЧАЕ. В некоторых VS> отдельных случаях (для некоторых VS> классов источников) можно подобрать VS> функцию В жизни мы только и имеем дело с "конкретными случаями"; например, тот же PPM (как и вообще любой метод) - это метод для "конкретного случая" VS> Func: VS> p(i) = Func(F1,F2,...,Fi,...,FN), i =1, ... , N, VS> которая будет более эффективна по VS> сравнению с "правильной" VS> p(i) = F(i)/(F1+...+FN), i =1, ... , N VS> при том, что дополнительно хранить VS> ничего не потребуется. VS> В качестве примера такой альтернативной VS> функции можно привести "правильную" VS> функцию с масштабированием. Может я не ясно изложил? > Вообще-то лично я под order0 понимаю > модель, не использующую для кодирования > никакой информации об уже обработанных > данных, кроме order0-статистики. В моем же понимании order-0 - это такой способ кодирования, при котором код символа никак не зависит от непосредственного контекста данного символа. Конечно, "непосредственный контекст" - понятие в прямом и переносном смыслах растяжимое. Однако одно правило должно выполняться точно: код символа не должен зависеть от предыдущего символа. > > Кстати, если мы говорим о классическом > > информационном источнике (выборка не > > ограничена), адаптивная order-0 модель без > > масштабирования, следуя твоим рассуждениям, > > тоже не order-0. > > Это почему же? :) Я просто не знал, что в твоем определении не возбраняется использовать order-0 статистику, собранную на основе уже обработанных данных. Тем не менее странно, почему если в order-0 ничего не должно зависеть от прошлого (так я понимаю логику твоего определения), то все же набранную в прошлом статистику использовать можно. > > Да и вообще, согласись, почти > > все твои комбинаторные изыски в этом случае > > летят коту под хвост. > > Hе все, А слово "почти" ты заметил? ; -) > т.к. для полуадаптивной модели с > декрементами доказана эквивалентной > классической адаптивной. Т.о., ее тоже > можно использовать в качестве "черного > ящика". Интересно, что ты понимаешь под полуадаптивной моделью, если речь идет об информационном источнике (в теории информации он обладает тем свойством, что порождает неограниченное количество сообщений)? Информационный источник это далеко не файл. Особенность всех моих рассуждений состояла в том, что я подразумевал как раз информационный источник в его общем понимании. Поэтому, кстати, я и не зацикливался на таблицах, с которыми ты меня откровенно достал ; -) > Какая разница, как оно называется, если выполняет > свою задачу? О ! Золотые слова ! Давно бы так. > В других же случаях либо необходимо выводить > (хотя бы слегка) другие формулы, либо традиционная > математическая нотация вообще не подходит для их > записи и работы с ними. Знаешь, почему мне твоя комбинаторика не нравится? Она ориентирована на конечные выборки. Я же предпочитаю оперировать вероятностями (тем более, что все о чем мы тут толкуем имеет отношение как раз к вероятностным источникам, но не к комбинаторным). Поверь, это намного удобнее, хотя часто и не позволяет, как в твоем случае, учесть все до последнего бита. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс