Encriptación - Compreción [Algoritmo Huffman]

Deeo
Habitual

Desconectado

Mensajes: 225

Ozzy Slave.

Encriptación - Compreción [Algoritmo Huffman]

« en: Julio 26, 2008, 10:49:39 »

Hola que tal como estan, aca les traigo algo interesante, como Comprimir archivos con el Algoritmo Huffman, y al estan comprimidos se puede usar un facilmente para encriptar archivos.

Bien abrimos un Proyecto nuevo y comocamos en un Modulo lo siguiente:

'################################################################
' Huffman Coding Compression / Decompression Algorithm
' Created 1 August 2000 by James Vincent Carnicelli
'
' NOTES
'
' The Huffman algorithm, named after its inventor, was created
' around about 1952. It's the method used by most commercial
' compression utilities, like PKZIP, and even by the JPEG image
' file format. It's generally thought to offer an average of
' 50% compression, given a typical mix of text and binary data.
' For long strings that contain lots of repeating characters or
' only a handful of different characters, the compression ratio
' could get as high as 80%. While efficient, this algorithm is
' not guaranteed to result in a compressed string that is
' smaller than the original source.
'
' This is a less-than-optimal implementation of this compression
' algorithm. It's very simple to use in your programs (even if
' it is difficult to understand how it works). You need only
' call:
'
' Compressed = HuffmanEncode(SourceText, [Force])
'
' passing in the text you want compressed. If the compressed
' version is actually larger than the original source, this
' algorithm spits out a special string that contains a four-
' byte header and the original source string, so the resulting
' string will always be at most four bytes larger than the
' source string. If you pass in True for Force, the result will
' always be huffman-encoded, bypassing this neat optimization.
' Be aware that the output is binary data, so it might not work
' nicely with some things like text boxes, certain Windows
' API calls, and some SQL and database field formats.
'
' To decode a string encoded with HuffmanEncode, simply call
' the following:
'
' UncompressedText = HuffmanDecode(Compressed)
'
' One cool application of this algorithm is encryption. Because
' Huffman coding relies on variable-bit-length character
' representations, it's next to impossible to decrypt a string
' compressed with this algorithm without recognizing the
' lookup tables in the header as the key to decrypting it. You
' could even strip out this lookup table and keep it as a
' private key to be shared only with those you want. Without
' the lookup table, even someone equiped with this very code
' would not likely be able to decrypt the string.
'
' One last thing. While I've tested this algorithm with plain
' text strings and even some binary files, I don't know how
' much data you can cram into the compression engine before it
' breaks. With luck, it's something like 2GB. In that case,
' though, this would be pretty slow. Also, I have not proven
' beyond a doubt that this won't choke on some data, so I would
' encourage you to do so to your satisfaction before putting
' this into full production. Be sure to let me know if you find
' anything interesting.
'################################################################

Option Explicit

Private Enum HuffmanTreeNodeParts
htnWeight = 1
htnIsLeaf = 2
htnAsciiCode = 3
htnBitCode = 4
htnLeftSubtree = 5
htnRightSubtree = 6
End Enum

'Compress the text.
Public 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

'Initialize for processing.
TextLen = Len(Text)
Set HuffmanTrees = New Collection

'Is there anything to encode?
If TextLen = 0 Then
HuffmanEncode = "HE0" & vbCr 'Version 0 = Plain text
Exit Function 'No point in continuing
End If

HuffmanEncode = "HE2" & vbCr 'Version 1

'Count how many times each ASCII code is encountered in text.
For i = 1 To TextLen
Char = Asc(Mid(Text, i, 1))
CodeCounts(Char) = CodeCounts(Char) + 1
Next

'Initialize the forest of Huffman trees; one for each ASCII
'character used.
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

'Now place 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
End If
Next

'Now assemble all these single-level Huffman trees into
'one single tree, where all the leaves have the ASCII codes
'associated with them.
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

'The next part of the header is a checksum value, which
'we'll use later to verify our decompression.
Char = 0
For i = 1 To TextLen
Char = Char Xor Asc(Mid(Text, i, 1))
Next
HuffmanEncode = HuffmanEncode & Chr(Char)

'The final part of the header identifies how many bytes
'the original text strings contains. We will probably
'have a few unused bits in the last byte that we need to
'account for. Additionally, this serves as a final check
'for corruption.
HuffmanEncode = HuffmanEncode & TextLen & vbCr

'Now we can encode the data by exchanging each ASCII byte for
'its appropriate bit string.
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

'If it takes up more space compressed because the source is
'small and the header is big, we'll leave it uncompressed
'and prepend it with a 4 byte header.
If Len(HuffmanEncode) > TextLen And Not Force Then
HuffmanEncode = "HE0" & vbCr & Text
End If
End Function

'Decompress the string back into its original text.
Public 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

'If this was left uncompressed, this will be easy.
If Left(Text, 4) = "HE0" & vbCr Then
HuffmanDecode = Mid(Text, 5)
Exit Function
End If

'If this is any version other than 2, we'll bow out.
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)

