Сжатие данных

← →
Kerk © (2015-01-27 14:20) [0]

Есть небольшая задача, в принципе у меня есть некоторые идеи, но вдруг внезапно что-то свежее и лучшее в этой ветке возникнет.

И так.

Есть ASCII-строка текста (достаточно длинная, допустим 42000 символов). Строка представляет собой запись 16ричного числа, то есть она содержит исключительно символы 0-9 и A-F.

Нужно передать эту строку по сети с одного устройства на другое. И тут начинаются ограничения.

Во-первых, максимальный размер пакета - чуть больше 1000 байт, давайте считать, что просто 1000. То есть в принципе можно порезать строку на 42 части и передать. Но тут возникает второе ограничение - качество соединения так себе, поэтому количество пакетов в идеале нужно свести к минимуму.

Возникает логичная весьма идея - сжать данные. Но тут опять есть пара ограничений.

Передавать нужно строго ASCII-строку. Даже если мы сожмем исходную, то результат все равно должен помещаться в ASCII. Понятно, что в полноценной ASCII-строке больше символов, чем 0-9 и A-F, поэтому потенциал для сжатия есть. Еще один нюанс в том, что принимающая сторона - не ПК, а довольно убогое устройство, поэтому разжатие данных не должно требовать сложных алгоритмов.

Вот так. Мысли?

← →
Kilkennycat © (2015-01-27 14:23) [1]

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

← →
MBo © (2015-01-27 14:23) [2]

какое подмножество ASCII-таблицы (из 256) может использоваться?

← →
Eraser © (2015-01-27 14:24) [3]

> Вот так. Мысли?

base64 - первое что приходит на ум, без изобретения велосипедов.

← →
Kerk © (2015-01-27 14:29) [4]

> MBo © (27.01.15 14:23) [2]
>
> какое подмножество ASCII-таблицы (из 256) может использоваться?

Все латинские буквы (оба регистра) и цифры.

← →
brother © (2015-01-27 14:30) [5]

zip сжатие, ну и от повоторв пакета никак не уйти...

← →
junglecat © (2015-01-27 14:31) [6]

> почти три символа

это как? )

← →
Kilkennycat © (2015-01-27 14:32) [7]

> Все латинские буквы (оба регистра) и цифры.

а передаем только большой регистр А-F и цифры?

← →
Kilkennycat © (2015-01-27 14:33) [8]

> junglecat © (27.01.15 14:31) [6]
> > почти три символа
>
> это как? )

работает каждый бит.

← →
Kerk © (2015-01-27 14:33) [9]

> а передаем только большой регистр А-F и цифры?

В исходных данных только большой A-F и цифры.
В запакованном виде могут использоваться большие/маленькие A-F и цифры.

← →
Kerk © (2015-01-27 14:34) [10]

В исходный данных закодировано 16тиричное число, поэтому регистр просто неважен. Можно свести все к upper case (или lower, кому как нравится) без потери информации.

← →
MBo © (2015-01-27 14:43) [11]

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

← →
Jeer © (2015-01-27 15:42) [12]

Тут вступает в силу теория кодов с коррекцией/исправлением ошибок в канале передачи.

Оно надо?

← →
Kilkennycat © (2015-01-27 16:10) [13]

ну, очень небольшое сжатие просто получается:
доступные нам для передачи:
30 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f 50 51 52 53 54 55 56 57 58 59 5a 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70 71 72 73 74 75 76 77 78 79 7a

тут сразу видно, что вторая цифра в
41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f 50 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70
уже достаточно информативна.
примем первые 4 и 5 за ноль, 6 и 7 за единицу.
для передачи 16 знаков достаточно 4 бита.
то есть, передав любые 4 символа из
41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f 50 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70
мы передаем пятый.

← →
Kilkennycat © (2015-01-27 16:17) [14]

можно увеличить сжатие (непрогнозируемо), использовав оставшиеся для каких-то правил.
например, передача 51 52 53 54 55 56 57 58 59 5a (тут а = 0) означает передачу 11 22 33 44 55 66 77 88 99 00

← →
Kilkennycat © (2015-01-27 16:19) [15]

ну а семерки для аа bb cc dd ee ff

← →
кгшзх © (2015-01-27 17:11) [16]

упаковать исходное в четырех битную кодировку
сжать упакованное
base64 на сжатое

