FilesExpand file tree

master

/

huffman.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

82 lines (72 loc) · 2.25 KB

master

/

huffman.py

Copy path

Top

File metadata and controls

• Code
• Blame

82 lines (72 loc) · 2.25 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import sys

class Letter:

def __init__(self, letter, freq):

self.letter = letter

self.freq = freq

self.bitstring = ""

def __repr__(self):

return f'{self.letter}:{self.freq}'

class TreeNode:

def __init__(self, freq, left, right):

self.freq = freq

self.left = left

self.right = right

def parse_file(file_path):

"""

Read the file and build a dict of all letters and their

frequences, then convert the dict into a list of Letters.

"""

chars = {}

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):

"""

Run through the list of Letters and build the min heap

for the Huffman Tree.

"""

while len(letters) > 1:

left = letters.pop(0)

right = letters.pop(0)

total_freq = left.freq + right.freq

node = TreeNode(total_freq, left, right)

letters.append(node)

letters.sort(key=lambda l: l.freq)

return letters[0]

def traverse_tree(root, bitstring):

"""

Recursively traverse the Huffman Tree to set each

Letter's bitstring, and return the list of Letters

"""

if type(root) is Letter:

root.bitstring = bitstring

return [root]

letters = []

letters += traverse_tree(root.left, bitstring + "0")

letters += traverse_tree(root.right, bitstring + "1")

return letters

def huffman(file_path):

"""

Parse the file, build the tree, then run through the file

again, using the list of Letters to find and print out the

bitstring for each letter.

"""

letters_list = parse_file(file_path)

root = build_tree(letters_list)

letters = traverse_tree(root, "")

print(f'Huffman Coding of {file_path}: ')

with open(file_path) as f:

while True:

c = f.read(1)

if not c:

break

le = list(filter(lambda l: l.letter == c, letters))[0]

print(le.bitstring, end=" ")

print()

if __name__ == "__main__":

# pass the file path to the huffman function

huffman(sys.argv[1])