(Шумный декодер сообщений) с использованием модели Markav

Question

Я пишу программу на Python, которая принимает целое число k (порядок модели) и строку s (зашумленное сообщение) в качестве аргументов командной строки, считывает входной текст из стандартного ввода и выводит наиболее вероятную исходную строку.

Шумно: это были лучшие времена, я был в худшие времена.

Ожидаемый результат: это были лучшие времена, это были худшие времена.

Мой вывод: это было лучшее время, это было худшее время. Ниже приведен псевдокод:

Может кто-нибудь, пожалуйста, помогите мне, сравнив псевдокод и мой код и укажите, где я не прав. Я бился головой об этом в течение последних трех дней, но не могу найти выход

Когда мы исправляем испорченные сообщения, мы должны смотреть на пропущенную букву в контексте того, что предшествует ей, а что - после. Например, пусть поврежденный текст будет "it w~s th", k = 4, и пусть символы, следующие за 4-граммовым "it w", будут "a", "b" и "c". Итак, вы хотите выбрать лучшую из трех гипотез (назовите их Ha, Hb и Hc). Давайте используем обозначение "abcd" | "e" для обозначения вероятности нахождения "e" после 4-граммового "abcd". Эта вероятность равна 0, если "e" не следует за "abcd" в тексте.

Псевдокод

если повреждено [i] == '~':

kgram_before = kgram перед ~

kgram_after = kgram после ~

пробники = []

для каждой гипотезы из гипотез (символы, которые могут заменить ~):

контекст = kgram_before + гипотеза + kgram_after

   p = 1.0

для меня от 0 до _k + 1:

kgram = kgram из контекста, начинающегося с i

char = символ из контекста, который следует за kgram

если kgram или char не существует, тогда установите p в 0 и сломайте. В противном случае умножьте p на вероятность char, следующего за kgram

  append p to probs

добавить оригинальную гипотезу, которая максимизирует пробники (используйте argmax())

Мой код:

def replace_unknown(self, corrupted):
    """
    Replaces unknown characters (~) in corrupted with most probable
    characters, and returns that string.
    """

    # Given a list a, argmax returns the index of the maximum element in a.
    def argmax(a):
        return a.index(max(a))

    original = ''
    for i in range(len(corrupted)):
        if corrupted[i] == '~':
            kgram_before = corrupted[i - self._k:i] # getting kgram before ~
            kgram_after = corrupted[i+1: i + self._k+1] #getting kgram after ~
            probs=[]
            if bool(kgram_before in self._st.keys()):
                    hypothesis = self._st[kgram_before].keys()#values that can replace ~
                    for hypothesees in hypothesis:
                        context = kgram_before + hypothesees + kgram_after
                        p  = 1.0
                        for i in range (0, self._k + 1):
                            kgram = context[i:self._k + i]
                            char = context[self._k + i]
                            if bool(kgram in self._st.keys()):
                                if(char in self._st[kgram].keys()):
                                    a = self._st[kgram].values()
                                    charr = sum(self._st[kgram].values())
                                    charr_prob = float ((self._st[kgram][char] * 1.0 / charr *1.0)) #calculating the character probability by dividing character count by total characters in the set.
                                    p *= charr_prob
                            else:
                                p=0
                                break
                        probs.append(p)
            max_prob = hypothesis[argmax(probs)]
            original += max_prob
        else:
            original += corrupted[i]
    return original