• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Ex3

a guest Sep 15th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. package dk.itu.BIDMT.F19.P1.Part3
2.
3. import scala.collection.immutable
4.
5. object HuffmanCoding {
6.
7.   /**
8.     * The Huffman coding is represented as a tree where:
9.     * * each leaf representing a symbol; we also store the frequency of that symbol
10.     * * each non-leaf represents all the symbols stored in the sub-tree rooted by it and the sum of the frequencies of these symbols
11.     */
12.   abstract class HuffmanCodingTree{
13.     def chars : List[Char]
14.     def nodeWeight : Int
15.     def printTree : Unit
16.   }
17.
18.   case class HuffmanCodingTreeLeaf(symbol: Char, weight: Int) extends HuffmanCodingTree{
19.     def chars = List(symbol)
20.     def nodeWeight = weight
21.     def printTree = println("LEAF: synmbols: " + List(symbol) + " weight: " + weight)
22.   }
23.   case class HuffmanCodingTreeNonLeaf(symbols: List[Char], weight: Int, left: HuffmanCodingTree, right: HuffmanCodingTree) extends HuffmanCodingTree{
24.     def chars = symbols
25.     def nodeWeight = weight
26.     def leftChild = left
27.     def rightChild = right
28.     def printTree = {
29.       println("NonLEAF: symbols: " + symbols + " weight: " + weight)
30.       print("Left Subtree: ")
31.       left.printTree
32.       print("Right Subtree: ")
33.       right.printTree
34.       println()
35.     }
36.   }
37.
38.
39.   /*---- Start: Helper functions ----*/
40.
41.   /**
42.     * Given a list of characters, group characters together and assign for each character found in the list a frequency
43.     * param text : list of characters
44.     * return a list of pairs, where each pair is a character and its frequency in the input list
45.     */
46.   def extractCharFrequencies(text: List[Char]):  List[(Char,Int)]= {
47.     text.groupBy(e =>e).mapValues(_.length).toList
48.   }
49.
50.
51.   /**
52.     * Given a list of pairs of characters and their frequencies, return a list of HuffmanCodingTree nodes for each character
53.     * the weight of each node is the corresponding frequency for that character
54.     * param charFreqs : list of pairs of characters and their frequencies
55.     * return list of HuffmanCodingTree nodes, where each node represent a character from the input list
56.     */
57.
58.   def makeTreeLeaves(charFreqs : List[(Char,Int)]): List[HuffmanCodingTree] = {
59.     charFreqs.map(e => HuffmanCodingTreeLeaf(e._1 , e._2))
60.   }
61.
62.
63.   /**
64.     * Given two HuffmanCodingTree nodes, merge their info into one HuffmanCodingTree node
65.     * param a : a HuffmanCodingTree node
66.     * param b : a HuffmanCodingTree node
67.     * return a new non-leaf HuffmanCodingTree node
68.     */
69.   /**class HuffmanCodingTreeNonLeaf(symbols: List[Char], weight: Int, left: HuffmanCodingTree, right: HuffmanCodingTree)*/
70.
71.   def makeNonLeaf(a:HuffmanCodingTree,b:HuffmanCodingTree):HuffmanCodingTree = {
72.     val non_weight = a.nodeWeight + b.nodeWeight
73.     val non_chars = a.chars ::: b.chars
74.     HuffmanCodingTreeNonLeaf (non_chars, non_weight, a, b)
75.
76.   }
77.   /**
78.     * Insert a HuffmanCodingTree node into a list of HuffmanCodingTree nodes. Make sure that the nodes are in an  ascending ordered in the list
79.     * according to their frequencies
80.     * @param treeNode : new HuffmanCodingTree to insert in the list
81.     * @param listTreeNodes : list of HuffmanCodingTree nodes
82.     * @return a list of HuffmanCodingTree nodes sorted in an ascending order according to their frequencies
83.     */
84.
85.   def insertAsc(treeNode : HuffmanCodingTree, listTreeNodes : List[HuffmanCodingTree]):List[HuffmanCodingTree] = {
86.     val pre_list = treeNode :: listTreeNodes
87.     pre_list sortBy (_.nodeWeight)
88.     /**def sortListLength(list: List[HuffmanCodingTree]): List[HuffmanCodingTree] = {
89.       if (list.isEmpty) Nil
91.     }
92.
93.     def insertListLength(head: HuffmanCodingTree, tail: List[HuffmanCodingTree]): List[HuffmanCodingTree] = {
96.     }
97.     {
98.       val pre_list = treeNode :: listTreeNodes
99.       sortListLength(pre_list)
100.       */
101.     }
102.
103.
104.     /**
105.       * If there is only one HuffmanCodingTree node in the list, return that node
106.       * else,
107.       * find two nodes with the lowest frequencies,
108.       * merge these two nodes into one tree by creating a new tree node with these nodes are its children,
109.       * remove those two nodes from the list and add the newly created tree node
110.       * repeat the above steps
111.       *
112.       * param treeLeaves list of HuffmanCodingTree nodes
113.       * return a HuffmanCodingTree node representing the root of the tree
114.       */
115.     def generateTree(treeLeaves: List[HuffmanCodingTree]): HuffmanCodingTree = {
116.       def help_func(treeLeaves: List[HuffmanCodingTree]): List[HuffmanCodingTree] = treeLeaves match {
117.         case Nil => Nil
118.         case x :: Nil => List(x)
119.         case xs :: xss :: Nil => List(makeNonLeaf(xs, xss))
120.         case x :: xs :: xss => List(makeNonLeaf(makeNonLeaf(x, xs), help_func(xss).head))
121.
122.       }
123.
125.     }
126.
127.     /** {
128.       * for(i <- 0 until treeLeaves.length){
130.       * println(fuckme)
131.       * println(treeLeaves)
132.       * println(insertAsc(fuckme, treeLeaves))
133.       **
134.       *}
135.       */
136.
137.     //case Nil => throw new error "You fucked up big time, son" : String
138.     //if (treeLeaves.length == 1) treeLeaves.head
139.     //else
140.     //treeLeaves.map(e => makeNonLeaf())
141.
142.
143.     /*---- End: Helper functions ----*/
144.
145.
146.     /**
147.       * Constructing the Huffman tree from a list of characters
148.       *
149.       * Use the following steps
150.       * 1. Generate a list of all the characters appearing in the \$text\$ and  pair each character with its frequency based on how many times it appears in the text.
151.       * 2. From the above created list, generate a list of  HuffmanCodingTree nodes. Initially, this list contains a leaf tree node for each character in the text.
152.       * 3. generate a tree from the list of HuffmanCodingTree nodes and return the root of that tree
153.       *
154.       * param text : list of chars
155.       * return the root node of the Huffman Tree
156.       */
157.
158.     def createHuffmanTree(text: List[Char]): HuffmanCodingTree = {
159.       generateTree(makeTreeLeaves(extractCharFrequencies(text)))
160.     }
161.
162.
163.     /*---- Encoding a message ----*/
164.
165.     /**
166.       * Encoding a message
167.       *
168.       * Replace each character in message with each code in the tree
169.       */
170.     /**
171.       * Given the root of a HuffmanCodingTree and a character, find the code representing this char in the tree
172.       *
173.       * param tree : the root of a  HuffmanCodingTree
174.       * param c    : a character to find its code in the tree
175.       * return : a list of 1s and 0s representing the code of the input character in the Huffman tree
176.       */
177.     //def encodeChar(tree: HuffmanCodingTree, c: Char): List[Int] = ???
178.
179.
180.     /**
181.       * Given the root of a HuffmanCodingTree and a string represented as a list of characters, generate the code for
182.       * that string.
183.       * You will probably need to call encodeChar for each character in that string
184.       *
185.       * param tree    : the root of a  HuffmanCodingTree
186.       * param message : a string represented as a list of characters
187.       * @return : list of 1s and 0s representing the code for all the characters in the input message
188.       */
189.     //def encode(tree: HuffmanCodingTree, message: List[Char]): List[Int] = ???
190.
191.
192.     /*---- Decoding a code into a message ----*/
193.
194.     /**
195.       * Given the root of a HuffmanCodingTree and a list of 1s and 0s representing the code for a character,
196.       * traverse the tree guied by the code to find the character that it represent
197.       *
198.       * param tree : the root of a  HuffmanCodingTree
199.       * param code : a list of 1s and 0s representing the code of a message
200.       * return : a pair, its first element of the pair is a character that is found,
201.       *         and the second element of the pair is a code  (list of 1s and 0s) after removing
202.       *         the code of the found character from the input code
203.       *
204.       *         Example: using tree in Figure 1, calling getCharCode for List(0 , 1, 0, 1, 1, 1, 0, 1, 1)
205.       *         the returned value is the pair ('a' , List( 1, 0, 1, 1, 1, 0, 1, 1))
206.       */
207.     //def getCharCode(tree: HuffmanCodingTree, code: List[Int]): (Char, List[Int]) = ???
208.
209.     /**
210.       * Given the root of a HuffmanCodingTree and a list of 1s and 0s representing the code for a message, decode that code
211.       * into a message represented as a list of characters
212.       * You will probably need to call getCharCode several times to achieve that
213.       *
214.       * param tree : the root of a  HuffmanCodingTree
215.       * param code : a list of 1s and 0s representing the code of a message
216.       * return : a list of characters representing the message that was decoded
217.       *
218.       *         Example: using tree in Figure 1, calling decode for List(0 , 1, 0, 1, 1, 1, 0, 1, 1)
219.       *         the returned value is List( 'a', 'd', 'd')
220.       */
221.     //def decode(tree: HuffmanCodingTree, code: List[Int]): List[Char] = ???
222.
223.
224.     def main(args: Array[String]): Unit = {
225.       val tree = createHuffmanTree(List('A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'C', 'D', 'E', 'F', 'G', 'H'))
226.       println("Generated Tree:")
227.       //for testing purpose !
228.       tree.printTree
229.
230.       //test encoding a message
231.       //val encodedMsg = encode(tree, "ABCAH".toList)
232.       //println("encoding of msg: ABCAH = "+encodedMsg)
233.
234.       //test decoding a code into its corresponding message
235.       //val decodedMsg = decode(tree, List(0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0))
236.       //println("decoding of the above msg: "+ decodedMsg)
237.
238.     }
239.   }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top