# Fibonacci prefix code

This one is kind of involved. Is there a simpler way to implement this prefix code in base python, my existing code goes below but any help in modification or review will be helpful.

# Lagged fibonacci numbers the sequence starts: 1,2,3,5,8,11
def fibonacci(n):
a = 1
b = 1
out = []
for i in range(n):
out.append(a)
a,b = a+b,a
return out

# There has to be a better way to do this, right?
# Go through the list for the first few fibonacci numbers from greatest to
# make a list of fibonacci numbers that add up to each code number (1,2,3...)
# The code is then the indexes of those fibonacci numbers, with leading zeroes
# removed, reversed, with an additional "1" at the end.
def makeCodebook(decode=False):
F = fibonacci(10)
F.reverse()
codes = []
for x in range(1,27):
while x != 0:
code = []
for f in F:
if f <= x:
code.append("1")
x = x-f
else:
code.append("0")

while code[0] == "0":

code.pop(0)
code.reverse()
code.append("1")
codes.append("".join(code))

# Matchup codes with letters
D = {}
alpha = "ETAOINSRHLDCUMFPGWYBVKXJQZ"
if decode == False:
for a,b in zip(alpha,codes):
D[a] = b

if decode == True:
for a,b in zip(alpha,codes):
D[b] = a
return D

def prefixCode(text,decode=False):

# Build the codebook
D = makeCodebook(decode=decode)

# When encoding we simply translate each letter to its code
if decode == False:
out = []
for letter in text:
out.append(D[letter])
return "".join(out)

• Can you put the part that is currently only a comment into the body of the question, so reviewers don't have to search for it? Also some example in- and output would help a lot! – Graipher Jan 8 at 13:16

When you need to loop a fixed number of time, but don't actually need the loop index, it is customary to use _ as the loop index. So, in fibonacci(n), you would write for _ in range(n):.

Your fibonacci() generator is generating too many values. Your last code value is 26, so any fibonacci value greater than 26 is unnecessary. Instead of asking for a fixed number of values, ask for values up to a specific limit.

def fibonacci_up_to(last):
a, b = 1, 1
out = []
while a <= last:
out.append(a)
a, b = a+b, a
return out


And use F = fibonacci_up_to(26)

The following is an incorrect comment:

# Lagged fibonacci numbers the sequence starts: 1,2,3,5,8,11


The fibonacci sequence doesn't contain an 11; the number, following after 5 and 8 would be 5+8=13!

In makeCodebook():

It is usually clearer to write x = x-f as x -= f

Instead of always appending "1" to the end of code after reversing it, you could simply initialize code = ["1"] at the start.

The while x != 0: loop is unnecessary. After the for f in F: loop, x will have become zero, or there is a logic error in constructions of the code for x. Remove while x != 0:, and optionally add an assert if you are unsure x actually reaches zero.

Construction your code dictionary D:

D = {}
for a,b in zip(alpha, codes):
D[a] = b


can be re-written with list-comprehension as:

D = { a: b for a, b in zip(alpha, codes) }


Or, as pointed out by @Graipher in the comments, simply:

D = dict(zip(alpha, codes))


Using if decode == False: followed by if decode == True: is unnecessary verbose. if decode == False: can simply be if not decode:, and the reverse condition should simply be else:. Or better, eliminate the negated logic, by swapping the statement order:

if decode:
D = { code: letter for letter, code in zip(alpha, codes) }
else:
D = { letter: code for letter, code in zip(alpha, codes) }


Or, leveraging @Graipher's simplification from the comments and Python's x if cond else y expression, the above can be written in one line. Whether this is clearer or more obfuscated is a matter of taste:

D = dict(zip(codes, alpha)) if decode else dict(zip(alpha, codes))


In prefixCode():

Constructing the out array can be done with list comprehension:

out = [ D[letter] for letter in text ]


but this out array is just a temporary used as an argument in the next statement, so you should combined them:

return "".join( D[letter] for letter in text )


Your function has (or will have) two entirely different execution paths with almost no common functionality, one for encoding, and (eventually) one for decoding. Write this as two functions, not as one function with a decode parameter to choose between the paths:

def encode(text):
# ...

def decode(text):
# ...


Use pylint or similar to check your code for PEP-8 compatibility. Including things such as:

• use spaces after commas: zip(alpha, codes) not zip(alpha,codes)
• use spaces around operators: x - f not x-f
• use lower_case_function_names(), not mixedCaseFunctionNames()
• use lower_case_variables not uppercase identifiers like D and F

This can be simplified by (for the moment, ignore the final terminating 1) noting that the code for a Fibonacci number is simply a number of placeholder 0's followed by a 1, and the code for a number like 17 (=13+4) will be the code for 4 (101), followed by a number of placeholder 0's, and then a 1 for the largest Fibonacci value smaller than the number (13). After building all of the codes, add the final 1 terminator to each.

def codebook(key):
codes = [""]
a, b = 1, 1
digits = 0

for x in range(1, len(key)+1):
if x >= a:
a, b = a+b, a
digits += 1

prefix = codes[x-b]
codes.append(prefix + "0"*(digits - len(prefix) - 1) + "1")

return { letter: code+'1' for letter, code in zip(key, codes[1:]) }

letter_to_code = codebook("ETAOINSRHLDCUMFPGWYBVKXJQZ")

code_to_letter = { code: letter for letter, code in letter_to_code.items() }

• Instead of D = { a: b for a,b in zip(alpha, codes) } you can just use D = dict(zip(alpha, codes)). – Graipher Jan 9 at 14:06
• @Graipher Excellent point. dict(zip(alpha, codes)) is around 14% faster. – AJNeufeld Jan 9 at 17:21
• Hm, I thought it was just easier to read, good to know! – Graipher Jan 9 at 19:40

Your fibonacci doesn't need the variables a and b; out is already tracking them.

def fibonacci(n):
out = [1,2]
for i in range(n-2):
out.append(out[i]+out[i+1])
return out


You should build both the encoding and coding codebooks at the same time, so you don't have to run the same function twice to get both.

You can build your codebooks as you find the codes:

def makeCodebook():
alpha = "ETAOINSRHLDCUMFPGWYBVKXJQZ"
F = fibonacci(10)
F.reverse()
D = {}
E = {}
for x,letter in enumerate(alpha,1):
while x != 0:
code = []
for f in F:
if f <= x:
code.append("1")
x = x-f
else:
code.append("0")

while code[0] == "0":

code.pop(0)
code.reverse()
code.append("1")
D[code] = letter
E[letter] = code
return D,E


Note that this eliminates the need to keep a codes list.

Then you can have

def prefixCode(text,decode=False):
D, E = makeCodebook(decode=decode)
if not decode:
return "".join([E[letter] for letter in text])

• You’ve changed the fibonacci() function so that it now produces 12 values, when given the argument 10. Worse, it produces the sequence starting with 1, 1, 2, 3, 5 … instead of the “lagged” version starting 1, 2, 3, 5 …, which breaks the codebook generation. – AJNeufeld Jan 9 at 1:41
• Other bugs you’ve introduced: codes is no longer defined, so codes.append( ) is an error. alpha[26] is an index out of range, and alpha[0] (the letter ”E”) is not added to the encode/decode dictionaries. It would be better (and more importantly, correct) to use for x, letter in enumerate(alpha, 1): to loop over the letters of alpha, providing a 1-based index for each. – AJNeufeld Jan 9 at 2:57
• Finally, D, E = makeCodebook(decode=decode) is an error since makeCodebook() no longer takes a decode argument. – AJNeufeld Jan 9 at 21:35