LZ78 Index Cost

Problem

Parse a string with LZ78, emitting the shortest prefix starting at the current position that is not yet in the dictionary. An index into a dictionary of d stored phrases costs ceil(log2(d + 1)) bits, because index 0 points at the empty prefix. Return the total number of index bits, and 0 for the empty string.

Hint

The first phrase always references the empty prefix, so it costs zero index bits.

Test cases

case 1

in: ["ABABABA"]

expected: 5

case 2

in: ["AAAAAAAA"]

expected: 5

case 3

in: [""]

expected: 0

case 4

in: ["A"]

expected: 0

Starter codePython

import math
def lz78_index_cost(s):
    # Your code here
    pass

4 test cases · run your code against them in the editor