COMPRESION HUFFMANAlgoritmo para la compresión de archivos sin pérdida de datos desarrollado por David Huffman. Para la compresión se basa en la frecuencia de ocurrencia de un símbolo en un archivo que será comprimido. El algoritmo Huffman está basado en codificación estadística, lo que significa que la probabilidad de un símbolo tiene una directa relación con el tamaño de su representación. Hay mayor probabilidad de ocurrencia de un símbolo, mientras más corto sea el tamaño de su representación en bits.

En cualquier fichero, ciertos caracteres son usados más que otros. Usando representación binaria, el número de bits requeridos para representar cada caracter depende del número de caracteres que tienen que ser representados. Por ejemplo, si se usa un bit, significa que pueden representarse como máximo dos caracteres (0 un caracter, y 1 el otro). Si se usan dos bits significa que pueden representarse cuatro caracteres (00, 01, 10, 11, cada uno representa un caracter), y así sucesivamente.

La compresión Huffman es un sistema de longitud variable que asigna los códigos más pequeños a aquellos caracteres más frecuentemente usados y los códigos más largos a aquellos menos frecuentes. Esto sirve para reducir el tamaño de los archivos.

Veamos un ejemplo. Supongamos que en un archivo de datos se tiene la siguiente información: AAAAAABBBBCC. Donde A tiene una frecuencia de 6, B de 4 y C de 2. Cada caracter es representado usando una longitud fija de códigos de dos bits, entonces el número de bits requeridos para almacenar el archivo sería 24, por ejemplo (2 bits x 6) + (2 bits x 4) + (2 bits x 2) = 24 bits.

Si esa información es comprimida usando compresión Huffman, el caracter más frecuente debería ser representado por los bits más pequeños como sigue:

A por el código 0 (1 bit) B por el código 10 (2 bits)C por el código 11 (2 bits)

Por lo tanto el tamaño del archivo pasará a ser de 18, (1 bit x 6) + (2 bits x 4) + (2 bits x 2) = 18 bits

O sea: 000000101010101111

En el ejemplo anterior, los caracteres que se repetían más frecuentemente son asignados al código más pequeño, resultando en un menor número de bits en el archivo final comprimido.

CODIGO FUENTE PARA LA COMPRESION HUFFMAN EN VISUAL BASIC

Private Enum HuffmanTreeNodeParts htnWeight = 1

htnIsLeaf = 2 htnAsciiCode = 3 htnBitCode = 4 htnLeftSubtree = 5 htnRightSubtree = 6End Enum

'Comprime el textoPublic Function HuffmanEncode(Text As String, Optional Force As Boolean) As String Dim TextLen As Long, Char As Byte, i As Long, j As Long Dim CodeCounts(255) As Long, BitStrings(255), BitString Dim HuffmanTrees As Collection Dim HTRootNode As Collection, HTNode As Collection Dim NextByte As Byte, BitPos As Integer, Temp As String ‘inicia el proceso TextLen = Len(Text) Set HuffmanTrees = New Collection 'Pregunta si hay algo que codificar If TextLen = 0 Then HuffmanEncode = "HE0" & vbCr 'Version 0 = Plain text Exit Function 'No point in continuing End If HuffmanEncode = "HE2" & vbCr 'Version 1 ‘Cuenta cuantas veces el codigo ASCII se encuentra en el texto For i = 1 To TextLen Char = Asc(Mid(Text, i, 1)) CodeCounts(Char) = CodeCounts(Char) + 1 Next ‘Inicia el arbol Huffman, uno por cada caracter ASCII usado For i = 0 To UBound(CodeCounts) If CodeCounts(i) > 0 Then Set HTNode = NewNode S HTNode, htnAsciiCode, Chr(i) S HTNode, htnWeight, CDbl(CodeCounts(i) / TextLen) S HTNode, htnIsLeaf, True ‘Ahora los posiciona en reserva For j = 1 To HuffmanTrees.Count + 1 If j > HuffmanTrees.Count Then HuffmanTrees.Add HTNode Exit For End If

If HTNode(htnWeight) >= HuffmanTrees(j)(htnWeight) Then HuffmanTrees.Add HTNode, , j Exit For End If Next End If Next ‘Ahora emsambla todos los niveles simples del arbol Huffman en un solo arbol, donde todos estan asociados a un codigo ASCII If HuffmanTrees.Count = 1 Then Set HTNode = NewNode S HTNode, htnLeftSubtree, HuffmanTrees(1) S HTNode, htnWeight, 1 HuffmanTrees.Remove (1) HuffmanTrees.Add HTNode End If While HuffmanTrees.Count > 1 Set HTNode = NewNode S HTNode, htnRightSubtree, HuffmanTrees(HuffmanTrees.Count) HuffmanTrees.Remove HuffmanTrees.Count S HTNode, htnLeftSubtree, HuffmanTrees(HuffmanTrees.Count) HuffmanTrees.Remove HuffmanTrees.Count S HTNode, htnWeight, HTNode(htnLeftSubtree)(htnWeight) + HTNode(htnRightSubtree)(htnWeight) 'Place this new tree it in its reverse-ordered position. For j = 1 To HuffmanTrees.Count + 1 If j > HuffmanTrees.Count Then HuffmanTrees.Add HTNode Exit For End If If HTNode(htnWeight) >= HuffmanTrees(j)(htnWeight) Then HuffmanTrees.Add HTNode, , j Exit For End If Next Wend Set HTRootNode = HuffmanTrees(1) AttachBitCodes BitStrings, HTRootNode, Array() For i = 0 To UBound(BitStrings) If Not IsEmpty(BitStrings(i)) Then Set HTNode = BitStrings(i) Temp = Temp & HTNode(htnAsciiCode) _ & BitsToString(HTNode(htnBitCode)) End If Next HuffmanEncode = HuffmanEncode & Len(Temp) & vbCr & Temp