'Extract the ASCII character bit-code table's byte length.
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)
'Now extract the ASCII character bit-code table.
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)

'Extract the length of the original string.
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)

'Now that we've processed the header, let's decode the actual data.
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
'Uh oh. We've followed the tree to a Huffman tree to a dead
'end, which won't happen unless the data is corrupt.
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

'Verify data to check for corruption.
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 If
End Function

'----------------------------------------------------------------
' Everything below here is only for supporting the two main
' routines above.
'----------------------------------------------------------------

'Follows the tree, now built, to its end leaf nodes, where the
'character codes are, in order to tell those character codes
'what their bit string representations are.
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 If
End Sub

'Turns a string of '0' and '1' characters into a string of bytes
'containing the bits, preceeded by 1 byte indicating the
'number of bits represented.
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 Cool

End If
Next
BitsToString = BitsToString & Chr(Char)
End Function

'The opposite of BitsToString() 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 Cool

) > 0 Then 'Bit value = 1
Bits(UBound(Bits)) = 1
Else 'Bit value = 0
Bits(UBound(Bits)) = 0
End If
Next
StringToBits = Bits
End Function

'Remove the specified item and put the specified value in its place.
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 If
End Sub

'Creates a new Huffman tree node with the default values set.
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 = Node
End Function

Y en un Formulario, colocamos 2 Botones, Command1 (Comprimir) y Command2 (Descomprimir), tambien agregarmos un CommondDialog, para cargarlo vamos a: Proyecto >> Componentes, ahy buscamos y seleccionamos la opción Microsoft Commond Dialog Control 6.0, y hacemos clic en aceptar, lo colocamos en el formulario y lo renombramos a CD por comodidad y colocamos en el form este code:

Dim Archivo As String 'Esta es la variable que almacenara los bites del archivo

Private Sub Command1_Click()
CD.ShowOpen 'Abrimos la ventana de dialogo
If CD.FileName <> "" Then 'Si elejimos un archivo ....
Open CD.FileName For Binary As #1 'Abrimos el archivo
Archivo = Space(LOF(1))
Get #1, , Archivo 'Tomamos los bites del archivo
Close #1 ' Lo cerramos

CD.ShowSave
If CD.FileName <> "" Then
Open CD.FileName For Binary As #2 'Abrimos el nuevo el archivo
Put #2, , HuffmanEncode(Archivo, True) 'Colocamos Los bits encriptados
Close #2 'Lo cerramos
Else
Exit Sub
End If

Else ' Si no elejimos nada...
Exit Sub 'Salimos
End If
End Sub

Private Sub Command2_Click()
CD.ShowOpen 'Abrimos la ventana de dialogo
If CD.FileName <> "" Then 'Si elejimos un archivo ....
Open CD.FileName For Binary As #1 'Abrimos el archivo
Archivo = Space(LOF(1))
Get #1, , Archivo 'Tomamos los bites del archivo
Close #1 ' Lo cerramos

CD.ShowSave
If CD.FileName <> "" Then
Open CD.FileName For Binary As #2 'Abrimos el nuevo el archivo
Put #2, , HuffmanDecode(Archivo) 'Colocamos Los bits desencriptados
Close #2 'Lo cerramos
Else
Exit Sub
End If

