Молодогвардейцев 454015 Россия, Челябинская область, город Челябинск 89085842764
MindHalls logo

Создание списка запрещенных биграмм английского языка

Доброго времени суток, дорогие читатели! Недавно вышла статья про реализацию шифра Цезаря и его взлом. В конце я пообещал, что буду реализовывать и другие шифры. И вот мой выбор пал на перестановочный шифр. Но появилась проблема, для взлома понадобился список запрещенных биграмм в английском языке. После упорного и безрезультатного поиска, я решил поступить, как настоящий программист и составить эту таблицу самостоятельно.

Идея такая: взять достаточно большой литературный текст на английском языке и вычленить из него все возможные биграммы, обязательно с пробелами. Сравнить их со списком всех биграмм языка и найти запрещенные, которые ни разу не встретились в литературном тексте. Для этой задачи я выбрал язык программирования Python, так как хотелось сделать быстро и не заморачиваться с эклипсом и прочими радостями компилируемых языков. Вот, что у меня получилось, поехали!

Анализируемый текст

Первое, что пришло в голову это взять библию в качестве исходного текста. Кажется, именно ее анализируют статисты всего мира. Однако я столкнулся со следующими проблемами: очень много сокращений и спецсимволов. Специальные символы программно убрать не составило труда, а вот с сокращениями возникла проблема, из-за них портится статистика биграм. Кроме того, текст получился обрезанный, много абзацев из одного символа и прочие радости.

godftager in mindhall.ruПомучившись пару часов с библией, я решил взять текст одной из своих любимых книг. «Крестный отец» подошел отлично, достаточно объемный текст, без излишеств спецсимволов. И самое главное — это полностью художественный, литературный текст, восхитительный кандидат. Эта книга настолько мне нравится, что я вставил фото из одноименного фильма! Однажды я напишу свою рецензию на крестного отца, а сейчас самое время перейти к алгоритму.

Мой алгоритм поиска запрещенных биграмм

Поиск реализуется в три шага:

Первый шаг

Открываем файл с текстом и обрабатываем его: убираем цифры, все спецсимволы и знаки препинания. Я создаю новый файл, дабы не портить первоисточник, ведь я наверняка буду перечитывать его не один раз. Время работы напрямую зависит от размера текста, но в целом пробегаемся быстро. Больше времени уходит  на перезапись файла.

Исходный код на python

