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

← →
xayam © (2012-10-17 18:32) [0]

для черно-белых изображений типа этого

[

каждый пиксел обозначен черным квадратиком
красный линией обозначен центр симметрии
зелёный цвет, чтобы лучше было видно

очень длинное по высоте означает порядка 10^6 и больше...

]

http://ic.pics.livejournal.com/xayam/26173943/14570/14570_original.png

?

← →
Kerk © (2012-10-17 18:37) [1]

Сжатие с потерями или без?

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

В своё время препод предлагал вариант: сохраняем координаты условного начала фигуры, бежим по границе, каждый пиксель обозначаем направлением (3 бита): вверх, вниз, вверх-налево и т.д.

← →
xayam © (2012-10-17 18:47) [3]

> Сжатие с потерями или без?

БЕЗ

← →
xayam © (2012-10-17 19:04) [4]

> сохраняем координаты условного начала фигуры, бежим по границе,
> каждый пиксель обозначаем направлением (3 бита): вверх,
> вниз, вверх-налево

есть ещё идея центральные пикселы вообще "убрать", поскольку этот прямоугольник легко восстановить:

http://ic.pics.livejournal.com/xayam/26173943/14642/14642_original.png

и сжимать это (левая и правые части соединены):

http://ic.pics.livejournal.com/xayam/26173943/14867/14867_original.png

Похоже на японские свечи у трейдеров на фин.рынков, хотя сама инфа к этому никакого отношения не имеет (честно :)

← →
Rouse_ © (2012-10-17 19:06) [5]

> xayam © (17.10.12 18:32)
> для черно-белых изображений типа этого

Ну для начала перевести все это из байтов в биты - сжатие в 8 раз как никак :) А дальше уже можно придумывать.

← →
Rouse_ © (2012-10-17 19:08) [6]

зы: ну с условием что черно-белое изображение без градаций серово, т.е. 0 - белый пиксель, 1 - черный

← →
xayam © (2012-10-17 19:10) [7]

> Ну для начала перевести все это из байтов в биты

я так не думаю, это помешает увидеть суть

← →
xayam © (2012-10-17 19:11) [8]

> из байтов в биты

опс

из битов в байты?

← →
Rouse_ © (2012-10-17 19:12) [9]

> xayam © (17.10.12 19:10) [7]
> я так не думаю, это помешает увидеть суть

Эмм, вообще-то результатом сжатия обычно является практически идеальный "белый шум", т.е. энтропия блока данных при идеальном сжатии равна восьми, при неидеальном, очень близко находится рядом с этим значением. В результирующем блоке увидеть что-то нереально... Или мы не про то говорим?

← →
Rouse_ © (2012-10-17 19:14) [10]

> xayam © (17.10.12 19:11) [8]
>
> > из байтов в биты
>
> опс
>
> из битов в байты?

эээ :))) Нет, из байтов в биты :) Ну например если у тебя блок 8 на 8 кодируется 64 байтами (по 1 на пицсель) то его можно выразить в 8 байт, каждый байт на одну 8-пиксельную строчку :)

← →
xayam © (2012-10-17 19:18) [11]

> Нет, из байтов в биты

чего-то не понял, это же и так уже биты и есть...

черный квадрат = 1 пиксел = бит установлен в 1

← →
xayam © (2012-10-17 19:19) [12]

картинки

http://ic.pics.livejournal.com/xayam/26173943/14265/14265_original.png
http://ic.pics.livejournal.com/xayam/26173943/14642/14642_original.png
http://ic.pics.livejournal.com/xayam/26173943/14867/14867_original.png

это битовые поля УЖЕ!

← →
Rouse_ © (2012-10-17 19:22) [13]

> xayam © (17.10.12 19:18) [11]

Ну ты же не написал как это у тебя хранится.
Смотри:
картинка такая (* -черны, _ - белый)
"*__*__**"
это можно хранить как
const MyLine: array [0..7] of Byte = (1, 0, 0, 1, 0, 0, 1, 1);
А можно как:
const MyLine: Byte = 147; // 1001001