‘La siguiente parte es la cabeza de un chekeo de los valores, los cuales utilizaremos después para verificar nuestra compresion Char = 0 For i = 1 To TextLen Char = Char Xor Asc(Mid(Text, i, 1)) Next HuffmanEncode = HuffmanEncode & Chr(Char) ‘La parte final identifica cuantos bytes del texto original contiene. Nostros probablemente tenemos unos cuantos bits sin usar en el ultimo byte que necesitamos para el conteo. Adicionalmente sirve para un chequeo final por si existe corrupción de algún dato HuffmanEncode = HuffmanEncode & TextLen & vbCr ‘Ahora podemos codificar el dato mediante el intercambio de cada byte ASCII por su apropiado bit en cadena BitPos = -1 Char = 0 Temp = "" For i = 1 To TextLen BitString = BitStrings(Asc(Mid(Text, i, 1)))(htnBitCode) 'Add each bit to the end of the output stream's 1-byte buffer. For j = 0 To UBound(BitString) BitPos = BitPos + 1 If BitString(j) = 1 Then Char = Char + 2 ^ BitPos End If 'If the bit buffer is full, dump it to the output stream. If BitPos >= 7 Then Temp = Temp & Chr(Char) 'If the temporary output buffer is full, dump it 'to the final output stream. If Len(Temp) > 1024 Then HuffmanEncode = HuffmanEncode & Temp Temp = "" End If BitPos = -1 Char = 0 End If Next Next If BitPos > -1 Then Temp = Temp & Chr(Char) End If If Len(Temp) > 0 Then HuffmanEncode = HuffmanEncode & Temp End If

‘Si toma mas espacio comprimido porque la fuente is pequeña y el encabezamiento es grande, lo dejaremos sin comprimir y lo antemponemos con un encabezamiento de 4 bytes. If Len(HuffmanEncode) > TextLen And Not Force Then HuffmanEncode = "HE0" & vbCr & Text End IfEnd Function

‘Descomprimimos la cadena denuevo a su texto originalPublic Function HuffmanDecode(ByVal Text As String) As String Dim Pos As Long, Temp As String, Char As Byte, Bits Dim i As Long, j As Long, CharsFound As Long, BitPos As Integer Dim CheckSum As Byte, SourceLen As Long, TextLen As Long Dim HTRootNode As Collection, HTNode As Collection ‘Si fue dejado sin comprimir sera facil If Left(Text, 4) = "HE0" & vbCr Then HuffmanDecode = Mid(Text, 5) Exit Function End If ‘Si hay alguna version diferente a la 2, se retirará If Left(Text, 4) <> "HE2" & vbCr Then Err.Raise vbObjectError, "HuffmanDecode()", _ "The data either was not compressed with HE2 or is corrupt" End If Text = Mid(Text, 5) Pos = InStr(1, Text, vbCr) If Pos = 0 Then Err.Raise vbObjectError, "HuffmanDecode()", _ "The data either was not compressed with HE2 or is corrupt" End If On Error Resume Next TextLen = Left(Text, Pos - 1) If Err.Number <> 0 Then On Error GoTo 0 Err.Raise vbObjectError, "HuffmanDecode()", _ "The header is corrupt" End If On Error GoTo 0 Text = Mid(Text, Pos + 1) Temp = Left(Text, TextLen) Text = Mid(Text, TextLen + 1)

‘Ahora extrae el caracter ASCII codificado por bit Set HTRootNode = NewNode Pos = 1 While Pos <= Len(Temp)

Char = Asc(Mid(Temp, Pos, 1)) Pos = Pos + 1 Bits = StringToBits(Pos, Temp) Set HTNode = HTRootNode For j = 0 To UBound(Bits) If Bits(j) = 1 Then If HTNode(htnLeftSubtree) Is Nothing Then S HTNode, htnLeftSubtree, NewNode End If Set HTNode = HTNode(htnLeftSubtree) Else If HTNode(htnRightSubtree) Is Nothing Then S HTNode, htnRightSubtree, NewNode End If Set HTNode = HTNode(htnRightSubtree) End If Next S HTNode, htnIsLeaf, True S HTNode, htnAsciiCode, Chr(Char) S HTNode, htnBitCode, Bits Wend 'Extract the checksum. CheckSum = Asc(Left(Text, 1)) Text = Mid(Text, 2) ‘Extrae la longitud de la cadena original Pos = InStr(1, Text, vbCr) If Pos = 0 Then Err.Raise vbObjectError, "HuffmanDecode()", _ "The header is corrupt" End If On Error Resume Next SourceLen = Left(Text, Pos - 1) If Err.Number <> 0 Then On Error GoTo 0 Err.Raise vbObjectError, "HuffmanDecode()", _ "The header is corrupt" End If On Error GoTo 0 Text = Mid(Text, Pos + 1) TextLen = Len(Text) ‘Ahora que ya hemos procesado la cabeza, vamos a codificar los datos actuales i = 1 BitPos = -1 Set HTNode = HTRootNode Temp = ""

