Наиболее эффективный алгоритм сжатия

← →
Inovet © (2012-10-17 20:24) [40]

> [37] брат Птибурдукова (17.10.12 20:08)
> Сколько отвести под эти длины? Байт, два, четыре? Будет ли экономия? ;-)

Автор умалчивает. В любом случае меньне, чем в битовых масках.

← →
MBo © (2012-10-17 20:24) [41]

Табличный метод без сжатия будет обеспечивать 7 бит на строку, со сжатием - скорее всего около 5

← →
брат Птибурдукова (2012-10-17 20:32) [42]

> В любом случае меньне, чем в битовых масках.
Не знаю, о каких битовых масках речь... Предлагаемый мною метод занимает 3 бита * длину контура + координаты начальной точки (4 байта, скажем)

← →
Inovet © (2012-10-17 20:36) [43]

> [42] брат Птибурдукова (17.10.12 20:32)
> > В любом случае меньне, чем в битовых масках.
> Не знаю, о каких битовых масках речь...

Не масок - полей.

← →
брат Птибурдукова (2012-10-17 20:43) [44]

А нет ножек — нет и мультиков. О чём речь? :о)

← →
Inovet © (2012-10-17 20:46) [45]

> [42] брат Птибурдукова (17.10.12 20:32)
> метод занимает 3 бита * длину контура

здесь 1 бита хватит - влево и вверх или сразу 2 для обеих сторон этого изображения. Но может в итоге и больше исходного получиться.

← →
Sha © (2012-10-17 21:14) [46]

> MBo © (17.10.12 20:24) [41]
> Табличный метод без сжатия будет обеспечивать 7 бит на строку,
> со сжатием - скорее всего около 5

У него 6*9=54 варианта всего. Без сжатия получается 6 бит на строку (в один int64 влезет 11 строк).

← →
Eraser © (2012-10-17 21:16) [47]

> xayam © (17.10.12 18:32)

LZMA

← →
Inovet © (2012-10-17 21:33) [48]

> [46] Sha © (17.10.12 21:14)
> У него 6*9=54 варианта всего.

5*8=40

← →
Sha © (2012-10-17 21:34) [49]

> Inovet © (17.10.12 21:33) [48]

[0..5,0..8]

← →
Inovet © (2012-10-17 21:45) [50]

> [49] Sha © (17.10.12 21:34)
> [0..5,0..8]

0 и 0 всегда есть, их выбрасываем.

← →
Sha © (2012-10-17 21:53) [51]

> Inovet © (17.10.12 21:45) [50]

слева может быть любое количество точек от нуля до 5, итого 6 возможностей,
справа может быть любое количество точек от нуля до 8, итого 9 возможностей,
всего 6*9=54 комбинаций.

← →
xayam © (2012-10-17 21:58) [52]

Так что имеем :)

хаффман, LZW, RLE, LZMA...

Вот такое ещё нарыл, надо потестить:

http://www.cl.cam.ac.uk/~mgk25/jbigkit/
http://ru.wikipedia.org/wiki/JBIG

← →
xayam © (2012-10-17 22:00) [53]

> JBIG

Алгоритм разработан группой экспертов ISO (Joint Bi-level Experts Group) специально для сжатия однобитных черно-белых изображений, например, факсов или отсканированных документов. В принципе, может применяться и к 2-х, и к 4-х битовым картинкам. При этом алгоритм разбивает их на отдельные битовые плоскости. JBIG позволяет управлять такими параметрами, как порядок разбиения изображения на битовые плоскости, ширина полос в изображении, уровни масштабирования. Последняя возможность позволяет легко ориентироваться в базе больших по размерам изображений, просматривая сначала их уменьшенные копии. Настраивая эти параметры, можно использовать описанный выше эффект “огрубленного изображения” при получении изображения по сети или по любому другому каналу, пропускная способность которого мала по сравнению с возможностями процессора. Распаковываться изображение на экране будет постепенно, как бы медленно “проявляясь”. При этом человек начинает анализировать картинку задолго до конца процесса разархивации.
Алгоритм построен на базе Q-кодировщика, патентом на который владеет IBM. Q-кодер, так же как и алгоритм Хаффмана, использует для чаще появляющихся символов короткие цепочки, а для реже появляющихся - длинные. Однако, в отличие от него, в алгоритме используются и последовательности символов.

(c) Интернет

← →
Inovet © (2012-10-17 22:04) [54]

> [51] Sha © (17.10.12 21:53)

Ты не понял, 2 центральных всегда есть, их можно не кодировать. Другое дело что.

> [18] xayam © (17.10.12 19:27)
> наверное, наиболее вероятная ширина = 20 пикселам - 2 центральных = 18

