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
  90.       else insertListLength(list.head, sortListLength(list.tail))
  91.     }
  92.  
  93.     def insertListLength(head: HuffmanCodingTree, tail: List[HuffmanCodingTree]): List[HuffmanCodingTree] = {
  94.       if (tail.isEmpty || head.nodeWeight <= tail.head.nodeWeight) head :: tail
  95.       else tail.head :: insertListLength(head, tail.tail)
  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.  
  124.       help_func(treeLeaves).head
  125.     }
  126.  
  127.     /** {
  128.       * for(i <- 0 until treeLeaves.length){
  129.       * var fuckme = makeNonLeaf(treeLeaves.head, treeLeaves.tail.head)
  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. OK, I Understand
 
Top