모르스 부호는 도트(점)와 대시(선)의 조합으로 구성된 메시지 전달용 부호로 1830년대에 미국의 사뮤엘 모르스(Samuel Morse)에 의해 고안되었다.
결정트리는 여러 단계의 복잡한 조건을 갖는 문제에 대해 조건과 그에 따른 해결방법을 트리 형태로 나타낸 것을 말한다.
결정트리를 이용하면 알파벳을 찾는데 걸리는 시간은 O(log_2 n)이다.
모르스 코드 표
출처 : 파이썬으로 쉽게 풀어쓴 자료구조
table =[('A', '.-'), ('B', '-...'), ('C', '-.-.'), ('D', '-..'),
('E', '.'), ('F', '..-.'), ('G', '--.'), ('H', '....'),
('I', '..'), ('J', '.---'), ('K', '-.-'), ('L', '.-..'),
('M', '--'), ('N', '-.'), ('O', '---'), ('P', '.--.'),
('Q', '--.-'), ('R', '.-.'), ('S', '...'), ('T', '-'),
('U', '..-'), ('V', '...-'), ('W', '.--'), ('X', '-..-'),
('Y', '-.--'), ('Z', '--..') ]
class TNode:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
def make_morse_tree():
root = TNode(None, None, None)
for tp in table: # table에 있는 요소 하나 하나씩 넣음.
code = tp[1] # 모르스 코드 table 한 요소의 모르스 코드를 넣음
node = root
for c in code: # 맨 마지막 문자 이전까지 -> 이동
if c == ".": # 점(.): 결정트리에서 왼쪽으로 이동
if node.left == None: # 비었으면 빈 노드 만들기
node.left = TNode(None, None, None)
node = node.left # 그쪽으로 이동
elif c == "-": # 오른쪽으로 이동
if node.right == None: # 비었으면 빈 노드 만들기
node.right = TNode(None, None, None)
node = node.right # 그쪽으로 이동
node.data = tp[0] # 코드의 알파벳을 해당 노드에 넣음.
return root
def decode(root, code): # 모르스 코드에 대한 문자를 찾는 함수
node = root
for c in code:
if c == ".":
node = node.left
elif c == "-":
node = node.right
return node.data
def encode(ch): # 문자에 대한 코드를 찾아 반환하는 함수
idx = ord(ch) - ord("A") # 예로 C의 코드를 찾는다고하면 C(67)-A(65)=2
return table[idx][1] # C의 코드는 table[2][1]에 해당한다.
morseCodeTree = make_morse_tree()
str = input("입력 문장 : ") # 알파벳 대문자만 입력가능. 그 외 오류
mlist = []
for ch in str:
code = encode(ch)
mlist.append(code)
print("Morse Code: ", mlist)
print("Decoding : ", end="")
for code in mlist:
ch = decode(morseCodeTree, code)
print(ch, end="")
print()
--------------------------------------------------
입력 문장 : GAMEOVER
Morse Code: ['--.', '.-', '--', '.', '---', '...-', '.', '.-.']
Decoding : GAMEOVER
