'===========================================================================
' Subject: HUFFMAN COMPRESSION ALGORITHM     Date: 10-16-99 (19:56)       
' Author:  Michael T. Rankin                 Code: LB                     
' Origin:                                  Packet: LIBERTY.ABC
'===========================================================================
'Huffman Compression Algorithm by Michael Rankin
'February 1999
'Requires Liberty Basic 1.41


    Dim Key$(255,2)
    dim tree$(255,2)

    Input "Enter String to Compress: "; instring$
    NOC = LEN(instring$)

' Count the frequency of each character in the string
    Csr=0
    while Csr<>LEN(instring$)
      Csr=Csr+1
        X=ASC(MID$(instring$,Csr,1))
          Key$(X,1)=MID$(instring$,Csr,1)
        Key$(X,2)=STR$(VAL(Key$(X,2))+1)
      if VAL(Key$(X,2))<2 then NF=NF+1
    wend

' Need to subtract 1 from NF to account for 0.
    NF = NF - 1
    sort Key$(,0,255,2


' Build the tree by assigning binary value to each letter
    dec=NF
    gosub [dec2bin]
    length=len(binary$)

    for x = 0 to NF
      dec=x:gosub [dec2bin]
        num =asc(Key$(255-x,1))
          tree$(num,1)=Key$(255-x,1)
        while len(binary$)<length
          binary$="0"+binary$
        wend
      tree$(num,2)=binary$
    next x


' Compress the string by replacing each character with a binary value
' then take 8 bits at a time and convert it to an ASCII character
    Csr=0
    while Csr<>LEN(instring$)
      Csr=Csr+1
        X=ASC(MID$(instring$,Csr,1))
          Hold$ = Hold$ + tree$(X,2)
      if len(Hold$)>8 then
        X$=MID$(Hold$,1,8):Hold$=MID$(Hold$,9)
          GOSUB [Bin2Dec]
        Compressed$ = Compressed$ + CHR$(Bin2Dec)
      end if
    wend

' Add a byte at the end that contains any left-over bits
    IF LEN(Hold$)>0 THEN
      STRING=8-LEN(Hold$)
        gosub [Make.String$]
          Hold$=Hold$+STRING$
        X$=LEFT$(Hold$,8)
      gosub [Bin2Dec]:Compressed$=Compressed$ + CHR$(Bin2Dec)
    END IF


' Print the results
    print:print
    a=LEN(Compressed$)/LEN(instring$)
    b$=str$(100-val(mid$(str$(a),3,2)))+"%"
    PRINT "Original size of the string was: ";LEN(instring$);" bytes"
    PRINT "Compressed size of string is ";LEN(Compressed$);" bytes"
    PRINT:PRINT "This is what it looks like compressed: ";Compressed$
    print:print "The string was compressed by ";b$
    print

input "Press Enter to uncode"; whatever


' **** Unpack compressed string into character representation of binary

    J=0 : UnCompr$="" : NewText$=""
    while J<>LEN(Compressed$)
         J=J+1
         Hold$=MID$(Compressed$,J,1)
         dec=ASC(Hold$)
         gosub [dec2bin]
         Hold$=binary$
            WHILE LEN(Hold$)<8 : Hold$="0"+Hold$ : WEND
         UnCompr$=UnCompr$+Hold$
    wend

' Decode compressed string
    sort tree$(,0,255,2
    place=1
    while DL<>NOC
      DL=DL+1
        X$=Mid$(UnCompr$,place,length)
          GOSUB [Bin2Dec]
        NewText$=NewText$+tree$(255-NF+Bin2Dec,1)
      place=place+length
    wend

[xit]
    Print:Print:Print "Here's your original text: "; NewText$
    END
' *************************************************
' This is just converts decimal into binary numbers
[dec2bin]
    binary$="":result = 2
    while result > 1
      result = dec/2
        remainder = dec - (int(result)*2)
          binary$ = str$(remainder) + binary$
        dec = int(result)
      if result = 1 then binary$ = str$(1) + binary$
    wend
  return


' This is just converts binary into decimal numbers
[Bin2Dec]
    Tmp=1
    Bin2Dec=0
    FOR a = LEN(X$) TO 1 STEP -1
        Bin$ = MID$(X$, a, 1)
        IF Bin$ = "1" THEN Bin2Dec = Bin2Dec + Tmp
        Tmp = Tmp * 2
    NEXT a
    return


' Make the left over bits into a byte
[Make.String$]
    WHILE STRING<>0
        STRING$=STRING$+"0"
        STRING=STRING-1
    wend
    RETURN