Decode Bard's Tale Huffman files

tomas498 · Post by **tomas498** » Wed Nov 30, 2011 10:45 am

Caracas i need compression/decompression of text using static Huffman coding ..

...first script will compress text(from external .txt file) to PAC file using huffman coding and second script will decompress it

(.PAC to .TXT) ...and of course it should be done in VBScript

thanks for any help

Caracas · Post by **Caracas** » Wed Nov 30, 2011 10:52 am

So you need your proxy file coded with a Huffman tree?

tomas498 · Post by **tomas498** » Wed Nov 30, 2011 11:13 am

yes

in one file (.TXT) will be some text and that script will encode/decode it using Huffman tree to another file (.PAC)

i hope you understand ..my english isnt so good :/

Caracas · Post by **Caracas** » Wed Nov 30, 2011 12:28 pm

Why would you code/decode a pac file?

tomas498 · Post by **tomas498** » Wed Nov 30, 2011 12:34 pm

ok so again

it doesnt matter if it will be PAC file or anything else

first script will encode ASCII text from external TXT file to other external file (For example .PAC or .TXT ,it doesnt matter which extension it will be) using Huffman tree.

and second script will decode encoded file using Huffman tree to external .TXT

its something like from mp3 to wav and wav to mp3

i dont know how to better descripe it :/

Caracas · Post by **Caracas** » Wed Nov 30, 2011 12:53 pm

Ah, ok.. I get it now

interesting excersise... creating huffman files out of text files using vbscript. I'll have a look at it, but can't promise you anything.

Again, this might not be the best forum for it but it might be usefull if anyone wants to code their own maps.

tomas498 · Post by **tomas498** » Wed Nov 30, 2011 2:03 pm

thanks Caracas

Caracas · Post by **Caracas** » Mon Dec 05, 2011 11:20 am

ok, been having some fun with this... it's not finished yet, but I'll post what I have

First, you should create a C:\Huffman folder with 2 .txt files and 1 .vbs file in it.

The first .txt file should be named test.txt and can contain the text you want to encode wih Huffman. For my example, I took the following:

Code: Select all

This is a small test to see if I can encode this with a Huffman tree.

The second .txt file should be named coded_test.txt. This is the file where the coded text will appear. If this file is not created, the script will create it for you.

The .vbs file can have any name and should contain:

Code: Select all

Dim objFSO, objCodedFile, objTextFile 
Dim strCharacter
Dim strHuffVal
Dim strCount, tmpCount
Dim arrHuff(255)
Dim arrHuffVal(255)
Dim arrHuffChar(255)

Set objFSO = CreateObject("Scripting.FileSystemObject") 

Set objTextFile = objFSO.OpenTextFile ("C:\Huffman\test.txt", 1) 
Set objCodedFile = objFSO.OpenTextFile ("C:\Huffman\coded_test.txt", 8, True) 
strCount = 0

Do Until objTextFile.AtEndOfStream 
  strCharacter = objTextFile.Read(1)
  strHuffVal = asc(strCharacter)
  arrHuff(strHuffVal) = arrHuff(strHuffVal) + 1
  strCharacter = ""
  strHuffVal = ""
Loop 

for i = 0 to 255
  strCount = arrHuff(i)
  if strCOunt = "" then
  'do nothing
  else
  tmpCount = tmpCount + 1
  arrHuffVal(tmpCount) = arrHuff(i)
  arrHuffChar(tmpCount) = i
  end if
next

for a = tmpCount - 1 To 0 Step -1
     for j= 0 to a
         if arrHuffVal(j)>arrHuffVal(j+1) then
             temp=arrHuffVal(j+1)
             tempChar=arrHuffChar(j+1)
             arrHuffVal(j+1)=arrHuffVal(j)
             arrHUffChar(j+1)=arrHuffChar(j)
             arrHuffVal(j)=temp
             arrHuffChar(j)=tempChar
         end if
     next
next

for k = 1 to tmpCount
  strBin=""
  strBinCalc = arrHuffChar(k)
  Do While strBinCalc > 0
    If strBinCalc Mod 2 > 0 Then
      strBin = "1" & strBin
    Else
      strBin = "0" & strBin
    End If
  strBinCalc = Int(strBinCalc / 2)
  Loop
  Do While len(strBin) < 8
    strBin = "0" & strBin
  Loop
  objCodedFile.Writeline(arrHuffVal(k) & "," & arrHuffChar(k) & "," & strBin)
next

objTextFile.Close 
objCodedFile.Close

When launching this script with the correct .txt files in the correct folder, this gives me following result on my test.txt file:

Code: Select all

1,46,00101110
1,72,01001000
1,73,01001001
1,84,01010100
1,100,01100100
1,114,01110010
1,117,01110101
1,119,01110111
2,99,01100011
2,108,01101100
2,109,01101101
2,111,01101111
3,102,01100110
3,104,01101000
3,110,01101110
5,97,01100001
5,105,01101001
6,115,01110011
6,116,01110100
7,101,01100101
15,32,00100000

This result is a sorted list of all characters that appear in my test.txt file. The first column indicates the amount of times a certain character appears in the text. The second column is the decimal value of that character on the ASCII table and the 3rd column is the binary value of that character.
So for example, character 32 appears 15 times in my test.txt file, which is a " " (space bar).
"e" (character 101) appears 7 times in my test.txt file.
And so on...

The next step would be to start building the actual Huffman tree. No idea yet how I'm going to do that... looks a bit tricky.
Also, I may be going about this all wrong... I have no idea, I'm just having fun trying to get it all sorted

Caracas · Post by **Caracas** » Mon Dec 05, 2011 1:35 pm

btw Tomas,

you wrote that you use static Huffman coding?
That means you already have a Huffman tree?

tomas498 · Post by **tomas498** » Thu Dec 08, 2011 7:27 pm

great job caracas

i haven't got that Huffman tree but here is the link with Huffman Coding/decoding..i hope it helps you

) many thanks

http://rosettacode.org/wiki/Huffman_coding#Objective-C

tomas498 · Post by **tomas498** » Thu Dec 08, 2011 7:29 pm

its in many programming languages but VBS is missing..

Caracas · Post by **Caracas** » Fri Dec 09, 2011 3:46 pm

hmm.. interesting.
They seem to first build the tree with all the leaves and nodes and then traverse it from root down to assign 1's and 0's as appropriate.

Not sure how this can be scripted. not sure how to 'store' the tree and then traverse it... yet

still looking

tomas498 · Post by **tomas498** » Thu Dec 15, 2011 9:45 am

caracas can you put some comments to every part of your script? i must describe it to my professor and i don't want to be confused

many thanks!

Caracas · Post by **Caracas** » Thu Dec 15, 2011 1:01 pm

lol, so not only you want me (or someone else) to do your homework, but you also want me to explain it to you?

tbh, the first part (script above) is easy enough to understand. If you can't figure that out yourself, then maybe you should try and get another assignement.

As for the rest of the script, the actual creation of the Huffman tree... I'm not seeing it happen very fast. Still looking, but I'm not sure I'll be able to find it.

Caracas · Post by **Caracas** » Mon Dec 19, 2011 4:42 pm

hmm, hmm, might still work out

I am now able to build all the nodes and the leaves of the Huffman tree...
next up: assigning "0"'s and "1"'s where appropriate.

Not going to spam the forum with every progress that I made... I'll hold the code until it's finished.