Decompressing Text There are two functions that work together to decompress text: a generate_tree_xxx function to...

 

Transcribed Image Text:

Decompressing Text There are two functions that work together to decompress text: a generate_tree_xxx function to generate a tree from its representation in a file, and a decompress_bytes function to generate the text itself. First, the functions to generate a Huffman tree from its file representation. Note that you are being asked to write two different generate_tree_xxx functions. Once you get one of them working, you can successfully decompress text. But we're asking for both, so don't forget to do the other one! generate_tree_general takes a list of ReadNodes representing a tree in the form that it is stored in a file. It reconstructs the Huffman tree and returns the root HuffmanTree object. This function assumes nothing about the order in which the nodes are given in the list. As long as it is given the index of the root node, it will be able to reconstruct the tree. This means that the tree nodes could have been written in postorder (as your assignment does), preorder, inorder, level-order, random-order, whatever. Note that the number of each node in the list corresponds to the index of the node in the list. That is, the node at index 0 in the list has node-number 0, the node at index 1 in the list has node-number 1, etc. # # Functions for decompression def generate_tree_general(node_lst: list[ReadNode], root_index: int) -> HuffmanTree: """ Return the Huffman tree corresponding to node_lst[root_index]. The function assumes nothing about the order of the tree nodes in the list. >>> 1st = [ReadNode(0, 5, 0, 7), ReadNode (0, 10, 0, 12), \ ReadNode (1, 1, 1, 0)] >>> generate_tree_general (1st, 2) Huffman Tree (None, Huffman Tree (None, Huffman Tree (10, None, None), \ Huffman Tree (12, None, None)), \ Huffman Tree (None, Huffman Tree (5, None, None), Huffman Tree (7, None, None))) || || || # TODO: Implement this function ht= Huffman Tree () Decompressing Text There are two functions that work together to decompress text: a generate_tree_xxx function to generate a tree from its representation in a file, and a decompress_bytes function to generate the text itself. First, the functions to generate a Huffman tree from its file representation. Note that you are being asked to write two different generate_tree_xxx functions. Once you get one of them working, you can successfully decompress text. But we're asking for both, so don't forget to do the other one! generate_tree_general takes a list of ReadNodes representing a tree in the form that it is stored in a file. It reconstructs the Huffman tree and returns the root HuffmanTree object. This function assumes nothing about the order in which the nodes are given in the list. As long as it is given the index of the root node, it will be able to reconstruct the tree. This means that the tree nodes could have been written in postorder (as your assignment does), preorder, inorder, level-order, random-order, whatever. Note that the number of each node in the list corresponds to the index of the node in the list. That is, the node at index 0 in the list has node-number 0, the node at index 1 in the list has node-number 1, etc. # # Functions for decompression def generate_tree_general(node_lst: list[ReadNode], root_index: int) -> HuffmanTree: """ Return the Huffman tree corresponding to node_lst[root_index]. The function assumes nothing about the order of the tree nodes in the list. >>> 1st = [ReadNode(0, 5, 0, 7), ReadNode (0, 10, 0, 12), \ ReadNode (1, 1, 1, 0)] >>> generate_tree_general (1st, 2) Huffman Tree (None, Huffman Tree (None, Huffman Tree (10, None, None), \ Huffman Tree (12, None, None)), \ Huffman Tree (None, Huffman Tree (5, None, None), Huffman Tree (7, None, None))) || || || # TODO: Implement this function ht= Huffman Tree ()