Сколько из них лево, сколько право не уточняется. Но прицип тот же. Для 5 и 8 в 10 байт уложим 64 строки.

← →
QAZ5 (2012-10-17 22:07) [55]

если эти квадраты есть по всей длинне значит они вообще не нужны и незачем их хранить

← →
Sha © (2012-10-17 22:09) [56]

> Inovet © (17.10.12 22:04) [54]

я считал точки на картинках из [12], а ты где?

← →
Inovet © (2012-10-17 22:15) [57]

> [56] Sha © (17.10.12 22:09)
> я считал точки на картинках из [12], а ты где?

Картинка № 3 из них.

← →
Sha © (2012-10-17 22:22) [58]

> Inovet © (17.10.12 22:15) [57]
> Картинка № 3 из них.

Она получена удалением центра, верно?

В ней:
В строке 5 слева 0 точек, верно?
В строке 6 слева 5 точек, верно?
Итого слева 6 вариантов, верно?
В строке 7 справа 0 точек, верно?
В строке 9 справа 8 точек, верно?
Итого справа 9 вариантов, верно?
Всего 54 варианта, верно?

Что не так?

← →
Inovet © (2012-10-17 22:58) [59]

> [58] Sha © (17.10.12 22:22)
> Что не так?

Всё, понял.:)))

← →
Sha © (2012-10-17 23:09) [60]

> Inovet © (17.10.12 22:04) [54]
> Для 5 и 8 в 10 байт уложим 64 строки.

Меньше 2 бит на строку?
Строки не помнутся? )

← →
Inovet © (2012-10-18 00:33) [61]

> [60] Sha © (17.10.12 23:09)
> Строки не помнутся? )

Маловато будет.:)

В общем примерно 5.3 бита на строку. значит в 64 бита поместится 12 строк и немногг лишнего останется. Если кодировать всю последовательность непрерывным блоком, то можно оптимально заполнить.

← →
Inovet © (2012-10-18 00:47) [62]

> [61] Inovet © (18.10.12 00:33)
> В общем примерно 5.3 бита на строку.

Это для 40
для 54 получается 5.8. Значит на 64 бита 11 строк и останется больше.

← →
Sha © (2012-10-18 12:08) [63]

> xayam

Ну вот, относительно хранения таблицы без сжатия
консенсус вроде достигнут (64 бита на 11 строк)

Для выбора способа сжатия таблицы надо знать,
что это такое, т.е. иметь ответы на следующие вопросы:

1) последовательные строки не зависимы друг от друга?

2) значения в одной строке слева и справа не зависимы?

3) все комбинации значений лево-право допустимы?

4) все допустимые комбинации значений лево-право равновероятны?

← →
xayam © (2012-10-18 13:58) [64]

> 1) последовательные строки не зависимы друг от друга?
> 2) значения в одной строке слева и справа не зависимы?

"зависимость" есть. Но она выражена только тем что нужно сохранить:
1) центр
2) последовательность при движении от левого верхнего угла вправо (по ширине), и сверху вниз (по высоте)

Скорей всего здесь не понятно будет, попробую объяснить.
На самом деле центр создан искусственно (добавлением пустого пространства), в исходных данных его нет.
То есть перепишу, для примера, первые пять строк с картинки http://ic.pics.livejournal.com/xayam/26173943/14265/14265_original.png по-другому:
------------------
4 3
2 1
3 1
2 2
1 4
------------------
[пробелом ^ здесь показан центр]
И суммы первых пять строк:
------------------
7
3
4
4
5
------------------
На картинке эти теперь уже длины отрезков отцентрированы, чтобы можно было при распаковке разбить эти суммы на исходные слагаемые.

Должно быть понятно :)

> 3) все комбинации значений лево-право допустимы?

да

> 4) все допустимые комбинации значений лево-право равновероятны?

нет. Чем больше число - тем меньше вероятность его появления, и наоборот.
То есть единица (слева и справа от центра) - чаще всего встречается, двойки - реже, ... , 10 - очень редко (одна на 500 строк в среднем ), 11 - ещё реже (на текстовых данных вообще не встречал, на бинарных возможно), ... (неограниченно)

← →
dmk © (2012-10-18 13:58) [65]

Делал как то конвертер Packbits TIFF в Pack16 для рипов. Pack16 - это компрессия RLE16 с предварительной обработкой строк. Каждая строка XOR"ится с предыдущей. Коэффициент сжатия 50-200 раз в зависимости от содержимого. Без потерь. Если заинтересует - могу поделится исходниками. Все равно без дела валяются.

← →
xayam © (2012-10-18 14:05) [66]

> могу поделится исходниками

лучше принцип работы алгоритма на пальцах объяснить можете ? :)

← →
xayam © (2012-10-18 14:20) [67]

