Сжатие без потерь в маленьких блоках с предварительно вычисленным словарем
Если Вы в веб-дизайн и создание веб-сайта тогда, я рекомендую Boagworld и также подкаст Rissington , даже если Вы не.
4 ответа
Самым сложным в моей голове является то, как вы создаете свой статический словарь. Вы не хотите использовать словарь LZW, созданный на основе ваших демонстрационных данных. LZW тратит кучу времени на обучение, поскольку он не может построить словарь быстрее, чем декомпрессор (токен будет использоваться только во второй раз, когда его увидит компрессор, поэтому декомпрессор может добавить его в свой словарь при первом просмотре) . Обратной стороной этого является то, что он добавляет в словарь вещи, которые могут никогда не использоваться, на случай, если строка снова появится. (например, чтобы иметь токен для 'stackoverflow', у вас также будут записи для 'ac', 'ko', 've', 'rf' и т. д.)
Однако, глядя на поток сырых токенов из алгоритм LZ77 может работать хорошо. Вы увидите жетоны только для строк, которые видели как минимум дважды. Затем вы можете составить список наиболее распространенных токенов / строк для включения в свой словарь.
Если у вас есть статический словарь, с использованием LZW sans обновление словаря кажется простой реализацией, но для получения наилучшего сжатия я бы подумал статическая таблица Хаффмана вместо традиционного 12-битного токена фиксированного размера (как предложил Джордж Филлипс). Словарь LZW будет записывать токены для всех подстрок, которые вы, возможно, никогда не закодируете (например, если вы можете закодировать 'stackoverflow', будут токены для 'st', 'sta', 'stac', 'stack', ' stacko 'и т. д.)
На данный момент это действительно не LZW - то, что делает LZW умным, - это то, как декомпрессор может построить тот же словарь, что и компрессор, только видя поток сжатых данных. То, что вы не будете использовать.
LZW добавляет в словарь во время распаковки, чтобы гарантировать он имеет то же состояние словаря, что и компрессор. В противном случае декодирование не будет работать должным образом.
Однако, если бы вы были в состоянии, когда словарь был исправлен, тогда да, вам не нужно было бы добавлять новые коды.
Ваш подход будет работать достаточно хорошо, и его легко можно будет добавить. использовать существующие инструменты для создания прототипов и измерения результатов. То есть сожмите файл примера, а затем данные примера и теста вместе. Размер последнего меньше первого будет ожидаемым размером сжатого блока.
LZW - это умный способ создания словаря на лету, который дает достойные результаты. Но более тщательный анализ ваших типичных блоков данных, вероятно, приведет к созданию более эффективного словаря.
Также есть возможности для улучшения того, как LZW представляет сжатые данные. Например, каждая словарная ссылка может быть закодирована по Хаффману до длины, близкой к оптимальной, исходя из ожидаемой частоты их использования. Чтобы коды были действительно оптимальными, они должны быть арифметически закодированы.
Я бы посмотрел на ваши данные, чтобы узнать, есть ли очевидная причина, по которой их так легко сжимать. Возможно, вам удастся сделать что-то более простое, чем LZ78. Я сделал и LZ77 (ретроспективный анализ), и LZ78 (словарь).
Попробуйте запустить LZ77 для ваших данных. В LZ77 нет словаря, поэтому вы можете использовать библиотеку без изменений. Deflate - это реализация LZ77.
Ваша идея использования общего словаря хороша, но сложно определить, похожи ли файлы друг на друга или просто самоподобны, не проводя некоторых тестов .
Правильный путь - использовать библиотеку - почти каждый современный язык имеет библиотеку сжатия. C #, Python, Perl, Java, VB.net, все, что вы используете.
LZW экономит место, полагаясь на словарь на предыдущих входах. У него есть начальный словарь, и когда вы что-то распаковываете, вы добавляете это в словарь - поэтому словарь растет. (Я опускаю здесь некоторые детали, но это общая идея)
Вы можете пропустить этот шаг, предоставив весь (полный) словарь в качестве начального. Но для этого потребуется немного места.