Skip to content

Instantly share code, notes, and snippets.

@IshitaTakeshi
Created June 25, 2016 15:46
Show Gist options
  • Save IshitaTakeshi/b73a333f84dab4f3a084181fb1feac70 to your computer and use it in GitHub Desktop.
Save IshitaTakeshi/b73a333f84dab4f3a084181fb1feac70 to your computer and use it in GitHub Desktop.
Judge whether given code is a prefix code or not
from copy import copy
def dangling_suffixes(code1, code2):
def suffixes(code, word):
N = len(word)
s = set()
for c in code:
if c == word:
continue
if c.startswith(word):
s.add(c[N:])
return s
ss = set()
for c1 in code1:
ss |= suffixes(code2, c1)
for c2 in code2:
ss |= suffixes(code1, c2)
return ss
def isprefixcode(code):
S0 = set(code)
S = dangling_suffixes(S0, S0)
D = dangling_suffixes(S0, S)
print("C : {}".format(code))
print("S0: {}".format(S0))
print("S1: {}".format(S))
i = 1
while S != (S | D):
print("D{}: {}".format(i, D))
S = S | D
D = dangling_suffixes(S0, S)
print("S{}: {}".format(i+1, S))
i += 1
print("S{}: {}\n".format(i+1, S))
return len(S & S0) == 0
def run(C):
if isprefixcode(C):
print("{} is a prefix code.".format(C))
else:
print("{} is not a prefix code.".format(C))
print("\n")
run(['0', '10', '101', '1100', '1110'])
run(['0', '10', '1011', '1100', '1101'])
run(['00', '0001', '001', '0011', '011'])
run(['00', '1000', '11', '110', '1101'])
run(['0000', '0001', '001', '01', '1'])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment