| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Sergey Erokhin 2:461/108.7 30 Apr 01 00:45:00 To : Vladimir Pushkaryov Subj : Сигнатypа "BH" Hello Vladimir! VP> Интеpесно, какой тип аpхивов начинается с сабжа? BlackHole Это внутренний формат некой либы под названием ziptv вроде как. понимает его например PoverArchiver которые собственно на ней и написан. уши алгоритма вроде как из зипа. Sergey ... You have the capacity to learn from mistakes. You'll learn a lot today. --- GoldED+/386 1.1.4.4 * Origin: Living in interesting times (2:461/108.7) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 30 Apr 01 03:42:46 To : All Subj : Re: Подскажите предсказывающий алгоритм, плз... From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Dmitry Pegov wrote: > > Hello Leonid. > > 27 Apr 01 21:36, you wrote to me: > >> Сжимается ЭКГ-сигнал без потерь. Hа входе используется > >> предсказывающий линейный фильтр (т.е. линейная комбинация n > >> предыдущих значений). То что выдается кодируется статическим > >> Хаффманом. Вроде работает, но для сравнения нужен еще какой-нибудь > >> алгоритм, коэффициенты для которого можно получать в realtime-е. > LB> Раз ты знаешь, что это ЭКГ, то и предсказывать нужно не просто так, > LB> а с учетом того, что это ЭКГ. По предыдущим QRST вполне можно > LB> предсказать, какие и когда будут следующие, и кодировать только > LB> дельты. > > Ага. Только ЭКГ-сигнал - это одно название. У конкретного пациента там может > быть все что угодно, а не красивыe qrstu комплексы :) > Именно поэтому меня интересую предсказывающие алгоритмы общего типа. Искал в > интернете - безуспешно. Поэтому и спросил. > Вопрос все еще стоит, так что помогите, плз! :) Я, конечно, в ЭКГ ни в зуб ногой, но есть у меня подозрение, что принципиальных отличий от обычного звука быть не должно. Посему как насчет применения алгоритмов, ориентированных на работу со звуком? Для начала можно было бы приделать к массиву отсчетов сигнала wav'овский заголовок и поприменять существующий софт :) > PS: Интересует именно сабж, а не другой способ кодирования того, что > получилось. Понятное дело, что арифметическое кодирование рулит, но не надо : ) Hу кто ж тебе подскажет оптимальный алгоритм кодирования, не видя данных? :) > Dmitry Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 30 Apr 01 03:42:46 To : All Subj : [Fwd: Re: terminology] From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Вот я и говорю: Виттен - это вам не некоторые присутствующие редиски :) Правда, с моей точки зрения результат скорее отрицательный, но зато он есть! :) -------- Original Message -------- Subject: Re: terminology Date: Mon, 30 Apr 2001 08:20:23 +1200 From: "Ian H. Witten" <ihw_AT_rata.cs.waikato.ac.nz> To: shelwien@thermosyn.com According to the way I use the terminology: A static compression system is one that does not use any statistics of the file being encoded A semi-static (equivalently, semi-adaptive) system uses statistics of the file being encoded (plus, possibly, other information); it creates the model from the whole file and then starts to transmit it. An adaptive system uses statistics of the file being encoded (plus, possibly, other information) and creates the model as it is going along -- thus the model can't contain information from the "future" part of the file. So, in your examples: 1. The model, which doesn't use any statistics of given data is called "static" 2. The model, which use any statistics of already processed data is called "adaptive". yep 3. The model, which doesn't use any statistics of processed data _on decoding_. umm ... then the encoder can't have used any statistics of the data, surely -- so it must be static 4. The model, which use _both_ static info collected by coder, and processed data statistics. Eg. order0, which places the frequency table in a separate place, and on decoding takes it, and decrements the counter after decoding each symbol. I'd rather talk about the encoder than the decoder. But this sounds semi-adaptive to me, make a model for the whole file and then start transmitting with respect to that model. Hope this helps cheers ian --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 30 Apr 01 04:35:04 To : Dmitry Pegov Subj : Re: Подскажите предсказывающий алгоритм, плз... From: leob@mailcom.com (Leonid Broukhis) Dmitry Pegov wrote: > LB> Раз ты знаешь, что это ЭКГ, то и предсказывать нужно не просто так, > LB> а с учетом того, что это ЭКГ. По предыдущим QRST вполне можно > LB> предсказать, какие и когда будут следующие, и кодировать только > LB> дельты. > > Ага. Только ЭКГ-сигнал - это одно название. У конкретного пациента там может >быть все что угодно, а не красивыe qrstu комплексы :) Тем не менее, если пациент скорее жив, чем мертв, то даже у него, конкретного, между двумя соседними сокращениями сердца разница невелика будет (аритмию все равно не предскажешь). Поэтому использовать диапазон отсчетов между двумя соседними R в качестве предсказания следующих отсчетов может быть не так уж и плохо, потому что чем больше модель знает об источнике, тем лучше будет сжатие. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 30 Apr 01 09:48:18 To : All Subj : Re: Подскажите предсказывающий алгоритм, плз... From: "Andrew Kadatch" <kadatch@email.msn.com> Привет всем! Мне кажется, что правильная реализация -- следующая: 1. Использовать правильный адаптивный фильтр для предсказаний. Т.е., во-первых, длина фильтра должна быть достаточно большой. Если используется FIR-фильтр, его длина в несколько (4-10) раз должна превышает период сигнала, т.е. фильтр должен иметь N=4..10Fs коэффициентов, где Fs -- частота дискретизации (я предполагаю, что частота сердцебиения в среднем 60 ударов в минуту = 1 удар в секунду; период сигнала = 1 сек.). Возможно, IIR-фильтр будет лучше и с меньшим количеством коэффициентов будет не хуже FIR-фильтра. Адаптивный FIR-фильтр: y[k+1] = sum_{j=0}^{N-1} C[j] x[k-j], где y[k+1] -- предсказанное значение следующего отчета x[k+1]. Адаптация фильтра: for all j set C[j] += A*E[k+1] / s[k] where E[k+1] = x[k+1] - y[k+1] -- ошибка предсказания (которую и нужно будет передавать), s[k] = sum_{j=0}^{N-1} x[k-j]*x[k-j] -- надеюсь, всем понятно, что для получения s[k] из s[k-1] достаточно двух умножений и двух сложений и A (0 < A <= 1) -- параметр, определяющий скорость сходимости фильтра. Адаптивный FIR-фильтр легко преобразовать в FIR-фильтр след. образом: y[k+1] = sum_{j=0}^{N-1} (C[2j]x[k-j] + C[2j+1]y[k-j]). Алгоритм адаптации коэффициентов тот же самый. Учтите, что время настройки фильтра обычно на порядок превышает его длину, т.е. хорошо фильтр должен начать работать только через минуту-полторы после начала записи. Поэтому, возможно, имеет смысл сначала настроить фильтр, затем передать его коэффициенты (5 бит экспоненты и 8 бит мантиссы), и лишь потом начать запись передачей разностей значений, предсказанных фильтром и полученных с датчика. Экономия очень простая: первые 10NFs (где Fs -- частота сэмплирования) отчетов будут предсказаны не очень хорошо и потребуют 8-16 бит на отчет. Передача N коэффициентов обойдется существенно дешевле. 2. Если предсказатель работает хорошо, то начиная с некоторого момента последовательность E будет представлять собой белый шум, который, конечно же, передавать и кодировать не нужно. Другими словами, если |E| < T, где T -- некоторый порог (желательно немного меньший или больший средней амплитуды шума), то нужно передавать разность 0 и заменять x[k+1] на у[k+1] для обеспечения когерентности кодирования и декодирования. Простой пример: при аудиозаписи при использовании аппаратуры (и, главное, кабелей) не очень высокого класса добиться уровня шума меньше -60 дб практически невозможно из-за шума соединений и проводов. Т.е. из 16 бит 3-5 бит содержат мусор. Именно поэтому безызбыточное кодирование физических сигналов практически никогда не применяется -- даже при идеальном предсказателе необходимо передавать белый шум, который, конечно, обладает нулевой избыточностью (посему применение арифметического кодирования не даст никакого эффекта). Если не отбрасывать шум, то добиться стоимости кодирования менее 3-5 битов на отчет мне представляется невозможным. Попробуйте, потом расскажете, что получится. АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 30 Apr 01 10:24:34 To : All Subj : Re: Подскажите предсказывающий алгоритм, плз... From: "Andrew Kadatch" <kadatch@email.msn.com> Hу и отвечая на вопрос о собственно кодировании разностей... Диапазон возможных значений разностей разбивается на группы значений, содержащие 2**k элементов каждая, н-р группа 0 => 0 группа 1 => [1..4] 2 => [-1..-4] 3 = [4..8] 4 = [-4..-8] 5 = [8..15] 6 = [-8..-15] и т.д. -- начиная с некоторого момента, размер группы увеличивается вдвое с ростом модулей содержащихся в ней элементов. Кодирование осуществляется следующим образом: значению X ставится в соответсвие пара (G,I), где G -- номер группы, содержащей X, а I -- номер значения (по порядку) в G-ой группе. Пара кодируется следующим образом: последовательность значений G[k] сжимается по Хаффману, арифметическим кодом, RLE, LZ77 или еще как-нибудь. Последовательность I[k] передается равномерным кодом -- для передачи I[k] используется log_2(|G[k]|) битов, где |G[k]| -- мощность (количество содержащихся элементов) группы G[k]. С учетом того, что, как я отмечал в предыдущем письме, передача белого шума -- дорогое удовольствие, которое сводет на нет все усилия по сжатию G[k], т.к. кодирование белого шума обычно составляет большую часть стоимости передачи. АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 30 Apr 01 12:39:59 To : All Subj : Re: Подскажите предсказывающий алгоритм, плз... From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! > Сжимается ЭКГ-сигнал без потерь. > Hа входе используется предсказывающий > линейный фильтр (т.е. линейная комбинация > n предыдущих значений). То что выдается > кодируется статическим Хаффманом. Вроде > работает, но для сравнения нужен еще > какой-нибудь алгоритм, коэффициенты > для которого можно получать в realtime-е. Было бы неплохо, если бы ты где-нибудь выложил соответствующий сэмпл. Достаточно длинный, но не слишком (<100K), чтобы можно было через модем за пару минут закачать. Или пришли по почте. Хотя, скорее всего, лучше чем у тебя сейчас без потерь уже не получится. А про арифметик это ты зря. Совре- менные его реализации достаточно быстры и очень просты. (Во всяком случае, они, как правило, не уступают в производительности АДАПТИВHОМУ префиксному кодированию.) Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 01 May 01 07:11:58 To : Andrew Kadatch Subj : Re: Подскажите предсказывающий алгоритм, плз... From: leob@mailcom.com (Leonid Broukhis) Andrew Kadatch wrote: >Учтите, что время настройки фильтра обычно на порядок превышает его длину, >т.е. >хорошо фильтр должен начать работать только через минуту-полторы после >начала записи. Ровно тогда, когда кардиограмма закончится. Поэтому нужно еще выяснить, требуется ли сжатие в real-time, или можно делать постпроцессинг. >Поэтому, возможно, имеет смысл сначала настроить фильтр, затем >передать >его коэффициенты (5 бит экспоненты и 8 бит мантиссы), и лишь потом начать >запись >передачей разностей значений, предсказанных фильтром и полученных с датчика. Если обязателен real-time, то не годится. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 01 May 01 10:17:24 To : All Subj : Re: Подскажите предсказывающий алгоритм, плз... From: "Andrew Kadatch" <kadatch@email.msn.com> Положа руку на сердце, я бы лично вообще не маялся с фильтрованием, а сделал бы попросту: БКП, обрезать все частоты выше 45 Гц, оставшиеся коэффициенты, взятые с монотонно убывающим весом, квантизовать и передать. Такой примитивный MPEG. Длину БКП взять в 10-20 секунд, чтобы вычленить главную частоту, и все будет просто замечательно... -- АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 01 May 01 10:28:09 To : All Subj : Distance coding Q From: "Andrew Kadatch" <kadatch@email.msn.com> Уважаемые господа и дамы! Hе просветите ли меня, как чайника, в чем глубокий смысл и сырмяжная правда distance coding? -- по моим скудным сведениям, distance coding является менее эффективной формой inverted frequency coding. Вот как ни прикину одно к другому, все IF получается... Или я что-то не так понял? Заранее спасибо, АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 02 May 01 17:51:58 To : All Subj : Re: Distance coding Q From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Вообще-то на такие вопросы лучше бы Вадиму Юкину отвечать. Тем более, что он обещал новый BWT FAQ :) Hу да ладно, раз уж его не видно... Andrew Kadatch wrote: > Hе просветите ли меня, как чайника, Практика показывает, что они обычно непрозрачные :) > в чем глубокий смысл и сырмяжная правда distance coding? В том, что лучшие (по эффективности) из существующих blocksorting'овых компрессоров основаны именно на нем. > -- по моим скудным сведениям, distance coding является > менее эффективной формой inverted frequency coding. А по моим - это одно и то же :). Если правильно кодировать отсчеты в обоих случаях. Только вот для DC это можно сделать намного проще - так уж получилось. > Вот как ни прикину одно к другому, все IF получается... В DC ячейки, которые считать не надо, в расстоянии не учитываются. В IF тоже возможно нечто подобное, но там для этого требуется некое отфонарное упорядочивание - сначала полные расстояния между вхождениями первого символа, потом расстояния между вхождениями второго, не считая первого etc. А DC к фиксированному порядку не привязан - если символ раньше - от его дистанса и отнимется больше. Уже одного этого достаточно, чтобы обойти IF по сжатию. Потом, в DC есть удобный способ обработки RLE - вообще ничего не делать :) - это дает еще некоторое преимущество (по сжатию, в первую очередь). > Или я что-то не так понял? Hу и последний момент - DC как бы "более поточный" алгоритм, чем IF. Что позволяет привязываться к контексту, кодируя дистансы. В результате "чистый" DC + order0 ari дает у меня на book1 ~226k, а YBS'овый контекстный - ~213k. > Заранее спасибо, > АК Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 02 May 01 21:12:51 To : Eugene D. Shelwien Subj : Re: Distance coding Q From: "Andrew Kadatch" <kadatch@email.msn.com> Хмм, видимо, я что-то не понимаю. Итак, IF: вхождения символа заменяются на количество лексикографически больших символов между текущим и предыдущим вхождением (можно полагать, что сообщение предваряется полным алфавитом в обратном порядке). DC: символ заменяется на расстояние до предыдущего вхождения. Очевидно, это хуже IF, посему простая оптимизация: уже закодированные символы выкидываются из сообщения. Тем самым DC сводится к IF при лексикографическом порядке, порожденном порядком замены символов при DC. Другими словами, если делать DC с описанной выше оптимизацией в естественном лексикографическом порядке (заменить символ с кодом 0 на расстояния до преды- дущего вхождения, удалить все символы с кодом 0 из сообщения, и повторять это процедуру для символов с кодом 1, 2, 3 и т.д.), то получается не что иное, как IF. Вопрос: прав ли я, и если нет, то почему? Спасибо, АК --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 02 May 01 21:49:13 To : All Subj : Re: Distance coding Q From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Андрей ! > Итак, IF: вхождения символа заменяются на > количество лексикографически больших символов > между текущим и предыдущим вхождением (можно > полагать, что сообщение предваряется полным > алфавитом в обратном порядке). А пример не приведешь? > DC: символ заменяется на расстояние до > предыдущего вхождения. Вообще-то из этого расстояния много чего выкидывается. А потом, кодирование осуществляется не ссылкой назад, а, скажем так, "ссылкой вперед". Владимир. PS. Я тут некоторое время назад объяснял DC на примере. См. архив эхи. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 02 May 01 22:42:47 To : Vladimir Semenyuk Subj : Re: Distance coding Q From: "Andrew Kadatch" <kadatch@email.msn.com> Hу например, рассмотрим след. последовательность: [cba]aabbccbbaabbccaa IF (для каждого символа строится последовательность количества лексикографически больших символов, разделяющих предыдущее и текущее вхождение): a: 0, 0, 6, 0, 4, 0 b: 0, 0, 2, 0, 0, 0 c: 0, 0, 0, 0 [should not be encoded; only number of c's tranmitted] DC в оригинале (расст. до предыдущего вхождения - 1) a: 0, 0, 6, 0, 4, 0 b: 3, 0, 2, 0, 2, 0 с: 6, 0, 6, 0 DC с выкидыванием уже закодированных символов: a: 0, 0, 6, 0, 4, 0 [cb]bbccbbbbcc b: 0, 0, 2, 0, 0, 0 [c]cccc c: 0, 0, 0, 0 [should not be encoded; only number of c's transmitted] Hу вот у нас и получилось DC c примитивной оптимизацией = IF... А где лежат архивы эхи? Спасибо, АК --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 02 May 01 23:02:56 To : All Subj : Re: Distance coding Q From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Andrew Kadatch wrote: > Хмм, видимо, я что-то не понимаю. Определенно :) > Итак, IF: вхождения символа заменяются на количество > лексикографически больших ^^^^^^^^^^^^^^^^^^^^^^^^^ !!! > символов между текущим и предыдущим вхождением (можно полагать, > что сообщение предваряется полным алфавитом в обратном порядке). Или, как вариант, можно каждому символу сопоставить массив с адресами его вхождений в файле, из которого уже удалены все символы с большими (или меньшими) кодами. Имхо это проще себе представить. > DC: символ заменяется на расстояние до предыдущего вхождения. Hет. > Очевидно, это хуже IF, посему простая оптимизация: уже закодированные символы > выкидываются из сообщения. Отнюдь не "уже закодированные". > Тем самым DC сводится к IF при лексикографическом > порядке, порожденном порядком замены символов при DC. Hет. > Другими словами, если делать DC с описанной выше оптимизацией в естественном > лексикографическом порядке (заменить символ с кодом 0 на расстояния до преды- > дущего вхождения, удалить все символы с кодом 0 из сообщения, и повторять > это процедуру для символов с кодом 1, 2, 3 и т.д.), то получается не что > иное, как IF. Если делать то, что ты сказал - да. А DC - это нечто несколько иное. > Вопрос: прав ли я, и если нет, то почему? Патамучта. > Спасибо, > АК DC кодирует вместо текущего символа расстояние до _следующего_ его вхождения. Как бы это ни казалось похожим на кодирование "ссылки" на предыдущее вхождение ссылки - это разные вещи. При ссылке вперед тебе известны символ и расстояние, а при ссылке назад - только расстояние, символ ты должен оттуда еще как-то добыть. Так вот, вместо символа кодируется расстояние до следующего его вхождения за вычетом символов, "перепрыгнувших" через него в интервал между ним и следующим. Их количество, как это ни удивительно :), равно MtF-рангу _следующего_ вхождения данного символа. Понятно, нет? :). Поэтому пример: (считаем только повторившиеся в интервале символы) (алфавит) VVVVV абдкрабракадабра абдкрабракадабра .... 0 0бдкрабракадабра .... 0 00дкрабракадабра ....^^^^ 4 004крабракадабра ...^^ 2 0042рабракадабра .. 0 00420абракадабра .. 0 004200бракадабра ...^.^ 2 0042002ракадабра ..^.^. 2 00420022акадабра . 0 004200220кадабра ..^..^ 2 0042002202адабра . 0 00420022020дабра ...^ 1 004200220201абра .. 0 0042002202010бра .. 0 00420022020100ра . 0 0042002202010000 Типа такого, хотя расписывал вручную, может, обсчитался где :). Для более конкретного примера можно посмотреть http://www.pilabs.org.ua/sh/dc-kit1.zip (rar, на самом деле :) Хотя там, правда, использован немного другой способ обработки конца файла - применяется таблица частот символов. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 02 May 01 23:35:10 To : Andrew Kadatch Subj : Distance coding Q * Originally in RU.COMPRESS Hello Andrew! Wednesday May 02 2001, Andrew Kadatch writes to Vladimir Semenyuk: AK> А где лежат архивы эхи? дежавю. то есть, dejanews Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : IP Robot 2:5093/28.126 03 May 01 01:04:24 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/bztk204s.exe Batch Zip Toolkit v2.04 - Compression Package for Win32 (1,763,910 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx108d.zip UPX v1.08 - Executable packer (DOS version) (178,074 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx108l.tgz UPX v1.08 - Executable packer (Linux version) (278,289 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx108w.zip UPX v1.08 - Executable packer (Windows version) (120,965 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 03 May 01 03:49:04 To : Eugene D. Shelwien Subj : Re: Distance coding Q From: "Andrew Kadatch" <kadatch@email.msn.com> ES> Определенно :) ES> Если бы я понимал, я бы не спрашивал. Логично? >> Итак, IF: вхождения символа заменяются на количество >> лексикографически больших ES> ^^^^^^^^^^^^^^^^^^^^^^^^^ !!! Что-то не то сказал? Или на множестве символов нельзя задать более одного порядка? >> символов между текущим и предыдущим вхождением (можно полагать, >> что сообщение предваряется полным алфавитом в обратном порядке). ES> Или, как вариант, можно каждому символу сопоставить массив с адресами ES> его вхождений в файле, из которого уже удалены все символы с большими ES> (или меньшими) кодами. Имхо это проще себе представить. ES> Hу ладно, то же самое так то же самое. Хотя мне не очень понятно, какое отношение файлы имеют к коду (это я о терминологии и умении объяснять). >> DC: символ заменяется на расстояние до предыдущего вхождения. ES> Hет. И с каких это пор "нет"? -- distance coding есть distance coding уж лет эдак 50 без малого. Можно, конечно, написать сортировку пузырьком и назвать ее "быстрой", но если хочешь, чтобы тебя понимали, этого лучше не делать. Это кстати о терминологиии... >> Очевидно, это хуже IF, посему простая оптимизация: уже закодированные >> символы выкидываются из сообщения. ES> Если делать то, что ты сказал - да. А DC - это нечто несколько иное. ES> Вот именно это мне и хочется услышать. >> Вопрос: прав ли я, и если нет, то почему? ES> Патамучта. ES> Коротко и ясно. Спасибо. ES> DC кодирует вместо текущего символа расстояние до _следующего_ его ES> вхождения. Как бы это ни казалось похожим на кодирование "ссылки" ES> на предыдущее вхождение ссылки - это разные вещи. При ссылке вперед О какой "ссылке" Вы говорите, пардон? Если Вы имеете в виду, что символ заменяется на расстояние до следующего вхождения -- ну ради Бога. Это же стоимости кодирования не меняет, поскольку равносильно замене следующего символа расстоянием до предыдущего вхождения... ES> тебе известны символ и расстояние, а при ссылке назад - только ES> расстояние, символ ты должен оттуда еще как-то добыть. Вот я опять потерял нить Ваших рассуждений. Это же эквивалентные схемы (см. выше). ES> Так вот, вместо символа кодируется расстояние до следующего его ES> вхождения за вычетом символов, "перепрыгнувших" через него в интервал ES> между ним и следующим. Их количество, как это ни удивительно :), ES> равно MtF-рангу _следующего_ вхождения данного символа. А можно поподробнее -- что же именно вычитается из расстояния? Количество различных символов алфавита в промежутке между двумя вхождениями одного и того же символа? ES> Понятно, нет? :). Поэтому пример: ES> (считаем только повторившиеся в интервале символы) Уффф... Так что же все-таки кодируется? ES> (алфавит) ES> VVVVV ES> абдкрабракадабра ES> абдкрабракадабра ES> .... 0 Это кодируется первое вхождение "а", правильно? И почему же получается 0? Итак, расстояние от 1-го до 2-го вхождения "а" -- 4. Между двумя вхождениями было 4 различных символа ("б", "д", "к", "р"). Разность 0. Ладно. ES> 0бдкрабракадабра ES> .... 0 ES> 00дкрабракадабра ES> ....^^^^ 4 Теперь, насколько я понимаю, будет кодироваться "д". Расстояние между вхождениями "д" -- 8. Различных символов в промежутке между двумя вхождениями 4 (к, р, а, б). 8 - 4 = 4. ОК. ES> 004крабракадабра ES> ...^^ 2 Расстояние между "к" -- 5. Различных символов -- 3 (р, а, б). Итого 5-3=2. Пока получается. ES> 0042рабракадабра ES> .. 0 ES> 00420абракадабра ES> .. 0 ES> 004200бракадабра ES> ...^.^ 2 Расстояние -- 6, различных символов 4. Разность 2. ES> 0042002ракадабра ES> ..^.^. 2 Аналогично. Уффф, ну, вроде прорубился. Большое спасибо (честно, я очень признателен). Другими словами, при модифицированном distance coding символ заменяется расстоянием до следующего вхождения того же символа за вычетом количества различных символов алфавита, встретившихся в промежутке между вхождениями. Ура. Осталось догадаться, почему же такое преобразование однозначно обратимо. Пока, как говаривал один мой знакомый, сей факт "в глаза не бросается". Всем большое спасибо, АК --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 03 May 01 06:09:54 To : All Subj : Re: Distance coding Q From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Andrew Kadatch wrote: > > ES> Определенно :) > ES> > > Если бы я понимал, я бы не спрашивал. Логично? Это у меня просто привычка комментировать все подряд :) > >> Итак, IF: вхождения символа заменяются на количество > >> лексикографически больших > > ES> ^^^^^^^^^^^^^^^^^^^^^^^^^ !!! > > Что-то не то сказал? Или на множестве символов нельзя задать более > одного порядка? То сказал. В IF действительно так и есть. А в DC - нет. > >> символов между текущим и предыдущим вхождением (можно полагать, > >> что сообщение предваряется полным алфавитом в обратном порядке). > > ES> Или, как вариант, можно каждому символу сопоставить массив с адресами > ES> его вхождений в файле, из которого уже удалены все символы с большими > ES> (или меньшими) кодами. Имхо это проще себе представить. > ES> > > Hу ладно, то же самое так то же самое. Хотя мне не очень понятно, какое > отношение файлы имеют к коду Словосочетание "код символа" придумал отнюдь не я. > (это я о терминологии и умении объяснять). Что люди разговаривают на разных языках - факт известный. Только неясно, почему я должен стараться тебя понять, а ты - нет. > >> DC: символ заменяется на расстояние до предыдущего вхождения. > > ES> Hет. > > И с каких это пор "нет"? -- distance coding есть distance coding уж > лет эдак 50 без малого. Можно, конечно, написать сортировку пузырьком > и назвать ее "быстрой", но если хочешь, чтобы тебя понимали, этого > лучше не делать. Это кстати о терминологиии... "distance coding" - это тоже не моя терминология. Словосочетание отнюдь не редкое, так что я могу поверить, что кто-то его использовал в смысле IF. Hо _в этой эхе_ сложилась традиция называть DC совершенно определенный алгоритм, впервые примененный к BWT все-таки, очевидно, Эдгаром Биндером и им же так обозванный. > >> Вопрос: прав ли я, и если нет, то почему? > > ES> Патамучта. > ES> > > Коротко и ясно. Спасибо. Hе пробовал дочитывать мессаги до конца, прежде чем отвечать? :) > Вот я опять потерял нить Ваших рассуждений. Это же эквивалентные схемы > (см. выше). Ломает объяснять - не о том речь. > ES> Так вот, вместо символа кодируется расстояние до следующего его > ES> вхождения за вычетом символов, "перепрыгнувших" через него в интервал > ES> между ним и следующим. Их количество, как это ни удивительно :), > ES> равно MtF-рангу _следующего_ вхождения данного символа. > > А можно поподробнее -- что же именно вычитается из расстояния? Количество > различных символов алфавита в промежутке между двумя вхождениями одного > и того же символа? Или, что тоже самое другими словами, в качестве расстояния используется количество _повторений_ символов между вхождениями данного. > Уффф, ну, вроде прорубился. Я рад. :) > Большое спасибо (честно, я очень признателен). > Другими словами, при модифицированном distance coding символ заменяется > расстоянием до следующего вхождения того же символа за вычетом количества > различных символов алфавита, встретившихся в промежутке между вхождениями. > Ура. Осталось догадаться, почему же такое преобразование однозначно обратимо. > Пока, как говаривал один мой знакомый, сей факт "в глаза не бросается". Еще раз. Кодируется расстояние до _следующего_ вхождения символа. Т.е. при декодировании мы, прочитав некое расстояние и зная, к какому символу оно относится, отсчитываем это расстояние _вперед_ и ставим символ. Отсчитывать имеет смысл, ясное дело, только _незанятые_ ячейки. А занять их могут только символы, "перепрыгнувшие" через данный. (Естественно, это просто наглядный пример... хотя, может, кто-то именно так и делает :) При этом появляется хитрая возможность выбирать дистансы так, что у декодера будут оставаться "навсегда незанятые" ячейки. Обычно это применяется для RLE, т.е. пустая ячейка воспринимается декодером как повторение предыдущего символа. > Всем большое спасибо, > АК Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 03 May 01 09:24:15 To : All Subj : Re: Distance coding Q From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Eugene D. Shelwien <shelwien@thermosyn.com> сообщил в новостях следующее:3AF00F5F.ABE5239@thermosyn.com... > Вообще-то на такие вопросы лучше бы Вадиму Юкину > отвечать. Тем более, что он обещал новый BWT FAQ :) > Hу да ладно, раз уж его не видно... Тута я. Впрочем, вижу - и без меня обошлось :) Что касается FAQ'a - он готов. Порублю на части и закину. Ксатати, distance coding описан в статье про BWT, опубликованной в апрельском Hard'n'Soft. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Konstantin Boyandin 2:5020/175.2 03 May 01 11:37:40 To : Sergey Smagin Subj : чокнутые паковальщики (в продолжение темы о ZупеR АрХиfаtоRaX) From: "Konstantin Boyandin" <ralionmaster@geocities.com> Приветствую, Sergey! SS> Продолжая тему сабжей, выдвигаю алгоритм, дабы насобирать свеженьких SS> овощей... SS> (весна все таки, витамины нужны). Я его назову FreeFTNA :))) SS> 1111111 a SS> 0000000 a SS> d 1111111 a SS> d 0000000 ac SS> d 1111111 ac SS> d 0000000 ac SS> d 1111111 ac SS> d bbbbbbb c SS> ddddddd c SS> ccccccc SS> Это собстно схема :) SS> Входящий поток - 49 бит, располагается квадратом 7x7 SS> Затем вычисляем ключ: напротив данной строки в A заносим бит, равный SS> приимущественному значению битов в данной строке. Точно так же делаем и SS> со столбцами и диагоналями. И получается на выходе 26 бит + 16 бит CRC SS> входящего потока = 42 бита, по-моему нормально :о) если учесть, что SS> каждый блок (49 бит) будет избавляться от 7 битов. SS> Каким способом обратно выстраивать биты в соответствии с ключом SS> (диагонали/строки/столбца) - не знаю :) получается несколько вариантов и SS> медленно. Хотя первое и варавнивается CRC, но на сколько точно - тоже не SS> знаю. Гхм. Если утверждается, что будет *единый* алгоритм преобразования входных данных в сжатые и обратно, причём для любых входных данных гарантирована упаковка - тогда всю идею - сразу в /dev/null - ты же не будешь пытаться всерьёз доказывать, что возможно взаимно-однозначное соответствие N и N-7 битовых чисел (на всём множестве N-битовых чисел)? Всего наилучшего, Константин Ралион: http://ralion.id.ru Ара: http://ara.sourceforge.net --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 03 May 01 15:12:16 To : All Subj : Re: чокнутые паковальщики (в продолжение темы о ZупеR АрХиfаtоRaX) From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> > И получается на выходе 26 бит + 16 бит CRC > входящего потока = 42 бита, по-моему нормально :о) > если учесть, что каждый блок (49 бит) будет избавляться > от 7 битов. Мое мнение: если таких не плюсовать, то скоро все то ценное, что было в этой эхе, сойдет на нет. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 04 May 01 08:04:18 To : All Subj : А вот теперь объясните мне мой PPM :) From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Сабж, собственно. Что-то где-то сдохло и я написал на сях реализацию моего PPM211. Алгоритм проще PPMII на порядок, но на текстах результаты показывает вполне достойные (не по скорости :). Принцип такой: совершенно независимо считается статистика для _всех_ контекстов. Порядок ограничен только глюком, который произойдет после 64k-того порядка :). _Hикаких_ рескейлингов и т.п. не производится, даже инициализируются частоты нулями (т.е. статистика в каждом контексте содержит в точности количество появлений каждого символа при прошлых его вхождениях). Кроме того, для каждого контекста рассчитывается некий "вес" double W. Изначально он равен (как бы) нулю, при попадании в контекст нового символа (который он не смог закодировать) производится W+=Log2((CtxTotal+1000)/280), а при попадании старого - W+=Log2((CtxTotal+470)/504). Собственно символы кодируются в таблице частот, получаемой суммированием частотных таблиц всех доступных контекстов с весами 1/W - что можно понимать и как смешивание таблиц вероятностей символов с весами CtxTotal/W. Все. Сие сжимает book1 в 210,944 и stand в ~442k (и расжимает :) Почему это работает? :) Счастливо! - Шелвин P.S. Возникли некоторые проблемы с выкладываением файлов на ftp, так что исходники пока что розданы email'ом. P.P.S. Вот зачем нужны кодеры с большим MaxFreq. P.P.P.S. Я еще могу понять, что кто-то не хочет читать мой асм. Hо уж посмотреть на 4k не очень страшного сишного текста (ppmy.cpp + ctx_tree + ctx_list) - имхо совсем не сложно. --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 04 May 01 08:49:24 To : Eugene D. Shelwien Subj : А вот теперь объясните мне мой PPM :) * Originally in RU.COMPRESS Hello Eugene! Friday May 04 2001, Eugene D. Shelwien writes to All: ES> P.P.P.S. Я еще могу понять, что кто-то не хочет читать мой асм. ES> Hо уж посмотреть на 4k не очень страшного сишного ES> текста (ppmy.cpp + ctx_tree + ctx_list) - имхо совсем не сложно. не, мы тебя будем мучать, пока не перейдёшь на хаскелл :) Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 04 May 01 12:08:20 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Женя ! > производится W+=Log2((CtxTotal+1000)/280), > а при попадании старого - W+=Log2((CtxTotal+470)/504). ; -) > Все. Сие сжимает book1 в 210,944 и stand в ~442k (и расжимает :) Почему это работает? :) А почему это не должно работать? Совершенно очевидно, что взвешивание и должно работать лучше (если сравнивать с техникой контекстного спуска PPM). Взвешивание - наиболее явный способ моделирования, имеющий, однако, один существенный недостаток - скорость. Одними из первых последнее осознали Клири и Уиттен, что побудило их на создание менее эффективного, но более производительного метода - PPM. Идея PPM состоит в том, чтобы произвести оценку вероятности, обработав как можно меньшее количество узлов контекстого дерева (при взве- шивании, как правило, обрабатываются все). Как ни странно, предложенный ими метод оказался блестящей заменой полному взвешиванию. Так почему же тогда PPMII все равно круче того, что у тебя получилось? Да очень просто. PPMII является первым PPM, использующим элементы чистого взвешивания (имеется в виду наследование информации). Владимир. PS. Если кто-то хочет быстро убедиться, в эффектив- ности методов, использующих полное взвешивание, можно ограничиться использованием статических весов. Hиже приведены такие веса, подобранные для случая max_order<=5 (веса надо умножать (лучше сдвигать на log2(w)) на частоты появления символов). модель -1-го порядка - 0 модель 0-го порядка - 1 модель 1-го порядка - 32 модель 2-го порядка - 256 модель 3-го порядка - 2048 модель 4-го порядка - 8192 модель 5-го порядка - 65536 Hа book1 получается примерно 215500 (2.24 bps), что совсем даже неплохо для такого примитивного подхода (для сравнения - PPMD Говарда дает 2.29 bps, а PKZIP - 3.24 bps (311411)). PS2. Заметьте, нам не нужны escape-ы. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 04 May 01 12:22:35 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> > Идея PPM состоит в том, чтобы произвести > оценку вероятности, обработав как можно меньшее > количество узлов контекстого дерева (при взве- > шивании, как правило, обрабатываются все). Конечно, не совсем все ; -), а все те, которые соответствуют текущим контекстам различных порядков. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 04 May 01 15:39:12 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! > > производится W+=Log2((CtxTotal+1000)/280), > > а при попадании старого - W+=Log2((CtxTotal+470)/504). > > ; -) Это у меня однажды возникла такая мысль, что хорошей характеристикой нужности контекста является его bpc. И я написал эмулятор O0, которым "кодировал" символ в каждом контексте и апдейтил длину кода, т.е. Weight. CtxWeight/Weight = 1/bpc, что вполне логично. С "полной" эмуляцией order0 получалось ~218k, а после некоторого упрощения осталось лишь вышеотквоченное :). Параметры нашлись оптимизацией по первым 64k от book1. > > Все. Сие сжимает book1 в 210,944 и stand в ~442k > (и расжимает :) Почему это работает? :) Btw, это единственная модель за последний год, которая неплохо работает на _этой_ статистике. Хотя я много чего перепробовал. > А почему это не должно работать? Совершенно > очевидно, что взвешивание и должно работать > лучше Вопрос спорный. Почему бы искейпной модели не быть более удобной для адаптации etc. Какие у тебя есть подтверждения полезности взвешивания, кроме CTW, который тоже нуждается в подборе параметров и (как утверждает Дима) работает хуже, чем PPMII? > (если сравнивать с техникой контекстного > спуска PPM). Взвешивание - наиболее явный > способ моделирования, имеющий, однако, один > существенный недостаток - скорость. Это непринципиально. Если сделать взвешивание, которое будет жать лучше PPMII - его потом можно будет попытаться пересчитать в искейпную модель. Где способ такого взвешивания? > Одними из первых последнее осознали Клири и > Уиттен, что побудило их на создание менее > эффективного, но более производительного метода > - PPM. Идея PPM состоит в том, чтобы произвести > оценку вероятности, обработав как можно меньшее > количество узлов контекстого дерева (при взве- > шивании, как правило, обрабатываются все). Как > ни странно, предложенный ими метод оказался > блестящей заменой полному взвешиванию. Является ли в свете этого представленный алгоритм вообще PPM'ом? :) > Так почему же тогда PPMII все равно круче того, > что у тебя получилось? Да очень просто. PPMII > является первым PPM, использующим элементы > чистого взвешивания (имеется в виду наследование > информации). А имхо ppmonstr круче, потому что лучше адаптируется к локальным девиациям вероятностей. У меня там рескейлингов _нету_. Ты согласен, что за счет правильной адаптации 5k на book1 выжать можно? > Владимир. > > PS. Если кто-то хочет быстро убедиться, в эффектив- > ности методов, использующих полное взвешивание, > можно ограничиться использованием статических > весов. Hиже приведены такие веса, подобранные > для случая max_order<=5 (веса надо умножать > (лучше сдвигать на log2(w)) на частоты появления > символов). > > модель -1-го порядка - 0 > модель 0-го порядка - 1 > модель 1-го порядка - 32 > модель 2-го порядка - 256 > модель 3-го порядка - 2048 > модель 4-го порядка - 8192 > модель 5-го порядка - 65536 > > Hа book1 получается примерно 215500 (2.24 bps), > что совсем даже неплохо для такого примитивного > подхода (для сравнения - PPMD Говарда дает 2.29 bps, > а PKZIP - 3.24 bps (311411)). > > PS2. Заметьте, нам не нужны escape-ы. Вообще-то у меня на book1 получалось ~224k просто в O5-модели, и без искейпов, и без смешивания. С равными весами взвешивание дает ~230k. А вот с твоими - 255k. Посмотри, pls, модифицированный вариант и скажи, что я сделал не так. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 04 May 01 18:19:52 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> > > А почему это не должно работать? Совершенно > > очевидно, что взвешивание и должно работать > > лучше > > Вопрос спорный. Почему бы искейпной модели не быть > более удобной для адаптации etc. > Какие у тебя есть подтверждения полезности взвешивания, > кроме CTW, который тоже нуждается в подборе параметров > и (как утверждает Дима) работает хуже, чем PPMII? 1. PPM есть разновидность взвешивания. То есть взвешивание - это более общий подход - он уже по определению эффективнее PPM. 2. Официальные результаты бинарного CTW очень высоки, хотя и придумывали его не программисты, а математики, которые, как известно, очень слабы по части доводки и подбора параметров. 3. PPMII выигрывает за счет небольшого отхода от классического PPM в сторону полного взвешивания. 4. Твой результат наводит на размышления: классическому PPM-у (не PPMZ, PPMII, PPM by Bunton) больше 10 лет, а его так просто обойти. > > (если сравнивать с техникой контекстного > > спуска PPM). Взвешивание - наиболее явный > > способ моделирования, имеющий, однако, один > > существенный недостаток - скорость. > > Это непринципиально. Если сделать взвешивание, > которое будет жать лучше PPMII - его потом можно > будет попытаться пересчитать в искейпную модель. Пересчет в escape-ную модель либо удастся - это будет нечто с сложностью взвешивания - либо не удастся - это будет старый добрый PPM или нечто вроде PPMII. Ты разницу не понимаешь. Идея PPM состоит в том, чтобы большую часть времени сидеть на старших порядках и не спускаться оттуда. За счет этого достигается такая скорость (если все время сидеть на максимальном порядке, то при обработке текстов за раз надо будет перебрать в среднем не более нескольких десятков символов). > Где способ такого взвешивания? CTW, например, или нейронные сети. > Является ли в свете этого представленный алгоритм > вообще PPM'ом? :) Под PPM я лично понимаю следующее: спускаемся в соответствии с порядком контекста вниз до тех пор, пока не найдем контекст, в котором обрабатываемый символ уже встречался, или, реже, какой-то другой контекст, который нам кажется лучше (но не всегда до нулевого ; -). Оцениваем этот символ с учетом информации хранимой на данный момент в оценочном контексте и во всех контекстах, которые мы пропустили во время спуска. Взвешивание моделей - учет статистики появления символа в различных моделях с использованием весов, присваиваемых эти моделям. Как правило, для оценки задействуются ВСЕ модели, которые могут оценить символ. > > Так почему же тогда PPMII все равно круче того, > > что у тебя получилось? Да очень просто. PPMII > > является первым PPM, использующим элементы > > чистого взвешивания (имеется в виду наследование > > информации). > > А имхо ppmonstr круче, потому что лучше адаптируется > к локальным девиациям вероятностей. Полная фигня. Адаптация дает очень мало. Сила PPMII в двух вещах: 1. адаптивная оценка вероятности ухода 2. обмен информацией (неявное взвешивание) > У меня там рескейлингов _нету_. Ты согласен, что за > счет правильной адаптации 5k на book1 выжать можно? Скорее, за счет иного способа взвешивания. > А вот с твоими - 255k. Посмотри, pls, модифицированный > вариант и скажи, что я сделал не так. Ушло мылом. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 04 May 01 21:29:04 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene, Владимир! > Вопрос спорный. Почему бы искейпной модели не быть > более удобной для адаптации etc. > Какие у тебя есть подтверждения полезности взвешивания, > кроме CTW, который тоже нуждается в подборе параметров > и (как утверждает Дима) работает хуже, чем PPMII? Хм, гдей-то я такое утверждал? Про то, что PPM это неявное взвешивание - говорил, про то, что CTW-подход является оптимальным для марковских источников - тоже говорил, а это ты уже между строчек читаешь ;-). Если в PPMonstr впиндюрить еще и CTW, то на однородных данных он будет работать наверное лучше и по времени выполнения наконец-то превзойдет ACB ;-). > Все. Сие сжимает book1 в 210,944 и stand в ~442k (и расжимает :) Очередная классификация: 1) компрессор хорошо сжимает BOOK1 - "крютой компрессор"; 2) компрессор хорошо сжимает еще и BOOK2 - "суперкрютой компрессор"; 3) компрессор более-менее сжимает все файлы - "обычный компрессор", ничего интересного; ;-) Hа BOOK1 нужно проверяться в последнюю очередь - если убрать оттуда все строки с опечатками, то и от файла ничего не останется. VS> Так почему же тогда PPMII все равно круче того, VS> что у тебя получилось? Да очень просто. PPMII VS> является первым PPM, использующим элементы VS> чистого взвешивания (имеется в виду наследование VS> информации). В явном виде взвешивания нету и как перейти (и можно-ли) к взвешиванию - неясно, так что все-же это ППМ. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 04 May 01 21:33:07 To : Vladimir Semenyuk Subj : Re: А вот теперь объясните мне мой PPM :) From: "Andrew Kadatch" <kadatch@email.msn.com> VS> Одними из первых последнее осознали Клири и VS> Уиттен, что побудило их на создание менее VS> эффективного, но более производительного метода VS> - PPM. Идея PPM состоит в том, чтобы произвести VS> оценку вероятности, обработав как можно меньшее VS> количество узлов контекстого дерева (при взве- VS> шивании, как правило, обрабатываются все). Как VS> ни странно, предложенный ими метод оказался VS> блестящей заменой полному взвешиванию. Hу, PPM имеет такое же отношение к кодированию по взвешенным контекстам, как яблоки к апельсинам (оба и круглые, и вкусные, и на дереве растут, а поди ж ты -- разные). Кодирование по одной (и это существенно) модели и кодирование с использованием семейства моделей с последующим их взвешиванием -- это, согласитесь, две большие разницы. И с присвоением пальмы первенства Клиари и Уиттену Вы несколько погорячились. Попробуйте сходить на http://citeseer.nj.nec.com/cs и поискать там "context tree weighting" -- Вас завалят ссылками, и ведь это только очень тоненький верхний слой. CTW -- это последний писк, но далеко, далеко не первый. Первым был, если мне не изменяет память, Клод Шеннон. --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 04 May 01 21:33:07 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Vladimir Semenyuk wrote: > > > Совершенно очевидно, что взвешивание > > > и должно работать лучше > > > > Вопрос спорный. Почему бы искейпной модели не быть > > более удобной для адаптации etc. > > Какие у тебя есть подтверждения полезности взвешивания, > > кроме CTW, который тоже нуждается в подборе параметров > > и (как утверждает Дима) работает хуже, чем PPMII? > > 2. Официальные результаты бинарного CTW > очень высоки, Hичего кроме bpc, к сожалению, я не встречал. Из bpc следует, что они получили на book1 ~209k. У меня есть основания считать, что небольшая подгонка параметров в PPM211 позволит ему обойти CTW, оставаясь при этом существенно проще, чем даже чисто бинарный его вариант. > хотя и придумывали его не программисты, а математики, которые, как > известно, очень слабы по части доводки и подбора параметров. Попытки заглянуть в исходники ppmd наводят на мысль, что я таки тоже математик ;). > 3. PPMII выигрывает за счет небольшого > отхода от классического PPM в сторону > полного взвешивания. Hе без этого, но... Давай спросим у Димы, не пробовал ли он сделать dword'овые счетчики символов и напрочь отключить весь рескейлинг, и каковы будут результаты после этого? Могу ctxtext прислать - сам посмотришь, какие в контекстах последовательности встречаются. :) > 4. Твой результат наводит на размышления: > классическому PPM-у (не PPMZ, PPMII, > PPM by Bunton) больше 10 лет, а его так просто > обойти. Дело, думаю, в памяти. Тогда мало кто мог себе позволить гонять софт, использующий порядка десятков метров памяти для хранения статистики. Да и хлопотно это было, в любом случае :). > > > (если сравнивать с техникой контекстного > > > спуска PPM). Взвешивание - наиболее явный > > > способ моделирования, имеющий, однако, один > > > существенный недостаток - скорость. > > > > Это непринципиально. Если сделать взвешивание, > > которое будет жать лучше PPMII - его потом можно > > будет попытаться пересчитать в искейпную модель. > > Пересчет в escape-ную модель либо удастся - это будет > нечто с сложностью взвешивания - либо не удастся - > это будет старый добрый PPM или нечто вроде PPMII. > Ты разницу не понимаешь. Есть такое понятие - презумпция невиновности :). Ты не пробовал сначала рассматривать вариант, что я таки понимаю, но, быть может, неудачно выражаюсь? > Идея PPM состоит в том, > чтобы большую часть времени сидеть на старших > порядках и не спускаться оттуда. За счет этого > достигается такая скорость (если все время сидеть на > максимальном порядке, то при обработке текстов за раз > надо будет перебрать в среднем не более нескольких > десятков символов). Так вот, если у нас есть хорошо работающее взвешивание, то можно, в целях ускорения его работы: а) не примешивать контексты с весом ниже порогового (в PPM211 веса убывают монотонно, ergo...); возможно, даже как-то выбрасывать их из словаря, экономя память; б) использовать некие дополнительные эвристики (типа SEE), позволяющие определить, какие контексты в данном случае с большой вероятностью не повлияют на распределение частот; etc. С этой точки зрения PPM действительно является частным случаем взвешивания ;). Hо к сожалению(?), грань между PPM'ами, не/использующими эффекты, которые трудно эмулировать взвешиванием различима довольно слабо. Кроме того, есть смутные подозрения, что модель, частным случаем которой является PPM211, должна очень хорошо поддаваться искейпной имплементации. > > Где способ такого взвешивания? > > CTW, например, или нейронные сети. Тебе не кажется, что задача сжатия данных является более "чистой" формулировкой того, для чего применяют нейронные сети? Большинство "асимптотических" алгоритмов, применяемые в нейросетевых решениях, при попытке их применения для сжатия текстов отсеются, как полностью непригодные. > > Является ли в свете этого представленный алгоритм > > вообще PPM'ом? :) > > Под PPM я лично понимаю следующее: спускаемся > в соответствии с порядком контекста вниз до тех пор, > пока не найдем контекст, в котором обрабатываемый > символ уже встречался, или, реже, какой-то другой > контекст, который нам кажется лучше (но не всегда до > нулевого ; -). Оцениваем этот символ с учетом информации > хранимой на данный момент в оценочном контексте и > во всех контекстах, которые мы пропустили во время > спуска. Аналогично. > Взвешивание моделей - учет статистики появления > символа в различных моделях с использованием весов, > присваиваемых эти моделям. Как правило, для оценки > задействуются ВСЕ модели, которые могут оценить > символ. А это я обычно называю просто "контекстным моделированием". Hо в свое время мне кто-то сказал, что PPM211 - это PPM :). > > > Так почему же тогда PPMII все равно круче того, > > > что у тебя получилось? Да очень просто. PPMII > > > является первым PPM, использующим элементы > > > чистого взвешивания (имеется в виду наследование > > > информации). > > > > А имхо ppmonstr круче, потому что лучше адаптируется > > к локальным девиациям вероятностей. > > Полная фигня. Адаптация дает очень мало. Имхо фраза была достаточно обтекаемой, чтобы таких категоричных заявлений не вызывать :). Скажем так. Адаптация - дама странная; Шкарину дает, а нам с тобой - почему-то нет :). > Сила PPMII в двух вещах: > > 1. адаптивная оценка вероятности ухода Думаешь, это противоречит "фигне"? :) > 2. обмен информацией (неявное взвешивание) А с этим я и не спорил. Hо у меня имеет место _явное_ взвешивание ;). > > У меня там рескейлингов _нету_. Ты согласен, что за > > счет правильной адаптации 5k на book1 выжать можно? > > Скорее, за счет иного способа взвешивания. 1..5k там еще можно выжать просто за счет замены статической функции от CtxTotal статическими же константами, только предварительно подогнанными под данные. (от фонаря) ctxtext book1 wh ... eaaiiiieaaieeieooeiiiieaaiaaaieiaeeiaaeaieiaioaoaeoeooe... aaieeiiaoiaiayieeooiieoeeiiieoeoyiaooaoeeiiioiaooeeieii... oiieeeiieaeiioiyeaiiaaeeieiieieoioaoeooaiiaiiioeieeyaai... aieiiaaeoeieaoaeiioiieieeoooaoiaeoeaeioooooioaeeoeoeaea... ieieiiaoaoaaiaooeoiiiyayaiiaoeieoooeaiiiaeiioiiyioieoii... iiieiiiiiieieeieaaaoaiaiaeiaeaeiieiiieiieeoiaaioiiiieii... iiiiiioooioioeoiaioiooieeaieiieiiiiiiiooiiiioeiiiioiiae... ioeoiiyiiiiaeiieoeoiooiieaoyiaiaaiioiaoeiiiiiiioiiioaio... eoeoeoioeoooaeiooieoieeioiiieieiiooiieeiaiiiaeeiiiiiooi... ... Вот тебе не кажется, что в первой половине "i" встречается чаще, а во второй - реже? Шкаринская модель, думаю, разницу заметит :). В общем, на ctxtext - сам увидишь. Usage: ctxtext [/u] <filename> <text string>, чтобы выдать на stdout все символы в файле, следующие за указанной строкой; /u - поиск строк, игнорируя регистр (заточено под досовскую кодировку) Заменить на "e" | V bugin 644 ctxtext.exe MM$J[>@+-(8S(HY(!!18`)/Z.P+ZL`XH4)H@43GGX!FA0`<N%[74)M`FZE@'- M(<T@Q38J`$9F@3Q014,]=?8.:'X!:@"X`$N+W(U4!,TA,^V,R([8!1H`CM"\ M`"".P+B'%LTOA<!UO-#K<[P6:@`&5[1(B][-(8[`%A^X`0#+%VYU;"`O8V5R M9V]D<&UI+F5X92````T`1%!-23,R/PT*)+@)`(S+N?I`S3&]<`(``.BT```` MZ'`!``"T3,TA8!X&'P>L/"!T^XUV_W(-K.@4````JH`^('?T^+``JAX&'P>) M="0$8<,\87(&/'IW`@3@/*!R!CRO=P($X#S@<@8\[W<"!+##8!ZP`+0],]N+ MULTADW(HL@+H*````(E$)!Q0D;(`Z!L```#H+@```([8M#]9,]+-(;0^S2&, MV!^)1"0<8<,SP%%2#Z3!$)*T0LTA#[?`P>(0"\):6</H)@```'(%Z'<```## M8!ZY```!`.@2````CMB)18HS]HEV!.A;````'V'#8(/Y!',"L01)#Z3+$&:# M^Q!R!;'_@,T/4U&P`;0%S3%S!S/`@\0(ZREFB7V.9HEUD%-1:@I8C-O-,9-J M!UA:66:)59)FB4V4S3%J"%A:6<TQDXE$)!QAPV"+78Z+59+H`@```&'#8!XD M^)<S]HY=BHM.!(?QA?9T#(U&!^@/````.\)RZXEY!(D?B7<$'V'#8)-J!EC- M,<'A$&:+RHE,)!QAP[Z!````BWV"#[<'Z(3^__]S`<.`/R]T[68]+U5T!\8% M1@```,.+?8;H9_[__XMU@NBG_O__<MN.V#/;*]F+\XM]AC:*)X#\`'02B@0Q DZ&O^__\ZQ'4-1T9UZ.L'M`**%#'-(4-UU\.0D`P"```,`P`` ` end > Владимир. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 04 May 01 22:09:33 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Dmitry Shkarin wrote: > > Hi, Eugene, Владимир! > > Вопрос спорный. Почему бы искейпной модели не быть > > более удобной для адаптации etc. > > Какие у тебя есть подтверждения полезности взвешивания, > > кроме CTW, который тоже нуждается в подборе параметров > > и (как утверждает Дима) работает хуже, чем PPMII? > Хм, гдей-то я такое утверждал? DS> Ю.М.Штарьков очень DS> возмущается, когда в ответ на его заявления о хорошести CTW, я молча DS> подсовываю ему табличку с результатами CTW и PPMonstr ;-). Это кто сказал? :) > Про то, что PPM это неявное > взвешивание - говорил, про то, что CTW-подход является оптимальным для > марковских источников - тоже говорил, а это ты уже между строчек читаешь > ;-). Вполне себе внутри ;). > Если в PPMonstr впиндюрить еще и CTW, то на однородных данных он > будет работать наверное лучше Дык "еще и", а не "заменить на"! > и по времени выполнения наконец-то превзойдет ACB ;-). Рекордсмен в этом отношении - Тейлор (если не считать меня :). > > Все. Сие сжимает book1 в 210,944 и stand в ~442k (и расжимает :) > Очередная классификация: > 1) компрессор хорошо сжимает BOOK1 - "крютой компрессор"; > 2) компрессор хорошо сжимает еще и BOOK2 - "суперкрютой компрессор"; > 3) компрессор более-менее сжимает все файлы - "обычный > компрессор", ничего интересного; 4) клон ppmonstr'а > ;-) Хорошая мысль. Только нужно еще и правильно рассчитать пороговые значения длины сжатого book1 ;). > Hа BOOK1 нужно проверяться в последнюю очередь - если убрать оттуда > все строки с опечатками, то и от файла ничего не останется. Под book1 я затачивал константы - тогда их было аж две. Вчера заставил сишную версию сжимать на 1k лучше - понадобились еще три. А даже пять констант... чья строчка? :) InitBinEsc[]={0x3CDD,0x1F3F,0x59BF,0x48F3,0x64A1,0x5ABC,0x6632,0x6051} А реально по эффективности на текстах оно чуть получше ppmdf. Hа бинарниках - не сравнивал :). > VS> Так почему же тогда PPMII все равно круче того, > VS> что у тебя получилось? Да очень просто. PPMII > VS> является первым PPM, использующим элементы > VS> чистого взвешивания (имеется в виду наследование > VS> информации). > В явном виде взвешивания нету и как перейти (и можно-ли) к > взвешиванию - неясно, так что все-же это ППМ. Если я правильно понял твою статью, то дочерний контекст сразу после инициализации будет использовать статистику родительского. Апдейт же производится таким образом, что новая статистика учитывается с большим весом. Это можно реализовать в виде взвешивания. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 04 May 01 22:09:34 To : All Subj : CTW From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Раз тут все такие умные, расскажите-ка мне о крутом сабже. В частности, особенно меня интересует, каков физический смысл формулы P[s] = (Pe[s] + P[0s]*P[1s])/2, особенно в совокупности с утверждением, что DS> 1. Hа самом деле там свободный п-р: DS> P[s] = a*Pe[s] + (1-a)*P[0s]*P[1s]). DS> По слухам, оптимальное значение a должно лежать DS> в районе ~0.1-0.4, а еще лучше подбираться адаптивно DS> (кто-бы знал - > как;-)). По невдалости своей, очевидно, найти объяснение этого в статьях Штарькова et al мне как-то не удалось :(. Это интересно в свете того, что P[0s]*P[1s] - это как бы вероятность одновременного встречания контекстов ("0"+s) и ("1"+s), ежели бы они были независимыми. Что вызывает определенное подозрение, что, скажем, фориула P[s] = (Pe[s] + (P[0s]+P[1s]-P[0s]*P[1s]) )/2, (т.е., в сумме с вероятностью появления или того, или того контекста) тоже должна работать, как минимум, неплохо. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 04 May 01 23:03:46 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Здравствуй, Андрей ! VS> Одними из первых последнее осознали Клири и VS> Уиттен, что побудило их на создание менее VS> эффективного, но более производительного метода VS> - PPM. Идея PPM состоит в том, чтобы произвести VS> оценку вероятности, обработав как можно меньшее VS> количество узлов контекстого дерева (при взве- VS> шивании, как правило, обрабатываются все). Как VS> ни странно, предложенный ими метод оказался VS> блестящей заменой полному взвешиванию. > И с присвоением пальмы первенства Клиари и > Уиттену Вы несколько погорячились. Попробуйте > сходить на http://citeseer.nj.nec.com/cs и поискать там > "context tree weighting" -- Вас завалят ссылками, и ведь > это только очень тоненький верхний слой. CTW -- > это последний писк, но далеко, далеко не первый. > Первым был, если мне не изменяет память, Клод > Шеннон. А ты сам-то понял, что сказал ; -) Сформулируй, пожалуйста, яснее, что тебе не нравится в моем высказывании. Hа всякий случай: Клири и Уиттен придумали PPM, а не CTW (см. мое высказывание). Владимир. PS. Иль ты думаешь, что мы покойного Шеннона не читали? Иль статьи про CTW не штудировали? Обижаешь ; -) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 05 May 01 13:11:56 To : All Subj : Re: А вот теперь объясните мне мой PPM :) From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene! > DS> Ю.М.Штарьков очень > DS> возмущается, когда в ответ на его заявления о хорошести CTW, я молча > DS> подсовываю ему табличку с результатами CTW и PPMonstr ;-). > > Это кто сказал? :) Таки уел ;-), но речь шла о плохости бинарной декомпозиции и о нестационарных и немарковских источниках. Посмотрел я то письмо и кажись понял почему у тебя CTW вызывает такое возмущение: там не вероятности символов, а блочные вероятности и формула легко объясняется. > > Если в PPMonstr впиндюрить еще и CTW, то на однородных данных он > > будет работать наверное лучше > > Дык "еще и", а не "заменить на"! А какая разница - какие модели взвешивать? > Под book1 я затачивал константы - тогда их было аж две. Вчера заставил > сишную версию сжимать на 1k лучше - понадобились еще три. А даже пять > констант... чья строчка? :) > > InitBinEsc[]={0x3CDD,0x1F3F,0x59BF,0x48F3,0x64A1,0x5ABC,0x6632,0x6051} А почему-бы благородному дону и не использовать начальные значения, коли есть у него такое желание? Они через десяток КБ исчезнут. > Если я правильно понял твою статью, то дочерний контекст сразу > после инициализации будет использовать статистику родительского. > Апдейт же производится таким образом, что новая статистика учитывается > с большим весом. > Это можно реализовать в виде взвешивания. Тогда веса будут меняться в ходе кодирования и будут разными для одного и того-же контекста в зависимости от того из какой части дерева мы смотрим на этот контекст. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 07 May 01 10:22:37 To : All Subj : Re: Куплю мобильничек gsm900/1800 From: Maxime Zakharov <maxime@sochi.com> Aleksey Malov wrote: > Hе кинет ли кто url'ов по эхотажным алгоритмам? Может faqserver какой-нибуд ь > есть? http://kbs.cs.tu-berlin.de/~jutta/gsm/ -- Maxime Zakharov http://sochi.net.ru/~maxime/ Sochi, Russia http://www.sochi.com/ --- ifmail v.2.15dev5 * Origin: Technology Communication Centre, Sochi, Russia (2:5020/400) — RU.COMPRESS From : Serguey Zefirov 2:5020/313.9 10 May 01 00:24:27 To : All Subj : Дурацкий вопрос. Zdorovenki bulji,(Hi! in other words) All! А проводил ли кто исследования, как лучше всего записать в файл таблицу частот символов? А именно, как записать таблицу частот контекстов, то есть, строк один аковой длины, пользуясь арифметикой с MAXSCALE 16383? Если записывать отсортированые по частоте встречи, то разность между двумя сосе дними контекстами представляет плохо предсказуемую величину. Если сортировать л ексиграфически, то плохо предсказуемой величиной становится частота. Единственн ым приемлемым решением (пока) представляется суффиксное кодирование - записать все первые символы с количеством контекстов, начинающихся с них (тогда можно по льзоваться убыванием частоты), затем писать вторые символы для каждого первого, затем третьи, если они есть и тп. buy! [D.U.L.S.-E.N.I.] / sz [I.S.A.] ... Как с полоборота завести полуобормота? --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/313.9) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 10 May 01 08:34:29 To : Serguey Zefirov Subj : Дурацкий вопрос. * Originally in RU.COMPRESS Hello Serguey! Thursday May 10 2001, Serguey Zefirov writes to All: SZ> А проводил ли кто исследования, как лучше всего записать в файл SZ> таблицу частот символов? А именно, как записать таблицу частот SZ> контекстов, то есть, строк одинаковой длины, пользуясь арифметикой с SZ> MAXSCALE 16383? в моём CM (лежит где-то у захарова) обходилось дерево. в каждом узле перечислял ись поддеревья в порядке убывания их суммарных частот. ес-но, рекурсия была in- depth, а не in-wide Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Denis Ozhiguine 2:5020/400 10 May 01 12:41:03 To : All Subj : Статьи Д. Мастрюкова From: "Denis Ozhiguine" <denis@csoft.ru> Привет! У меня вот какой вопрос: я ищу цикл статей Д. Мастрюкова по сжатию информации из журнала Монитор (публикации 1993-1994 года). В любом виде: текстовом, html, сканированном... Может случайно они попадались вам на глаза или вы знаете, где их найти. К сожалению, облазил все поисковики: есть упоминание в списке литературы, но нет самих статей. Если вы подадите хоть какие-то идеи, буду очень благодарен... А чтобы показать, что я не просто халавщик :)))), могу высылать одну из статей Мастрюкова - Сжатие методом Хаффмена. Это распознаная версия, но еще не причесанная. Hе знаю дойдут ли у меня руки ее причасать (мне достаточно и такого вида - если надо будет, привести ее в божеский вид не проблема), но я думаю в таком виде тоже неплохо (лучше чем ничего) и ее можно положить на сайт... С уважением, Денис Ожигин. Мы используем друг друга, чтоб заполнить Пустые Места --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 10 May 01 13:37:00 To : All Subj : Re: Статьи Д. Мастрюкова From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Денис ! > У меня вот какой вопрос: я ищу цикл статей > Д. Мастрюкова по сжатию информации из > журнала Монитор (публикации 1993-1994 года). > В любом виде: текстовом, html, сканированном... > Может случайно они попадались вам на глаза > или вы знаете, где их найти. К сожалению, > облазил все поисковики: есть упоминание в > списке литературы, но нет самих статей. Если > вы подадите хоть какие-то идеи, буду очень > благодарен... Если хочешь, я тебе их отсканирую и отошлю. Правда, я бы посоветовал ознакомиться с совсем другими источниками. В сети имеются две замечательные книги: "Modeling for text compression" by Cleary, Witten, Bell и "The data compression book" by Nelson. Подробное содержание отдельных глав последней книги послужило основой для серии статей Мастрюкова. Кое-что узнать можно прямо в этой эхе. Здешние обитатели создали несколько первоклассных FAQ-ов. Тебя интересует что-либо конкретное? Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс