Huffman Coding 
Author Message
 Huffman Coding

Does anyone out there has any sort of algorithmn or source code for Huffaman
Codding


Sat, 19 May 2001 03:00:00 GMT  
 Huffman Coding
Please Help !!!!!!

Does anyone have the source code for Huffman Coding ?



Sat, 19 May 2001 03:00:00 GMT  
 Huffman Coding

Quote:

> Does anyone out there has any sort of algorithmn or source code for Huffaman
> Codding

http://www.geocities.com/SiliconValley/2926/tp.html
chapter information, look for Joe Jared, please!

Franz Glaser



Sat, 19 May 2001 03:00:00 GMT  
 Huffman Coding

Quote:

> Does anyone out there has any sort of algorithmn or source code for Huffaman
> Codding

Yes. Get the ChiefLZ v2.0 package from my homepage.

Best regards, The Chief
----------------------------
Dr A{*filter*}la A Olowofoyeku (The African Chief)

Homepage: http://www.*-*-*.com/
Author of: Chief's Installer Pro v4.70 for Win16 and Win32
     ftp://ftp.demon.co.uk/pub/ibmpc/win3/apps/chief/pro/chief470.zip



Sat, 19 May 2001 03:00:00 GMT  
 Huffman Coding
unit Ahuff;

{ adaptive order-0 fixed size Huffman Encoding
  Copyright K.H.S. Weissenbacher
  Internet: www.kers.nl/mensen/bas/default.htm

  -------------------------------------------------------------------
  NOTE:
  -------------------------------------------------------------------
  Using this code for personal or commercial purposes is allowed and
  royalty-free as long as proper credits are given.
  -------------------------------------------------------------------

Quote:
}

interface

uses SysUtils, ComCtrls;

type

Tnode     = record
              count : Integer;
              parent: Integer;
              lchild: Integer; {if negative: value = not lchild}
            end;

TANode    = array[0..2047] of TNode;
PANode    = ^TANode;
TALeaf    = array[0..1023] of Integer;
PALeaf    = ^TALeaf;

TBitProc  = Procedure(b:Boolean) of object; //output procedure type

TBitFunc  = Function:Boolean of object;     //input function type

THuffman  = class
  private
    tree        : PANode;
    leafs       : PALeaf;
    BitOut      : TBitProc;
    BitIn       : TBitFunc;
    unordered   : Boolean;
    Fadaptive   : Boolean;
    NLEAFS      : Integer;
    NNODES      : Integer;
    MAXWEIGHT   : Integer;
    TreeView    : TTreeView;
    Function  AddNode(node:Tnode):Integer;
    Procedure BuildTree; {input: sortlist contains leafnodes}
    Procedure RescaleTree;
    Procedure SetCount(value,count:Integer);
    Function  GetCount(value: Integer): Integer;
    Procedure TraverseTreeRec(NewNode: Integer; ParentNode: TTreeNode);
  public
    Constructor Create(leafcount:Integer);
    Destructor  Destroy; override;
    Procedure EncodeSymbol(v:Integer);
    Function  DecodeSymbol:Integer;
    Procedure UpdateSymbol(v:Integer);
    Procedure RebuildTree;
    Procedure GetTree(ATreeView: TTreeView);
   {------------------------------------------------}
    Property Adaptive: Boolean read Fadaptive write Fadaptive;
    Property MaxCount: Integer read MAXWEIGHT write MAXWEIGHT;
    Property Count[value: Integer]: Integer read GetCount write SetCount;
    Property Input: TBitFunc read BitIn write BitIn; //input function
    Property Output: TBitProc read BitOut write BitOut; //output procedure
  end;

implementation

var

sortlist    : array[0..1023] of Tnode;
sortptr     : Integer;
nodes       : Integer;
childp      : Integer;

Function Thuffman.AddNode(node:Tnode):Integer;
var t:Integer;
begin
  if node.lchild<0 then
  begin {leaf}
    leafs^[not node.lchild]:=nodes;
  end
  else begin {subtree}
         node.lchild:=childp;
         with tree^[childp] do
         begin
           t:=count;
           parent:=nodes;
         end;
         with tree^[childp+1] do
         begin
           Inc(t,count);
           parent:=nodes;
         end;
         node.count:=t;
         Inc(childp,2);
       end;
  node.parent:=nodes+1;
  tree^[nodes]:=node;
  Inc(nodes);
  AddNode:=node.count;