#определяет, является ли символ спецсимволом
def checkSymb(symb):
    badSymbols = ['”' ,'“', '*', ')', '(', '\t', '¶', '–', ',', '.', ':', ';', '`', '-', '!', '&', '?', '_', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    for s in badSymbols:
        if symb == s:
            return True
    else:
        return False

def processFile(fileName):
    file = open(fileName, 'r')

    text = []
    for line in file:
        text.append(list(line.lower()))

    file.close()

    #Убрать все спец символы, кроме пробелов и перевода строки, и цифры
    for i in range(len(text)):
        for j in range(len(text[i])-1):
            if checkSymb(text[i][j]) == True:
                text[i][j] = ''    

    newFileName = fileName + 'New'
    file = open(newFileName, 'w')

    for line in text:
        file.write(''.join(line))

    file.close()

    return newFileName

Второй шаг

Открываем новый файл и бежим по всем строкам, забиваем массив всех встречающихся сочетаний двух символов, включая сочетания с пробелом. Именно ради них это программа была написана.

Исходный код на Python

def findAllBigrammsInFile(fileName):
    file = open(fileName, 'r')

    text = []
    for line in file:
        text.append(list(line))

    file.close()

    allBigrammsInText = []
    for i in range(len(text)):
        for j in range(1, len(text[i])-1):
            allBigrammsInText.append(text[i][j-1] + text[i][j])

    return allBigrammsInText

Третий шаг

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

Исходный код на python

def getAllBigramms():
    allBigramms = []
    for num in range(ord('a'), ord('z')+1, 1):
        for secondNum in range(ord('a'), ord('z')+1, 1):
            allBigramms.append(chr(num) + chr(secondNum))

    for num in range(ord('a'), ord('z')+1, 1):
        allBigramms.append(chr(num) + ' ')
        allBigramms.append(' ' + chr(num))

    return allBigramms

#------------------------------------
#MAIN

newFileName = processFile('godfather')
allBigrammsInText = findAllBigrammsInFile(newFileName)
allBigramms = getAllBigramms()

indexesOfGoodBigramms = []
for i in range(len(allBigramms)):
    for j in range(len(allBigrammsInText)):
        if allBigramms[i] == allBigrammsInText[j]:
            indexesOfGoodBigramms.append(i)
            break

badBigramms = []
for i in range(len(allBigramms)):
    flag = True
    for j in range(len(indexesOfGoodBigramms)):
        if i == indexesOfGoodBigramms[j]:
            flag = False
            break
    if flag == True:
        badBigramms.append(allBigramms[i])

file = open('badBigramms', 'w')
file.write(str(badBigramms))
file.close()

Список запрещенных биграмм

Вот, что у меня получилось при анализе текста «Крестный отец»:

['aa', 'bc', 'bf', 'bh', 'bk', 'bn', 'bp', 'bq', 'bw', 'bx', 'bz', 'cb', 'cf', 'cg', 'cj', 'cm', 'cv', 'cw', 'dx', 'dz', 'fk', 'fp', 'fq', 'fv', 'fx', 'fz', 'gb', 'gj', 'gk', 'gp', 'gq', 'gv', 'gx', 'gz', 'hg', 'hj', 'hk', 'hp', 'hq', 'hv', 'hx', 'hz', 'iw', 'jb', 'jc', 'jd', 'jf', 'jg', 'jh', 'jj', 'jk', 'jl', 'jm', 'jn', 'jp', 'jq', 'jr', 'js', 'jt', 'jv', 'jw', 'jx', 'jy', 'jz', 'kk', 'kq', 'kv', 'kx', 'kz', 'lj', 'lq', 'lx', 'lz', 'md', 'mj', 'mk', 'mq', 'mv', 'mw', 'mx', 'mz', 'pc', 'pf', 'pj', 'pq', 'pv', 'px', 'pz', 'qa', 'qb', 'qc', 'qd', 'qe', 'qf', 'qg', 'qh', 'qi', 'qj', 'qk', 'ql', 'qm', 'qn', 'qo', 'qp', 'qq', 'qr', 'qs', 'qt', 'qv', 'qw', 'qx', 'qy', 'qz', 'rj', 'rq', 'rx', 'sv', 'sx', 'sz', 'tj', 'tq', 'tv', 'tx', 'uj', 'uq', 'uu', 'uw', 'vb', 'vc', 'vd', 'vf', 'vg', 'vh', 'vj', 'vk', 'vl', 'vm', 'vn', 'vp', 'vq', 'vt', 'vv', 'vw', 'vx', 'vz', 'wq', 'wv', 'wx', 'wz', 'xd', 'xf', 'xg', 'xj', 'xk', 'xl', 'xn', 'xr', 'xs', 'xv', 'xx', 'xz', 'yj', 'yk', 'yq', 'yx', 'zb', 'zc', 'zd', 'zf', 'zh', 'zj', 'zk', 'zm', 'zn', 'zp', 'zq', 'zr', 'zs', 'zt', 'zv', 'zw', 'zx', 'q ']

Заключение

Чисто теоретически, получился список биграмм, которые не встречаются в литературном тексте. Для большей уверенности стоит взять несколько романов разных авторов и проанализировать их вместе. Да, это займет больше времени, но зато уверенности прибавится. Перед реализацией перестановочного шифра я так и сделаю.

Я готов приступать ко взлому перестановочного шифра. Это совсем не такая легкая задача, как мне показалось на первый взгляд. И большой минус в том, что я использую собственноручно составленный список запрещенных биграмм, он не дает совершенно никаких гарантий. Но не смотря на это, я все же попытаюсь, спасибо за внимание!

  • Илья

    Как по мне, наиболее изящный вариант — это:
    allBigrammsInText = dict(), где в качестве ключей будут храниться все возможные биграммы букв алфавита и пробела (сгенерировать это нужно, разумеется)

    А в качестве значений будет bool.

    Тогда мы проходим по тексту, и если нашли там биграмму S, то allBigrammsInText[S] = True
    После полного прохода можно вывести (или перекидать в другой массив) не найденные биграммы:
    for k, v in allBigrammsInText.items():
    if v == False:
    print(k)

    И ВСЁ — То, что в Мэйне вообще не нужно, а другие функции в размере уменьшатся.

    • Кузьминых Кирилл

      Замечательно, родилось альтернативное решение. Вы бы его еще оформили в один комментарий и было бы просто отлично

      • Илья

        В комментариях табуляция не работает.

        • Кузьминых Кирилл

          Можно воспользоваться шорткодами code /code

  • import string
    
    def initBigramsDict():
        d = dict()
        alph = string.ascii_lowercase + ' '
        alphLen = len(alph)
        for i in range(alphLen):
            for j in range(alphLen):
                d[alph[i] + alph[j]] = False
        return d
    
    def checkBigramsInText(text, d):
        textLen = len(text)
        for i in range(textLen-1):
            bigram = (text[i] + text[i+1]).lower()
            if bigram in d.keys():
                d[bigram] = True
        return d
        
    def main():
    
        res = initBigramsDict()
        
        with open('text.txt', 'r') as inF:
            inText = inF.read()
               
        res = checkBigramsInText(inText, res)
               
        with open('bad_bigrams.txt', 'w+') as outF:        
            for e in sorted(res):
                if res[e] == False:
                    outF.write(e + " ")
    
    if __name__ == '__main__':
        main()