compression/huffman.py · python/Python

Fetch the repository succeeded.

richgiteeai

Watch

Unwatch Watching Releases Only Ignoring

1 Star 0 Fork 324

python/Python

forked from 编程语言算法集/Python

Code Issues 0 Pull Requests 0 Wiki Insights Pipelines

Service

Tencent Cloud Serverless

Create your Gitee Account

Explore and code with more than 14 million developers,Free private repositories !:)

Already have an account? Sign in

文件

master

Branches (54)

Manage

master

mypy-reality-check

Python-3.10-beta-1

bubble_sort

Fix-validate_initial_digits-of-credit_card_validator.py

long-running-tests

fix-project-euler-problem-15

mypy-project-euler-092-sol-1

Add-tests-to-morse_code.py

from-__future__-import-annotations

flake8-bugbear

is_ip_v4_address_valid.py

cclauss-patch-4

cclauss-patch-3

mypy_--install-types_--non-interactive

Write-for-current-Python

harris_corner.py

dhruvmanila-patch-1

refactor/action

fix/action

Clone or Download

Clone/Download

HTTPS SSH SVN SVN+SSH Download ZIP

Prompt

To download the code, please copy the following command and execute it in the terminal

To ensure that your submitted code identity is correctly recognized by Gitee, please execute the following command.

git config --global user.name userName 
git config --global user.email userEmail

When using the SSH protocol for the first time to clone or push code, follow the prompts below to complete the SSH configuration.

1 Generate RSA keys.

2 Obtain the content of the RSA public key and configure it in SSH Public Keys

To use SVN on Gitee, please visit the usage guide

When using the HTTPS protocol, the command line will prompt for account and password verification as follows. For security reasons, Gitee recommends configure and use personal access tokens instead of login passwords for cloning, pushing, and other operations.

Username for 'https://gitee.com': userName

Password for 'https://userName@gitee.com': # Private Token

Branches 54

Tags 0

Python

compression

huffman.py

huffman.py 2.69 KB

from __future__ import annotations

import sys

class Letter:
 def __init__(self, letter: str, freq: int):
 self.letter: str = letter
 self.freq: int = freq
 self.bitstring: dict[str, str] = {}

def __repr__(self) -> str:
 return f"{self.letter}:{self.freq}"

class TreeNode:
 def __init__(self, freq: int, left: Letter | TreeNode, right: Letter | TreeNode):
 self.freq: int = freq
 self.left: Letter | TreeNode = left
 self.right: Letter | TreeNode = right

def parse_file(file_path: str) -> list[Letter]:
 """
 Read the file and build a dict of all letters and their
 frequencies, then convert the dict into a list of Letters.
 """
 chars: dict[str, int] = {}
 with open(file_path) as f:
 while True:
 c = f.read(1)
 if not c:
 break
 chars[c] = chars[c] + 1 if c in chars.keys() else 1
 return sorted((Letter(c, f) for c, f in chars.items()), key=lambda l: l.freq)

def build_tree(letters: list[Letter]) -> Letter | TreeNode:
 """
 Run through the list of Letters and build the min heap
 for the Huffman Tree.
 """
 response: list[Letter | TreeNode] = letters # type: ignore
 while len(response) > 1:
 left = response.pop(0)
 right = response.pop(0)
 total_freq = left.freq + right.freq
 node = TreeNode(total_freq, left, right)
 response.append(node)
 response.sort(key=lambda l: l.freq)
 return response[0]

def traverse_tree(root: Letter | TreeNode, bitstring: str) -> list[Letter]:
 """
 Recursively traverse the Huffman Tree to set each
 Letter's bitstring dictionary, and return the list of Letters
 """
 if type(root) is Letter:
 root.bitstring[root.letter] = bitstring
 return [root]
 treenode: TreeNode = root # type: ignore
 letters = []
 letters += traverse_tree(treenode.left, bitstring + "0")
 letters += traverse_tree(treenode.right, bitstring + "1")
 return letters

def huffman(file_path: str) -> None:
 """
 Parse the file, build the tree, then run through the file
 again, using the letters dictionary to find and print out the
 bitstring for each letter.
 """
 letters_list = parse_file(file_path)
 root = build_tree(letters_list)
 letters = {
 k: v for letter in traverse_tree(root, "") for k, v in letter.bitstring.items()
 }
 print(f"Huffman Coding of {file_path}: ")
 with open(file_path) as f:
 while True:
 c = f.read(1)
 if not c:
 break
 print(letters[c], end=" ")
 print()

if __name__ == "__main__":
 # pass the file path to the huffman function
 huffman(sys.argv[1])

Copy Edit Raw Blame History

Erwin Junge authored 2021年10月26日 18:29 +08:00 . [mypy] annotate compression (#5570)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

from __future__ import annotations

import sys


class Letter:
 def __init__(self, letter: str, freq: int):
 self.letter: str = letter
 self.freq: int = freq
 self.bitstring: dict[str, str] = {}

 def __repr__(self) -> str:
 return f"{self.letter}:{self.freq}"


class TreeNode:
 def __init__(self, freq: int, left: Letter | TreeNode, right: Letter | TreeNode):
 self.freq: int = freq
 self.left: Letter | TreeNode = left
 self.right: Letter | TreeNode = right


def parse_file(file_path: str) -> list[Letter]:
 """
 Read the file and build a dict of all letters and their
 frequencies, then convert the dict into a list of Letters.
 """
 chars: dict[str, int] = {}
 with open(file_path) as f:
 while True:
 c = f.read(1)
 if not c:
 break
 chars[c] = chars[c] + 1 if c in chars.keys() else 1
 return sorted((Letter(c, f) for c, f in chars.items()), key=lambda l: l.freq)


def build_tree(letters: list[Letter]) -> Letter | TreeNode:
 """
 Run through the list of Letters and build the min heap
 for the Huffman Tree.
 """
 response: list[Letter | TreeNode] = letters # type: ignore
 while len(response) > 1:
 left = response.pop(0)
 right = response.pop(0)
 total_freq = left.freq + right.freq
 node = TreeNode(total_freq, left, right)
 response.append(node)
 response.sort(key=lambda l: l.freq)
 return response[0]


def traverse_tree(root: Letter | TreeNode, bitstring: str) -> list[Letter]:
 """
 Recursively traverse the Huffman Tree to set each
 Letter's bitstring dictionary, and return the list of Letters
 """
 if type(root) is Letter:
 root.bitstring[root.letter] = bitstring
 return [root]
 treenode: TreeNode = root # type: ignore
 letters = []
 letters += traverse_tree(treenode.left, bitstring + "0")
 letters += traverse_tree(treenode.right, bitstring + "1")
 return letters


def huffman(file_path: str) -> None:
 """
 Parse the file, build the tree, then run through the file
 again, using the letters dictionary to find and print out the
 bitstring for each letter.
 """
 letters_list = parse_file(file_path)
 root = build_tree(letters_list)
 letters = {
 k: v for letter in traverse_tree(root, "") for k, v in letter.bitstring.items()
 }
 print(f"Huffman Coding of {file_path}: ")
 with open(file_path) as f:
 while True:
 c = f.read(1)
 if not c:
 break
 print(letters[c], end=" ")
 print()


if __name__ == "__main__":
 # pass the file path to the huffman function
 huffman(sys.argv[1])