CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Huffman Encoding Accessibility Application - Typing interface

1. Accessibility Keyboard Demo
2. Efficiency Analysis

1. Accessibility Keyboard Demo
   
   Note: This work was inspired by a similar feature of Android's switchaccess. The original code is here. You will want to in particular look at HuffmanTreeBuilder.java and PPMTrie.java
   
   

   ###############################################################################
   # An implementation of a very basic typing interface designed for users with
   # motor imparment who are not able to use a traditional keyboard but are rather
   # rather constrained to using only one or two switches. 
   #
   # In paricular this typing interface is designed to show how Huffman encoding
   # can improve the typing efficiency of these users in particular if a good 
   # language model is utilized. Here we're using a naive language model that is 
   # based only on English letter frequencies. A better model would further 
   # illustrate how powerful Huffman encoding can be in improving the typing 
   # efficiency. 
   # 
   # Author: Rudina Morina (rmorina@andrew.cmu.edu)
   ##############################################################################
   
   from Animation import Animation
   from tkinter import *
   import string
   import heapq
   
   def rgbString(red, green, blue):
       return "#%02x%02x%02x" % (red, green, blue)
   
   # A class utilized to build the huffman and the linear tree 
   class TreeNode(object):
       def __init__(self, freq=None, char=None, left=None, right=None):
           self.char = char
           self.freq = freq
           self.left = left
           self.right = right
   
       def isLeaf(self):
           return (self.left == None and self.right == None)
   
       # needed mainly for debugging purposes 
       def __repr__(self):
           return "TreeNode(char=%s, freq=%s)" % (self.char, self.freq)
   
       def __lt__(self, other):
           return self.freq < other.freq  
   
   class TextBox(object):
       def __init__(self, font, canvas, width, height):
           self.font = font
           self.canvas = canvas
           self.width = width
           self.height = height
           self.typedSequence = ""
           self.textMargin = 10
           self.boxXMargin, self.boxYMargin = 50, 60
           self.textBoxHeight = self.height/2 - 3*self.boxYMargin
           self.textBoxWidth = self.width - 2*self.boxXMargin
   
       def textSize(self, text):
           temp = self.canvas.create_text(0, 0, text=text, anchor=NW, font=self.font)
           (x0, y0, x1, y1) = self.canvas.bbox(temp)
           self.canvas.delete(temp)
           return (x1-x0, y1-y0)
   
       def draw(self):
           # draw the text box
           textBoxLeft, textBoxTop = self.boxXMargin, self.boxYMargin
           textBoxRight = textBoxLeft + self.textBoxWidth
           textBoxBottom = textBoxTop + self.textBoxHeight
           self.canvas.create_rectangle(textBoxLeft, textBoxTop, textBoxRight, 
               textBoxBottom)
   
           # draw the text
           textXStart = self.boxXMargin + self.textMargin
           textYStart = self.boxYMargin + self.textMargin
           maxCharHeight = 0
           for char in self.typedSequence:
               charWidth, charHeight = self.textSize(char)
               maxCharHeight = max(charHeight, maxCharHeight)
               if (textXStart + charWidth > textBoxRight - self.textMargin):
                   # filled the current line, move to the next line
                   textYStart += (maxCharHeight + self.textMargin)
                   textXStart = self.boxXMargin + self.textMargin
               if (textYStart > textBoxBottom - self.textMargin):
                   print("The current page is filled")
                   return
               self.canvas.create_text(textXStart, textYStart, text=char,
                   font=self.font, anchor=NW)
               textXStart += charWidth
   
       def addChar(self, char):
           if (char == "_"):
               # add space
               self.typedSequence += " "
           else:
               self.typedSequence += char
   
   class Keyboard(object):
   
       KEYS = list(string.ascii_lowercase) + ["_"]
       # scanning methods: linear and probability-based utilizing huffman encoding
       HUFFMAN = "huffman"
       LINEAR = "linear"
       # we're utilizing binary trees to create the huffman and linear encoding so
       # the keys of a keyboard are seperated into two buckets. 
       LEFT = "left"
       RIGHT = "right"
   
       def __init__(self, canvas, width, height, languageModel=None):
           self.languageModel = languageModel
           self.keyboardContent = [
                                   Keyboard.KEYS[0 : 10], 
                                   Keyboard.KEYS[10 : 19],
                                   Keyboard.KEYS[19 : ]
                                   ]
           self.canvas = canvas
           self.width = width
           self.height = height
           self.unreachableKeys = set()
           self.rightKeys = set()
           self.leftKeys = set()
           self.scanningMethod = Keyboard.LINEAR
           self.leftKeysColor = rgbString(204, 255, 204) # light green
           self.rightKeysColor = rgbString(255, 255, 255) # white
   
       def draw(self):
           xMargin, yMargin, keyMargin = 50, 100, 10
           keyboardX, keyboardY = xMargin, self.height/2 + yMargin
           #TODO: fix the magic numbers
           keySize = (self.width - 2*xMargin - 9*keyMargin) / 10
           rowMargin = keySize / 3
           for row in range(len(self.keyboardContent)):
               keyboardX += row*rowMargin
               for col in range(len(self.keyboardContent[row])):
                   curChar = self.keyboardContent[row][col]
                   curKeyX = keyboardX + (keySize + keyMargin)*col
                   curKeyY = keyboardY + (keySize + keyMargin)*row
                   rectFill = rgbString(255, 255, 255)
                   border = rgbString(0, 0, 0)
                   if curChar in self.leftKeys:
                       rectFill = self.leftKeysColor
                   elif curChar in self.rightKeys:
                       rectFill = self.rightKeysColor
                   elif curChar in self.unreachableKeys:
                       border = rgbString(136,136,136)  # light gray
                   self.canvas.create_rectangle(curKeyX, curKeyY, curKeyX + keySize, 
                       curKeyY + keySize, fill=rectFill, outline=border)
                   self.canvas.create_text(curKeyX + keySize/2, curKeyY + keySize/2, 
                       text=curChar, fill=border)
   
       def addUnreachableKeys(self, keys):
           self.unreachableKeys = self.unreachableKeys.union(keys)
   
       def resetKeys(self):
           self.unreachableKeys = set()
           self.rightKeys = set()
           self.leftKeys = set()
   
       def setRightKeys(self, keys):
           self.rightKeys = keys
   
       def setLeftKeys(self, keys):
           self.leftKeys = keys
   
       def setScanningMethod(self, scanningMethod):
           self.resetKeys()
           self.scanningMethod = scanningMethod
           if (self.scanningMethod == Keyboard.LINEAR):
               self.leftKeysColor = rgbString(204, 255, 204) # light green
               self.rightKeysColor = rgbString(255, 255, 255) # white
           else:
               self.leftKeysColor = rgbString(204, 255, 204) # light green
               self.rightKeysColor = rgbString(255,239,213) # light orange
   
   class Editor(Animation):
   
       def __init__(self, font="Arial 30", languageModel=None):
           self.languageModel = languageModel
           self.font = font
   
       def buildLinearTree(self):
           tree = None
           for i in range(len(Keyboard.KEYS) - 1, -1, -1):
               char = Keyboard.KEYS[i]
               charNode = TreeNode(char=char)
               tree = TreeNode(left=charNode, right=tree)
           return tree
   
       def buildHuffmanTree(self):
           huffmanNodes = []
           for char in self.languageModel:
               huffmanNodes.append(TreeNode(self.languageModel[char], char))
           heapq.heapify(huffmanNodes)
           while (len(huffmanNodes) > 1):
               # obtain the two minimum-frequency Huffman nodes 
               child1 = heapq.heappop(huffmanNodes)
               child2 = heapq.heappop(huffmanNodes)
               parent = TreeNode(child1.freq + child2.freq, left=child1, right=child2)
               heapq.heappush(huffmanNodes, parent)
           return None if huffmanNodes == [] else heapq.heappop(huffmanNodes)
   
       def getNodes(self, path):
           # get all the node to the left or to the right of the current node
           nodesToHighlight = set()
           if (self.curNode == None):
               return nodesToHighlight
           def walkTree(tree):
               if (tree == None): return
               if (tree.left == None and tree.right == None):
                   nodesToHighlight.add(tree.char)
               walkTree(tree.left)
               walkTree(tree.right)
           if (path == Keyboard.LEFT):
               walkTree(self.curNode.left)
           else:
               walkTree(self.curNode.right)
           return nodesToHighlight
   
       def drawScanPrefButtons(self):
           if (self.keyboard.scanningMethod == Keyboard.HUFFMAN):
               hBoxFill = rgbString(192,192,192)
               lBoxFill = rgbString(255, 255, 255)
           else:
               hBoxFill = rgbString(255, 255, 255)
               lBoxFill = rgbString(192,192,192)
   
           hBoxLeft = self.boxLeft
           self.canvas.create_rectangle(hBoxLeft, self.boxTop, hBoxLeft + self.boxWidth,
               self.boxTop + self.boxHeight, fill=hBoxFill)
           self.canvas.create_text(hBoxLeft + self.boxWidth/2, 
               self.boxTop + self.boxHeight/2, text="Huffman Scan")
   
           lBoxLeft = hBoxLeft + self.boxWidth + self.boxMargin
           self.canvas.create_rectangle(lBoxLeft, self.boxTop, lBoxLeft + self.boxWidth,
               self.boxTop + self.boxHeight, fill=lBoxFill)
           self.canvas.create_text(lBoxLeft + self.boxWidth/2, 
               self.boxTop + self.boxHeight/2, text="Linear Scan")
   
       def redrawAll(self):
           self.keyboard.draw()
           self.textBox.draw()
           self.drawScanPrefButtons()
           if (self.keyboard.scanningMethod == Keyboard.HUFFMAN):
               text  = "Press Space to select the orange keys and Enter to select"\
                       " the green keys." 
           else:
               text  = "Press Space to move to the next key and Enter to select"\
                       " the currently highlighted key"
           self.canvas.create_text(self.instructionLeft, self.instructionTop, 
               text=text)
   
       def init(self):
           self.boxTop, self.boxLeft = self.height/2, 50
           self.boxWidth = 150
           self.boxHeight = 30
           self.boxMargin = 20
           self.instructionLeft = self.width/2
           self.instructionTop = 20
           self.keyboard = Keyboard(self.canvas, self.width, self.height, 
               self.languageModel)
           self.textBox = TextBox(self.font, self.canvas, self.width, self.height)
           self.treeRoot = self.buildLinearTree()
           self.curNode = None
   
       def mousePressed(self, event):
           # We don't have a language model so the only scanning method we can use
           # is linear
           if (self.languageModel == None): return
           hBoxLeft = self.boxLeft
           lBoxLeft = hBoxLeft + self.boxWidth + self.boxMargin
           boxBottom = self.boxTop + self.boxHeight 
           if (event.x >= hBoxLeft and event.x <= hBoxLeft + self.boxWidth and 
               event.y >= self.boxTop and event.y <= boxBottom):
               self.keyboard.setScanningMethod(Keyboard.HUFFMAN)
               self.treeRoot = self.buildHuffmanTree()
               self.curNode = None
           elif (event.x >= lBoxLeft and event.x <= lBoxLeft + self.boxWidth and 
               event.y >= self.boxTop and event.y <= boxBottom):
               self.keyboard.setScanningMethod(Keyboard.LINEAR)
               self.treeRoot = self.buildLinearTree()
   
       def keyPressed(self, event):
           # only recognize 2 keys
           if(event.keysym != "space" and event.keysym != "Return"): return
           if (event.keysym == "space"):
               if (self.curNode == None):
                   self.curNode = self.treeRoot
               else:
                   # if we move to the right of the current node, all the nodes to 
                   # the left of the current node won't be reachable anymore
                   newUnreachableKeys = self.getNodes(Keyboard.LEFT)
                   self.keyboard.addUnreachableKeys(newUnreachableKeys)
                   self.curNode = self.curNode.right
           elif (event.keysym == "Return"):
               if (self.curNode == None):
                   self.curNode = self.treeRoot
               else:
                   # if we move to the left of the current node, all the nodes to 
                   # the right of the current node won't be reachable anymore
                   newUnreachableKeys = self.getNodes(Keyboard.LEFT)
                   self.keyboard.addUnreachableKeys(newUnreachableKeys)
                   self.curNode = self.curNode.left
           if (self.curNode == None):
               self.keyboard.resetKeys()
               self.curNode = self.treeRoot
           elif (self.curNode.isLeaf()):
               self.textBox.addChar(self.curNode.char)
               self.keyboard.resetKeys()
               self.curNode = self.treeRoot
           # based on the curNode, divide the reachable keys into two buckets, the
           # one to the left of the current node and the one to the right of the 
           # current node
           self.keyboard.setLeftKeys(self.getNodes(Keyboard.LEFT))
           self.keyboard.setRightKeys(self.getNodes(Keyboard.RIGHT))
   
   # a language model based on frequency of English letters
   languageModel = {
     "e": 10.02, "t": 9.10, "a": 8.12, "o": 7.68, "i": 7.31, "n": 6.95, 
     "s": 6.28, "r": 6.02, "h": 5.92, "d": 4.32, "l": 3.98, "u": 2.88,
     "c": 2.71, "m": 2.61, "f": 2.30, "y": 2.11, "w": 2.09, "g": 2.03,
     "_": 2.0, "p": 1.82, "b": 1.49, "v": 1.11, "k": 0.69, "x": 0.17, "q": 0.11,
     "j": 0.10, "z": 0.07
     }
   
   editor = Editor(languageModel=languageModel)
   editor.run(800, 800)

   Select
   
   
   
2. Efficiency Analysis
   
   How many key presses does it take for each character when using linear vs. huffman scanning?
   
   

   Character	Linear	Huffman
   'a'	1	4
   'b'	2	6
   'c'	3	5
   'd'	4	5
   'e'	5	3
   'f'	6	5
   'g'	7	6
   'h'	8	4
   'i'	9	4
   'j'	10	10
   'k'	11	7
   'l'	12	5
   'm'	13	5
   'n'	14	4
   'o'	15	4
   'p'	16	6
   'q'	17	9
   'r'	18	4
   's'	19	4
   't'	20	3
   'u'	21	5
   'v'	22	6
   'w'	23	6
   'x'	24	8
   'y'	25	6
   'z'	26	10
   'space'	27	6