霍夫曼編碼
題目 8：霍夫曼編碼法問題 (15%)
python
data = list(map(lambda x: x.split(), input().split(', ')))
# build tree
tree = {}
while len(data) > 1:
data.sort(key=lambda x: int(x[1]))
a1, a2 = data.pop(0)
b1, b2 = data.pop(0)
c1 = int(a2) + int(b2)
data.append(['', c1])
tree[c1] = [(a1, a2), (b1, b2)]
# main
queue = [(data[0], '')]
record = {}
while queue:
node, st = queue.pop(0)
char, num = node
if char:
record[char] = st
if num in tree:
queue.append((tree[num][0], st + '0'))
queue.append((tree[num][1], st + '1'))
for i, j in sorted(record.items()):
print(i, j)霍夫曼編碼
python
def dfs(n, target, depth):
if n == target:
return depth
for father, child in tree:
if father == n:
res = dfs(child, target, depth + 1)
if res:
return res
for _ in range(int(input())):
ary = list(map(int, input().split(',')))
tree = []
nodes = ary.copy()
ary.sort()
while ary:
node = ary.pop(0)
if not ary:
break
node2 = ary.pop(0)
newNode = node + node2
ary.append(newNode)
ary.sort()
tree.append([newNode, node])
tree.append([newNode, node2])
root = tree[-1][0]
result = [dfs(root, i, 0) for i in nodes]
print(*result, sep=',')1 霍夫曼編碼還原 模擬測驗-4
python
from collections import defaultdict
def build_tree():
graph = defaultdict(list)
while len(ary) > 1:
node = ary.pop(0)
node2 = ary.pop(0)
total = node[1] + node2[1]
ary.append(('', total))
ary.sort(key=lambda x: x[1])
graph[total].append(node2)
graph[total].append(node)
return graph, total
def dfs(n, path):
a, b = graph[n]
if a[1] in graph:
dfs(a[1], path + "0")
if b[1] in graph:
dfs(b[1], path + "1")
if a[0] != '':
record.append((a[0], path + '0'))
if b[0] != '':
record.append((b[0], path + '1'))
for _ in range(int(input())):
char = input()
ary = sorted({i: char.count(i)
for i in set(char)}.items(), key=lambda x: x[1])
# build_tree
graph, total = build_tree()
# record
record = []
dfs(total, '')
# main
for __ in range(int(input())):
a = input()
i = 0
ans = ''
while i < len(a):
for title, content in record:
if a[i:i + len(content)] == content:
ans += title
i += len(content)
break
print(ans)Contributors
lucashsu95