Есть поток данных, для которого более критичным параметром является время отклика нежели кол-во переданных данных. Но вот у меня появилась идея, проанализировать этот поток составить большей словарь и часто встречающихся "кусков" ( желательно кусков с параметрами те вида FFCDFDCF(XXXXXXX)DCFCEF и т.п. ) и передать этот словарь один раз, а в остальные "разы" передавать лишь номер в списке и параметры. Насколько идея реализуема? понятно что основная проблема это поиск этих самых кусков, размер списка для меня по сути не важен, пусть будет хоть 100мб, один раз передать можно. И вообще будет ли это эффективно? или лучше взять просто готовый алгоритм архивации и и сжимать им, а есть специальные потоковые алгоритмы? можно для них "скармливать" готовый словарь?
Угу. Есть до фигища алгоритмов для потокового сжатия данных. Какого типа ваши данные? Как их нужно сжимать - с потерями, без потерь? Какой коэффициент сжатия устроит? "По словарю" - это не Хаффман, это Лемпел-Зив (LZ77, LZ78, LZW и их производные).
данные в основном синхронизирующего харакьера. Протокол синхронизации скриптов на удаленных машинах. Сжатие без потерь! И еще конкретно какой алгос вы бы посоветовади? Мне охото один раз передать много а потом уэе с хорошим сжатием. Сори если мутно, вынужден с телефона.
А еще поконкретней? Это строки или наборы чисел? Сколько битов занимает один элемент? Много ли в данных регулярных фрагментов? Много ли в них повторяющихся элементов? Сильно ли отличаются соседние элементы? Каков общий объем данных для сжатия? Лучше приложить файлик, а мы посмотрим. Расплывчато. Результат очень сильно зависит от типа данных и использованного алгоритма. Ну, и от системных требований: персоналка или микроконтроллер, Венда или Линух и т.п. Если: 1) Венда (кроме 9X) и 2) пофиг на выжимание эффективности и 3) хоцца че попроще, то: стандартная функция RtlCompressBuffer() в стандартной либе ntdll.dll использует метод LZNT1 - это как раз словарное сжатие, разновидность LZ77, применяется для сжатия служебных полей данных в docfile и катологов в NTFS, на текстовых данных и программных файлах дает коэффициент сжатия порядка 1.5-3. Подробности формата сжатия здесь: http://www.nf-team.org/drmad/zf/zf5/zf5_025.htm. Ы?
drmad 8 Мб за сеанс. Набор чисел 4, 8, 12, 16 по разному, но в основном как я написал. чаще 4. Достаточно, но они не "идеально" повторяются. те бывает последовательность отличается лишь парой байт. Не совсем понятно что значит элемент, но по идеи могут сильно различаться. Коры на винде, те с вычислительными мощностями не должно быть проблем. Мысль то как раз в том чтобы держать словарь/базу/статистические данные большого объема, но зато при сеансе трафика тратилось как можно меньше. Есть такие инструменты. PS сори за задержку (( и дампы дать не могу. Верней. как раз и надо чтобы инструмент был желательно самонастраивающимся, но а общее характеристики потока я привел.
как раз не пофиг, пусть лучше проц будет "греться" но сжать как можно сильнее. Конечно без фанатизма, чтобы передача не занимала времени меньше чем сжатие)
Извиняюсь за задержку, не каждый день читаю форум. Итак, про сжатие "на лету". Вообще, еще раз: все зависит от вида данных. 1. Например, если это результаты измерения какого-нибудь медленно изменяющегося процесса, тогда два соседних отсчета (не зря я спрашивал про размер элемента - 1 байт, или 2, или 4) будут отличаться очень мало. Тогда выгодней хранить не сами элементы, а разность между ними. Получаются очень маленькие числа, которые можно записать меньшим количеством битов. Это "дельта-кодирование" - примитив, но иногда очень эффективно. 2. Или, если в данных есть длинные серии повторяющихся элементов (тут опять важен их размер), то каждую такую цепочку можно закодировать парой (значение, длина_цепочки). Это RLE, он же метод длин серий, он же метод группового кодирования. На некоторых типах данных тоже очень хорошо жмет. 3. Достоточо быстры так же словарные методы Лемпела-Зива. Очень просты разновидности LZ77: повторяющиеся фрагменты кодируются ссылкой на самый первый фрагмент. Тут многое зависит от длины скользящего окна - чем она меньше, тем быстрей работа, но хуже сжатие. Так что, я бы рекомендовал поэкспериментировать с окнами 4 Кб, 8 Кб... 256 Кб, чтобы подобрать оптимальное соотношение скорость/сжатие. Описание и издохники можно взять, например, здесь: http://compression.ru/download/lz.html. Ну, а, если устроит окно 4Кб, то можно не париться и ограничиться функцией RtlCompressBuffer. 4. Более продвинутая разновидность Лемпела-Зива - это что-нибудь на основе LZ78, прежде всего LZW. Там сам словарь нашпигован ссылками на самого себя, соответственно, алгоритм там похитрей, но жмет заметно лучше, чем LZ77. 5. Энтропийные методы (Хаффман, например), в общем случае для потокового сжатия малоприемлемы, т.к. требуют накопления статистики обо всем наборе данных. Ну есть там адаптивные методы, но придется усложнять алгоритм, а надо? Впрочем, если поток данных приблизительно стационарен (т.е. частоты встречаемости элементов сохраняются во времени), то можно заранее посчитать вероятности элементов и жестко назначить им битовые комбинации. Тогда жать будет вообще мухой. Для текстов, например, азбука Морзе очень неплохо работает. Так что, имеет смысл попробовать. Ну, вот как-то так. Про другие методы сжатия на лету только слышал, но не разбирался и не пробовал. А эти - вполне ничего. Рекомендую.
Обычный хафман, хм можно попробовать. Но вод в чем проблема у меня надо рассматривать не байты. а элементы которые могут быть разного размера. Поэтому оптимальный вариант. Вообще идеальный вариант это вариант 4 ( с доработкой в виде того, что часть потока на который будут ссылка уже есть на локальном компьютере до передачи данных. ) Посмотрю что получится. Попробую посмотреть LZW
Дык, основная-то идея: наиболее часто встречающиеся фрагменты кодировать меньшим числом битов. А какие это элементы, - одинаковой длины или разные, большие или маленькие, - в общем, не важно.
drmad конечно, я вас в личку даже предупрежу. Ибо пробовать вполне возможно буду в начале след месяца только.
