Algorithm Misra & Gries implementation in python

Question

I have this pseudocode:

A = empty associative array;
// Processing
while ( not end of sequence ) #referente ao data stream
     j = current_token();
     if ( j in keys(A) ) then A[ j ] = A[ j ] + 1;
     else if ( | keys(A) | < ( k – 1 ) ) then A[ j ] = 1;
     else for each i in keys(A) do
         A[ i ] = A[ i ] – 1;
         if ( A[ i ] == 0 ) then remove i from A;
// Output
if( a in keys(A) ) then freq_estimate = A[ a ];
else freq_estimate = 0;

I implement this way:

def contMisraGries(dataClean, k):
    frequencia_MisraGries = {}
    A={}

    for caracter in dataClean:
        if  caracter in A.keys():
            A = increment(caracter, A)
        else:
            if A.keys() < k-1:
                A.keys(caracter) = 1
            else:
                for i , v in A.items():
                    A.keys(i) -= 1
                    if v == 0:
                        del A.items(i)

    for car, val in A.items() :
        if car in frequencia_MisraGries.keys():
            frequencia_MisraGries.keys(car) = frequencia_MisraGries.values(val) 
        else:
            frequencia_MisraGries.keys(car) = 0

    return frequencia_MisraGries

def increment(caracter, A):
    for k, v in A.items():
        if k == caracter:
            A[k]=A[v]+1

    return A

The data clean is a list, like this:

['o','n','c','e','y','o',...]

The value k is passed form user the program.

But the code not compile. I have error in this line A.keys(caracter) = 1. I don't if i take the code the correct way.

Answer 1

It looks like you are trying to acces the content of a dictionary with a key. However, note that the keys() method takes no arguments, as from the documentation, what it does is:

This method returns a list of all the available keys in the dictionary.

If you want to access the content of a dictionary using its key, do A[caracter].

Example

d = {'a':3, 'b':4}

Using the keys method:

d.keys()
dict_keys(['a', 'b'])

Now, what you're trying to do will raise an error:

d.keys('a')

TypeError: keys() takes no arguments (1 given)

Instead do:

d['a']
3

Find more on Accessing Values in Dictionary in the attatched link.