> ------------------
> 4 3
> 2 1
> 3 1
> 2 2
> 1 4
> ------------------

в исходных данных была просто строка: 4 3 2 1 3 1 2 2 1 4
потом её оформил в одну (при желании можно сделать больше одной нити) вертикальную нить:
------------------
4 3
2 1
3 1
2 2
1 4
------------------ (здесь нужно сохранить только последовательность)
потом сложил:
------------------
7
3
4
4
5
------------------ (здесь нужно сохранить ещё и центр, иначе обратное преобразование на слагаемые сделать не получится)
далее для визуализации этого, числа взял за длины черно-белых отрезков и получилась картинка:
http://ic.pics.livejournal.com/xayam/26173943/14642/14642_original.png

← →
xayam © (2012-10-18 14:21) [68]

> и получилась картинка:
> http://ic.pics.livejournal.com/xayam/26173943/14642/14642_original.
> png

эта то есть
http://ic.pics.livejournal.com/xayam/26173943/14265/14265_original.png

Слово := ЧитаемСлово(Исходный_Массив); if Слово > $7FFF then {Если бит 15 установлен в 1, то это счётчик однородных данных} begin Кол-во однородных слов := Слово xor $8000; {Кол-во повторяющихся слов} Слово := ЧитаемСлово(Исходный_Массив); Пишем_в_массив_картинки(Слово, Кол-во однородных слов); end else begin {Если бит 15 установлен в 0, то это счётчик кол-ва разнородных слов данных следующих сразу за счётчиком} Кол-во слов := Слово;{кол-во слов данных} Пишем_в_массив_картинки(Строку из слов(Исходный_Массив), длиной из Кол-во слов); end;

Потом XOR по всем скан-линиям сверху вниз.
Врхнюю со следующей, получившуюся со следующей и так до последней.
Получаем изображение.

При упаковке обратный алгоритм. Сначала XOR снизу вверх по всем линиям кроме первой,
а полученный массив упаковываем как RLE16.
Вроде как после XOR больше однородных данных получается, поэтому упаковывает хорошо.

676 мб битмап упаковался при:
Packbits - 128 Мб
RLE16 + XOR - 82.8 Мб
LZW - 38.8 Мб
ZIP - 34 Мб

А вообще есть еще CCIT Group 4. Вроде еще лучше сжимает.
Туту подробнее: http://www.compression.ru/download/i_blless.html

> 4 3
> 2 1
> 3 1
> 2 2
> 1 4
> ...
> потом сложил:

сложно как... зачем складывать?
просто в упакованный байт... старшая часть "рог" налево, младшая направо, + лишнее (стержень из 2х в середине) выкинуть
получится $32 $10 $20 $11 $03 ... это если "рога" не превышают 15 (или 16 со "стержнем")
а уже эту последовательность архивировать... что теоретически уберет избыточность (о чем говорили выше) из 2х бит на байт, + какой нибудь дополнительный профит от, если будут, повторений (хорошо жмутся, в любом количестве, 1 число на количество и второе на значение).

> xayam © (18.10.12 13:58) [64]

тогда тебе лучше всего подойдет вариант MBo [19]

или самопальный вариант использующий короткие коды для частых строк,
например (очень сырой прототип):

