Arithmetic Coding Interval

Problem

Encode a message with arithmetic coding given a list of symbols and their positive integer weights, and return the final interval as [low, high] floats within [0, 1].

Each symbol owns a subinterval of proportional width; encoding narrows the current interval by that subinterval for every character. Use exact fractions internally and return floats. The empty message gives [0.0, 1.0].

Hint

Each character scales the remaining interval by its own probability subinterval.

Test cases

case 1

in: ["ab",["a","b"],[1,1]]

expected: [0.25,0.5]

case 2

in: ["xyz",["x","y","z"],[1,1,2]]

expected: [0.09375,0.125]

case 3

in: ["aaa",["a"],[1]]

expected: [0,1]

case 4

in: ["",["a"],[1]]

expected: [0,1]

case 5

in: ["ba",["a","b"],[1,1]]

expected: [0.5,0.75]

Starter codePython

def arithmetic_coding_interval(message, symbols, weights):
    # Your code here
    pass

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