Else ' Si no elejimos nada...
Exit Sub 'Salimos
End If
End Sub

Este codigo esta dedicado a Forious Dami que me pidio que le explicara como utilizar esta opción. Bueno espero que les sirva y que puedan hacer varias cosas con este lindo Algoritmo.

Salu2
Deeo Raiser


	En línea

Los seres queridos hacen que la vida valga la pena, los enemigos...que tenga sentido.
CrEaCiOnEs DeeoRaiser Production®

Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion
Change Icon
,
Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion
BaTcH CoMpIlEr 2.2b
,
Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion
KGB Tool's (Encriptadores)
,
Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion
Password Keeper
,
Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion
Steal IP
,
Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion
Tres en Raya (Imposible de ganar)

sami el dragon rosa
Colaborador

Desconectado

Mensajes: 451

Re: Encriptación - Compreción [Algoritmo Huffman]

« Respuesta #1 en: Julio 27, 2008, 08:23:14 »

me podrias explicar con tus palabras en q consiste ese algoritmo?


	En línea

Deeo
Habitual

Desconectado

Mensajes: 225

Ozzy Slave.

Re: Encriptación - Compreción [Algoritmo Huffman]

« Respuesta #2 en: Julio 28, 2008, 08:30:04 »

La verdad es bastante complicado de explicar, asique nadie mejor para hacerlo que Wikipedia, has Click
Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion

AQUI

y mira la explicación.


	En línea

sami el dragon rosa
Colaborador

Desconectado

Mensajes: 451

Re: Encriptación - Compreción [Algoritmo Huffman]

« Respuesta #3 en: Julio 29, 2008, 03:31:47 »

lo que suponia... vamos que no te has enterado de nada... empezando pq no es complciado de explicar (sobre todo si lo entiendes) xD


« Última modificación: Julio 29, 2008, 03:33:01 por sami »	En línea

alesteir
Visitante

Re: Encriptación - Compreción [Algoritmo Huffman]

« Respuesta #4 en: Julio 29, 2008, 05:08:53 »

Sami explícanos tu, siempre me gustan tus explicaciones, y este tema se ve que te gusta!


	En línea

sami el dragon rosa
Colaborador

Desconectado

Mensajes: 451

Re: Encriptación - Compreción [Algoritmo Huffman]

« Respuesta #5 en: Julio 30, 2008, 02:46:40 »

me podria llevar varias horas explicarlo...
si hay otras 4 personas interesadas me tomare mi tiempo.


	En línea

plof
Miembro

Desconectado

Mensajes: 92

Re: Encriptación - Compreción [Algoritmo Huffman]

« Respuesta #6 en: Julio 30, 2008, 03:51:09 »

Cita de: Deeo en Julio 26, 2008, 10:49:39

Hola que tal como estan, aca les traigo algo interesante, como Comprimir archivos con el Algoritmo Huffman, y al estan comprimidos se puede usar un facilmente para encriptar archivos.

Esa no es una buena definición del algoritmo de Huffman.
No me gusta replicar a nadie pero ya que envias a sami a la wikipedia podías haberle echado un vistazo primero.

Cita de: WiKipEdia

La codificación Huffman es un algoritmo usado para compresión de datos.
La codificación Huffman usa un método específico para elegir la representación de cada símbolo, que da lugar a un código prefijo (es decir, la cadena de bits que representa a un símbolo en particular nunca es prefijo de la cadena de bits de un símbolo distinto) que representa los caracteres más comunes usando las cadenas de bits más cortas, y viceversa.

La verdad es que entiendo bastante poco de vbs así que intentaré exponer un posible diseño preliminar para un lenguaje cualquiera tomando como referencia el ejemplo de la wikipedia.

Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion

.:.Diseño del algoritmo.:.

.:TDAs empleados:.
* Contenedor que almacene la tabla de frecuencias.
* Cola con prioridad.
* Bintree (árbol binario).
* Contenedor que almacene la tabla de codificación.