end;

{Sort-list for building tree}

Procedure AddList(node:Tnode);
var n:Integer;
begin
  n:=0;
  while n<>sortptr do
  begin
    if sortlist[n].count<=node.count then BREAK;
    Inc(n);
  end;
  if n<sortptr then
    Move(sortlist[n],sortlist[n+1],(sortptr-n)*Sizeof(Tnode));
  Inc(sortptr);
  sortlist[n]:=node;
end;

Procedure DelList(n:Integer);
begin
  Dec(sortptr,n);
end;

Procedure Thuffman.BuildTree; {input: sortlist contains leafnodes}
var node :Tnode;
begin
  nodes:=0;
  childp:=0;
  node.lchild:=0;
  while sortptr>1 do
  begin
    node.count:=AddNode(sortlist[sortptr-1]);
    Inc(node.count,AddNode(sortlist[sortptr-2]));
    DelList(2);
    AddList(node);
  end;
  AddNode(sortlist[0]);  {rootnode}
  sortptr:=0;
end;

Procedure Thuffman.RebuildTree;
var n:Integer;
begin
  sortptr:=0;
  for n:=NLEAFS-1 downto 0 do
  begin
    AddList(tree^[leafs^[n]]);
  end;
  BuildTree;
  unordered:=FALSE;
end;

Procedure Thuffman.RescaleTree;
var n:Integer;
begin
  for n:=0 to NLEAFS-1 do
  begin
    with tree^[leafs^[n]] do
      count:=succ(count)shr 1;
  end;
  RebuildTree;
end;