← →
SergeyIT © (2012-10-17 19:22) [14]

Перфолента?

← →
MBo © (2012-10-17 19:22) [15]

ширина какая?

← →
xayam © (2012-10-17 19:23) [16]

> Ну ты же не написал как это у тебя хранится

да это не важно как хранится,

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

← →
Rouse_ © (2012-10-17 19:27) [17]

> xayam © (17.10.12 19:23) [16]
> да это не важно как хранится,

Ну как-же не важно? :)
А алгоритм - тут вариантов не много, хаффман, LZW и RLE

← →
xayam © (2012-10-17 19:27) [18]

> Перфолента?

один из вариантов после японских свечей :)
хотя и на акустич. волну тоже похоже если повернуть на 90 градусов

> ширина какая?

заранее неизвестно, но можно посчитать на небольшом блоке-странице, для больших файлов нереально медленно это, да и не за чем, наверное, наиболее вероятная ширина = 20 пикселам - 2 центральных = 18

← →
MBo © (2012-10-17 19:29) [19]

Если ширина невелика, вариантов немного, и их частота сильно различается, то можно попробовать свести их в таблицу и сжатие Хаффмана.

← →
SergeyIT © (2012-10-17 19:34) [20]

Черные квадраты без пробелов идут - то есть просто строчка длины К сдвинутая на М пикселей?

← →
Inovet © (2012-10-17 19:36) [21]

Судя по картинке, кождая горизонтальная линия непрерывна - т.е. задаётся смещением от центра и длиной, или двумя длинами. Почему сразу так не хранить?

← →
Rouse_ © (2012-10-17 19:38) [22]

А кстати, недавно нашел еще один оригинальный вариант сжатия: http://podrobnosti.ua/technologies/2012/07/27/849624.html

← →
xayam © (2012-10-17 19:38) [23]

> Черные квадраты без пробелов идут

без пробелов

> то есть просто строчка длины К сдвинутая на М пикселей?

да
отцентрировано просто, можно отцентрировать влево или вправо, но так лучше видно имхо

← →
Rouse_ © (2012-10-17 19:39) [24]

Ой не - не то, это крипто, а был еще один вариант, тоже от японской головоломки, блин забыл как называется... щас попробую поискать

← →
Rouse_ © (2012-10-17 19:41) [25]

А во: http://ru.wikipedia.org/wiki/%D0%AF%D0%BF%D0%BE%D0%BD%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D1%80%D0%BE%D1%81%D1%81%D0%B2%D0%BE%D1%80%D0%B4

Сжимается достаточно хорошо, только алгоритм распаковки нужно как обычно написать нормальный :)

← →
xayam © (2012-10-17 19:42) [26]

> да
> отцентрировано просто, можно отцентрировать влево или вправо,
> но так лучше видно имхо

опс, ошибка нельзя влево вправо. Центр нужно знать.

← →
xayam © (2012-10-17 19:50) [27]

> Rouse_ © (17.10.12 19:41) [25]
> Японский кроссворд

интересно. Можно переделать битое поле на несколько таких ниток в ширину, отцентрировать каждую нить,
оформить в квадрат, и такой алгоритм может быть эффективным...

> Сжимается достаточно хорошо

есть код, примеры?

← →
Rouse_ © (2012-10-17 19:52) [28]

> xayam © (17.10.12 19:50) [27]

Сам не писал, но в инете приводили варианты... Сам тоже хочу как время найдется заняться этой темой...

← →
Inovet © (2012-10-17 19:54) [29]

> [27] xayam © (17.10.12 19:50)
> Можно переделать битое поле на несколько таких ниток в ширину

Зачем тебе вообще битовые поля? Это уже избыточная информация. Ты прочитал?

> [21] Inovet © (17.10.12 19:36)

← →
xayam © (2012-10-17 19:55) [30]

> Сам тоже хочу как время найдется заняться этой темой

могу любой файл привести к такому виду :)