Para cada elemento de las tablas, se almacenaran un par <clave,valor> y se exigirá una mayor eficiencia en busqueda por clave. En ambos contenedores, la 'clave' será el símbolo y el 'valor' será la frecuencia o el código asociado según la tabla. Para una mayor eficiencia de búsqueda recomiendo contenedores del tipo asociativos como diccionarios o una tabla de hash con órdenes de eficiencia logarítmico.
Si el lenguaje lo permite, recomiendo uso de clases para bintree, los contenedores y aún más, una clase código Huffman si queremos que nuestro código haga algo más que codificar un triste y solitario documento.
Además podíamos plantearnos usar un buffer para no estar accediendo sucesivas veces al documento.
Creo que sobra decir que deberíamos de tener bien claro el diseño y representación del problema antes de ponernos a dar pantallazos con el pc.

.:Construción del árbol:.
Primero tendremos que hacer una pasada al documento y almacenar cada símbolo y su respectiva frecuencia en un contenedor. Para cada símbolo del contenedor creamos un árbol etiquetado con <símbolo, frecuencia> y los vamos introduciendo en una cola con prioridad cuyos elementos se ordenan según la frecuencia de menor a mayor.

Cita de: WiKipEdia

Se crean varios árboles, uno por cada uno de los símbolos del alfabeto,
consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetado
cada uno con su símbolo asociado y su frecuencia de aparición.

Mientras haya más de un elemento en la cola con prioridad...

Cita de: WiKipEdia

Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol.
También se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un 1 la de la derecha.

Sí, de acuerdo, pero daros cuenta que eso de etiquetar las ramas con 0's y 1's como que no hace falta ya que bajar por un hijo izquierdo lo interpretaremos como un 0 y por el hijo derecho como un 1 ( o viceversa ).

Una vez estén todos los árboles en la cola con prioridad, vamos sacando los dos primeros, creamos un árbol (con frecuencia igual a la suma de los dos extraídos de la cola ) y ramificamos a la izquierda y derecha con estos dos.

Cola con Prioridad ( iteración 0 )
(1)F    0.05
(2)D    0.05
(3)G    0.10
(4)E    0.15
(5)A    0.15
(6)C    0.20
(7)B    0.30

Cola con Prioridad ( iteración 1 )
(1) 0.10
/\
D F
(2)G    0.10
(3)E    0.15
(4)A    0.15
(5)C    0.20
(6)B    0.30

Cola con Prioridad ( iteración 2 )
(1)E    0.15
(2)A    0.15
(3) 0.20
/ \
/ /\
G D F
(4)C    0.20
(5)B    0.30

Cola con Prioridad ( iteración 3 )
(1) 0.20
/ \
/ /\
G D F
(2)C    0.20
(3)      0.30
/\
A E
(4)B    0.30

Cola con Prioridad ( iteración 4 )
(1)      0.30
/\
A E
(2)B    0.30
(3) 0.40
/ \
/ /\
/ / /\
C G D F

Cola con Prioridad ( iteración 5 )
(1) 0.40
/ \
/ /\
/ / /\
C G D F

(2) 0.60
/ \
/ /\
B A E

Cola con Prioridad ( iteración 6 )
(end) Nodo Raiz
/ \
/ \
/ \
/ /\
/\ / / \
/ /\ / / /\
B A E C G D F

Ya tenemos el árbol montado, pero fijaros bien que el dibujo ascii es indicativo ya que en realidad los nodos hojas de los símbolos de mayor frecuencia (B,C) pertenecean a un nivel inferior a los símbolos de menor frecuencia lo que minimiza el tamaño del documento codificado.

Las características del árbol dependen del número de símbolos distintos que disponemos.
Si contamos con un alfabeto de tamaño m:
- El número de nodos en el árbol de Huffman es de 2m-1.
- Si hay m nodos pueden haber como máximo (m+1)/2 niveles y como mínimo log2(m+1) niveles.

Necesitas ser usuario para ver los enlaces Crear Usuario Hacer Sesion

.:Codificación:.

Cita de: WiKipEdia

