» Компрессия текстовой строки

Я пишу щас сетевой компонент для быстрой разработки сетевых приложений (игры, распределенные системы и прочее).
Уже написал многое - встроенный механизм авторизации по MD5-CHAP - алгоритму, поддержка сессий, высокоуровневые процедуры отсылки и формирования пакетов, броадкасты, поддержка различных уровней доступа для юзеров и прочее.
Вопрос такой - я формирую пакет и преобразую его в Base64 для безизменной передачи, все работает на ура, но пакеты получаются немного больше чем исходные данные.
Вопрос такой - чем бы еще сжимать пакет перед отправкой, но так чтобы не убить Base64?
Есть мысли?

чо-та ты хитрое хочешь намутить - чтобы base64 строка еще раз сжималась и при этом оставалась читабельными символами ? ты гонишь - так не бывает, даже huffman тебе такое не даст
сжимай данные перед конвертацией в base64 - тогда любой алгоритм сойдет, хучь aplib хучь zlib + поле под длину возможно придетца отвести

redp Согласен. Вначале пакуй любым алгоритмом, а потом кодируй в B64 и отправляй.

UncoNNecteD
А ты абсолютно уверен что тебе необходимо base64? Он обычно нужен только в тех протоколах, где нельзя передавать в теле сообщения специальные символы.

mymuss
Да, это необходимо.

ShIvADeSt
redp
Какой алгоритм взять? Есть готовые юниты?

UncoNNecteD Алгоритм ИМХО зависит от того, какие у тебя будут данные. Если много повторяющихся, то хоть RLE, иначе попробуй LZ. Думаю описание у тебя есть. Исходников чистых нет. Но у меня где то есть компонента для работы с ZIP архивами в исходниках. Думаю если ее разобрать, то можно воспользоваться готовым решением. Только вот что я думаю, если ты собираешься паковать пакет, для скорости передачи, то это подойдет, но блин как юзера тормозить, при его распаковке. .

ShIvADeSt
Помоему проблема скорости последней мили стоит гораздо больше чем мощности процессора в последнее время.
Жаль никто не посоветовал готового решения, времени жаль...

Куча алгоритмов в библиотеке DCPcrypt v1.3. Могу выслать.

mastervigo
Мне нужно не криптование а компрессия. Если ты не ошибся то шли плиз на the_unc&mail.ru !

Цитата:

Мне нужно не криптование а компрессия.

Методы иногда назвают кодирование информации (вместо сжатия), вот я и запарился.
По компресии могу скинуть методы Фано, Лива-Земпеля, Хаффмана. (все что нарыл в инете).
Смотри в почте.

а есть у кого алгоритмы и сорсы динамической компрессии, типа старых файловых Stack и DoubleSpace или новых в NTFS, т.е. копресиия и декопрессия при записи/чтении потока данных?

mastervigo
Спасибо - посмотрю.
abzac
А что значит алгоритмы? помоему это не компрессии алгоритмы а обработки потока. Бери и компресь любым алгоритмом поток - вот тебе и динамика

Цитата:

а есть у кого алгоритмы и сорсы динамической компрессии

Посмотри здесь. Может пойдет. Правда сайт вроде на польском
http://www.csk.pl/~sc/Tekst/Programowanie/delphi.htm

UncoNNecteD

дело в том, что не все алгоритмы компрессии имеют возможность распаковать часть информации выдранной из произвольного места архива

Цитата:

дело в том, что не все алгоритмы компрессии имеют возможность распаковать часть информации выдранной из произвольного места архива

Не все, но если эта часть представляет собой законченный блок(со своими последовательностями/деревом), то такое возможно.

Цитата:

Не все, но если эта часть представляет собой законченный блок(со своими последовательностями/деревом), то такое возможно.

а если надо иметь доступ к любому сжатому предложению? как тогда паковать?

Ну не вдаваясь в подробности я понял.

Цитата:

а если надо иметь доступ к любому сжатому предложению? как тогда паковать?

Имеется ввиду текст?

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

Добавлено
у меня пока на уме только кодирование по внешнему словарю (слова и слоги)

Что первое на ум пришло - кодировать предложения по одному, записывать кодированную инфу в файл (каждый кусок - одно предложение). После окончания криптования текста в начало файла записать служебную информацию - для каждого предложения позиция в файле. При выдергивании i-того предложения сначала гладеть в эту таблицу размещений, потом тянуть блок и расшифровывать. Пока написал - подумал что похоже на файловую систему :)

mastervigo
да, это то понятно
проще делается второй файл - индексный, указывающий начало предложений (потом его можно и приклеить куда хочешь)
вопрос как паковать сами предложения? какой алгоритм?

Цитата:

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

Суть одна и таже

Цитата:

вопрос как паковать сами предложения? какой алгоритм?

А в чем проблема с обычными алгоритмами?

mastervigo
суть одинакова, только вопрос не в этом

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

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

В данном случае нужно просто использовать однопроходный алгоритм сжатия потока. Самое простое LZW. Статистические алгоритмы здесь не пойтут совершенно.
Можно присмотреть что-нибудь интересное на http://algolist.manual.ru/compress/standard/
Там есть и описание алгоритмов и примеры.
Честно говоря не вижу смысла вообще использовать здесь кодирование в BASE64. Если уж так нужно использовать служебные символы для управления передачей, то можно просто ограничить таблицу сжимающего алгоритма. Например зарезервировать первые 16 символов для управления потоком, и скорректировать сжимающий алгоритм, чтобы он выдавал резульдат в диапазоне с 17 символа.

VCLZip Native Delphi Zip/UnZip Component! (Version 2.03 Mar 10, 1998)
100кБ
http://www.cydsoft.com/vr-online/files/ziparc.zip

Пакеты маленькие нецелесообразно впрочим паковать.

Snowy
Дело в том что я пишу универсальный пакет для разработки сетевых приложений. Соответственно я не могу предсказать какие данные будут идти по протоколу и какой вообще будет протокол
Поэтому для нормального функционирования необходим BASE64.
Я так полагаю что нужно просто провести эксперимент - посмотреть насколько эффективно тот же zip (спасибо MetroidZ) будет сжимать небольшие пакеты и какой выигрышь это даст.
Хотя наверное это уже дело не сетевого модуля а забота разработчика - сжимать данные до формирования пакета или нет. Сейчас я уже думаю что загибаю лишку
Всем сенк.

UncoNNecteD
вообще для твоих целей ZIP будет наверное тяжеловат
полегче будет бесплатная кросплатформенная библиотека ZLib http://www.gzip.org/zlib/
работать должно побыстрее
а вообще для твоих целей лучше использовать специально созданные алгоритмы для потокового сжатия
http://www.winton.org.uk/zebedee/

Цитата:

Zebedee is a simple program to establish an encrypted, compressed “tunnel” for TCP/IP or UDP data transfer between two systems. This allows traffic such as telnet, ftp and X to be protected from snooping as well as potentially gaining performance over low-bandwidth networks from compression.

Кстати,народ,объясните точное назначение Base64 и почему Хаффман не сможет своим алгоритмом сжать её(кодировки) продукт?Если у кого есть исходники(и того,и другого),выложите plz

TP09H

Цитата:

Кстати,народ,объясните точное назначение Base64

http://ru.wikipedia.org/wiki/Base64


Цитата:

и почему Хаффман не сможет своим алгоритмом сжать её(кодировки) продукт?

Потому что он уже умер.

Почему это умер?? Сжать не может, потому что отсутствует избыточность, которую он мог бы убрать. А слухи о его смерти, боюсь, чрезмерно преувеличены.