скоопирируемся?

← →
xayam © (2012-10-17 19:56) [31]

> Inovet © (17.10.12 19:36) [21]
> Судя по картинке, кождая горизонтальная линия непрерывна
> - т.е. задаётся смещением от центра и длиной, или двумя
> длинами. Почему сразу так не хранить?

вопрос не в "хранить" :)

← →
Inovet © (2012-10-17 20:00) [32]

> [31] xayam © (17.10.12 19:56)
> вопрос не в "хранить" :)

У тебя уже будет вместо 15 бит 4

← →
Inovet © (2012-10-17 20:01) [33]

> [32] Inovet © (17.10.12 20:00)
> 4

или сколько там?

← →
Rouse_ © (2012-10-17 20:02) [34]

> xayam © (17.10.12 19:55) [30]
> скоопирируемся?

:) я бы не против, но это у меня стоит в рабочих планах, т.е. пока начальство отмашку не даст на доработку ядра базы след версии, этим не занимаюсь :)

← →
xayam © (2012-10-17 20:05) [35]

> У тебя уже будет вместо 15 бит 4
> или сколько там?

битовое поле не для хранения, это как бы промежуточное состояние между исходным файлом и сжатым

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

> [35] xayam © (17.10.12 20:05)
> это как бы промежуточное состояние между исходным файлом и сжатым

Почему тогда акцент сделан на сжатие изображения?

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

> есть ещё идея центральные пикселы вообще "убрать"
Ты не понял, центральные пиксели вообще не рассматриваются, мы бежим по контуру фигуры.

> Судя по картинке, кождая горизонтальная линия непрерывна
> - т.е. задаётся смещением от центра и длиной, или двумя
> длинами. Почему сразу так не хранить?
Сколько отвести под эти длины? Байт, два, четыре? Будет ли экономия? ;-)

← →
xayam © (2012-10-17 20:12) [38]

> центральные пиксели вообще не рассматриваются, мы бежим
> по контуру фигуры

я понял, но без центральных пикселей твои приращения могут занимать меньше места...
аналогично этому:

> Сколько отвести под эти длины? Байт, два, четыре? Будет
> ли экономия?

:)

← →
xayam © (2012-10-17 20:15) [39]

> Почему тогда акцент сделан на сжатие изображения?

черно-белого изображения

Почему? Битовое поле слишком заумное словечко :)
черное-белое изображение быстрей доходит

← →
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]

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

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

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

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

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

> xayam

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

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

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

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

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

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

> 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 - ещё реже (на текстовых данных вообще не встречал, на бинарных возможно), ... (неограниченно)

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

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

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

> ------------------
> 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

> и получилась картинка:
> 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?

> значит 80 пар
блин, а считаешь то в программе ты длину массива, а не чисел... не учел. тогда у тебя 160 в 69 архивирует. а "мой" из 160 даст 80, да.

> Откуда у тебя 40?
2 байта упаковывается в 1, сколько не возьми длина уменьшится вдвое.

> а "мой" из 160 даст 80, да.

Ура, тут достигли консенсуса.

> 2 байта упаковывается в 1, сколько не возьми длина уменьшится вдвое.

Беру 80 TPoint"ов, упаковываю в 80 байтов, длина не изменилась.
Консенсус где-то рядом.

← →
han_malign (2012-10-19 12:24) [83]

> Консенсус где-то рядом.

- да что вы паритесь, товарищ с помощью универсальной биекции пытается уменьшить энтропию произвольного набора данных...
А ведь ему уже не раз объясняли, что байт в 7 бит не воткнешь, а из градаций серого - однозначно RGB не восстановишь...

> А ведь ему уже не раз объясняли, что байт в 7 бит не воткнешь

Наполеон говорил, что один араб победит пятерых французов.
Но десять тысяч французов победят пятьдесят тысяч арабов.

В перекладе на наше сие означает:
произвольные 8 бит не воткнешь в 7 - это факт, но 8000 бит упаковать в 7000 бит можно :)

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