
Viterbi-Musterlösung aus dem Kurs:
    def viterbi(self, words):
        ''' berechnet die beste Tagfolge für eine gegebene Wortfolge '''
        words =  [''] + words + ['']  # Grenztokens hinzufügen

        # Initialisierung der Viterbi-Tabelle
        vitscore = [dict() for _ in range(len(words))]  # speichert logarithmierte Werte
        bestprev = [dict() for _ in range(len(words))]  # speichert die besten Vorgänger
        vitscore[0][('<s>','<s>')] = 0.0  # =log(1)
        for i in range(1, len(words)):
            lexprobs = self._lex_probs(words[i])  # die möglichen Tags nachschlagen
            for tag, lexprob in lexprobs:
                for tagpair in vitscore[i-1]:
                    tag1, tag2 = tagpair  # Kontext-Tags
                    p = self._context_prob(tagpair, tag) * lexprob / self._apriori_tag_prob[tag]
                    p = vitscore[i-1][tagpair] + log(p)
                    newtagpair = (tag2, tag)
                    if newtagpair not in vitscore[i] or vitscore[i][newtagpair] < p:
                        vitscore[i][newtagpair] = p
                        bestprev[i][newtagpair] = tagpair
        # in der letzten Spalte das Tagpaar mit der höchsten Bewertung suchen
        tagpair = max(vitscore[-1], key=vitscore[-1].get)
        # beste Tagfolge extrahieren
        result_tags = []
        for i in range(len(words)-1, 1, -1):
            result_tags.append(tagpair[0])
            tagpair = bestprev[i][tagpair]
        return reversed(result_tags)  # Tagfolge umdrehen
 

Musterlösung zur Prüfungsaufgabe:

def forward(words):
    words =  [''] + words + ['', '']  # Grenztokens hinzufügen

    # Initialisierung der Forward-Tabelle
    fwd_prob = [defaultdict(float) for _ in words]
    fwd_prob[0][('<s>','<s>')] = 1.0
    for i in range(1, len(words)):
        tags = tagset if i < len(words)-2 else ['<s>']
        for tag3 in tags:
            for (tag1, tag2), prevp in fwd_prob[i-1].items():
                p = prevp * contextprob(tag1, tag2, tag3) * lexprob(word[i], tag3)
                fwd_prob[i][(tag2, tag3)] += p
    return fwd_prob

def backward(words):
    words =  [''] + words + ['', '']  # Grenztokens hinzufügen

    # Initialisierung der Forward-Tabelle
    bwd_prob = [defaultdict(float) for _ in words]
    bwd_prob[-1][('<s>','<s>')] = 1.0
    for i in range(len(words)-1, 0, -1):
        tags = tagset if i > 2 else ['<s>']
        for tag1 in tags:
            for (tag2, tag3), nextp in bwd_prob[i].items():
                p = nextp * contextprob(tag1, tag2, tag3) * lexprob(word[i], tag3)
                bwd_prob[i-1][(tag1, tag2)] += p
    return bwd_prob

def estimated_freq(words, fwd_prob, bwd_prob, freq):
    words =  [''] + words + ['', '']  # Grenztokens hinzufügen
    total_prob = fwd_prob[-1][('<s>','<s>')]
    for i in range(1, len(words)):
        tags = tagset if i < len(words)-2 else ['<s>']
        for tag3 in tags:
            for (tag1, tag2), prevp in fwd_prob[i-1].items():
                p = prevp * contextprob(tag1, tag2, tag3) * lexprob(word[i], tag3)
                freq[(tag1, tag2, tag3)] += p * bwd_prob[i][(tag2, tag3)] / total_prob

