Как я могу получить все возможности, используя цепочку марков?

Question

Я пытаюсь реализовать взломщик лингвистических парольных фраз с использованием цепей Маркова.

Идея заключается в том, чтобы выбрать n-грамм из текста, выбрать начальный n-грамм (обычно это слово в начале предложения) и представить его как состояние, используя первые n-1 символов , В качестве примера, для "the" у меня будет "th". Это будет иметь список букв с их вхождениями, и будет представлен в виде словаря. dict["th"] = [('e', 120), ('a', 79)] и т. Д. Для каждого из этих значений я попытаюсь создать цепочку markov, которая будет соответствовать как моему паролю, так и длине пароля. Это означает, что когда цепочка markov будет иметь ту же длину, что и мой пароль, который я пытаюсь найти, я остановлю выполнение и проверим, совпадает ли цепочка markov с моим паролем. Я пытаюсь реализовать это с помощью рекурсивной функции, но по какой-то причине я получаю переполнение стека.

def ceva(myTry, good_all, pwd, guess, level):
        save = myTry
        if len(pwd) == len(guess):
            if pwd == guess:
                return 1
        else:
            if myTry in good_all.keys():
                values = good_all[myTry]
                for i in range(0,len(values)):
                    #print(i, len(values))
                    letter = values[i][0]
                    #print("First",myTry, letter)

                    pwd += letter
                    if i != len(values)-1:

                        if len(pwd) == len(guess):
                            #print("In if", pwd, myTry)
                            if pwd == guess:
                                print("I found:", pwd)
                                return 1
                            else:

                                pwd = pwd[0:len(pwd)-1]
                        else:

                            myTry += letter
                            myTry = myTry[1:]
                            #print("In else: ",pwd, myTry)
                            return ceva(myTry, good_all, pwd, guess, level)
                    else:
                        if len(pwd) == len(guess):
                            #print("In if", pwd, myTry)
                            if pwd == guess:
                                print("I found:", pwd)
                                return 1

                        pwd = pwd[0:len(pwd)-1]


    for key, letterList in starter_follows.items():
        myTry = key.replace("_", "")

        # i will not treat the case when the starting phrase
        # is a single character
        if myTry == "i":
            pass
        else:
            for letter in letterList:

                if letter[0] not in "_.-\"!":
                    myTry += letter[0]
                    pwd = copy.copy(myTry)
                    #print("Starter:", pwd)
                    res=ceva(myTry, good_all, pwd, toGuess, 1)
                    myTry = myTry[0:len(myTry)-1]

С помощью этого алгоритма я достигаю максимальной глубины рекурсии. Но я пытаюсь получить все цепочки Маркова, пока не будет найдена ключевая фраза.

РЕДАКТИРОВАТЬ 1: Теперь, с обновленным кодом, пароль найден, но только потому, что я чередую все возможные последние буквы.

Например: "действительно"

ind уже есть в моем списке начинающих, и все триграммы, которые я нахожу, имеют "e" в качестве их наиболее распространенного следующего письма. Таким образом, добавляется e, затем следующее e, затем следующее e, а теперь пароль - «Indeee», но я нарезаю последнюю букву и снова перебираю for, и в конечном итоге он находит «действительно», что нормально. Проблема в том, что если я дам indedd, он не найдет мой пароль, потому что второе «d» никогда не проходит через петлю. Как я могу вернуться к своей итерации и перебрать все возможные буквы на всех уровнях?

Answer 1

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

def ceva(myTry, good_all, pwd, guess, flag):

if len(pwd) > len(guess):
    return 0
if len(pwd) == len(guess):
    if pwd == guess:
        flag = 1
        return 1
    else: 
        return 0
save = copy.copy(myTry)
#print("Start of functionn:", "[", pwd, ",", myTry, "]")

if flag == 1:
    return 1
else:   

    if myTry in good_all.keys():
        # get the list of letters for this specific trigram
        values = good_all[myTry]

        if len(pwd) <= len(guess):
            for i in range(0,len(values)):
                #myTry = copy.copy(save)
                # get the letter
                letter = values[i][0]

                # add the letter to the password
                pwd += letter


                # if i found the password, set flag to 1 and break the loop
                if pwd == guess:
                    flag = 1
                    print("I found:", pwd)
                    return 1

                # add the new letter to the trigram, and the get rid of the first
                # letter, in order to create the new trigram
                myTry += letter
                myTry = myTry[1:]
                #print("Pwd before cutting: [", pwd, "]")
                res = ceva(myTry, good_all, pwd, guess, flag)
                #print(res)
                if res == 0:
                    pwd = pwd[0:len(pwd)-1]
                    myTry = pwd[-3:]
                #   print("This is after stop: [", pwd,",", myTry, "]")
                else:
                    return 1


    if flag == 0:
        return 0
    else:
        return 1

flag = 0

for key, letterList in starter_follows.items():
    myTry = key.replace("_", "")
    # i will not treat the case when the starting phrase
    # is a single character
    if myTry == "i":
        pass

    else:
        #print("Aaaa")
        for letter in letterList:

            if letter[0] not in "_.-\"!":

                # add the letter to create a (n-1)-gram
                myTry += letter[0]
                # create a copy of the starting password
                pwd = copy.copy(myTry)

                # call the recursive function
                res=ceva(myTry, good_all, pwd, toGuess, flag)
                # go back to the begining, to try a new start
                # e.g.: "the" first, "tha" second
                myTry = myTry[0:len(myTry)-1]