Arithmetc

from fractions import Fraction

def CalFreq(string):
    freq = {}
    prob = {}
    #check evey characters' frequency in the string
    for char in string:
        #if this character has already in the dict, then the frequecny add one
        if char in freq:
            freq[char] += 1
        #else, this character's frequency = 1
        else:
            freq[char] = 1
    #sort them in the desending order, reverse=True means desending order
    freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)

    temp = freq
    sum = 0

    for i in range(len(temp)):
        prob[temp[i][0]] = (temp[i][1], sum/len(string), (sum+temp[i][1])/len(string))
        sum = sum + temp[i][1]
    print(prob)
    #prob{} is to record all the upper-bound and lower-bound for every character
    return prob

def Arithmeticencoding(probability, string):
    Range = 1
    lower = 0
    upper = 1

    for i in range(len(string)):
        #print(probability[text[i]])
        lower = lower + Range * probability[string[i]][1]
        #print(lower)
        Range = Range * (probability[string[i]][2]-probability[string[i]][1])
        upper = lower + Range
        #print(upper)

    return lower, upper

if __name__ == '__main__':
    #input string
    string = input("Enter a sequence to encode: ")

    #calculate every characters' frequency and probability
    char_freq = CalFreq(string)

    #Do the Arithmetc Encoding
    lower, upper = Arithmeticencoding(char_freq, string)
    print("Arithmetic Encoding final tag: ")
    print((lower+upper)/2)