Алгоритм Витерби

# This function takes data to tag (brown_dev_words), a set of all possible tags (taglist), a set of all known words (known_words),
# trigram probabilities (q_values) and emission probabilities (e_values) and outputs a list where every element is a tagged sentence 
# (in the WORD/TAG format, separated by spaces and with a newline in the end, just like our input tagged data)
# brown_dev_words is a python list where every element is a python list of the words of a particular sentence.
# taglist is a set of all possible tags
# known_words is a set of all known words
# q_values is from the return of calc_trigrams()
# e_values is from the return of calc_emissions()
# The return value is a list of tagged sentences in the format "WORD/TAG", separated by spaces. Each sentence is a string with a 
# terminal newline, not a list of tokens. Remember also that the output should not contain the "_RARE_" symbol, but rather the
# original words of the sentence!
def viterbi(brown_dev_words, taglist, known_words, q_values, e_values):
    
    tagged = []
    
    pi = defaultdict(float)
    bp = {}
    bp[(-1,'*','*')] = '*'
    pi[(-1,'*','*')] = 0.0
    
    for line in brown_dev_words:    
        tokens = [w if w in known_words else '_RARE_' for w in line]
        tokens = tokens
        
                # k = 1 case
        for w in taglist:
            pi[(0, '*', w)] = pi[(-1,'*','*')] + q_values.get(('*', '*', w), -1000) + e_values.get((tokens[0], w), -1000)
            bp[(0, '*', w)] = '*'
 
        # k = 2 case
        for (w, u) in itertools.product(taglist, taglist):
            key = ('*', w, u)
            pi[(1, w, u)] = pi.get((0, '*', w), -1000) + q_values.get(key, -1000) + e_values.get((tokens[1], u), -1000)
            bp[(1, w, u)] = '*' 
 
        # k >= 2 case
        for k in range (2, len(tokens)):
            for (u, v) in itertools.product(taglist, taglist):
                max_prob = -float('Inf')
                max_tag = ""
                for w in taglist:
                    score = pi.get((k-1, w, u), -1000) + q_values.get((w,u,v), -1000) + e_values.get((tokens[k], v), -1000)
                    if(score > max_prob):
                        max_prob = score
                        max_tag = w
                bp[(k,u,v)] = max_tag
                pi[(k,u,v)] = max_prob
                
        max_prob = -float('Inf')
 
        #finding the max probability of last two tags
        for (u,v) in itertools.product(taglist, taglist):
            score = pi.get((len(line)-1, u, v),-1000) + q_values.get((u,v,'STOP'),-1000) 
            if score >  max_prob:
                max_prob = score
                u_max = u
                v_max = v
 
        #append tags in reverse order
        tags = []
        tags.append(v_max)
        tags.append(u_max)
        count = 0
        
        for k in range(len(line) - 3, -1, -1):
            tags.append(bp[(k + 2, tags[count+1], tags[count])])
            count +=1
        tagged_sentence = ""
 
        #reverse tags
        tags.reverse()
 
                #stringify tags paired with word without start and stop symbols
        for k in range(0, len(line)):
            tagged_sentence = tagged_sentence + line[k] + "/" + str(tags[k]) + " "
        
        tagged_sentence += "\n"
        tagged.append(tagged_sentence)
        
    return tagged