← →
Rouse_ © (2015-01-27 19:58) [17]

> Еще один нюанс в том, что принимающая сторона - не ПК,
> а довольно убогое устройство, поэтому разжатие данных не
> должно требовать сложных алгоритмов.

Пожалуй, нужно начать с этого момента.
А так-то конечно пожать, хоть через RLE можно.

← →
имя (2015-01-27 20:29) [18]

Удалено модератором

← →
Kerk © (2015-01-27 20:37) [19]

Удалено модератором

← →
Kerk © (2015-01-27 20:40) [20]

> Kilkennycat © (27.01.15 16:10) [13]

Я, честно говоря, не очень понял твою идею.

← →
Дмитрий С © (2015-01-27 21:07) [21]

Я бы сделал контроль целостности каждого пакета отдельно и передавал бы пока не передастся.

Ну и возможно преобразовал бы hex->bin->base64 - на треть сократились бы данные

← →
Kerk © (2015-01-27 21:12) [22]

Целостность каждого пакета и так проверяется, там контрольная сумма передается.
А base64 похоже нормальный вариант. О нем думал сначала, но сомневался, вдруг что-то еще бы придумали.

← →
Kilkennycat © (2015-01-27 21:13) [23]

пример:
кодируем 120AB
1 - 0x61
2 - 0x42
0 - 0x70
A - 0x6A
B = в 4-х битной кодировке 1011, то есть 6 4 7 6

← →
Sha © (2015-01-27 21:24) [24]

> Kerk © (27.01.15 14:20)
> Строка представляет собой запись 16ричного числа

значения всех битов этого числа равновероятны?

← →
Pavia © (2015-01-27 21:29) [25]

символы 0-9 и A-F. Т.е алфавит у вас 16 символов. 4 бита и того сжатие в 2 раза. Ещё поверх можно математическим кодирование ешё в 2 раза.
Табличка и математические операции с масками. Максимум в 2 раза.
Ещё повторы пар символов. Но тут нужен словарь. Тут тоже до 2-х раз.
Собственно всё сильнее не сожмёте. Если хотите сильнее то нужны дополнительные данные.

Советую прочитать:
Лидовский В.В., Теориинформации, 2003

← →
DVM © (2015-01-27 22:49) [26]

> Kerk © (27.01.15 14:20)

> Но тут возникает второе ограничение - качество соединения
> так себе, поэтому количество пакетов в идеале нужно свести
> к минимуму.

Вообще то при плохом канале количество пакетов надо увеличивать, а их размер уменьшать, что собственно и делает TCP, иначе при каждом ретрансмишене надо будет пересылать слишком большой кусок данных и вероятность его повреждения выше.

← →
Dimka Maslov © (2015-01-27 23:37) [27]

Есть у меня код на сях, которые четырёхбайтовые последовательности преобразует в пятибайтовые с символами в диапазоне от 32 до 126. Итого получается увеличение объёма на 25%, а не на 50, как при base64. Так-что после ужатися можно и его применить. У жать можно тем же zlibом, если он ещё поддерживается в delphi.

← →
Dimka Maslov © (2015-01-27 23:41) [28]

Нашёл:

typedef char FIVECHARS[5]; void EncodeInt(DWORD Value, FIVECHARS &Buffer) { for (int i=0; i<5; i++) { int Rem = Value % 86; Value /= 86; Buffer[i] = 126 - Rem; } } DWORD DecodeInt(FIVECHARS &Buffer) { DWORD Base = 1; DWORD Result = 0; for (int i=0; i<5; i++) { Result += Base * (126 - Buffer[i]); Base *= 86; } return Result; }

Проще всего не коитировать мозг, а сделать нормальный канал связи (хоть 3G/4G модем).
Ну и моя самая простая из всех идея - если число не особо меняется, то передавай только изменения в строке. То есть один раз (на флешке) передали число, а потом передаёшь только порядковый номер изменившейся цифры и её значение. Как-то так.

> Проще всего не коитировать мозг, а сделать нормальный канал
> связи (хоть 3G/4G модем).

ты живешь на другой планете?

> ты живешь на другой планете?

