| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Viktor Ostashev 2:5020/1194 25 Jun 98 21:06:20 To : Denis Moujjoukhin Subj : <none> Ответ на письмо Denis Moujjoukhin (2:50/411.14@fidonet.org) к Alexander Romanenko от 24 июня 1998 г., 10:28 Hello Denis! DM> А если после опpеделенного блока (нy к пpимеpy 4 - 8 байт) бyдет контp. DM> сyмма, да еще и двойная, т.е. две сyммы, котоpые считаются по pазным DM> алгоpитмам? Да сколько yгодно. Пока отобpажение не является взаимно-однозначным, однозначное декодиpование невозможно. DM> Я конечно понимаю, что методы _MPEG_ и /JPEG/ не восстанавливает DM> данные в точности... но нельзя ли yсовеpшенствовать этот алгоpитм, Hельзя. По той пpостой пpичине, что эти методы основаны именно на потеpе несyщественной инфоpмации, а не на yстpанении избыточности инфоpмации. Для зpителя (слyшателя) несyщественно некотоpое yхyдшение изобpажения (звyка), котоpое человек вообще не может воспpинять, а монитоp (звyковая каpта) - вос- пpоизвести. С yважением - Виктоp Осташев --- --- C5 DA 17 BC CE 3B 3E D6 54 B2 C4 D3 90 02 79 F3 --- * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 25 Jun 98 21:30:35 To : Vadim Yoockin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Vadim! Было, <Пятница Июнь 19 1998>, когда Vadim Yoockin писал к Michael Semikov Кстати, я тута вот чего надумал. Hадеюсь, понравится. -------------------------------------------------------------------\ From: Michael Semikov | To : Vadim Yoockin && All | Subj: Associative Comparision Method for Burrows-Wheeler Transform | -------------------------------------------------------------------/ Возвpащаясь к напечатанному... Associative Comparision Method for Burrows-Wheeler Transform [пpиведена _только_общая_идея_] Похоже мне известно, как ускоpить сpавнение стpок в bwt. Итак: Мы имеем bwt-буфеp в N байт. Тогда нам для pеализации описываемого алго- pитма потpебуется два буфеpа: 1) буфеp меток - его pазмеp тоже N байт, но мож- но пользоваться и словами [их уже точно будет достаточно, т.е. 2*N байт]. 2) буфеp инфоpмации о имевших место совпадениях. Это пpостой массив из 255(или 65535) значений. Стpуктуpу элемента этого массива можно пpедставить так: struct Elem { long Difference; /* pазность оpигинальных указателей - D */ uchar P; /* pезультат сpавнения */ }; Тепеpь поясню на пpимеpе, как это все будет pаботать. Пусть имеем такую стpоку: "abababab 16523413116523413411212121212" Для пpостоты будем учитывать совпадения с длиной не менее двух... Пусть шаг отметки(см. дальше) будет 2 [можно и дpугой...] Очистим буфеp (1). bwtbuf: "abababab 16523413116523413411212121212" buf1: [00000000000000000000000000000000000000] buf2: [00000000000000000000000000000000000000] - Difference [nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] - Properties Пусть пpи очеpедной пpовеpке сpавнивались &bwtbuf[0] и &bwtbuf[2]. тогда получим: bwtbuf: "abababab 16523413116523413411212121212" buf1: [10101010000000000000000000000000000000] buf2: [20000000000000000000000000000000000000] [>nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] ^ Пусть пpи очеpедной пpовеpке сpавнивались &bwtbuf[14] и &bwtbuf[23]. тогда получим: bwtbuf: "abababab 16523413116523413411212121212" buf1: [10101010000000202000000202000000000000] buf2: [29000000000000000000000000000000000000] [><nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] ^ Пусть пpи очеpедной пpовеpке сpавнивались &bwtbuf[1] и &bwtbuf[3]. Тогда будем сpавнивать последоватьльно 2[==шагу отметки] символа стpок и паpаллельно смотpеть, нет ли в буфеpе N1 ненулевых элементов. В данном случае на втоpом сpавнении мы наткнемся на единицу по _обоим_указателям_. Тогда обpатимся в buf2 по индексу 1 [условимся, что это пеpвый элемент массива]. Получим D=2[еще pаз оговоpюсь, что pазность считается _с_учетом_цикличности_ bwt-буфеpа]. Hо, т.к. (3-1)==2, то мы выбиpаем пpизнак. Получим, что стpока &bwtbuf[1] лексикогpафически > &bwtbuf[3], ч.т.д. PS если бы оба элемента buf1 по обоим указателям были бы неpавну 0, то пpишлось бы пpовеpять для каждого из них D. И т.д....т.п.... Hет смысла объяснять, зачем выбpан шаг отметки != 1. Так же полезно увеличивать шаг отметки, если у нас сpавниваемые стpоки пеpе- кpываются по адpесам(типа "abab...")[или делать немного по-дpугому: учитывать основной пеpиод повтоpения(можно задействовать стаpший бит в properties)] Похоже, что эта pеализация алгоpитма будет _посильнее_ деpевца. Единственный недостаток: тpебуется дополнительная память [хотя если bwtbuf== 512k, то не так уж и много] P.S. Всякое усовеpшенствование данного алгоpитма пpиветствуется и не забудьте его [усовеpшенствование] описать в эхе. С наилучшими пoжеланиями , Denis. ... Мой дядя самых честных правил. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 27 Jun 98 22:03:55 To : Michael Semikov Subj : Сортировка в BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Michael! 25 Jun 98, Michael Semikov писал к Vadim Yoockin: MS> Пусть пpи очеpедной пpовеpке сpавнивались &bwtbuf[14] и &bwtbuf[23]. MS> тогда получим: MS> bwtbuf: "abababab 16523413116523413411212121212" MS> buf1: [10101010000000202000000202000000000000] MS> buf2: [29000000000000000000000000000000000000] MS> [><nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] MS> ^ У меня сразу 2 вопроса. 1) Получается, что мы можем сравнивать каждую подстроку входного потока лишь однажды, ибо в buf1 для нее предусмотрена только 1 ссылка. А если у нас ...41311...41341...41332...41323... (а на такие похожие контексты BWT, собственно, и расчитан)? 2) Как мы определяем порядок сравнений? Взять ту же строку abababab. Ведь явно лучше начать сравнение с последних подстрок. По методу, аналогичному используемого в BZIP2 (кстати, ты получил его?), меняем индексы 'ab 1' и 'abab' на, например, 'a\0\0\0' и 'a\0\0\1'. И, при очередном сравнении 'ababab 16...' и 'abab 1652...', получаем a001 > a000. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Sergey Erokhin 2:461/108.7 29 Jun 98 00:08:00 To : All Subj : Пpо сжатие и вообще ... ;-) Hello All! Hаписал мой знакомый статью маленькую (44444 байт) по теме эхи котоpая и пpедоставляется на суд читателей Коментаpии пpиветствуются ... Зовут его Евгений Костpомитин Aka Shadow Dragon ;-) в 4-х кусках ... ark1.doc === Cut === Project: Tightest/Fastest Data Compression Subj: ARK: Combinatorical compression algorithm Number: 1 Version: 1.0 (Ready) Modified: 06-20-1998, 06-21-1998 ---------------------------------------------------------------------------- - Я сказал: SRC Confidential !!! - А как же "Information must be free?" - А как же "There are no such thing as a free lunch?" Диалог. Внутренний :) (* SRC = Shadow Research Center :) ---------------------------------------------------------------------------- 1. Compression Limits / Compression Principles 1.1. аезд с happy end'ом. Once upon a time... Блин... Так вот, однажды задумался я в очередной раз над интересной такой задачей сжатия информации. Этой темой занимались многие весьма известные люди, и напридумывали они весьма немало загадочных сущностей. Одной из них, является, например, нечто, называемое "энтропией информации" (Шеннон придумал?) и масса сил была потрачена на попытки увеличить количество "энтропии" текста до максимума. Была даже выведена интересная формула для этого максимума: символ должен кодироваться в Log2[t/f] бит, где t - общее количество символов, а f - количество встречаний данного символа. (понятие энтропии возникло (IMHO) при анализе частотных алгоритмов сжатия). А потом был даже изобретен алгоритм кодирования (так называемое "арифметическое кодирование" или ARI), который позволил достичь теоретического (по вышеописанной формуле) максимального сжатия, а также, заодно, дал возможность использовать для кодирования символов дробное количество бит. Интересный вопрос - откуда вообще появилась идея, что путем специального кодирования информации на основе статистических данных о ней можно эту информацию сжимать? Очевидно, все началось с идеи, что можно заменять строку в тексте на ссылку, если такая строка в этом тексте встречается неоднократно, и что после произведения такой операции размер текста должен уменьшиться (при достаточной длине заменяемой строки). Потом, видимо, возникла идея, что можно попытаться применить тот же принцип на битовом уровне. Потом были придуманы всяческие алгоритмы нахождения "оптимального" кодирования символа в строку битов (я знаю алгоритмы Хаффмана и Шеннона-Фано). Еще позже, по-видимому, стали рассматривать возможность кодирования последовательностей символов (имея информацию только о частотах самих символов). Отсюда, наверное, и возникло "арифметическое кодирование". Ладно. Возьмем некий блок неких данных. Взяли. Изучив его, мы обнаруживаем, что содержащаяся в нем информация явно избыточна (или предполагаем это), и решаем, что лучше бы этот блок данных хранить в меньшем объеме памяти, чем он занимает в исходной форме. Каким же образом это можно сделать? Принято считать, что для этого следует (желательно - зная структуру этого блока данных, хотя обычно предполагается, что блок данные представляет из себя массив байтов - очевидно, по причине байт-ориентированности архитектуры нынешних компьютеров, которые используются для сжатия данных), так вот, следует определить, какие элементы структуры нашего блока данных занимают значительные области памяти, потом придумать, каким образом эти элементы могут быть закодированы так, чтобы занимать меньший объем. Из предположения, что блок данных представляет из себя массив байтов, таким образом следует, что для его сжатия следует применять ARI, (если требуется добиться наилучшего коэффициента сжатия и либо не нужно коммерческое применение, либо есть лицензия на соответсвующий патент (IBM обладает более чем 18-ю патентами на разные варианты реализации ARI)) Альтернативный подход (мой :) - основан на принципе "разделяй и..." - при необходимости сжать блок данных берем :) и находим некоторую информацию, наличие которой значительно уменьшит количество вариантов возможных блоков имеющих данную структуру. Потом применяем тот же принцип к "некоторой информации" до тех пор, пока объем памяти, который она занимает не станет совсем незначительным. После чего, то что осталось можно записать как есть. Общепринятый метод, очевидно, можно отнести к "жадным" алгоритмам - это когда при решении задачи, состоящей из зависимых подзадач предполагается, что оптимальное решение первой подзадачи является оптимальным для всей системы. Яркий пример подобного подхода: предположим, что у нас есть блок данных, о котором известно, в нем могут встречаться два разных символа, причем один из них - значительно чаще, чем другой. Что нам дает стандартный метод, если его применять к данной задаче? у, как же. Вот тот символ, которого много, занимает много места. К тому же данный :) (по ангельски - given data block - и никакой тавтологии :) блок данных можно представить в виде набора длинных участков, заполненных _только_ частовстречающимся символом, между которыми вставлены вторые символы. Ах, так? у тогда возьмем и запишем этот блок в виде последовательности длин этих самых "длинных участков". у и что получилось? Что, что - RLE :) Записали? у а теперь можно сидеть и восхищаться своей мудростью :) потому, как, ежели посмотреть: пусть x - количество встречаний первого символа (которого много) y - -//- -//- второго символа (y<<x) ("<<" в математике это вам не SHR :), а "значительно меньше") таким образом, мы закодировали x+y символов в log(k)*(y+1) символов ( здесь k - максимальное количество последовательных повторений первого символа в блоке, соответственно log(k) обозначает количество символов, требуемое, чтобы это максимальное количество записать ) То есть, если (в качестве примера) в блоке длиной 256 у нас встречается только один второй символ (и 255 первых, как ни удивительно :), то его можно закодировать в log(255)*(1+1)=2*log(255) символов. Теперь, если предположить что эти "символы" - на самом деле биты (а чего их два? :), то получается приблизительно 2*8=16 бит (если округлить логарифм:) Ура-а-а-а! Мы совершили подвиг - закодировали целых 256 бит в 16. А если вторых символов будет два, то в 24, а если три, то в 32, а если... Какой офигительный коэффициент сжатия! Какой-какой... А теперь подумаем: у нас есть блок, заполненный в основном первым символом, по которому разбросаны несколько вторых. И при этом - (предположительно, за неимением дополнительной информации) разбросаны совершенно случайным образом. Что-то это напоминает... А, как же, как же - комбинаторика! Исходя из которой мы знаем, что количество возможных вариантов расположения (то есть разбрасывания :) вторых символов, количеством y, по блоку, заполненному первыми, длиной x+y, есть: y C - число сочетаний из x+y по y x+y то есть, для y=1 - есть 256 разных блоков, для y=2 - 256*255/2 = 32640 и т.д. Если теперь записать в качестве результата байт, содержащий количество встречаний второго символа (если y таки <<256), то его можно даже еще дополнительно упаковать, но пусть уж будет байт) и ceiling(log2(C(x+y,y))) бит номера сочетания (тоже теряя какую-то часть бита :) на такой записи, но ладно уж...), то получим: y = 1 -> 8+8 =16 бит (ну и чего было страдать?) но уже y = 2 -> 8+15=23 (было 24) y = 3 -> 8+22=30 (C(256,3)=2763520=2A2B00h) (было 32) и т.п. То есть разница как бы маленькая :), но есть. (К сожалению, судя по некоторым экспериментам, разница возрастает где-то по логарифму и, поэтому, _намного_ большей не будет (так чтоб в два раза :) единственная надежда на факт, что при увеличении количества различных символов эта разница возрастает) Так вот, самое смешное заключается в том, что между патентованным ARI и вышеописанным методом разница тоже есть. И в ту же сторону :) Как же так, ведь ARI достигает теоретического минимума длины? Значит, такой вот ARI и такая вот теория. у кто ж им доктор, что они посчитали теоретический минимум именно для используемого ими алгоритма (кодирования Хаффмана?), потом его достигли и жутко этому радовались :) Вот с комбинаторикой спорить сложнее - если у нас есть число, которое может принимать значение от 0 до c-1 ( C(n,k) ), и при этот все значения равновероятны, то вряд ли есть смысл тратить на это число больше чем log2(c) бит, но с другой стороны и меньше уже как бы не получится. То есть - вот он, новый предел сжатия на основе частотной статистики! :) Единственная проблема - обязательно ли использовать в качестве "некоторой информации" именно таблицу частот встречаний символов? Просто трудно придумать что-то другое, что к ней бы не сводилось... о кто доказал, что невозможно ? ------------------------------------------------------------------------- 1.2. Метаалгоритм, Берроуз-Вилер и все-все-все. Теперь, все же, к вопросу о том, что из себя представляет сжатие информации в принципе? x Казалось бы, если есть число из интервала 0..2 - 1, то как же его можно записать менее чем в виде x бит, ведь x бит могут принимать как раз ровно 2^x различных значений? о вот оказывается, что некоторые из этих значений являются более некоторыми чем другие :), и встречаются в жизни значительно чаще. Поэтому на их хранение расходуется в целом больше памяти. И вообще. То есть, если предполагается, что данный объем памяти может использоваться для хранения только некоторых :) значений из возможных, то - очевидно - имеет смысл (дешевле :) использовать для этих целей меньший объем памяти, в котором хранить не само значение (некоторое :), а его номер. Остается еще задача определения номера по значению (сжатия данных :) и значения по номеру при условиях, что множество возможных значений - неизвестно. Интересная задача... Решается обычно путем определения этого (или похожего :) (или не очень :-) множества на основе статистического анализа самого блока данных (значения :) (некоторого :-), предполагая (очевидно :) наличие самоподобия (фрактальности :) структуры. При всем при этом, совсем неплохо было бы, если бы авторы архиваторов (бы :) это осознавали и сознательно использовали. К сожалению, в большинстве случаев при написании архиватора используются общеизвестные алгоритмы сжатия (иногда слегка модифицированные на основе данных полученных из собственных экспериментов). екоторые, правда, еще пытаются использовать таки собственные алгоритмы, но созданные не для сжатия данных, а для предсказания будущего поведения некоего процесса (Буяновский со своим ACB, например), очевидно, полагая, что это одно и то же. Хотя это задачи и похожие, но слегка различные - алгоритм предсказания должен оставлять, пусть малую, но вероятность происхождения любого события из возможных, а алгоритм сжатия может использовать _всю_ информацию о блоке данных, которую он способен использовать (и, таким образом, исключать некоторые варианты). Тем не менее, несмотря на вышесказанное, тот же ACB, например, дает совсем неплохое сжатие (вот со скоростью сжатия, увы...). Тем не менее, одно исключение, правда, относительно недавно, появилось - block-sorting алгоритмы Шиндлера (который я не знаю - szip) и Burrows-Wheeler'а (bzip). То есть в результате-то получается нечто вроде хитрого кодирования пар символов, но вот над самим методом еще стоит подумать. === Cut === Bye. Sergey. --- GoldED 2.50.A0307+ * Origin: -=*=- (2:461/108.7) — RU.COMPRESS From : Sergey Erokhin 2:461/108.7 29 Jun 98 00:15:00 To : All Subj : Пpо сжатие и вообще [2] Hello All! === Cut === Метод, собственно, следующий (BWT = Burrows-Wheeler Transform) Есть текст (на нем BWT дает неплохие результаты, в отличие от некоторых других видов данных): "абракадабра" Заполняем на основе этого текста квадратную таблицу: абракадабра записываем исходный текст бракадабраа с круговыми сдвигами ракадабрааб акадабраабр кадабраабра адабраабрак дабраабрака абраабракад браабракада раабракадаб аабракадабр Потом сортируем эту таблицу как массив строк в лексикографическом порядке. аабракадабр [Sorted by QEdit] абраабракад абракадабра - исходный текст адабраабрак акадабраабр браабракада бракадабраа дабраабрака кадабраабра раабракадаб ракадабрааб Теперь возьмем последний столбец отсортированной таблицы (так в BWT, хотя в принципе можно любой, а IMHO лучше второй), запишем его в строку, и заодно отметим где в ней находится символ, принадлежащий исходному тексту (несдвинутому) рд(а)краааабб (последний) р1д1а1к1р1а4б2 аб(б)дкрраааа (второй) а1б2д1к1р2а4 Так вот, по причине того, что первый столбец можно восстановить во вышенаписанному (любому) столбцу посимвольной сортировкой (а наличия любых двух столбцов и начального номер достаточно для восстановления перестановки, которая использовалась для сортировки), то в результате получается, что замучанного сортировкой столбца и номера в нем символа, принадлежащего исходному тексту достаточно для однозначного восстановления этого текста. А замучанный сортировкой столбец характерен тем, что в нем повторения нескольких одинаковых символов подряд встречаются несколько (иногда - значительно) чаще, чем в исходном тексте. Следовательно - его можно пожать RLE :) (это не я, это Burrows-Wheeler :) >> Увы, это все же я. Как выяснилось после изучения comp.compression >> faq'а, >> Burrows (который в 1983 году придумал этот алгоритм, а опубликовал >> почему-то только в мае 1994) использовал в качестве второго >> препроцессора >> так называемый "метод стопки книг" - когда символы хранятся в стеке, >> при использовании из него извлекаются, а потом складываются на вершину >> стека. Таким образом, если на выходе кодировать позицию символа в >> стеке, то часто используемые (в прошлом) символы будут находится ближе >> к вершине стека, соответственно номера символов близких к вершине >> будут >> чаще встречаться в результате. >> Я не знаю, может именно этот метод идеален именно для кодирования >> _последнего_ столбца матрицы, но мне все же больше нравится RLE. А потом результат дожать ARI. Или по Хаффману, если денег на лицензию нет :) И радоваться жизни, если от приложенных усилий есть какой-то толк :) Хотя мне все же кажется, что им все же в результате повезло только с упаковкой текстов - видимо тексты имеют соответствующую структуру :) о сама идея... Ладно, пока не забыл - метаалгоритм оптимального сжатия данных - распознаем структуру блока данных - записываем в выходной файл информацию об этой структуре (возможно, тоже упакованную, по этому же алгоритму) - записываем номер варианта значения структуры, соответствующий исходным данным (сжимать номер варианта смысла по идее не имеет если правильно определена структура данных) А, еще возникает вопрос, почему же всевозможные "динамические" алгоритмы все же что-то сжимают, несмотря на то, что никакой дополнительной информации о данных вроде бы не записывалось? > Я думаю, что все просто. Просто эта дополнительная информация размазана по всему сжатому файлу таким образом, чтобы в процессе распаковки ее можно было бы получить как раз тогда, когда она необходима. Это тоже может быть полезно, но только с точки зрения конкретной реализации (программы) конкретного алгоритма сжатия - для увеличения скорости работы, уменьшения объема используемой для работы памяти, при необходимости потоковой работы (когда читать исходные данные можно только один раз, а писать сжатые данные надо уже в процессе чтения). Это собственно тема для отдельного разговора - соотношение качество/скорость/объем_используемой_памяти и как его сбалансировать. (Ведь если при увеличении коэффициента сжатия на 0.00001% время сжатия увеличивается в два раза, то, наверное, не стоит этого делать. Этот вопрос, по-видимому относится к серии "Artifical Intelligence", потому что как иначе _программа_ может определить, насколько больше времени я смогу вытерпеть ради данного увеличения коэффициента сжатия. :) Вот еще все же вызывает интерес (раз уж вспомнил) этот самый "метод стопки книг" (хотя его тоже можно отнести к "динамическим", но все же это не есть _метод сжатия_ - это перекодирование при сохранении занимаемого объема памяти). асколько я понимаю, в случае с BWT он все же представляет собой не более чем такой вот забавный выриант RLE (похоже получится, если ввести спецсимвол для повторения предыдущего символа), в котором самое ценное качество заключается в том, что он экономит ресурсы на кодирование одного лишнего символа. (Интересно, а если считать обычный текст закодированным с помощью RLE со спецсимволом, потом взять и раскодировать его, а потом снова закодировать по "стопке книг". Количество различных символов на выходе вроде бы должно быть на один меньше? А размер в памяти - тот же. :) Увы, так не получится. _Любой_ обычный текст нельзя считать закодированным со RLE со спецсимволом - получится неоднозначность, если в тексте и на самом деле будут повторяющиеся символы.) А на самом деле, (IMHO), "метод стопки книг" изобретался-то собственно в качестве замены динамическому частотному кодированию (тому же хаффману) для повышения скорости работы упаковщика (за счет коэффициента сжатия, естественно) - выходные номера символов в стеке кодировались потом фиксированными префиксными кодами. А идея применять хаффмана для допаковки... это извращение :) у, и последний момент. Поскольку для распаковки сжатого блока данных требуется некая программа (алгоритм), содержащая в себе некоторое количество информации, то стоит помнить, что некая (или вся) часть информации о структуре сжатого файла может быть представлена частью этой программы. (В явном случае в программе, скажем, может храниться словарь.) ------------------------------------------------------------------------- 2. Simplifying: Frequency algorithms. Теперь перейдем к более конкретному вопросу: самой сложной (на мой взляд) задачей упаковщика является определение структуры сжимаемых данных. Поэтому пока обойдемся без этого и рассмотрим реализацию доморощенного алгоритма кодирования на основе частот символов (я обозвал его ARK). ------------------------------------------------------------------------- 2.1. Sum x^n algorithm. Печальный случай. Пусть, для начала, в нашем алфавите наличествуют всего два символа: мю и зю (ладно, 0 и 1 :). И пусть количество встречаний 0 в блоке данных равно x, а 1 - y. Тогда, как уже сообщалось, существует всего C(x+y,y) различных блоков данных с такими характеристиками. Это-то хорошо, но остается вопрос, каким же образом определить номер _данной_ последовательности 0 и 1 среди возможных 0..C(x+y,y)? Первая возникшая идея была такая: будем кодировать не сами символы, а координаты одного из них (скажем 1) в блоке данных. Если потом блок инициализировать нулями, а потом прочитать координаты и по ним прописать единицы, то получится как раз то, что надо. Итак, пусть, для примера, y=2. Местонахождение двух единиц в блоке может быть описано двумя координатами (считая от нуля): y1: 0..x+y-2 y2:y1+1..x+y-1 (перестановки без повторений!) Задача: построить некую функцию от y1,y2,x,y, такую, чтобы ее значение (целое) изменялось от 0 до C(x+2,2)-1 (y=2) и было различным при различных парах {y1,y2}. Переберем-ка все :) варианты пар {y1,y2}: ----T--------------¬ ¦y1 ¦ y2¦ +---+--------------+ Что-то это напоминает... ¦0 ¦ 1,2,3,..,x+1¦ ¦1 ¦ 2,3,..,x+1¦ Очевидно, можно взять функцию ¦2 ¦ 3,..,x+1¦ y1*(y1+1) ¦...¦ ¦ f(x,y1,y2) = x*(x+1) - --------- + y2 ¦x ¦ x+1¦ 2 L---+--------------- (для этой таблицы) y2*(y2+1) Или можно взять функцию попроще: f(y1,y2) = --------- + y1 2 Эта лучше, потому, что не зависит от x. 1 Итак: f(y1,y2) = - * ( y2*y2 + y2 + 2*y1 ) 2 Можно заодно попытаться построить функцию и для трех координат: 1 f(y1,y2,y3) = -- * ( 2*y3^3 + 9*y3^2 + 7*y3 + 6*y2^2 + 6*y2 + 12*y1 ) 12 Увы, особых закономерностей не замечается :( В принципе, общую формулу я таки (как бы) вывел, но при терпимых значениях длины блока (хотя бы несколько сотен бит) это будет полином степени x+y. И кто, интересно, будет его такой считать? о это-то еще ладно, а ведь возникает еще вопрос, каким образом по значению f(y..) находить потом эти y? ет, ну в общем-то я себе представляю такой итеративный алгоритм (поразрядный), но... Так что же, неужели сжатие данных на основе таблицы частот, лучшее чем ARI неприменимо по причине сложности и требуемых вычислительных мощностей? еужели же ARI остается best of show? ------------------------------------------------------------------------ === Cut === Bye. Sergey. --- GoldED 2.50.A0307+ * Origin: -=*=- (2:461/108.7) — RU.COMPRESS From : Sergey Erokhin 2:461/108.7 29 Jun 98 00:15:00 To : All Subj : Пpо сжатие и вообще [3] Hello All! === Cut === 2.2. Cnk algorithm. есколько радостней. Итак, с координатами не получилось. Что же можно сказать об обычном подходе - последовательном посимвольном? Вот есть у нас последовательность бит длиной x+y, где x - количество нулей, а y - единиц. Как же посчитать номер перестановки для данной последовательности? Рассмотрим количество вариантов хвоста последовательности без первого бита в зависимости от его значения: - пусть первый бит 0. Тогда хвост представляет собой последовательность длиной x+y-1, состоящую из x-1 нулей и y единиц. Следовательно количество разных значений хвоста в этом случае - C(x+y-1,y) - пусть первый бит 1. Тогда аналогично количество значений хвоста равно C(x+y-1,y-1) Ага. о если первый бит - 1, то блок не сможет принять ни одно из C(x+y-1,y) значений, принимаемых, когда бит1 = 0. Поэтому можно считать, что если бит1=0, то номер блока находится в интервале 0..C(x+y-1,y)-1, а если бит1=1, то в интервале C(x+y-1,y)..C(x+y,y)-1, а точное его значение определяется исходя из номера варианта хвоста. о хвост ведь тоже начинается с бита... И ничем принципиально не отличается от всего блока... Так что вот он - ARK, комбинаторный частотный алгоритм сжатия. Ура. Ура-то ура, но возникает новый вопрос: не будет ли это тоже слишком медленно? Ведь хотя на первый взгляд в алгоритме используется только одно сложение на итерацию (да и то не всегда), но это ведь сложение с C(x+y-1,y), который (коэффициент) тоже надо вычислить, а считается он по ценной формуле: n! C(n,k) = --------- k!*(n-k)! при k<n/2 для вычисления значения потребуется 2*k умножений и деление. При размере блока хотя бы 1024 бита, где y может принимать значение 512 (при нем C(x+y-1,y) максимально для данного размера блока), стало быть, потребуются 1024 умножения и еще каких! Ведь для представления значения C(1024,512) потребуется ~128 байт памяти. Хм. Однако. 1024 стодвадцативосьмибайтных операций на бит это действительно несколько многовато. о, с другой стороны, этой тяжелый случай все же легче, чем с f(y,...), ведь у C(n,k) всегда ровно два аргумента, да еще и ограниченных размером блока. Я хочу сказать, что можно же, в конце концов, и таблицу значений C(n,k) посчитать перед упаковкой и хранить в памяти. Правда для n=1024 квадратная таблица займет 128k памяти, но это не так уж и много. Кстати, уже при n=720 эта таблица поместится в 64k, а на коэффициент сжатия это практически не повлияет. Вот. То есть идея вполне рабочего алгоритма уже есть: (на самом деле, есть даже и уже написанный упаковщик - см. ark1.asm,etc) - определить размер блока MaxN (паковать придется блоками) - посчитать таблицу C(n,k) для n от 1 до размера блока - определить размер входного файла и записать его в выходной - повторять пока не закончатся блоки - считать блок размером n (0<n<=MaxN) - определить количество y единичных битов в нем - записать y в выходной файл - отвести буффер длиной int(log2(C(n,y))) - повторять для всех битов блока - n=n-1 - если очередной бит равен 1, то: - прибавить к буфферу C(n,y) - y=y-1 А вот и алгоритм распаковщика ( из лени распаковщик к ARK1 не написан вовсе ) - определить размер блока MaxN - посчитать таблицу C(n,k) для n от 1 до размера блока - прочитать из архива размер l - повторять пока не закончатся блоки - определить размер текущего блока n (либо MaxN, либо l mod MaxN) - прочитать из архива количество y единичных битов в нем - прочитать из архива блок размером log2(C[n,y]) бит - отвести буффер длиной n - повторять для всех битов блока - n=n-1 - если значение в сжатом блоке больше или равно C(n,y), то: - отнять от сжатого блока C(n,y) - записать в буффер бит 1 - y=y-1 - иначе - записать в буффер бит 0 Собственно, и все. у, еще можно изменять проверку бита на равенство тому биту, который встречается реже, чтобы выполнять меньшее количество сложений. ? Это все хорошо. о хотелось бы, все же увеличить размер рабочего блока > Запросто. Есть такая вот еще идея: вместо полных многобайтных значений C(n,k) можно хранить их в формате с плавающей точкой. При этом несколько теряется точность вычислений, но если считать таблицу С(n,k), как треугольник Паскаля, то, по крайней мере, при этом не потеряется возможность распаковки :) К тому же, на самом деле достаточно хранить в таблице C(n,k) только мантиссы, потому, что порядок pC(n,k) может быть вычислен, как pF(n)-pF(k)-pF(n-k), где pF(n) - порядок n!, правда, с небольшой погрешностью, но она может быть компенсирована соответствующего обработкой мантисс C(n,k). А pF() зависит уже только от одного аргумента. Таким образом, можно посчитать таблицу порядков факториалов и таблицу мантисс C(n,k), скажем, по 16 бит на значение. Размер блока при этом зависит только от того, сколько памяти можно себе позволить использовать под таблицы. Кроме того, размер таблицы C(n,k) можно так же уменьшить за счет симметрии по k, а также некоторых других закономерностей. Еще была идея полностью вычислять значение C(n,k) по таблице факториалов, но она еще нуждается в проверке на точность вычислений. -------------------------------------------------------------------------- 3. ARK: Speed or Quality? Еще один печальный случай. Реальная трудоемкость табличного алгоритма - два вычитания, сдвиг и сложение на бит. Так что он получается (как бы :) круче ARI не только по коэффициенту сжатия, но и по скорости работы. Какая радость! Единственная проблема - вышеописанные алгоритмы упаковки/распаковки расчитаны исключительно на работу с потоком _битов_. о, поскольку даже тот же ARI будучи сразу применен к блоку данных обычно принципиального сжатия не дает (текст можно сжать, ну, в два раза...), то его обычно применяют в качестве кодировщика потока символов, выдаваемого кодировщиком первого уровня (который разбирается со структурой входного файла). Так что как насчет упаковки по тому же принципу количества битов, большего, чем два? Да раз плюнуть :) Возьмемся снова за комбинаторику и посчитаем количество вариантов значений блока данных, состоящего из _трех_ символов (0,1,2) - количеством x,y,z соответственно. Вот есть пустой буффер длиной x+y+z. X первых символов можно в нем расположить C(x+y+z,x) способами, после чего останется еще y+z свободных ячеек. В них можно расположить y вторых символов C(y+z,y) способами, а оставшиеся свободными в результате z ячеек можно уже сразу заполнить третьими символами. То есть, в результате получилось, что вышеописанный блок данных может принимать C(x+y+z,x)*C(y+z,y) возможных значений. Соответственно, хвост блока, без первого символа, может принимать: если первый_символ = 0 -> C(x+y+z-1,x-1)*C(y+z,y); если первый_символ = 1 -> C(x+y+z-1,x)*C(y+z-1,y-1); если первый_символ = 2 -> C(x+y+z-1,x)*C(y+z-1,y) различных значений. Таким образом, для того, чтобы закодировать первый символ, нам понадобится прибавить к выходному буфферу: если первый_символ = 0: 0 если первый_символ = 1: C(x+y+z-1,x-1)*C(y+z,y) если первый_символ = 2: C(x+y+z-1,x-1)*C(y+z,y) + C(x+y+z-1,x)*C(y+z-1,y-1) Снова печальный случай. Опять пошли какие-то умножения... да и сложения лишние... а таблички для всех вариантов троек x,y,z уже не составишь... Так, а что если посмотреть, что получится, если расписать произведение коэффициентов? (x+y+z)! (y+z)! (x+y+z)! C(x+y+z,x)*C(y+z,y) = -------- * ------ = -------- x!*(y+z)! y!*z! x!*y!*z! Гм. "Триномиальный коэффициент"? А если расписать границу второго интервала? x-1 y x y-1 (x+y+z-1)! (x+y+z-1)! C *C + C *C = ----------- + ---------- = x+y+z-1 y+z x+y+z-1 y+z-1 (x-1)!*y!*z! x!*(y-1)!*z! (x+y)*(x+y+z-1)! = ---------------- . Ага, теперь, по крайней мере, понятно, что это такое. x!*y!*z! То есть, вроде бы и не так уж все и сложно... о как это считать, понятнее не стало. В особенности, для случая если различных символов будет, скажем, 256. -да, даже если считать по флоат-пойнтовской таблице факториалов, все равно получается (если n - количество разных символов) n+1 вычесление факториала по таблице, n умножений float-point'ов и одно деление. а символ. Так что, чем больше символов, тем медленнее... о что если все же записать явно формулу для суммарного количества различных значений блока данных для случая, когда первый символ находится в интервале 0..i. Пусть n - количество символов в алфавите, а f[i] - количество символов i, используемых в блоке данных. Тогда количество различных значений блока при условии, что первый символ принадлежит 0..i (оно же - нижняя граница интервала номеров этих значений для символа i) равно: ( Sum( f[k], k:0..n-1 ) - 1 ) ! L(i) = Sum( f[k], k:0..i-1 ) * ------------------------------- Prod( f[k]!, k:0..n-1 ) Ой! о правый множитель совершенно не зависит от i - то есть, от номера текущего символа! Да и первый множитель очень уж кое-что напоминает... Особенно, учитывая, что это формула для границы интервала... Короче. Вот именно в этом-то и заключается вся проблема. Как становится теперь понятно, алгоритм ARK и битовый ARI - близнецы-братья :) Я даже подозреваю, что при соответсвующем старании можно добиться того, что они на выходе будут выдавать одинаковый результат по одному и тому же блоку данных! Стоп. у а что же тогда можно сказать о моем утверждении, что мой метод дает больший коэффициент сжатия чем ARI? Что-что... То что это утверждение справедливо :) о только для того ARI, примеры работы которого приводятся в литературе по сжатию данных :) === Cut === Bye. Sergey. --- GoldED 2.50.A0307+ * Origin: -=*=- (2:461/108.7) — RU.COMPRESS From : Sergey Erokhin 2:461/108.7 29 Jun 98 00:16:00 To : All Subj : Пpо сжатие и вообще [4] Hello All! === Cut === Действительно, ведь если обдумать принцип работы статического ARI, то получится, что кодировать символы одинаковыми интервалами при обработке всего входного блока данных неправильно! Ведь если перед обработкой мы знали, что количество встречаний символа i в блоке данных равно f(i), то, после того, как закодирован первый символ i, мы знаем, что дальше он встретится не более, чем f(i)-1 раз. Так что в тех (во всех ?!) примерах работы ARI в литературе рассматривается _упрощенная_ реализация ARI (с постоянной таблицей частот). Кроме того, оказывается, что утверждение о том, что "символ с частотой f(i) при оптимальном кодировании занимает -log2(f(i)) бит" совершенно справедливо. С одной оговоркой: оно справедливо только в момент кодирования _этого_ символа. Следующий символ уже должен занимать -log2(f(i)-1) бит! Конечно, печально, что эпопея с изобретением "абсолютно нового метода, сжимающего лучше ARI" закончилась именно так. о, с другой стороны, как минимум, из всего этого можно сделать несколько достаточно ценных выводов: - стандартной реализации ARI (Q-Coder?) требуется n умножений для кодирования n символов (не говоря уж о сложениях и прочем). При этом вышеописанному алгоритму ARK (с некоторыми простыми модификациями, правда :) требуется _меньше_ n/2 _сложений_ (правда, это для битового случая. о, как будет описано несколько позже (это еще не все :), ARK'у, модифицированному для работы с k символами потребуется максимум n/2*ceiling(-log2(k)) сложений. Все равно быстрее :) - собственным опытом подтверждено (можно сказать - доказано) утверждение об оптимальности кодирования блока символов на основе таблицы частот с помощью ARI (как, впрочем, и с помощью ARK :) - получена некоторая информация о приципе действия ARI (что полезно, так как обычно алгоритмы сжатия данных публикуются уже в готовом виде, без обсуждения того, каким же образом автор дошел до такой жизни :) - замечен интересный факт: динамический ARI в стандартной реализации на самом деле _всегда хуже_ статического ( по коэффициенту сжатия ). И никаким слухам о том, что, дескать, динамический ARI адаптируется к конкретным данным и может давать лучший результат, чем статический. Очевидно, его просто сравнивали с _совсем статическим_ ARI. (в котором частоты символов не меняются в процессе кодирования) А в этом случае правильно написанный (и даже если слегка неправильно :) динамический ARI (который начинает с фиксированной таблицы частот, а потом ее изменяет в соответствии с обработанными данными) должен быть также _всегда лучше_. Особенно, если в статическом алгоритме, с которым производится сравнение, неправильно организовано хранение таблицы частот. А на самом деле, у меня есть подозрение, что даже специальная предустановленная таблица частот, ориентированная именно на данный :) блок данных, не поможет динамическому ARI быть лучше статического (правильно реализованного :) Вот. о что все же можно сказать о возможности создания варианта алгоритма ARK, работающего с многосимвольным алфавитом? > а самом деле, обнаружившееся родство ARK с ARI значительно упрощает работу по выбору подходящего варианта: ARI тратит одно умножение на каждый символ (как минимум, Q-Coder тратит 2 умножения, 2 _деления_, 2 сложения и 3 вычетания на символ), следовательно все варианты ARK'а с умножениями можно вообще отбросить за ненадобностью. Точно так же можно отбросить все варианты, работающие с полным (очень длинным) представлением C(n,k) при n>64 (восемь байт на коэффициент) Таким образом, на нынешний момент у меня остается в наличии только одна идея, каким образом можно использовать _битовый_ ARK (следовательно- только со сложениями) для работы с многосимвольными алфавитами - кодировать битовую маску размещения каждого символа отдельно. апример: есть любимое слово абракадабра. Мы можем закодировать его следующим образом: а: 10010101001 из битовой маски символа должны исключаться б: 10 0 0 10 места, о которых известно, что они использованы р: 1 0 0 1 в маске другого символа. к: 1 0 д: <позиция известна заранее> Из этого следует, что, скажем при кодировании 256 различных символов в результате получится, как минимум, 256 отдельных блоков сжатых данных, в каждом из которых записана информация только о данном конкретном символе. Как ни странно, производительность алгоритма от этого падает не принципиально (8 сложений на два символа вместо одного сложения на бит - это одно и то же), но вот коэффициент сжатия несколько страдает - поскольку размеры блоков сжатых данных будут достаточно велики (>=1024 символа), чтобы не вызывать желания их перемножать, то на кодировании каждого блока будет теряться некая часть бита. Впрочем, это может быть принципиально только для совсем маленьких блоков данных (длиной не многим более количества различных символов). При более значительных объемах на эту погрешность, по-видимому не имеет смысла обращать внимания (я не думаю, что не стоит потерять 256 бит на сжатии 256k данных, учитывая увеличение скорости работы; кроме того, у меня все же есть некоторые подозрения, что даже и коэффициент сжатия у ARK будет все равно лучше, чем у существующих реализаций ARI :) Есть и еще одна :) вещь, касающаяся как скорости, так и качества сжатия (прописанных в заголовке пункта): количество бит, используемых для представления мантиссы C(n,k) при применении формата с плавающей точкой. Дело в том, что количество бит, занимаемых полным (без округления) значением C(x+y,y), где x - количество битов 0, а y - 1, и определяется размер сжатого блока данных. Таким образом, для выбора размера мантиссы, требуется протестировать несколько возможных вариантов и выбрать минимальный из них, при котором (при данном размере блока) ни один округленный коэффициент не будет превышать свое правильное значение на порядок (то есть на бит длины). Хотя, может быть даже и стоит использовать коэффициенты со значительной накопленной ошибкой, если это приведет к ухудшению качества типа использования 1024 бит вместо 1023 для кодирования блока размером 2048 бит :) К тому же, на самом деле список возможных значений длины мантиссы весьма невелик - это либо 1 байт (очень бы неплохо и с точки зрения скорости работы тоже), либо 2, либо 4. Так что... надо тестировать! И вот еще: я только что дорисовал пример битового кодирования слова "абракадабра" и подумал - зачем же, собственно, записывать битовые маски символов в разных блоки? Достаточно просто иметь возможность однозначно разделить одну битовую строку на маски для каждого конкретного символа (что не представляет сложности, поскольку длины масок можно вычислить, исходя из известных частот символов). Так что все оказалось значительно проще, чем я думал. (Самое смешно - это то, что для, скажем ускорения/упрощения ARI такой подход не особенно поможет - умножений там меньше не станет). ... Хотя, что-то тут не так. Вот если посчитать общее количество битов, суммируя длины битовых масок для символов... 0: Sum( f(k), k:0..n-1 ) 1: Sum( f(k), k:1..n-1 ) ... n-2: Sum( f(k), k:n-2..n-1 ). Получается, что размер сжатого блока для такого представления будет: Sum(f(k),k:0..n-1) С Sum((k+1)*f(k), k:0..n-1) Ага. Вот оно что... Вобщем, ничего так хорошего не выйдет. Это неправильно. (А уже бродили такие гениальные идеи насчет дожатия ARK'ом хаффмановского кода...) Битовые маски различных символов все же должны быть разнесены в разные блоки, так как для упаковки/распаковки одного блока используется только _одно_ значение частоты (при фиксированном размере блока). То есть, если упаковывать все символы в один блок, то информация об их частотах теряется - следовательно, ухудшается качество упаковки (значительно, я-таки пробовал допаковывать хаффмановский код ARK'ом - коэффициент сжатия (100*получилось/было) - 99%, да и то, по-моему только за счет неоптимального представления таблицы частот использованным мной хаффмановским паковщиком (не моим :) ) Ладно. В результате, хотя бы, стало однозначно ясно, какой именно метод придется использовать. ---------------------------------------------------------------------------- 4. What about frequency tables? о раз уж я так выступаю за применение статических методов упаковки, то остается еще один вопрос, о котором ничего еще сказано не было: кодирование таблиц частот. Даже для обычных статических методов (для которых не обязательно кодирование блоками, как для ARK'а) этот вопрос все же представляет некоторый интерес, так как в результате обработки входного файла словарным алгоритмом обычно получается несколько больше различных символов, чем их было изначально. о если скажем, для хаффмана (по причине его специфического отношения к частотам) достаточно закодировать двоичное дерево с развешанными по нему символами, например, таким образом: "абракадабра" р-2 1--------¬<0 кдр-4 1-¬<0 к-1 1-¬<0 ¦ ¦ кд-2 0-- бкдр-6 1-¬ д-1 0-- ¦ ¦ ¦ ¦ б-2 0----------------- абкдр-11 <---- Root ¦ а-5 0-------------------------- Теперь, начиная от корня, рекурсивно обойдем это дерево (начиная с верхней :) ветви), причем будем записывать в выходной поток бит 0 каждый раз, когда при обходе будет происходить рекурсивный вызов для обработки ветви, и бит 1 - при обнаружении узла, в котором хранится частота _одного_ символа. Кроме того, в этом случае мы будем писать еще и 8 бит кода этого символа. Итак: (при выходе из Root'а ничего не пишем, так как Root не может содержать один символ) 001 р 01 к 1 д 1 б 1 а = 8 + 5*8 = 48 бит на хранение этого дерева. В каждом хаффмановском дерево для n символов есть эти самые n cимвольных узлов и n-2 "объединительных" (не считая Root). Исходя из этого, получаем, что при такой кодировке, при n символах дерево будет занимать n*8+n+n-2=n*10-2 бит (что и видно из полученного результата) абракадабра = 0 10 111 0 1101 0 1100 0 10 111 0 = 23 бита. То есть, это слово, закодированное по хаффману будет занимать 48+23=71 бит вместо 11*8=88 исходных. (адо же, даже упаковалось...). о если для хранения таблицы частот применялась бы, например просто таблица 4 бита на символа (4*256=1024 бита), то, естественно, никакой упаковки бы не произошло. о этот метод применим только для хаффмана (зато он и пакует не сказать, чтоб очень хорошо...). Для ARK же, как, впрочем, и для ARI требуется полная таблица частот, со значениями частот для всех символов, и, желательно, без какого бы то ни было округления. Что же получается? Пусть у нас есть размер блока n и k символов с частотами f(i), такими, что Sum( f(i), i:0..k-1 ) = n. Что-то это мне напоминает... А, как же, C(n+k-1,k-1), вот что мне это напоминает. Так что никакой особо сложной кодировки выдумывать не придется (по крайней мере, для ARK, с его ограниченными размерами блоков). А вот и сама идея: Берем битовый массив размером n+k-1, заполняем его нулями, и располагаем в нем соответсвующим образом k-1 единиц. Эти единицы делят оставшиеся n нулей на k частей разной длины, причем сумма этих частей равна, что характерно, n. Вот и все. Если теперь взять и расположить единичные биты таким образом, чтобы длина i-го нулевого участка была равна f(i), а потом полученный битовый массив закодировать ARK'ом (или даже ARI), то получится битовая строка длиной Ceiling(Log2(C(n+k-1,k-1))). Для последнего примера это будет C(11+5-1,5-1)=C(15,4)=1365=555h (rulez!) Ceiling(Log2(555h))=11 бит опять же. Даже если к этому еще дописать 16 бит размера текста и 16 бит количества символов, то все равно получится 16+16+11=43, то есть на 5 бит меньше, чем для хаффмана. И это еще учитывая то, что по тем 48 битам точные значения частот восстановить было нельзя... Что-то тут не так? Да нет, все нормально... Просто надо выбирать правильный алгоритм кодировки :) Судя по всему, правда, более оптимального алгоритма представления таблицы частот не существует, так как мы опять посчитали все возможные комбинации частот. Так что для того, чтобы этих комбинаций было еще меньше, требуется вводить какие-то дополнительные ограничения на частоты. о с применением этого принципа кодировки частот к ARK'у возникают сложности - дело в том, что для него нужно будет хранить не совсем те таблицы частот, а скорее просто количества нулей и единиц в блоках. а эти значения налагаются те же ограничения, что и на обычную таблицу частот, но проблема заключается в том, что в результате применения кодировки в битовую маску к ARK'овским частотам, получится битовая строка длиной в общее количество символов в исходном файле, что может быть достаточно много, чтобы не было возможности закодировать эту строку ARK'ом в один блок (для соотвествующих C(n,k) просто не хватит никакой памяти, если строить таблицу). А если попытаться саму таблицу частот разбить на блоки... То где хранить параметры _этих_ блоков? Так что, как бы не пришлось все же кодировать таблицу частот с помощью ARI :) А с ARI была и остается проблема его относительной тормознутости - так что он будет распаковывать эту несчастную таблицу частот ровно стролько же времени, сколько и весь остальной файл :( -да, не знаю. Как бы придумать для таблицы частот какую-нибудь альтернативную кодировку :) ... Или как бы придумать способ _быстрого_ вычисления C(n,k) при n>2048? И такой, чтобы не требовалось 10G памяти? А еще лучше для n=2^32... Тогда вообще с блоками голову морочить не придется. === Cut === Bye. Sergey. --- GoldED 2.50.A0307+ * Origin: -=*=- (2:461/108.7) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26.26 29 Jun 98 19:01:53 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Wednesday June 17 1998, Vadim Yoockin writes to Michael Semikov: VY>> Тем более, что BZIP, например, на типичных файлах не так часто VY>> страдает от длинных сравнений. Hапомню, что сначала он делит все VY>> строки по пакетам (поразрядная сортировка - очень быстро). Затем VY>> сортирует наименьший пакет. Затем - чуть больший, причем использует VY>> результаты сортировки предыдущего пакета... Хотя, к строкам типа VY>> 'abab...' он, конечно, чувствителен. Как он использует результаты сортировки предыдущего пакета?? Все, видишь ли, хочу разобраться в своем exp'е ;) Bulat --- GoldED/386 2.50+ * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/26.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26.26 29 Jun 98 19:07:45 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Thursday June 11 1998, Vadim Yoockin writes to dmitry bortoq: db>> сжимaемые дaнные. попpобуй взять cabarc и пожaть кaкую-нибудь тaбличку db>> (особенно с большой длиной зaписи) и сpaвнить pезультaты с pезультaтaми db>> дpугих apхивaтоpов (мaлтимедийное сжaтие конечно нужно отключить - у db>> кого оно есть). VY> Ага. Ты прав. Еще cabarc ловко обрабатывает и упорядоченные данные VY> внутри EXE. Что интересно, IMP делает тоже самое. VY> Как-то под впечатлением от cabarc'a я написал небольшой препроцессор VY> для EXE на принципе run-encoding. Размер архива от cabarc'a и imp'a VY> от него только вырос, а, например, rar'овский здорово похудел: Меня не было в июне.... Что за препроцессинг, объясни плиз на пальцах? VY> Ты ведь статистику получал через makecab (вроде в самом cabarc'e я этого VY> не видел)? Там-то видно, что он считывает по 32768 байтов, а на VY> выход может писать по нескольку раз за один считанный блок (метод LZX, VY> конечно). Общими усилиями разломаем и cabarc скоро, как jar разломали :) Я, кстати, в июне разобрался в его поиске, он использует сочетание хеширования с двоичными деревьями, и похоже подбирает строки с конца блока. Вот не знаю, кому-нибудь это интересно, рассказывать подробнее? Bulat --- GoldED/386 2.50+ * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/26.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26.26 29 Jun 98 21:02:33 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Wednesday June 17 1998, Vadim Yoockin writes to Michael Semikov: VY>> Тем более, что BZIP, например, на типичных файлах не так часто VY>> страдает от длинных сравнений. Hапомню, что сначала он делит все VY>> строки по пакетам (поразрядная сортировка - очень быстро). Затем VY>> сортирует наименьший пакет. Затем - чуть больший, причем использует VY>> результаты сортировки предыдущего пакета... Хотя, к строкам типа VY>> 'abab...' он, конечно, чувствителен. Как он использует результаты сортировки предыдущего пакета?? Все, видишь ли, хочу разобраться в своем exp'е ;) Bulat --- GoldED/386 2.50+ * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/26.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26.26 29 Jun 98 21:08:25 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Thursday June 11 1998, Vadim Yoockin writes to dmitry bortoq: db>> сжимaемые дaнные. попpобуй взять cabarc и пожaть кaкую-нибудь тaбличку db>> (особенно с большой длиной зaписи) и сpaвнить pезультaты с pезультaтaми db>> дpугих apхивaтоpов (мaлтимедийное сжaтие конечно нужно отключить - у db>> кого оно есть). VY> Ага. Ты прав. Еще cabarc ловко обрабатывает и упорядоченные данные VY> внутри EXE. Что интересно, IMP делает тоже самое. VY> Как-то под впечатлением от cabarc'a я написал небольшой препроцессор VY> для EXE на принципе run-encoding. Размер архива от cabarc'a и imp'a VY> от него только вырос, а, например, rar'овский здорово похудел: Меня не было в июне.... Что за препроцессинг, объясни плиз на пальцах? VY> Ты ведь статистику получал через makecab (вроде в самом cabarc'e я этого VY> не видел)? Там-то видно, что он считывает по 32768 байтов, а на VY> выход может писать по нескольку раз за один считанный блок (метод LZX, VY> конечно). Общими усилиями разломаем и cabarc скоро, как jar разломали :) Я, кстати, в июне разобрался в его поиске, он использует сочетание хеширования с двоичными деревьями, и похоже подбирает строки с конца блока. Вот не знаю, кому-нибудь это интересно, рассказывать подробнее? Bulat --- GoldED/386 2.50+ * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/26.26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 30 Jun 98 19:24:44 To : Sergey Erokhin Subj : Re: Пpо сжатие и вообще ... ;-) Пpиветствую, Sergey! 28 Jun 98, Sergey Erokhin писал к All: SE> Теперь возьмем последний столбец отсортированной таблицы (так в SE> BWT, хотя в принципе можно любой, а IMHO лучше второй), запишем его Знатоки BWT советуют брать первый столбец, утверждая, что там сплошные последовательности символов, и что, якобы, сжимать этот столбец одно удовольствие :) Булат Зиганшин запретил брать второй столбец своим контрпримером '000101', но остальные столбцы еще никем опорочены :) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 30 Jun 98 19:25:59 To : Sergey Erokhin Subj : Re: Пpо сжатие и вообще [4] Пpиветствую, Sergey! 28 Jun 98, Sergey Erokhin писал к All: SE> а: 10010101001 из битовой маски символа должны исключаться SE> б: 10 0 0 10 места, о которых известно, что они SE> р: 1 0 0 1 использованы в маске другого символа. SE> к: 1 0 SE> д: <позиция известна заранее> Можно записать еще и такую маску, ничем не хуже: а: 10010101001 б: 1 0 0 1 р: 01 0 0 01 д: 0 1 Количество битов там такое же (в примере, надеюсь, сортировка по частотам символов, а не по месту появления в исходной строке). А разнообразие разложения по битовым маскам = избыточность выходной информации. К тому же кодировать '1' в битовой маске для 'а' после 100 всегда приятней, если знать что этому контексту соответствуют '1' в битовых масках 'б' и 'р'. Т.е. раздельное кодирование битовых масок жестоко разрывает контексты. Hельзя же так - прямо по-живому :) SE> о если скажем, для хаффмана (по причине его специфического SE> отношения к частотам) достаточно закодировать двоичное дерево с SE> развешанными по нему символами, например, таким образом: SE> 001 р 01 к 1 д 1 б 1 а = 8 + 5*8 = 48 бит на хранение этого дерева. BTW, есть способ сохранить это дерево в 4 + 5*8 = 44 битах. SE> Для последнего примера это будет C(11+5-1,5-1)=C(15,4)=1365=555h SE> (rulez!) Ceiling(Log2(555h))=11 бит опять же. Даже если к этому SE> еще дописать 16 бит размера текста и 16 бит количества символов, SE> то все равно получится 16+16+11=43, то есть на 5 бит меньше, чем SE> для хаффмана. И это еще учитывая то, что по тем 48 битам точные SE> значения частот восстановить было нельзя... Зато по тем 48 битам можно было узнать, какие именно символы были. А по предлагаемым 43 мы знаем частоты символов, их количество, длину текста, но не эти сами символы. Если по-честному брать C(11+256-1,256-1), то имеем 64 бита (не считая битов на кодирование размера). Это были мелкие замечания. А сама статья очень понравилась. Читал с большим удовольствием. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Sergey Bogdanov 2:5030/208.11 01 Jul 98 19:28:20 To : Viktor Ostashev Subj : <none> Hello Viktor! On the 24-Jun-1998 (Wed) at 23:04 Viktor Ostashev wrote to Denis Moujjoukhin: DM> Т.е. два pазных по стpоению файла, но с одинакоой длинной он сжал бы DM> в одинаковое кол-во pаз... VO> Hетy такого. И быть не может. backup.exe :) Yours truly, Sergey --- * Origin: Home-RT * (2:5030/208.11) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 01 Jul 98 20:26:48 To : Vadim Vygovsky Subj : Re: RAR/2 bug Пpиветствую, Vadim! 26 Jun 98, Vadim Vygovsky писал к Vadim Yoockin: VV>> Как мне подсказал в свое время Булат Зиганшин, это от того, что в VV>> UC max. размер подстроки в словаре - 64K. VY> Hа самом деле (помнишь, я тебе писал об этом) - от того, что в UC VY> иной VY> метод обеспечения "солидности" - он создает общий словарь на весь VY> архив и затем сжимает все файлы со ссылками на этот словарь (помимо VY> текущего окна, конечно). И потому размер окна ему почти без разницы. VV> Пожалуй. Кладезь мудрости у меня зимой гавкнулась вместе с винтом, VV> мучительно вспоминал тот твой форвард - и увы :(. VY> Влияние же размера строки не столь сильно сказывается (1 строка 64K VY> вместо 256 строк по 256 байт - всего лишь экономия на 255 ссылках, VY> причем очень редкая ссылка на 64K хуже дожимается Хаффманом, VY> чем просто редкая на 256 байт). VV> Тогда наверняка влияние размера строки сказывается в случае, когда VV> значительную часть файла составляют повторяющиеся VV> последовательности размером в несколько десятков Kb. Конкретно - я VV> замечал на файле IMAGE.DAT - (образ системных областей диска, VV> создаваемый утилькой IMAGE.EXE, но(!) только из NU не новее 8.0 для VV> DOS/Win) - там подряд идут 2 копии FAT, и UC кроет Rar примерно VV> вдвое. Вадь, это вряд ли сказывается размер строки. Чтобы отделить влияние фактора длинной строки от дальнобойных свойств словаря UC, достаточно сжать файл, состоящего из двух одинаковых случайных достаточно длинных (но короче 64k!) кусков. Результаты оказываются очень близкими. А вот при превышении 64k проявляется ограниченность окна досовского RAR'a. Попробуй, кстати, напустить на image.dat WinRAR (RAR/OS2, консольный RAR) с хорошим -md. VV> P.S. Hе думал ли ты над применением для дожатия Буяновского AC ? VV> Облегченного варианта, конечно. После LZ77? Честно говоря, не вижу смысла. LZ77 ведь безбожно разламывает контексты, на которые расчитан AC. А в AC уже присутствует LZ-подобное кодирование, лишенное этого недостатка. Кстати, LZP тоже бережно относятся к контекстам, что нравится всяким PPM'ам (типа PPMZ, PPMdet). Именно поэтому у нас в лидерах по сжатию текстов BOA, RKIVE и ACB. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 01 Jul 98 20:29:00 To : Bulat Ziganshin Subj : BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Bulat! 29 Jun 98, Bulat Ziganshin писал к Vadim Yoockin: VY>> Тем более, что BZIP, например, на типичных файлах не так часто VY>> страдает от длинных сравнений. Hапомню, что сначала он делит все VY>> строки по пакетам (поразрядная сортировка - очень быстро). Затем VY>> сортирует наименьший пакет. Затем - чуть больший, причем использует VY>> результаты сортировки предыдущего пакета... Хотя, к строкам типа VY>> 'abab...' он, конечно, чувствителен. BZ> Как он использует результаты сортировки предыдущего пакета?? Все, BZ> видишь ли, хочу разобраться в своем exp'е ;) После сортировки очередного большого пакета, все его индексы делятся на не более чем 65534 квадранта. Hомера этих квадрантов записываются в соответствующий массив, элементы которого соответствуют индексам отсортированного пакета. Эти значения используются при сортировке строк. После того, как нам надоест сравнивать строки в лоб (6 попыток), мы пытаемся воспользоваться квадрантами. Ты вот скажи, почему EXP в 2.5 раз сжимает быстрее BZIP2'a? Простая перекомпиляция под Watcom ускорила его в 2 раза. А откуда еще 0.5 - ты все-таки как-то оптимизировал EXP? Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 01 Jul 98 20:30:05 To : Bulat Ziganshin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Bulat! 29 Jun 98, Bulat Ziganshin писал к Vadim Yoockin: VY> Как-то под впечатлением от cabarc'a я написал небольшой препроцессор VY> для EXE на принципе run-encoding. Размер архива от cabarc'a и imp'a VY> от него только вырос, а, например, rar'овский здорово похудел: BZ> Меня не было в июне.... BZ> Что за препроцессинг, объясни плиз на пальцах? Документированная в CABARC'е замена относительной адресации в FAR CALL на абсолютные значения и сокращенная запись всяких табличек типа Relocation Table. VY> Ты ведь статистику получал через makecab (вроде в самом cabarc'e я VY> этого VY> не видел)? Там-то видно, что он считывает по 32768 байтов, а на VY> выход может писать по нескольку раз за один считанный блок (метод VY> LZX, VY> конечно). BZ> Общими усилиями разломаем и cabarc скоро, как jar разломали :) Я, BZ> кстати, в июне разобрался в его поиске, он использует сочетание BZ> хеширования с двоичными деревьями, и похоже подбирает строки с BZ> конца блока. Вот не знаю, кому-нибудь это интересно, рассказывать BZ> подробнее? Конечно, интересно. И еще как. А JAR - ты имеешь ввиду использование словаря английских сочетаний или еще что-то (меня тоже не было в феврале-марте)? Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Igor Pavlov 2:5020/400 01 Jul 98 21:12:57 To : All Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы From: "Igor Pavlov" <igorp@albea.rb.ru> Привет Булат! Bulat Ziganshin wrote in message <899154545@p26.f26.n5093.z2.ftn>... > Общими усилиями разломаем и cabarc скоро, как jar разломали :) Я, кстати, в >июне разобрался в его поиске, он использует сочетание хеширования с двоичными >деревьями, и похоже подбирает строки с конца блока. Вот не знаю, кому-нибудь это >интересно, рассказывать подробнее? Мне интересно. Рассказывай и подробнее. Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Andrew Kuksov 2:5030/533.4 01 Jul 98 23:28:51 To : Vadim Yoockin Subj : Пpо сжатие и вообще ... ;-) Vadim, ты меня уввввважаешшшшь? Ик! ;*) А Вы знаете, _ЧТО_ Vadim Yoockin сказал Sergey Erokhin? #8-[ ] VY> Знатоки BWT советуют брать первый столбец, утверждая, что VY> там сплошные последовательности символов, и что, якобы, VY> сжимать этот столбец одно удовольствие :) VY> Булат Зиганшин запретил брать второй столбец своим контрпримером VY> '000101', но остальные столбцы еще никем опорочены :) Сpазу попpошу ногами не бить :) - ~0 в compression. А почему не сжать по всем столбцам, а потом выбpать, где кpуче сжатие и сохpанить в аpхиве инфоpмацию, что сжимали мы по XX столбцу? Если тоpмознуто, то пусть это будет, скажем, "паpаноидальное" сжатие?:) Гоpячий pусский паpень Andrew Kuksov. [Team Krivye Ruki] --- В аpмии матом не pугаются, в аpмии матом говоpят. * Origin: Дpуг познается в бидэ. (2:5030/533.4) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 02 Jul 98 11:03:10 To : Vadim Yoockin Subj : Re: Пpо сжатие и вообще ... ;-) @RealName: Leonid Broukhis From: leob@asylum.mailcom.com (Leonid Broukhis) In article <899234755@p50.f1042.n5020.z2.fidonet.ftn>, Vadim Yoockin wrote: > SE> Теперь возьмем последний столбец отсортированной таблицы (так в > SE> BWT, хотя в принципе можно любой, а IMHO лучше второй), запишем его > >Знатоки BWT советуют брать первый столбец, утверждая, что >там сплошные последовательности символов, и что, якобы, >сжимать этот столбец одно удовольствие :) > Булат Зиганшин запретил брать второй столбец своим контрпримером >'000101', но остальные столбцы еще никем опорочены :) ST берет второй столбец, и горя не знает - потому что сортирует не по значениям символов. Так что дело не столько в номере столбца, сколько в том, как этот столбец был отсортирован. Leo PS. Вырожденный случай BWT/ST - сортировать по позициям в исходном буфере, начиная с первого столбца, и записать первый столбец. :-) :-) --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 02 Jul 98 11:55:00 To : Vadim Yoockin Subj : BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Wednesday July 01 1998, Vadim Yoockin writes to Bulat Ziganshin: VY> Ты вот скажи, почему EXP в 2.5 раз сжимает быстрее BZIP2'a? VY> Простая перекомпиляция под Watcom ускорила его в 2 раза. А чем exp откомпилирован? Кажется, bcc32i 5.0, я точно не помню. VC 5.0 не пробовал? Он у меня к сожалению в оптимизации запутался :( VY> А откуда VY> еще 0.5 - ты все-таки как-то оптимизировал EXP? Разве что вместо putc() использовал *p++=c, p>BUFFER_END && write() Ты ведь про скорость упаковки говоришь? Hа ней это уж вовсе несущественно. Вот unarjz входной буфер вообще pop'ом читал. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Alex Krestinov 2:50/720.50 02 Jul 98 19:26:44 To : All Subj : PCX Привет, All. Who know the format of PCX-file??? Кто знает формат PCX файлов??? * Crossposted in PASCAL * Crossposted in RU.COMPRESS Hа сегодня все, All. Krestinov Alexander AKA Колумб --- Enilraet on * Origin: Скажем их Интер ЕТу наше российское ИнтерДА... (2:50/720.50) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 03 Jul 98 07:18:49 To : Vadim Yoockin Subj : RAR/2 bug Hello, Vadim! Среда Июль 01 1998 20:26, Vadim Yoockin wrote to Vadim Vygovsky: VV>> Тогда наверняка влияние размера строки сказывается в случае, VV>> когда значительную часть файла составляют VV>> повторяющиеся последовательности размером в несколько десятков VV>> Kb. Конкретно - я замечал на файле IMAGE.DAT - (образ системных VV>> областей диска, создаваемый утилькой IMAGE.EXE, но(!) только из VV>> NU не новее 8.0 для DOS/Win) - там подряд идут 2 копии FAT, и UC VV>> кроет Rar примерно вдвое. VY> Вадь, это вряд ли сказывается размер строки. Чтобы отделить влияние VY> фактора длинной строки от дальнобойных свойств словаря UC, достаточно VY> сжать файл, состоящего из двух одинаковых случайных достаточно длинных VY> (но короче 64k!) кусков. Результаты оказываются очень близкими. VY> А вот при превышении 64k проявляется ограниченность окна досовского VY> RAR'a. VY> Попробуй, кстати, напустить на image.dat WinRAR (RAR/OS2, VY> консольный RAR) с хорошим -md. Именно его и кроет вне зависимости от словаря. WBR, Vadim З.Ы. 2All Я с завтрашнего дня в отпуску - убываю на родину Rar'а (и свою). --- Оглоед 3.00.Beta3+ * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Moderator of ru compress 2:5020/500 03 Jul 98 08:33:40 To : Alex Krestinov Subj : moderatorial [+] 02 Jul 98 20:26, Alex Krestinov wrote to All: AK> Who know the format of PCX-file??? AK> Кто знает формат PCX файлов??? [+] offtopic. Vsevolod, moderator of ru.compress --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Moderator of ru.compress 2:5020/500 03 Jul 98 10:36:53 To : All Subj : rules Пpавила конфеpенции RU.COMPRESS Редакция от 15.12.97 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Тематика конфеpенции - сжатие и архивирование данных. Разрешается: - обсуждение методов, алгоритмов архивации и сжатия данных. - обсуждение [под]программ, реализующих сжатие данных. - анонсирование новых методов и программ сжатия данных (при этом _сразу_же_ необходимо давать информацию о возможности или HЕвозможности их получения). Запрещается: + _поиск_ программных продуктов, в том числе, имеющих отношение к тематике конференции; для этого обращайтесь в конференции *.FILEECHO; + обсуждение использования архиваторов, в аспектах не имеющих прямого отношения к методам и алгоритмам; то есть, если у кого-то что-то виснет/глючит/и т.п. - обсуждайте это в SU.SOFT, RU.BUG и т.п. Также не разрешаются: + личная переписка или сообщения не по теме конференции (offtopic), а также сообщения на темы, для которых есть специализированные конференции + черезмерное цитирование и/или "украшательство" сообщений - приветствие, пролог, подпись и эпилог не должны занимать в сумме больше пяти строк; не цитируйте их и служебную информацию - origin, tearline, rfc, kludges, path, seen-by и т.п. * непропечатывание в письме русской буквы 'H' - она _должна_ заменяться на соответствующую по начертанию латинскую букву + искажение/несоответствие технической информации сообщения, в том числе - поле 'To:' должно соответствовать адресату (нельзя писать 'To: All', если в письме вы обращаетесь к конкретному человеку) адрес отправителя должен соответствовать другим атрибутам сообщения (msgid, path, поле 'From:' и т.д.) + использование "вb1kpyTAss0в" или языка, отличного от русского/английского + реклама и/или публикация коммерческой информации ! призывы к экстремистским акциям, хулиганским действиям, нарушению законов + персональная атака, неконструктивные споры, использование грубых/ нецензурных/оскорбительных выражений * неконструктивные письма - к таким относятся сообщения типа "и мне", "я тоже так думаю", "согласен", "знаю, но вам не скажу", "есть, но не дам", "кругом козлы!" и т.п. + пропуск писем из сетей, не имеющих разрешения на гейтование конференции + посылка без предварительного разрешения модератора больших (занимающих больше одного обычного письма) файлов в закодированном (UUE) виде ! самовольное модерирование и/или обсуждение действий модератора в эхе + обсуждение тем, которые [временно] запрещены к обсуждению: <на данный момент таких тем нет> Виды предупреждений: * простое предупреждение, их может быть неопределенно много, но накопленные звездочки *могут* заменяться на плюсы в соотношении 3:1 + серьезное предупреждение, их может быть не больше трех за полгода, вместо четвертого плюса вы получите [!]. ! отключение от конференции на срок от одного месяца до бесконечности. Обратите внимание, что нарушение нарушению рознь и вы можете заработать [!] с первого раза. С предварительного согласия модератора возможна подача конференции в другие сети, но ответственность за *все* нарушения правил читателями из другой сети будет нести FidoNet-узел, через который сообщения из этой другой сети попадают в FidoNet. Hастоящие правила периодически (не реже чем ежемесячно) публикуются в конференции и могут быть изменены без предварительного уведомления. Hовые правила вступают в силу через неделю после первого опубликования. Всю переписку с модератором можно вести _только_ нетмейлом. Конференция создана в ноябре 1993 года ее текущим модератором. Модеpатоp: Vsevolod Fedotov (Всеволод Федотов) Адpес модеpатоpа: 2:5020/500@fidonet --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Moderator of aUtlComp/aDevComp 2:5020/500 03 Jul 98 10:37:28 To : All Subj : rules ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Правила файловых конференций Редакция от 24.10.97 aUtlComp, aDevComp ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Данные файловые конференции предназначены для распространения - законченного программного обеспечения (aUtlComp) - исходных текстов алгоритмов/программ и другой информации, ориенти- рованной на разработчиков (aDevComp) так или иначе связанных со сжатием и/или архивированием данных. Данные файловые конференции являются постмодерируемыми с установленным лимитом траффика. Это означает, что любой подписчик может эпизодически отправлять в конференцию соответствующие ее тематике файлы без предва- рительного разрешения и/или уведомления модератора, если при этом от одного отправителя поступает не более 1.5 Мб в сутки и не более 15 Мб в месяц. С предварительного согласия модератора разрешается превышение лимита. Регулярные (периодические) публикации также необходимо предварительно согласовать с модератором. Помещаемые в данные файловые конференции материалы не должны нарушать действующего законодательства ни по содержанию публикуемых материалов, ни по самому факту публикации. Кроме того, запрещается: - использование файловых конференций в целях извлечения коммерческой выгоды в любой форме; - нарушение целостности данных и/или атрибутов публикуемых материалов а также служебной сопровождающей информации; - гейтование конференции в другие сети без разрешения модератора. Факт подписки на данные файловые конференции автоматически означает согласие с действующими правилами и обязательство их соблюдать. Модератор может изменить текущие правила по собственному усмотрению, в этом случае если по истечении недели подписчик не прекратил подписку на данные конференции, то это автоматически означает согласие с новыми правилами. Вопросы, связанные с данными файловыми конференциями, можно обсуждать с модератором только с помощью netmail. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Модератор: Vsevolod Fedotov (Всеволод Федотов) Адрес: 2:5020/500@fidonet, vsf@usa.net ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 03 Jul 98 19:28:47 To : Leonid Broukhis Subj : Re: Пpо сжатие и вообще ... ;-) Пpиветствую, Leonid! 02 Jul 98, Leonid Broukhis писал к Vadim Yoockin: > SE> Теперь возьмем последний столбец отсортированной таблицы (так в > SE> BWT, хотя в принципе можно любой, а IMHO лучше второй), запишем его > >Знатоки BWT советуют брать первый столбец, утверждая, что >там сплошные последовательности символов, и что, якобы, >сжимать этот столбец одно удовольствие :) > Булат Зиганшин запретил брать второй столбец своим контрпримером >'000101', но остальные столбцы еще никем опорочены :) LB> ST берет второй столбец, и горя не знает - потому что сортирует не LB> по значениям символов. Так что дело не столько в номере столбца, LB> сколько в том, как этот столбец был отсортирован. Так то ж ST. Будучи частным случаем ST (как выяснилось позже), оригинальный BWT себе такого не позволял. LB> PS. Вырожденный случай BWT/ST - сортировать по позициям в исходном LB> буфере, начиная с первого столбца, и записать первый столбец. :-) ^^^^^^^^^^^^^^^^^^^^^^^^^^ Вот эта фраза вроде лишняя, а то будет сортировка от ST(1), а выход - от ST(0) :) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 04 Jul 98 11:15:16 To : Bulat Ziganshin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Bulat! Было, <Понедельник Июнь 29 1998>, когда Bulat Ziganshin писал к Vadim Yoockin BZ> * Crossposted in RU.COMPRESS BZ> Hello Vadim! BZ> Thursday June 11 1998, Vadim Yoockin writes to dmitry bortoq: db>>> сжимaемые дaнные. попpобуй взять cabarc и пожaть кaкую-нибудь db>>> тaбличку (особенно с большой длиной зaписи) и сpaвнить db>>> pезультaты с pезультaтaми дpугих apхивaтоpов (мaлтимедийное db>>> сжaтие конечно нужно отключить - у кого оно есть). VY>> Ага. Ты прав. Еще cabarc ловко обрабатывает и упорядоченные VY>> данные внутри EXE. Что интересно, IMP делает тоже самое. VY>> Как-то под впечатлением от cabarc'a я написал небольшой VY>> препроцессор для EXE на принципе run-encoding. Размер архива от VY>> cabarc'a и imp'a от него только вырос, а, например, rar'овский VY>> здорово похудел: BZ> Меня не было в июне.... BZ> Что за препроцессинг, объясни плиз на пальцах? VY>> Ты ведь статистику получал через makecab (вроде в самом cabarc'e VY>> я этого не видел)? Там-то видно, что он считывает по 32768 VY>> байтов, а на выход может писать по нескольку раз за один VY>> считанный блок (метод LZX, конечно). BZ> Общими усилиями разломаем и cabarc скоро, как jar разломали :) Я, BZ> кстати, в июне разобрался в его поиске, он использует сочетание BZ> хеширования с двоичными деревьями, и похоже подбирает строки с конца BZ> блока. Вот не знаю, кому-нибудь это интересно, рассказывать подробнее? BZ> Bulat Расскажи plz. С наилучшими пoжеланиями , Denis. ... С утpа пpинял -- весь день свободный --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 04 Jul 98 11:18:24 To : Bulat Ziganshin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Bulat! Было, <Понедельник Июнь 29 1998>, когда Bulat Ziganshin писал к Vadim Yoockin BZ> Как он использует результаты сортировки предыдущего пакета?? Все, Вот как раз я недавно разбирался с bzip2[big thanx to Vadim Yoockin for posting of bzip2]. Там я увидел следующее: сортируется минимальный _однобуквенный_пакет_. Чтобы было понятнее, покажу на примере. Пусь минимальный по количеству ссылок пакет - это 0x4a. Сортируются естественно внутри него 2-х байтовые пакеты ви да [0x4a ???], где ??? - все возможные байты в bwt-буфере после 0x4a. Дальше подбираются _2-х_байтовые_ пакеты вида [??? 0x4a], где ??? - все воз можные байты, стоящие перед 0x4a. Hо так как у нас [0x4a ???] были уже отсор- тированы, то при добавлении спереди байта полученные строки тоже будут от- сортированы [заметь, что _нигде_ в других пакетах не будет строк вида [0x4a ???] кроме как в только что отсортированном], соответственно при добавлении спереди байта мы получим _полный_ пакет [??? 0x4a]]. Далее каждый пакет вида [??? 0x4a] помечается как уже отсортированный. Чтобы было веселее[в смысле быстрее] сортировать, попутно строятся квадранты[это когда отсортированные пакеты помечаются числами по возрастанию - что бы помочь функции FullGTu в случае нападения на них сразу получить результат сравнения]. Кстати, попро буй отключить квадранты в исходнике и на неоднородных файлах[где имеет место ненормально много длинных сравнений - например squish-базы] получишь падение в быстродействии до 2-х раз. В принципе я как раз и хочу подменить в bzip2 квадранты на acm. Посмотрим что из этого выйдет.. С наилучшими пoжеланиями , Michael. ... Во имя овса,и сена, и свиного уха.Алюминий. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 04 Jul 98 11:38:03 To : Vadim Yoockin Subj : Re: BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Vadim! Было, <Среда Июль 01 1998>, когда Vadim Yoockin писал к Bulat Ziganshin VY> Пpиветствую, Bulat! VY> 29 Jun 98, Bulat Ziganshin писал к Vadim Yoockin: VY>>> Тем более, что BZIP, например, на типичных файлах не так часто VY>>> страдает от длинных сравнений. Hапомню, что сначала он делит все VY>>> строки по пакетам (поразрядная сортировка - очень быстро). Затем VY>>> сортирует наименьший пакет. Затем - чуть больший, причем VY>>> использует результаты сортировки предыдущего пакета... Хотя, к VY>>> строкам типа 'abab...' он, конечно, чувствителен. BZ>> Как он использует результаты сортировки предыдущего пакета?? BZ>> Все, видишь ли, хочу разобраться в своем exp'е ;) VY> После сортировки очередного большого пакета, все его индексы делятся VY> на не более чем 65534 квадранта. Hомера этих квадрантов записываются VY> в соответствующий массив, элементы которого соответствуют индексам VY> отсортированного пакета. VY> Эти значения используются при сортировке строк. После того, VY> как нам надоест сравнивать строки в лоб (6 попыток), мы пытаемся VY> воспользоваться квадрантами. VY> Ты вот скажи, почему EXP в 2.5 раз сжимает быстрее BZIP2'a? VY> Простая перекомпиляция под Watcom ускорила его в 2 раза. А откуда VY> еще 0.5 - ты все-таки как-то оптимизировал EXP? Я конечно не видел exp, но могу предположить, что адресовать массивы по индексу, а не воспользоваться типа uchar *ptr; for(int i=0;i<n;++i) ptr++, а не ptr[i] будет медленнее(ведь наверно еще требуется каждый раз прибавлять к ptr индекс). Хотя я может быть и не прав ибо не часто дебужировал watcom-ов ский exe-шник в asm-е. Хотя это вообще-то offtopic. VY> Всего доброго. Vadim Yoockin VY> ... 2.000.000 Lemmings can't be wrong. С наилучшими пoжеланиями , Denis. ... Что естественно-то не без оргазма. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9)
Предыдущий блок Следующий блок Вернуться в индекс