Constructor Thuffman.Create(leafcount:Integer);
var n:Integer;
begin
  if (leafcount<=0)or(leafcount>1024) then
    raise Exception.Create(IntToStr(leafcount)+' is illegal number of
leafs');
  adaptive:=True;
  NLEAFS:=leafcount;
  NNODES:=leafcount*2-1;
  MAXWEIGHT:=NNODES*24;
  unordered:=FALSE;
  ReallocMem(tree,NNODES*Sizeof(TNode));
  ReallocMem(leafs,NLEAFS*Sizeof(Integer));
  for n:=0 to NLEAFS-1 do
  begin
    with sortlist[n] do
    begin
      lchild:=not n;
      count :=1;
    end;
  end;
  sortptr:=NLEAFS;
  BuildTree;
end;

Destructor Thuffman.Destroy;
begin
  ReallocMem(tree,0);
  ReallocMem(leafs,0);
  Inherited Destroy;
end;

Procedure Thuffman.UpdateSymbol(v:Integer);
var curnode,newnode,cnt,t:Integer;
    n1,n2:Tnode;
begin
  if unordered then
      RebuildTree;
  if tree^[NNODES-1].count>=MAXWEIGHT then
      RescaleTree;
  curnode:=leafs^[v];
  repeat
    with tree^[curnode] do
    begin
      cnt:=count+1; count:=cnt;
    end;
    newnode:=curnode;
    while tree^[newnode+1].count<cnt do
    begin
      Inc(newnode);
    end;
    if newnode<>curnode then
    begin {swap nodes}
      n1:=tree^[curnode];
      n2:=tree^[newnode];
      if n1.lchild<0 then
        leafs^[not n1.lchild]:=newnode
      else begin {swap children}
             tree^[n1.lchild].parent:=newnode;
             tree^[n1.lchild+1].parent:=newnode;
           end;
      if n2.lchild<0 then
        leafs^[not n2.lchild]:=curnode
      else begin {swap children}
             tree^[n2.lchild].parent:=curnode;
             tree^[n2.lchild+1].parent:=curnode;
           end;
      with tree^[curnode] do
      begin
        count :=n2.count;
        lchild:=n2.lchild;
      end;
      with tree^[newnode] do
      begin
        count :=n1.count;
        lchild:=n1.lchild;
      end;
      curnode:=newnode;
    end;
    curnode:=tree^[curnode].parent;
  until curnode>=NNODES-1;
  Inc(tree^[NNODES-1].count);
end;

Procedure Thuffman.EncodeSymbol(v:Integer);
var stack:array[0..1023] of Boolean;
    sptr,index,t:Integer;
begin
  if not Assigned(Bitout) then
    raise Exception.Create('Huffman: unassigned output function');
  sptr:=0;
  index:=leafs^[v];
  repeat
    t:=tree^[index].parent;
    stack[sptr]:=(tree^[t].lchild=index);
    Inc(sptr);
    index:=t;
  until index>=NNODES-1;
  while sptr>0 do
  begin
    Dec(sptr);
    BitOut(stack[sptr]);
  end;
  if adaptive then
  begin
    UpdateSymbol(v)
  end
  else if unordered then
          RebuildTree;
end;

Function Thuffman.DecodeSymbol:Integer;
var w,index:Integer;
begin
  if not Assigned(BitIn) then
    raise Exception.Create('Huffman: unassigned input function');
  index:=NNODES-1;
  repeat
    if BitIn then index:=tree^[index].lchild
             else index:=tree^[index].lchild+1;
    w:=tree^[index].lchild;
  until w<0;
  DecodeSymbol:=not w;
  if adaptive then
  begin
    UpdateSymbol(not w)
  end
  else if unordered then
          RebuildTree;
end;

{BEWARE ! Setting symbol counts yields an unordered tree. Therefore you
should
 call RebuildTree before calling EncodeSymbol }

Procedure Thuffman.SetCount(value,count:Integer);
begin
  unordered:=TRUE;
  tree^[leafs^[value]].count:=count;
end;

Function Thuffman.GetCount(value: Integer): Integer;
begin
  result:=tree^[leafs^[value]].count;
end;

Procedure THuffman.TraverseTreeRec(NewNode: Integer; ParentNode: TTreeNode);
var tn: TTreeNode;
begin
  with tree^[NewNode] do
  begin
    if lchild < 0 then
    begin
      TreeView.Items.AddChildObject(ParentNode,IntToStr(not lchild)+
                                    '
['+IntToStr(count)+']',Pointer(count));
    end
    else begin

tn:=TreeView.Items.AddChildObject(ParentNode,'['+IntToStr(count)+']',
                                               Pointer(count));
           TraverseTreeRec(lchild+1,tn);
           TraverseTreeRec(lchild,tn);
         end;
  end;
end;

{ Copy Huffman tree into a TreeView component }

Procedure THuffman.GetTree(ATreeView: TTreeView);
begin
  TreeView:=ATreeView;
  TraverseTreeRec(NNODES-1,ATreeView.Selected);
end;

end.



Wed, 23 May 2001 03:00:00 GMT  
 Huffman Coding
Although I don't have the source... I do remember writing a couple of
huffman coding algorithms when I was an idle 15 year old with nothing to
do. If you want I can explain the basic principles of minimum cost
spanning trees, which should get you 80% of the way to an algorithm.

MH.

Quote:

> Please Help !!!!!!

> Does anyone have the source code for Huffman Coding ?



Thu, 24 May 2001 03:00:00 GMT  
 Huffman Coding

Quote:

> unit Ahuff;

Well, I suppose it probably works. It's not going to be very efficient
tho. If I were doing such a thing, I'd write a component that just took
a TStream, and gave you a compressed version of it. In addition, this
implementation is allowing one to huffman encode integers. Are these 16
or 32 bit?  Either way, that's a darn big huffman tree. I'd be tempted
to only allow huffman encoding of bytes, and instead of having to
iterate when encoding or decoding, simply have a look up table between
the 256 possible inputs and outputs. It'll prbably run at at least 6
times the speed, and the compression ratio won't be that much worse
either!

MH.



Thu, 24 May 2001 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Huffman coding in pascal code//~~ Hellp~~~~

2. Huffman Coding in Pascal

3. FLE and Huffman coding in Pascal

4. Help !!! Huffman Coding

5. Need help for Huffman Coding

6. Huffman Coding

7. Huffman code (long, sorry)

8. I need huffman code

9. Help pleaseee :) i need Huffman code

10. HELP!!!! I need a simple HUFFMAN Code!!!!

11. searching for huffman source code

12. searching huffman source code

 

 
Powered by phpBB® Forum Software