Para obtener el código asociado a un símbolo se debe proceder del siguiente modo:
1. Comenzar con un código vacío
2. Iniciar el recorrido del árbol en la hoja asociada al símbolo
3. Comenzar un recorrido del árbol hacia arriba
4. Cada vez que se suba un nivel, añadir al código la etiqueta de la rama que se ha recorrido
5. Tras llegar a la raíz, invertir el código
6. El resultado es el código Huffman deseado

Sí, muy bonito, pero ésto implica que en la clase bintree debemos tener en cada nodo un puntero apuntando al nodo padre y deberíamos poder detectar si hemos subido por el hijo izquierdo o derecho además de tener que buscar la hoja que correspona en cada momento.

En vez de hacer sucesivos recorridos por el árbol para cada símbolo a codificar, lo ideal sería recorrer en preorden* el árbol una sola vez y almacenar la tabla de codificación en un nuevo contenedor donde la 'clave' sería cada símbolo y el 'valor' su código binario correspondiente. Un poco más de memoria pero mucho más eficiente.
*NoTa: El recorrido en preorden comienza por el nodo raiz y luego va explorando cada uno de sus hijos en orden previo.
De esta forma, vamos recorriendo el documento, buscamos los símbolos en el contenedor y vamos codificando mientras quede algún símbolo en el documento.

.:Decodificación:.

Cita de: WiKipEdia

Para obtener un símbolo a partir de un código se debe hacer así:
1. Comenzar el recorrido del árbol en la raíz de éste
2. Extraer el primer símbolo del código a descodificar
3. Descender por la rama etiquetada con ese símbolo
4. Volver al paso 2 hasta que se llegue a una hoja, que será el símbolo asociado al código

Como ya he dicho antes, la rama debería ser una idea y no se debería de incluir dentro de la clase bintree. Fijaros que si queremos un árbol n-ario, pues buscamos el hijo que corresponda con un contador y no con ramas etiquetadas.

De esta forma, vamos recorriendo el documento y bajando por el árbol desde la raiz hasta las hojas.
Si leemos un 0 bajamos por el hijo izquierdo y si leemos un 1 por el derecho (o viceversa).
Cuando llegamos a una hoja, decodificamos con el símbolo que indica la etiqueta de la hoja y volvemos a la raiz para seguir leyendo el resto del documento a decodificar.

Cita de: WiKipEdia

En la práctica, casi siempre se utiliza el árbol para obtener todos los códigos de una sola vez;
luego se guardan en tablas y se descarta el árbol.

Desde mi punto de vista, se debería de emplear una tabla para la codificación y un árbol binario para la decodificación y nunca llegar a descartar el árbol.

.:Análisis de eficiencia:.
n: número de símbolos del documento.
n': número de símbolos del documento codificado.
m: tamaño del alfabeto (número de símbolos distintos).
* Construcción del árbol
- Tabla de frecuencias O(n*log(m)).
O(n): recorrer cada símbolo.
O(log(m)): busqueda y actualización de frecuencia.
- Cola con prioridad O(m-1).

* Codificación
- Tabla de codificación O(2m-1).
Recorremos en preorden 2m-1 nodos.
- Busqueda y codificación O(n*log(m)).
O(n): recorrer cada símbolo.
O(log(m)): busqueda y codificación del símbolo.

* Decodificación
- Recorrer el documento y decodificar O(n').

Estos datos de eficiencia se dan siempre y cuando hayamos escogido los TDA's apropiados.

Un SaLUdO.

pd.

Cita de: sami en Julio 30, 2008, 02:46:40

si hay otras 4 personas interesadas me tomare mi tiempo.

Puedes dejar de contar Tongue


	En línea

Páginas: [1]

Comunidad Underground Hispana \| Programacion \| Programación \| Visual Basic y Net (Moderador: ANYD00M) \| Tema: Encriptación - Compreción [Algoritmo Huffman]	« anterior próximo »

	Bienvenido(a), Visitante. Favor de ingresar o registrarse. ¿Perdiste tu email de activación? - Enero 08, 2009, 10:56:27