1
2
3
4
5
6
7
8
9
10
11
def compress(gene:str) -> str:
    bit_string:int = 1
    for nucleotide in gene.upper():
        bit_string <<= 2
        if   nucleotide == "A": bit_string |= 0b00
        elif nucleotide == "C": bit_string |= 0b01
        elif nucleotide == "G": bit_string |= 0b10
        elif nucleotide == "T": bit_string |= 0b11
        else: 
            raise ValueError(f"Invalid nucleotide: { nucleotide }")
    return bit_string

1
2
3
4
5
6
from sys import getsizeof

original = "ATGC"
compressed = compress(original)
print(f"{ original }: { getsizeof(original) }바이트")
print(f"{ bin(compressed) }: { getsizeof(compressed) }바이트")

1
2
3
4
5
6
7
8
9
10
11
def decompress(bit_string:str) -> str:
    gene:str = ""
    for i in range(0, bit_string.bit_length() - 1, 2):
        bits:int = bit_string >> i & 0b11
        if   bits == 0b00: gene += "A"
        elif bits == 0b01: gene += "C"
        elif bits == 0b10: gene += "G"
        elif bits == 0b11: gene += "T"
        else: 
            raise ValueError(f"Invalid bits: { bits }")
    return gene[::-1] # Reverse

1
2
decompressed = decompress(compressed)
print(f"{ decompressed }: { getsizeof(decompressed) }")

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
from copy import deepcopy
from sys import getsizeof

def find_key(dict, val):
  return next(key for key, value in dict.items() if value == val)

class TreeNode:
    def __init__(self, key, value, left=None, right=None, parent=None):
        self.key = key
        self.value = value
        self.left   = left   if (left   == None) else left.key 
        self.right  = right  if (right  == None) else right.key
        self.parent = parent if (parent == None) else parent.key

    def __repr__(self):
        return f'({self.key}:{self.value} left<{self.left}>-right<{self.right}>-parent<{self.parent}>)\n'

    def set_parent(self, parent):
        self.parent = parent.key

    def get_left(self):
        return self.left

    def get_right(self):
        return self.right

class HuffTree:
    def __init__(self, text:str):
        self.text = text
        self.frequency_map = self.get_frequency_map()
        self.huffTree = self.get_huffTree()
        self.binary_map = self.get_binary_map()
        self.compressed = self.compress()
        self.compressed_bin = bin(self.compressed)
        
    def get_frequency_map(self) -> dict[str:int]:
        frequency_map:dict[str:int] = {}
        for i in self.text:
            if i not in frequency_map:
                frequency_map[i] = 1
            else:
                frequency_map[i] += 1
        return frequency_map
        
    def get_huffTree(self) -> dict[str:TreeNode]:
        frequency_map:dict = self.frequency_map
        x_list:list = list(frequency_map.keys())
        LENGTH = deepcopy(len(frequency_map))
        # -------------------------------------------------- 허프만 트리 생성
        hTree:dict[str:TreeNode] = {}
        for i in range(len(frequency_map)):
            ky = x_list[i]
            vl = frequency_map[ky]
            hTree[ky] = TreeNode(ky, vl)
        # -------------------------------------------------- 갱신 루프
        for x in range(LENGTH - 1):
            print('-'*40,f'\n루프 {x}')
            # -------------------------------------------------- 1. 작업 목록 정렬
            print(f'정렬 전 : {frequency_map}')
            frequency_map = dict(sorted(frequency_map.items(), key=lambda item: item[1])) # ?
            x_list = list(frequency_map.keys())
            print(f'정렬 후 : {frequency_map}')
            # -------------------------------------------------- 2. 노드 병합
            first, second = x_list[0], x_list[1]
            newNodeKey = f'*{x+1000}'
            newNodeValue = frequency_map[first] + frequency_map[second]
            print(f'노드 병합 : {first} + {second} -> {newNodeKey}')
            # -------------------------------------------------- 3. 허프만 트리 갱신
            hTree[newNodeKey] = TreeNode(newNodeKey, newNodeValue, hTree[first], hTree[second])
            hTree[first].set_parent(hTree[newNodeKey])
            hTree[second].set_parent(hTree[newNodeKey])
            print(f'갱신된 허프만 트리 :\n {hTree}')
            # -------------------------------------------------- 4. 작업 목록 갱신
            del frequency_map[first]
            del frequency_map[second]
            frequency_map[newNodeKey] = newNodeValue
        return hTree

    def get_binary_map(self) -> dict[str:int]:
        binary_map:dict[str:int] = {}
        for data in self.frequency_map:
            data_key = deepcopy(data)
            nes = ""
            while True:
                temp = self.huffTree[data].parent
                if temp:
                    if data == self.huffTree[temp].left:
                        nes += "0"
                    else:
                        nes += "1"
                    data = temp
                else:
                    binary_map[data_key] = nes[::-1]
                    break
        return binary_map

    def compress(self) -> int:
        compressed:int = 1
        for char in self.text:
            bit = self.binary_map[char]
            compressed <<= len(bit)
            compressed |= int(bit, 2)
        return compressed

    def decompress(self) -> str:
        decompressed:str = ""
        bit_list = list(self.binary_map.values())
        check_list = self.compressed_bin[3:]
        while len(check_list) >= 1:
            temp = ""
            for i in check_list:
                temp += i
                if temp in bit_list:
                    check_list = check_list[len(temp):]
                    break
                continue
            decompressed += find_key(self.binary_map, temp)
        return decompressed

def find_key(dict, val):
  return next(key for key, value in dict.items() if value == val)

1
2
3
4
5
6
7
8
9
10
11
12
13
if __name__ == "__main__":
    original = "GOOGOLPLEX"
    # original = 'In the beginning God created the heavens and the earth.Now the earth was formless and empty, darkness was over the surface of the deep, and the Spirit of God was hovering over the waters.And God said, "Let there be light," and there was light.God saw that the light was good, and He separated the light from the darkness.God called the light "day," and the darkness he called "night." And there was evening, and there was morning--the first day.'
    machine = HuffTree(original)

    compressed= machine.compress()
    decompressed = machine.decompress()

    print(f'    original: <{ getsizeof(original)     }바이트> { original     } ')
    print(f'  compressed: <{ getsizeof(compressed)   }바이트> { compressed   } ')
    print(f'decompressed: <{ getsizeof(decompressed) }바이트> { decompressed } ')

    print(original == decompressed)