type Tpts= array of TPoint; Tpks= array of byte; function Pack(pts: Tpts): Tpks; var i, j, count, pkslen, buflen, x, y, buf: integer; pks: Tpks; procedure Put(bitcount, data: integer); begin; buf:=buf shl bitcount or data; inc(buflen,bitcount); if buflen>=8 then begin; dec(buflen,8); pks[pkslen]:=buf shr buflen; inc(pkslen); end; end; begin; count:=Length(pts); SetLength(pks,count+4); j:=count; for i:=0 to 3 do begin; pks[i]:=j; j:=j shr 8; end; pkslen:=4; buflen:=0; for i:=0 to count-1 do begin; x:=pts[i].x; if x<0 then x:=0; if x>5 then x:=5; y:=pts[i].y; if y<0 then y:=0; if y>8 then y:=8; if y>=7 then begin; Put(5,30+(y-7)); Put(3,x); end else if x>=4 then begin; Put(5,28+(x-4)); Put(3,y); end else Put(5,4*y+x); end; if buflen>0 then Put(8-buflen,0); SetLength(pks,pkslen); Result:=pks; end; function Unpack(pks: Tpks): Tpts; var i, count, pkslen, buflen, x, y, z, buf: integer; pts: Tpts; function Get(bitcount: integer): integer; const mask: array[0..8] of integer= (0, 1, 3, 7, 15, 31, 63, 127, 255); begin; if buflen<bitcount then begin; buf:=buf shl 8 or pks[pkslen]; inc(pkslen); inc(buflen,8); end; Result:=buf shr (buflen-bitcount) and mask[bitcount]; dec(buflen,bitcount); end; begin; count:=0; for i:=3 downto 0 do count:=count shl 8 or pks[i]; SetLength(pts,count); pkslen:=4; buflen:=0; for i:=0 to count-1 do begin; z:=Get(5); if z>=30 then begin; y:=7+(z-30); x:=Get(3); end else if z>=28 then begin; x:=4+(z-28); y:=Get(3); end else begin; y:=z div 4; x:=z mod 4; end; pts[i].x:=x; pts[i].y:=y; end; Result:=pts; end; procedure TForm1.Button1Click(Sender: TObject); var pts: Tpts; pks: Tpks; i: integer; begin; SetLength(pts,80); pts[0].x:=1; pts[0].y:=2; pts[1].x:=3; pts[1].y:=4; pts[2].x:=5; pts[2].y:=6; pts[3].x:=0; pts[3].y:=7; pts[4].x:=1; pts[4].y:=8; pts[5].x:=2; pts[5].y:=2; pts[6].x:=3; pts[6].y:=3; pts[7].x:=4; pts[7].y:=4; for i:=8 to Length(pts)-1 do pts[i]:=pts[i mod 8]; pks:=Pack(pts); Memo1.Lines.Clear; Memo1.Lines.Add(Format("%d %d",[Length(pts), Length(pks)])); pts:=Unpack(pks); for i:=0 to Length(pts)-1 do Memo1.Lines.Add(Format("[%d] %d %d",[i, pts[i].x, pts[i].y])); end;

> очень сырой прототип
ну, очень, очень... -
SetLength(pts, 80);
дает (первая строка с Length(pts), Length(pks))
80 69
80 не сжато, 69 сжато, а простая реализация "упакованного байта" ([71]) даст 80 40.

> sniknik © (18.10.12 22:55) [73]
> простая реализация "упакованного байта" ([71]) даст 80 40.

Простая реализация "упакованного байта" ([71]) даст 80 80.

В идеале, когда нет "больших значений"
алгоритм [72] упакует одну строку в 5 бит,
алгоритм [73] упакует одну строку в 8 бит.

А в худшем случае, когда все строки "большие",
оба алгоритма кодируют одну строку одним байтом.

> Простая реализация "упакованного байта" ([71]) даст 80 80.
шутить изволите?
$FF - 15:15
+ 1 обязательный в данном случае для каждого полубайта.

> В идеале, когда нет "больших значений"
на то и рассчитано -
> ... это если "рога" не превышают 15 (или 16 со "стержнем")

> sniknik © (19.10.12 00:05) [76]
> шутить изволите?

Серьезно.
Возможно, ты не заметил, что в примере 80 - это количество строк, т.е. пар чисел.
Алгоритм [73] упакует их в 80 байтов. И получит результат 80 80.
Разве нет?

Насчет большей частоты "малых" строк автор темы говорил выше.
На это и сделан упор в алгоритме [72]. Ну, так это ведь здорово, правда?

Конечно, в [72] жестко запаяны многие константы. Потому он и прототип.
Типа информация к размышлению о своем велосипеде.
Что MBo [19] будет скорее всего лучше я уже сказал.

> Алгоритм [73] упакует их в 80 байтов. И получит результат 80 80.
в 73 нет алгоритма, он в [71] на которую в [73] только отссылка.

еще там кусочки твоей проги, и вывод почему алгоритм плохой

> Разве нет?
а посмотрим на твоих же данных (примере).
pts[0].x:=1; pts[0].y:=2; pts[1].x:=3; pts[1].y:=4; pts[2].x:=5; pts[2].y:=6; pts[3].x:=0; pts[3].y:=7; pts[4].x:=1; pts[4].y:=8; pts[5].x:=2; pts[5].y:=2; pts[6].x:=3; pts[6].y:=3; pts[7].x:=4; pts[7].y:=4;
т.е. в байтах будет 1234560718223344 т.е 16 байт тут (которые ты после растягиваешь на весь массив)
в упакованных байтах это будет (не будем учитывать центр, для примера)
$12$34$56$07$18$22$33$44 для наглядности в hex, размер 8 байт.
в 2 раза, т.е. 80 тоже, по аналогии, станет 40.

> а простая реализация
"сжатие" тогда будет -
ar:= Byte(Point.X) shl 4 + Byte(Point.Y);
"расжатие"
Point.X:= ar shr 4; Point.Y:= ar and $0F;
и весь код, ну только циклом сделать.

1 пара чисел переходит в 1 байт, значит 80 пар перейдут в 80 байт.
Откуда у тебя 40?

Наиболее эффективный алгоритм сжатия Найти похожие ветки