मेरे पास एक ऐसा एप्लिकेशन है जहां मैं डेटा के छोटे ब्लॉक (कुछ सौ बाइट) लाखों बार पढ़ रहा हूं और लिख रहा हूं। मैं एक उदाहरण डेटा फ़ाइल के आधार पर एक संपीड़न शब्दकोश उत्पन्न करना चाहता हूं और उस शब्दकोष का हमेशा उपयोग करता हूं जैसा कि मैंने छोटे ब्लॉक को पढ़ और लिखते हैं। मैं एलजेडब्लूडब्ल्यू संपीड़न एल्गोरिदम की ओर झुका रहा हूँ। विकिपीडिया पेज (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);
क्या आपके ब्लॉक लगातार आकार में हैं? – user57368
इसके अलावा, मेरे पास एक नमूना डेटा फ़ाइल आरएआर-एड है और पुष्टि की है कि डेटा अत्यधिक संकुचित (~ 9 x संपीड़न अनुपात) है। – Fantius
नहीं, वे लगातार आकार में नहीं हैं। – Fantius