Construct Huffman Tree
(self, text)
| 519 | return counts |
| 520 | |
| 521 | def _build_tree(self, text): |
| 522 | """Construct Huffman Tree""" |
| 523 | PQ = [] |
| 524 | |
| 525 | if isinstance(text, Vocabulary): |
| 526 | counts = text.counts |
| 527 | else: |
| 528 | counts = self._counter(text) |
| 529 | |
| 530 | for (k, c) in counts.items(): |
| 531 | PQ.append(Node(k, c)) |
| 532 | |
| 533 | # create a priority queue with priority = item frequency |
| 534 | heapq.heapify(PQ) |
| 535 | |
| 536 | while len(PQ) > 1: |
| 537 | node1 = heapq.heappop(PQ) # item with smallest frequency |
| 538 | node2 = heapq.heappop(PQ) # item with second smallest frequency |
| 539 | |
| 540 | parent = Node(None, node1.val + node2.val) |
| 541 | parent.left = node1 |
| 542 | parent.right = node2 |
| 543 | |
| 544 | heapq.heappush(PQ, parent) |
| 545 | |
| 546 | self._root = heapq.heappop(PQ) |
| 547 | |
| 548 | def _generate_codes(self): |
| 549 | current_code = "" |