Dúvida sobre Codificação Huffman

[LunarPH]

Alguém aí sabe como essa codificação funciona?, estava tentando traduzir o arquivo arquivo dos cards do game Tag Force Special, porém notei que tinha esse tipo de codificação neles..

[Anime_World]

Sim, é um sistema de compressão de dados que usa arvores binárias.

O algoritmo de Huffman recebe um fluxo de bits e devolve um fluxo de bits comprimido que representa o fluxo original. Em geral, o fluxo comprimido é mais curto que o original.

O fluxo de bits original é lido de 8 em 8 bits (byte a byte), como se fosse um fluxo de caracteres. Transformando uma string em um cadeia de bits.

Por exemplo, a string "ABRACADABRA!" vai emitir uma saída:

Código Selecionar Expandir


Hexadecimal                             4A       CE       4A       F
Binário                                 01001010 11001110 01001010 1111

Por ser uma arvore binária você deve ir populando seus nós (O ideal é popular pelo número de ocorrências, do maior para o menor, mas pra exemplicar vou colocar na ordem de escrita). Ficando da seguinte forma:

Código Selecionar Expandir


0            |              1
|------------ --------------|
"A"          0              |             1
              |-------------- -------------|
      0       |       1             0      |       1
      |------- -------|             |------ -------|
     "B"             "R"            |         0    |    1
                                   "C"        |---- ----|
                                             "D"       "!"



Assim temos a seguinte tabela:

Código Selecionar Expandir


0    = A
100  = B
101  = R
110  = C
1110 = D
1111 = !


Agora se retornarmos a saída e colocarmos os valores das strings teremos:

Código Selecionar Expandir


Hexadecimal                             4A       CE       4A       F
Binário                                 01001010 11001110 01001010 1111
String                                  ABRA     CAD      ABRA     !


Portanto uma sequência de 12 bytes foi comprimida em 4 bytes com huffman.

Para fazer a edição desses dados, você vai ter que programar um decompressor/compressor huffman de acordo com a tabela huffman do jogo. Dá pra fazer na mão? Dá, mas é inviável!

[LunarPH]

Sim, é um sistema de compressão de dados que usa arvores binárias.

O algoritmo de Huffman recebe um fluxo de bits e devolve um fluxo de bits comprimido que representa o fluxo original. Em geral, o fluxo comprimido é mais curto que o original.

O fluxo de bits original é lido de 8 em 8 bits (byte a byte), como se fosse um fluxo de caracteres. Transformando uma string em um cadeia de bits.

Por exemplo, a string "ABRACADABRA!" vai emitir uma saída:

Código Selecionar Expandir


Hexadecimal                             4A       CE       4A       F
Binário                                 01001010 11001110 01001010 1111

Por ser uma arvore binária você deve ir populando seus nós (O ideal é popular pelo número de ocorrências, do maior para o menor, mas pra exemplicar vou colocar na ordem de escrita). Ficando da seguinte forma:

Código Selecionar Expandir


0            |              1
|------------ --------------|
"A"          0              |             1
              |-------------- -------------|
      0       |       1             0      |       1
      |------- -------|             |------ -------|
     "B"             "R"            |         0    |    1
                                   "C"        |---- ----|
                                             "D"       "!"



Assim temos a seguinte tabela:

Código Selecionar Expandir


0    = A
100  = B
101  = R
110  = C
1110 = D
1111 = !


Agora se retornarmos a saída e colocarmos os valores das strings teremos:

Código Selecionar Expandir


Hexadecimal                             4A       CE       4A       F
Binário                                 01001010 11001110 01001010 1111
String                                  ABRA     CAD      ABRA     !


Portanto uma sequência de 12 bytes foi comprimida em 4 bytes com huffman.

Para fazer a edição desses dados, você vai ter que programar um decompressor/compressor huffman de acordo com a tabela huffman do jogo. Dá pra fazer na mão? Dá, mas é inviável!

Sim eu já entendo um pouco de huffman, porém a dificuldade mesmo e entender como é a tabela do jogo e como ele puxa as palavras dos arquivos que ele monta...
Cada código hex que eu mudo no arquivo, ele meio que troca às palavras por outras.
Agora preciso entender como identificar o código da palavra para recriar ela no arquivo e montar uma ordem de palavras novas.
(Bem o jogo tem 3 arquivos, 1 com os códigos hex, 1 escrito huff, e o último que tem as palavras cortadas que são usadas no game, fora o arquivo index.)