While CharsFound < SourceLen If BitPos = -1 Then If i > TextLen Then Err.Raise vbObjectError, "HuffmanDecode()", _ "Expecting more bytes in data stream" End If Char = Asc(Mid(Text, i, 1)) i = i + 1 End If BitPos = BitPos + 1 If (Char And 2 ^ BitPos) > 0 Then Set HTNode = HTNode(htnLeftSubtree) Else Set HTNode = HTNode(htnRightSubtree) End If If HTNode Is Nothing Then

Err.Raise vbObjectError, "HuffmanDecode()", _ "The header (lookup table) is corrupt" End If If HTNode(htnIsLeaf) Then Temp = Temp & HTNode(htnAsciiCode) If Len(Temp) > 1024 Then HuffmanDecode = HuffmanDecode & Temp Temp = "" End If CharsFound = CharsFound + 1 Set HTNode = HTRootNode End If If BitPos >= 7 Then BitPos = -1 Wend If Len(Temp) > 0 Then HuffmanDecode = HuffmanDecode & Temp End If If i <= TextLen Then Err.Raise vbObjectError, "HuffmanDecode()", _ "Found extra bytes at end of data stream" End If ‘Verificamos los datos por si existe alguna corrupcion de estos If Len(HuffmanDecode) <> SourceLen Then Err.Raise vbObjectError, "HuffmanDecode()", _ "Data corrupt because check sums do not match" End If Char = 0

For i = 1 To SourceLen Char = Char Xor Asc(Mid(HuffmanDecode, i, 1)) Next If Char <> CheckSum Then Err.Raise vbObjectError, "HuffmanDecode()", _ "Data corrupt because check sums do not match" End IfEnd Function

----------------------------------------------------------------' Los que esta debajo de aqui is solo para poner un soperte a las dos retinas principales de arriba----------------------------------------------------------------

Private Sub AttachBitCodes(BitStrings, HTNode As Collection, ByVal Bits) If HTNode Is Nothing Then Exit Sub If HTNode(htnIsLeaf) Then S HTNode, htnBitCode, Bits Set BitStrings(Asc(HTNode(htnAsciiCode))) = HTNode Else ReDim Preserve Bits(UBound(Bits) + 1) Bits(UBound(Bits)) = 1 AttachBitCodes BitStrings, HTNode(htnLeftSubtree), Bits Bits(UBound(Bits)) = 0 AttachBitCodes BitStrings, HTNode(htnRightSubtree), Bits End IfEnd Sub

Private Function BitsToString(Bits) As String Dim Char As Byte, i As Long BitsToString = Chr(UBound(Bits) + 1) 'Number of bits For i = 0 To UBound(Bits) If i Mod 8 = 0 Then If i > 0 Then BitsToString = BitsToString & Chr(Char) Char = 0 End If If Bits(i) = 1 Then 'Bit value = 1 'Mask the bit into its proper position in the byte Char = Char + 2 ^ (i Mod 8) End If Next BitsToString = BitsToString & Chr(Char)End Function

Private Function StringToBits(StartPos As Long, Bytes As String) Dim Char As Byte, i As Long, BitCount As Long, Bits

Bits = Array() BitCount = Asc(Mid(Bytes, StartPos, 1)) StartPos = StartPos + 1 For i = 0 To BitCount - 1 If i Mod 8 = 0 Then Char = Asc(Mid(Bytes, StartPos, 1)) StartPos = StartPos + 1 End If ReDim Preserve Bits(UBound(Bits) + 1) If (Char And 2 ^ (i Mod 8)) > 0 Then 'Bit value = 1 Bits(UBound(Bits)) = 1 Else 'Bit value = 0 Bits(UBound(Bits)) = 0 End If Next StringToBits = BitsEnd Function

Private Sub S(Col As Collection, Index As HuffmanTreeNodeParts, Value) Col.Remove Index If Index > Col.Count Then Col.Add Value Else Col.Add Value, , Index End IfEnd Sub

Private Function NewNode() As Collection Dim Node As New Collection Node.Add 0 'htnWeight Node.Add False 'htnIsLeaf Node.Add Chr(0) 'htnAsciiCode Node.Add "" 'htnBitCode Node.Add Nothing 'htnLeftSubtree Node.Add Nothing 'htnRightSubtree Set NewNode = NodeEnd Function