Symbol := Symbol return Result end Create_Node - create internal node function Create_Node ( Left, Right : Node_Access ) return Node_Access is Result : Node_Access := new Huffman_Node begin Result. Map, Prefix => Zero_Sequence ) end Create_Tree - create leaf node function Create_Node ( Symbol : Symbol_Type Frequency : Frequency_Type ) return Node_Access is Result : Node_Access := new Huffman_Node begin Result. Append ( The_Node ) Next ( Position ) end loop end - sort by frequency (see " Tree. With Ada.Text_IO with Ada.Unchecked_Deallocation with package body Huffman is package Node_Vectors is new ( Element_Type => Node_Access, Index_Type => Positive ) function " Key ( Position ), Frequency => Element ( Position )) Node_Queue. Empty_Map end record - free memory after finalization overriding procedure Finalize ( Object : in out Huffman_Tree ) end Huffman Controlled with record Tree : Node_Access := null Map : Encoding_Maps. Map Prefix : Bit_Sequence ) - huffman tree has a tree and an encoding map type Huffman_Tree is new Ada. Map ) - encode a single symbol function Encode ( Tree : Huffman_Tree Symbol : Symbol_Type ) return Bit_Sequence - encode a symbol sequence function Encode ( Tree : Huffman_Tree Symbols : Symbol_Sequence ) return Bit_Sequence - decode a bit sequence function Decode ( Tree : Huffman_Tree Code : Bit_Sequence ) return Symbol_Sequence - dump the encoding table procedure Dump_Encoding ( Tree : Huffman_Tree ) private - type for encoding map package Encoding_Maps is new _Ordered_Maps ( Element_Type => Bit_Sequence, Key_Type => Symbol_Type ) type Huffman_Node type Node_Access is access Huffman_Node - a node is either internal (left_child/right_child used) - or a leaf (left_child/right_child are null) type Huffman_Node is record Frequency : Frequency_Type Left_Child : Node_Access := null Right_Child : Node_Access := null Symbol : Symbol_Type end record - create a leaf node function Create_Node ( Symbol : Symbol_Type Frequency : Frequency_Type ) return Node_Access - create an internal node function Create_Node ( Left, Right : Node_Access ) return Node_Access - fill the encoding map procedure Fill ( The_Node : Node_Access Map : in out Encoding_Maps. 0 ) := ( others => False ) - output the sequence procedure Put ( Code : Bit_Sequence ) - type for freqency map package Frequency_Maps is new _Maps ( Element_Type => Frequency_Type, Key_Type => Symbol_Type ) type Huffman_Tree is private - create a huffman tree from frequency map procedure Create_Tree ( Tree : out Huffman_Tree Frequencies : Frequency_Maps. With _Ordered_Maps with _Maps with Ada.Finalization generic type Symbol_Type is private with function " with procedure Put ( Item : Symbol_Type ) type Symbol_Sequence is array ( Positive range ) of Symbol_Type type Frequency_Type is private with function "+" ( Left, Right : Frequency_Type ) return Frequency_Type is with function " package Huffman is - bits = booleans (true/false = 1/0) type Bit_Sequence is array ( Positive range ) of Boolean Zero_Sequence : constant Bit_Sequence ( 1. (See the WP article for more information).Ī Huffman encoding can be computed by first creating a tree of nodes: The Huffman coding scheme takes each symbol and its weight (or frequency of occurrence), and generates proper encodings for each symbol taking account of the weights of each symbol, so that higher weighted symbols have fewer bits in their encoding. then you would not know if you should decode an 'e' or an 'x'. If you were to assign a code 01 for 'e' and code 011 for 'x', then if the bits to decode started as 011. To successfully decode such as string, the smaller codes assigned to letters such as 'e' cannot occur as a prefix in the larger codes such as that for 'x'. You can do better than this by encoding more frequently occurring letters such as e and a, with smaller bit strings and less frequently occurring letters such as q and x with longer bit strings.Īny string of letters will be encoded as a string of bits that are no-longer of the same length per letter. Huffman encoding is a way to assign binary codes to symbols that reduces the overall number of bits used to encode a typical string of those symbols.įor example, if you use letters as symbols and have details of the frequency of occurrence of those letters in typical strings, then you could just encode each letter with a fixed number of bits, such as in ASCII codes. You are encouraged to solve this task according to the task description, using any language you may know.
0 Comments
Leave a Reply. |