Python 데이터 구조 학습 의 하프 만 트 리

머리말
이 장 에 서 는 하프 만 트 리 와 하프 만 인 코딩 을 소개 하 는데 하프 만 트 리 의 기본 개념,구조,코드 실현 과 하프 만 인 코딩 을 포함 하고 Python 으로 이 루어 진다.
1.기본 개념
하 프 만 트 리(Huff man(Huff man Tree)Tree)는 가장 좋 은 이 진 트 리 라 고도 부 르 는데 권한 경로 길이 가 가장 작은 이 진 트 리 를 말한다.나무의 권한 이 있 는 경 로 를 항상 기록 합 니 다:

그 중에서 nnn 은 나무의 잎 결점 의 수,wkwkwk 는 제 kkk 개 잎 결산 점 의 가중치,lklklk 는 제 kkk 의 잎 결점 과 뿌리 결점 의 경로 길이 입 니 다.
밴드 경로 의 길 이 는 밴드 노드 와 루트 노드 간 의 경로 길이 와 이 노드 의 가중치 의 곱 이다.밴드 노드,경로 길이 에 대한 개념 은 이 블 로 그 를 참조 하 시기 바 랍 니 다.
nnn 개의 잎 결점 을 함유 한 하프 만 나 무 는 모두 2n-12n-12n-1 개의 결점 이 있다.하프 만 나 무 를 구성 하 는 과정 에서 매번 두 개의 두 갈래 나 무 를 서브 트 리 로 하여 새로운 두 갈래 나 무 를 만 들 기 때문에 하프 만 나무 에는 1 의 결점,즉 n1=0n 가 존재 하지 않 는 다.1=0 n1=0,이 진 트 리 의 성질 을 통 해 알 수 있 듯 이 잎 결산 점 수 n0=n2+1n0=n_2+1n 0=n2+1,그래서 n2=n0−1n2=n_0-1n2=n0−1,총 결 점 수 는 n=n0+n1+n2=n+n−1=n−1=n−1n=n0+n_1+n_2=n+n-1=2n-1n=n0​+n1​+n2​=n+n−1=2n−1。
2.구조 과정 및 실현
뿌리 결점 만 있 는 이 진 트 리 T1,T2,...,TnT1,T_2,\dots,T_nT1,T2,...,Tn,그들의 가중치 는 각각 w1,w2,...,wnw 이다.1,w_2,\dots,w_nw1,w2,...,wn,그것들 을 집합 FFF 에 넣 으 세 요.즉,F={T1,T2,...,Tn}F=\{T1,T_2,\dots,T_n\}F={T1​,T2​,…,Tn​}；그 다음 에 집합 FFF 에서 두 그루 의 가중치 가 가장 작은 뿌리 결산 점 을 선택 하여 새로운 이 진 트 리 를 구성 하여 새로운 이 진 트 리 의 뿌리 결산 점 의 가중치 가 왼쪽,오른쪽 나무 뿌리 결산 점 의 가중치 와 같 도록 한다.그리고 선택 한 두 노드 를 집합 FFF 에서 삭제 하고 새로운 이 진 트 리 를 FFF 에 추가 합 니 다.집합 FFF 에 이 진 트 리 한 그루 만 남 을 때 까지 이 동작 을 계속 반복 합 니 다.
예 를 들 어 F={(A,3),(B,7),(C,2),(D,11),(E,13),(F,13),(F,15),(G,9)}F=\{(A,3),(B,2),(B,7),(D,11),(E,13),(F,13),(F,15),(G,9)\}F={(A,3),(B,3),(B,7),(B,7),(C,2),(D,11),(D,11),(E,13),(F,15),(G,9)\}}F={(A,3),3),(A,3),(B,7),(B,7 만 나 무 는 바로 아래 에 있 는 이 두 갈래 나무 다.

코드 구현:

class HuffmanTreeNode(object):
 def __init__(self):
 self.data = '#'
 self.weight = -1
 self.parent = None
 self.lchild = None
 self.rchild = None


class HuffmanTree(object):
 def __init__(self, data_list):
 self.nodes = []
 #            
 for val in data_list:
  newnode = HuffmanTreeNode()
  newnode.data = val[0]
  newnode.weight = val[1]
  self.nodes.append(newnode)
 self.nodes = sorted(self.nodes, key=lambda node: node.weight, reverse=True)
 print([(node.data, node.weight) for node in self.nodes])

 def CreateHuffmanTree(self):
 #       
 # TreeNode = self.nodes[:]   TreeNode,         , TreeNode     nodes
 # TreeNode = self.nodes   TreeNode nodes      ,       , TreeNode     nodes
 TreeNode = self.nodes[:]
 if len(TreeNode) > 0:
  while len(TreeNode) > 1:
  letfTreeNode = TreeNode.pop()
  rightTreeNode = TreeNode.pop()
  newNode = HuffmanTreeNode()
  newNode.lchild = letfTreeNode
  newNode.rchild = rightTreeNode
  newNode.weight = letfTreeNode.weight + rightTreeNode.weight
  letfTreeNode.parent = newNode
  rightTreeNode.parent = newNode
  self.InsertTreeNode(TreeNode, newNode)
  return TreeNode[0]

 def InsertTreeNode(self, TreeNode, newNode):
 length = len(TreeNode)
 if length > 0:
  temp = length - 1
  while temp >= 0:
  if newNode.weight < TreeNode[temp].weight:
   TreeNode.insert(temp+1, newNode)
   return True
  temp -= 1
 TreeNode.insert(0, newNode)

3.하프 만 코드
데이터 통신 을 할 때 만약 에 우리 가'ABCDEFG','ABCDEFG','ABCDEFG'라 는 메 시 지 를 보 내 려 면 우 리 는 이런 형식 으로 직접 보 내지 않 고 컴퓨터 가 식별 할 수 있 는 바 이 너 리 형식 으로 인 코딩 한다.인 코딩 형식 에 따라 고정 길이 인 코딩 과 가 변 길이 인 코딩 으로 나 눌 수 있 습 니 다.말 그대로 고정 길이 인 코딩 은 인 코딩 후의 문자 길이 가 모두 같 고 가 변 길이 인 코딩 은 인 코딩 후의 문자 길이 가 다르다 는 것 입 니 다.이 두 가지 유형 은 어떤 차이 가 있 습 니까?우리 가 예 를 들 어 설명 하 자.
 
AA
BB
CC
DD
EE
FF
GG
고정 길이 인 코딩
000000
001001
010010
011011
100100
101101
110110
가 변 길이 코딩
00
11
0101
1010
1111
101101
110110
'ABCDEFG','ABCDEFG','ABCDEFG'라 는 정 보 는 고정 길이 인 코딩 을 사용 한 후의 길 이 는 21 이 고 가 변 길이 인 코딩 을 사용 한 후의 길 이 는 14 이 며 메시지 가 짧 아 지면 메시지 의 전송 효율 이 상응 하 게 향상 된다.그러나 전 송 된 문자 가'BD','BD','BD',가 변 길이 로 인 코딩 된 메 시 지 는'111','111','111','111'이지 만 디 코딩 에 서 는'BBB','BD','DB','BD','DB','BBB','BD','DB'등 다양한 결과 가 나 오기 때문에 가 변 길이 인 코딩 을 사용 할 때 다른 문자 의 접두사 가 되 지 않도록 주의해 야 한다.이러한 가 변 길이 인 코딩 에 맞 게 접두사 인 코딩 이 라 고 합 니 다.
메 시 지 는 가장 짧 으 면 이 진 트 리 의 경로 가 가장 짧다 는 것 을 설명 할 수 있다.즉,구조 접두사 인 코딩 의 실질 은 하 프 만 트 리 를 구성 하 는 것 이다.이런 형식 으로 얻 은 이 진 인 코딩 을 하 프 만 인 코딩 이 라 고 한다.여기 서 의 가중치 는 메시지 에 문자 가 나타 날 확률 입 니 다.나타 날 확률 이 높 은 문자 일수 록 짧 은 문자 로 표시 합 니 다.
아래 표 의 문자 와 나타 날 확률 을 예 로 들 어 하프 만 인 코딩 을 실현 합 니 다.
문자
AA
BB
CC
DD
EE
FF
GG
HH
출현 확률
0.010.01
0.430.43
0.150.15
0.020.02
0.030.03
0.210.21
0.070.07
0.08
하프 만 코드
101010101010
00
110110
101011101011
1010010100
111111
10111011
100

 
코드 구현 은 하프 만 트 리 에 인 코딩 함 수 를 추가 하 는 것 입 니 다.

 def HuffmanEncode(self, Root):
  TreeNode = self.nodes[:]
  code_result = []
  for index in range(len(TreeNode)):
   temp = TreeNode[index]
   code_leaf = [temp.data]
   code = ''
   while temp is not Root:
    if temp.parent.lchild is temp:
     #    
     code = '0' + code
    else:
     #    
     code = '1' + code
    temp = temp.parent
   code_leaf.append(code)
   code_result.append(code_leaf)
  return code_result

테스트 결 과 는 다음 과 같다.

if __name__ == '__main__':
 tree_obj = HuffmanTree([('A', 0.01), ('B', 0.43), ('C', 0.15), ('D', 0.02), ('E', 0.03), ('F', 0.21), ('G', 0.07), ('H', 0.08)])
 huf_tree = tree_obj.CreateHuffmanTree()
 huf_code = tree_obj.HuffmanEncode(huf_tree)
 for index in range(len(huf_code)):
  print('{0}: {1}'.format(huf_code[index][0], huf_code[index][1]))

총결산
파 이 썬 이 데이터 구조 학습 을 묘사 한 하 브 만 트 리 편 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 파 이 썬 데이터 구조 에 관 한 하 브 만 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!