Ну так не сказано в чём проблема связи, может просто не догадались до модема :)
Я живу в Урюпинске. Здесь всего 10 лет назад единственным видом интернета был диалап, с часовым дозвоном и обрывом связи через 3-5 минут. Зато сейчас у всех эти "свистки" (модемы) есть. Где связь хреновая, их подвешивают скотчем к потолку/окну, а через USB-удлинитель соединяют с компом. Если уж у нас такая связь работает, то где её нет? Да и какой смысл изобретать костыли, если через год-два, наладят связь и всё будет шикарно?
В любом случае, какой бы ты хитрый способ сжатия ни придумал, нужна связь, чтобы передать данные, так может лучше думать в сторону улучшения канала?

> Труп Васи Доброго © (28.01.15 10:16) [33]

> Если уж у нас такая связь работает, то где её нет?

Сотовая связь только в обжитых местах. Погляди на карту России в районе Сибири. Нет там ничего.
Например, на некой трубе длиной 200 км через N километров стоят датчики. Питание там есть, а вот связи нет. А информацию надо оперативно собирать. На каждый датчик по станции сотовой связи не поставишь, поэтому организуются медленные и не особенно надежные каналы связи с последовательным доступом и т.д. Примеров масса.

Я б с удовольствием протянул до каждого девайса 100мегабитный ethernet :), но реальность вот такая вот. Девайсы сделаны не мной и не вчера. Если их начинать менять, то это определенная воля нужна и бюджет. Сколько, например, стоит пара сотен 3g-модемов? Я лично не в курсе. Например, есть требование, что девайс должен работать строго от солнечной батареи. Не погубит ли эту затею мощный модем? Я опять не в курсе. Короче, работаю с тем, что есть.

а строку нельзя уменьшить?))

> девайс должен работать строго от солнечной батареи. Не погубит
> ли эту затею мощный модем?

не погубит, в космосе спутники на таких батареях намного мощнее живут :)

Ну там и батареи наверно огого :)

> Сколько, например, стоит пара сотен 3g-модемов?

Не знаю, наша контора их закупает и ставит десятками тысяч, причём даже там, где нет связи Мегафона, а симки по контракту должны быть только мегафоновские. Вот такие реалии бизьнеса по русски. Естественно, что нифига потом не рабтает, но главное что деньги освоены.

> Не погубит ли эту затею мощный модем?

Ну а сейчас то какой способ связи? Какой канал используется? Часты ли сеансы связи? И главное - данные в строке сильно меняются? Я к тому, то передавать не всю строку, а только изменённые участки.

> через N километров стоят датчики. Питание там есть, а вот
> связи нет.

Не смешите мои носки. Откуда питание? ЛЭП протянута? Значит можно и связь организовать (передатчик/радиостанцию/спутниковый телефон) Если это дорого, значит и данные не особо важные/критические. Да и опять же сколь важна точность этих данных? Да и какие данные могут быть на трубе??? Давление замеряется на каждой компрессорной станции, по его разнице между станциями вычисляется объём прошедшего газа и объём потерь в пути. Если этот объём в пределах расчётной нормы, то всё ништяк, если больше, то кричат "АЛЯРМ" и выезжают с "осмотром" трубы. Вот и вся песня. Никаких датчиков на трубе в тайге нет и не требуется.

> Примеров масса.

Хоть один реальный пожалуйста.

есть другие реальные примеры. одна компания выиграла тендер на установку и дальнейшее обслуживание пожарно-охранной сигнализации. Оборудование уже было закуплено. несколько тысяч штук. Меня приглашали осмотреть и что-нить изобрести, потому что там хоть и был 3Г модем, работало все это мерзко, так разработчику оторвали руки и ноги и пришили не в том порядке, а мож и не пришили, ушами делал, а думать ваще нечем было. Новое оборудование еще раз никто не купит.
Меня приглашали и в другие конторы, где надо было модернизировать какую-нить хрень, потому что новую никто не купит.
Ну, мож в каких-то богатых регионах дела несколько иным образом устроены, но мой опыт показывает, что в большинстве случаев новое не купят.
И не потому, что не хотят.

> Kerk © (28.01.15 12:27) [35]
> Сколько, например, стоит пара сотен
> 3g-модемов?

если обычных усб-свистков, то 12-15 долларов за модем. итого примерно 170 тысяч рублей
если промышленные, то 50-100 долларов за модем. итого примерно миллион рублей.
мелочь. а расходы на переоборудование - да ими ваще можно пренебречь, людям за счастье переделать что-то.

Сжатие данных Найти похожие ветки