Поиск строки на основе частоты символов

Question

Мне любопытны алгоритмы поиска строк, и я разработал методику, основанную на частотах использования символов. Моя наивная логика c выглядит следующим образом:

Если вы ищете "axe" в некоторой строке, нет смысла волноваться, когда вы сталкиваетесь с "a", но определенно волнуйтесь, если сталкиваетесь с "x", поскольку использование "x" намного ниже, чем "a".

Поэтому я решил попытаться реализовать эту идею. Код нарушает несколько необработанных правил алгоритма (использует list.index), но не до такой степени, чтобы он заметно влиял на производительность кода, и были бы подходящие обходные пути, которые я не могу потрудиться исследовать. Вот оно:

def algorithm(text, pattern):
    freqs = {'e' : 12.0,
    't' : 9.10,
    'a' : 8.12,
    'o' : 7.68,
    'i' : 7.31,
    'n' : 6.95,
    's' : 6.28,
    'r' : 6.02,
    'h' : 5.92,
    'd' : 4.32,
    'l' : 3.98,
    'u' : 2.88,
    'c' : 2.71,
    'm' : 2.61,
    'f' : 2.30,
    'y' : 2.11,
    'w' : 2.09,
    'g' : 2.03,
    'p' : 1.82,
    'b' : 1.49,
    'v' : 1.11,
    'k' : 0.69,
    'x' : 0.17,
    'q' : 0.11,
    'j' : 0.10,
    'z' : 0.07 }

    letters = list(freqs.keys())

    pattern_len = len(pattern)
    ranks = sorted([(letters.index(pattern[i]), i) for i in range(pattern_len)], key=lambda x: x[1], reverse=True)

    # This is the key outcome of preprocessing. It orders the indices of pattern's characters from least frequent, to most frequent, and in the case of duplicates, a secondary sort from rightmost occurrence to left.
    rep = [e[1] for e in sorted(ranks, key=lambda x: x[0], reverse=True)]

    reference_index = 0

    algstart = time.time()
    for i in range(len(text)):
        # This is a very important line. Essentially, it allows me to shift the sequence forward by a step greater than 1 and based on the character that has been shifted to, find the offset index of where I hope the least frequent character to appear in the text.
        z = i - reference_index

        if text[z] == pattern[rep[0]]:

            for j in range(1, pattern_len):
                text_char = text[z - rep[0] + rep[j]]

                # Char mismatch, so shift to match or beginning of substring
                if text_char != pattern[rep[j]]:
                    if text_char in pattern:
                        shift_distance = rep[j] - (pattern.index(text_char) + 1)
                    else:
                        shift_distance = rep[j]

                    i += shift_distance
                    reference_index = shift_distance
                    break

                # Found it!
                if j == pattern_len - 1:
                    local_vars = list(locals().items())
                    size = sum([sys.getsizeof(obj) for var, obj in local_vars if var != "text"])
                    print(f"My amended alg found the pattern at index {z - rep[0]} in {time.time() - algstart}ms using {size}b of memory!!")
                    return

У меня есть другое решение, которое не использует list.index или in, но оно гораздо менее читаемо и разница во времени незначительна.

В моем кратком тестировании с использованием текстового файла Алисы в Стране Чудес этот алгоритм работал примерно в 2 раза лучше, чем KMP, но Бойер-Мур по-прежнему превосходил его в> 3 раза. Однако с такими словами, как "queen", он превзошел оба алгоритма (хотя и немного Бойера-Мура). Очевидно, что алгоритм требует неравномерного распределения частот символов. Кроме того, данные частоты были просто извлечены из inte rnet, но я уверен, что я мог бы умеренно улучшить скорость, если бы я собирал частоты из фактического текста.

У кого-нибудь есть какие-либо предложения по улучшению скорости этого алгоритма? Есть ли подобный алгоритм, который я должен изучить? Спасибо!