Без потерь сжатие в небольших блоках с использованием предварительно вычисленного словаря
У меня есть приложение, в котором я читаю и записываю небольшие блоки данных (несколько сотен байтов) сотни миллионов раз. Я хотел бы создать словарь сжатия на основе файла данных примера и использовать этот словарь навсегда, когда я читаю и записываю маленькие блоки. Я склоняюсь к алгоритму сжатия LZW. Страница Wikipedia (http://en.wikipedia.org/wiki/Lempel-Ziv-Welch) содержит псевдокод для сжатия и декомпрессии. Это выглядит довольно просто, чтобы изменить его так, что создание словаря является отдельным блоком кода. Поэтому у меня есть два вопроса:
- Я на правильном пути или есть лучший способ?
- Почему алгоритм LZW добавляет словарь во время этапа декомпрессии? Могу ли я пропустить это или потерял бы эффективность в моем словаре?
Спасибо.
Обновление: Теперь я думаю, что идеальным вариантом будет найти библиотеку, которая позволит мне хранить словарь отдельно от сжатых данных. Есть ли что-нибудь подобное?
Обновление: Я закончил тем, что взял код http://www.enusbaum.com/blog/2009/05/22/example-huffman-compression-routine-in-c и адаптировал его. Я - Крис в комментариях на этой странице. Я отправил по электронной почте свои моды назад этому автору блога, но я еще не слышал назад. Коэффициенты сжатия, которые я вижу с этим кодом, не впечатляют. Возможно, это связано с размером 8-битного дерева.
Обновление: Я преобразовал его в 16 бит и сжатие лучше. Это также намного быстрее, чем исходный код.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace Book.Core
{
public class Huffman16
{
private readonly double log2 = Math.Log(2);
private List<Node> HuffmanTree = new List<Node>();
internal class Node
{
public long Frequency { get; set; }
public byte Uncoded0 { get; set; }
public byte Uncoded1 { get; set; }
public uint Coded { get; set; }
public int CodeLength { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public bool IsLeaf
{
get { return Left == null; }
}
public override string ToString()
{
var coded = "00000000" + Convert.ToString(Coded, 2);
return string.Format("Uncoded={0}, Coded={1}, Frequency={2}", (Uncoded1 << 8) | Uncoded0, coded.Substring(coded.Length - CodeLength), Frequency);
}
}
public Huffman16(long[] frequencies)
{
if (frequencies.Length != ushort.MaxValue + 1)
{
throw new ArgumentException("frequencies.Length must equal " + ushort.MaxValue + 1);
}
BuildTree(frequencies);
EncodeTree(HuffmanTree[HuffmanTree.Count - 1], 0, 0);
}
public static long[] GetFrequencies(byte[] sampleData, bool safe)
{
if (sampleData.Length % 2 != 0)
{
throw new ArgumentException("sampleData.Length must be a multiple of 2.");
}
var histogram = new long[ushort.MaxValue + 1];
if (safe)
{
for (int i = 0; i <= ushort.MaxValue; i++)
{
histogram[i] = 1;
}
}
for (int i = 0; i < sampleData.Length; i += 2)
{
histogram[(sampleData[i] << 8) | sampleData[i + 1]] += 1000;
}
return histogram;
}
public byte[] Encode(byte[] plainData)
{
if (plainData.Length % 2 != 0)
{
throw new ArgumentException("plainData.Length must be a multiple of 2.");
}
Int64 iBuffer = 0;
int iBufferCount = 0;
using (MemoryStream msEncodedOutput = new MemoryStream())
{
//Write Final Output Size 1st
msEncodedOutput.Write(BitConverter.GetBytes(plainData.Length), 0, 4);
//Begin Writing Encoded Data Stream
iBuffer = 0;
iBufferCount = 0;
for (int i = 0; i < plainData.Length; i += 2)
{
Node FoundLeaf = HuffmanTree[(plainData[i] << 8) | plainData[i + 1]];
//How many bits are we adding?
iBufferCount += FoundLeaf.CodeLength;
//Shift the buffer
iBuffer = (iBuffer << FoundLeaf.CodeLength) | FoundLeaf.Coded;
//Are there at least 8 bits in the buffer?
while (iBufferCount > 7)
{
//Write to output
int iBufferOutput = (int)(iBuffer >> (iBufferCount - 8));
msEncodedOutput.WriteByte((byte)iBufferOutput);
iBufferCount = iBufferCount - 8;
iBufferOutput <<= iBufferCount;
iBuffer ^= iBufferOutput;
}
}
//Write remaining bits in buffer
if (iBufferCount > 0)
{
iBuffer = iBuffer << (8 - iBufferCount);
msEncodedOutput.WriteByte((byte)iBuffer);
}
return msEncodedOutput.ToArray();
}
}
public byte[] Decode(byte[] bInput)
{
long iInputBuffer = 0;
int iBytesWritten = 0;
//Establish Output Buffer to write unencoded data to
byte[] bDecodedOutput = new byte[BitConverter.ToInt32(bInput, 0)];
var current = HuffmanTree[HuffmanTree.Count - 1];
//Begin Looping through Input and Decoding
iInputBuffer = 0;
for (int i = 4; i < bInput.Length; i++)
{
iInputBuffer = bInput[i];
for (int bit = 0; bit < 8; bit++)
{
if ((iInputBuffer & 128) == 0)
{
current = current.Left;
}
else
{
current = current.Right;
}
if (current.IsLeaf)
{
bDecodedOutput[iBytesWritten++] = current.Uncoded1;
bDecodedOutput[iBytesWritten++] = current.Uncoded0;
if (iBytesWritten == bDecodedOutput.Length)
{
return bDecodedOutput;
}
current = HuffmanTree[HuffmanTree.Count - 1];
}
iInputBuffer <<= 1;
}
}
throw new Exception();
}
private static void EncodeTree(Node node, int depth, uint value)
{
if (node != null)
{
if (node.IsLeaf)
{
node.CodeLength = depth;
node.Coded = value;
}
else
{
depth++;
value <<= 1;
EncodeTree(node.Left, depth, value);
EncodeTree(node.Right, depth, value | 1);
}
}
}
private void BuildTree(long[] frequencies)
{
var tiny = 0.1 / ushort.MaxValue;
var fraction = 0.0;
SortedDictionary<double, Node> trees = new SortedDictionary<double, Node>();
for (int i = 0; i <= ushort.MaxValue; i++)
{
var leaf = new Node()
{
Uncoded1 = (byte)(i >> 8),
Uncoded0 = (byte)(i & 255),
Frequency = frequencies[i]
};
HuffmanTree.Add(leaf);
if (leaf.Frequency > 0)
{
trees.Add(leaf.Frequency + (fraction += tiny), leaf);
}
}
while (trees.Count > 1)
{
var e = trees.GetEnumerator();
e.MoveNext();
var first = e.Current;
e.MoveNext();
var second = e.Current;
//Join smallest two nodes
var NewParent = new Node();
NewParent.Frequency = first.Value.Frequency + second.Value.Frequency;
NewParent.Left = first.Value;
NewParent.Right = second.Value;
HuffmanTree.Add(NewParent);
//Remove the two that just got joined into one
trees.Remove(first.Key);
trees.Remove(second.Key);
trees.Add(NewParent.Frequency + (fraction += tiny), NewParent);
}
}
}
}
Примеры использования:
Чтобы создать словарь из данных образца:
var freqs = Huffman16.GetFrequencies(File.ReadAllBytes(@"D:\nodes"), true);
Чтобы инициализировать кодировщик с данным словарем:
var huff = new Huffman16(freqs);
И для сжатия:
var encoded = huff.Encode(raw);
И декомпрессии:
var raw = huff.Decode(encoded);
Ответы
Ответ 1
Жесткая часть моего разума заключается в том, как вы создаете свой статический словарь. Вы не хотите использовать словарь LZW, построенный из ваших данных образца. LZW тратит кучу времени на обучение, так как он не может построить словарь быстрее, чем может работать декомпрессор (токен будет использоваться только во второй раз, когда он видит компрессор, поэтому декомпрессор может добавить его в свой словарь при первом просмотре), Оборотная сторона этого заключается в том, что он добавляет вещи в словарь, который никогда не сможет использоваться, на всякий случай, когда строка появится снова. (например, чтобы иметь токен для "stackoverflow", у вас также будут записи для "ac", "ko", "ve", "rf" и т.д.)
Однако просмотр исходного потока токенов из алгоритма LZ77 может работать хорошо. Вы увидите только токены для строк, видимые как минимум дважды. Затем вы можете создать список наиболее распространенных токенов/строк для включения в словарь.
Как только у вас есть статический словарь, использование LZW без обновления словаря выглядит как простая реализация, но для получения лучшего сжатия я бы рассмотрел статический Huffman вместо традиционного 12-битного токена фиксированного размера (как предполагал Джордж Филлипс). Словарь LZW будет записывать токены для всех подстрок, которые вы, возможно, никогда не кодируете (например, если вы можете кодировать "stackoverflow", будут использоваться токены для "st", "sta", "stac", "stack", stacko 'и т.д.).
На данный момент это действительно не LZW - то, что делает LZW умным, - это то, как декомпрессор может построить тот же словарь, который использует компрессор, только видя сжатый поток данных. То, что вы не будете использовать. Но все реализации LZW имеют состояние, в котором словарь заполнен и больше не обновляется, так как вы будете использовать его со своим статическим словарем.
Ответ 2
LZW добавляет словарь во время декомпрессии, чтобы гарантировать, что он имеет то же самое состояние словаря, что и компрессор. В противном случае декодирование не будет работать должным образом.
Однако, если вы были в состоянии, когда словарь был исправлен, тогда да, вам не нужно будет добавлять новые коды.
Ваш подход будет работать достаточно хорошо и легко использовать существующие инструменты для прототипа и измерения результатов. То есть сжимайте пример файла, а затем пример и тестовые данные вместе. Размер последнего меньше первого будет ожидаемым сжатым размером блока.
LZW - это умный способ создания словаря на лету и дает достойные результаты. Но более тщательный анализ ваших типичных блоков данных, скорее всего, приведет к созданию более эффективного словаря.
Там также можно улучшить то, как LZW представляет сжатые данные. Например, каждая ссылка на словарь может быть закодирована по шкале Хаффмана ближе к оптимальной длине, исходя из ожидаемой частоты их использования. Чтобы быть действительно оптимальным, коды должны быть закодированы в арифметическом режиме.
Ответ 3
Я бы посмотрел ваши данные, чтобы увидеть, есть ли очевидная причина, которую так легко сжимать. Возможно, вы сможете сделать что-то намного проще, чем LZ78. Я сделал оба LZ77 (backback) и LZ78 (словарь).
Попробуйте запустить LZ77 в ваших данных. Там нет словаря с LZ77, поэтому вы можете использовать библиотеку без изменений. Deflate - это реализация LZ77.
Ваша идея использования общедоступного словаря хорошая, но трудно понять, похожи ли файлы друг на друга или просто самоподобны, не выполняя некоторые тесты.
Ответ 4
-
Правильный трек должен использовать библиотеку - почти каждый современный язык имеет библиотеку сжатия. С#, Python, Perl, Java, VB.net, все, что вы используете.
-
LZW сохраняет некоторое пространство, в зависимости от словаря на предыдущих входах. У него есть начальный словарь, и когда вы что-то декомпрессируете, вы добавляете их в словарь, поэтому словарь растет. (Здесь я опускаю некоторые подробности, но это общая идея)
Вы можете пропустить этот шаг, поставив полный (полный) словарь в качестве начального. Но это стоило бы некоторого пространства.
Ответ 5
Я нахожу этот aproach довольно интересным для повторных записей журнала и того, что я хотел бы изучить с помощью.
Можете ли вы поделиться статистикой сжатия для использования этого подхода для вашего случая использования, чтобы я мог сравнить его с другими альтернативами?
Считаете ли вы, что общий словарь растет со временем или это не допустимый вариант?
