0

Биграммы русского языка таблица

850 [1]

Трактат о дешифровке криптографических сообщений
مخطوط في فك رسائل التشفير
Трактат о дешифровке криптографических сообщений

Первая страница рукописи
Авторы Абу Ю́суф Яку́б ибн Исха́к ибн Саббах аль-Ки́нди
Дата написания
Язык оригинала арабский
Жанр научная литература
Объём 12 страниц,

6,5 тыс. слов [2]

Содержание криптоанализ и криптография
Хранение Библиотека Сулеймание (Турция), Документ No.4832 [2]
Оригинал неизвестен

«Трактат о дешифровке криптографических сообщений» — книга, написанная Абу Юсуфом Аль-Кинди, известная как первое упоминание о частотном криптоанализе. До середины IX века самым распространённым в мире методом шифрования сообщений был моноалфавитный шифр (в котором каждой букве кодируемого текста ставится в соответствие однозначно какая-то шифрованная буква). Арабский философ и математик Аль-Кинди в своей работе описал эффективный метод расшифровки таких сообщений, тем самым подтолкнув развитие полиалфавитных шифров [3] [4] . В европейских странах полиалфавитные шифры начали применять лишь в XV веке.

Содержание

История [ править | править код ]

В 750 году приход династии Аббасидов ознаменовал начало золотого века исламской цивилизации. Арабский халифат к тому времени простирался от Атлантического океана на западе до границ с Индией на востоке, занимая примерно половину известного мира. Халифы династии Аббасидов в меньшей степени, чем их предшественники, были заинтересованы в завоеваниях, и вместо этого сосредоточились на создании организованного и обеспеченного общества. Низкие налоги обеспечили подъём торговли и ремесленничества, в то время как строгие законы привели к снижению коррупции и защищали граждан. Всё это опиралось на эффективную систему управления, которая, в свою очередь, опирались на защищённость систем связи. Чиновники зашифровывали конфиденциальные государственные документы и документы налогового учёта [3] , что свидетельствует о широком и регулярном применении криптографии. Во многих руководствах для чиновников, таких как «Руководство для секретарей» (араб. أدب الكتـاب ‎), содержались разделы, посвящённые криптографии. Обычно использовался моноалфавитный шифр, выходной алфавит которого был простой перестановкой входного алфавита, но иногда использовали выходные алфавиты, содержащие другие символы.

Арабские учёные стремились получать знания предшествующих цивилизаций, добывая египетские, вавилонские, индийские, китайские, персидские, сирийские, армянские, ивритские, римские тексты и переводя их на арабский язык. В 815 году халиф аль-Мамун основал в Багдаде Дом Мудрости (араб. بيتالحكمة ‎) — библиотеку и центр перевода рукописей. Основные духовные школы были основаны в Басре, Куфе и Багдаде, где теологи изучали откровения Мухаммеда, содержащиеся в Коране [3] . Теологи были заинтересованы в установлении хронологии откровений, и они делали это путём подсчёта частот слов, содержащихся в каждом откровении. Считалось, что определённые слова появились в арабском языке сравнительно недавно, и, следовательно, если в откровении содержится большое количество этих новых слов, то оно появилось позже в хронологии. Теологи также изучали Хадисы, которые состоят из ежедневных высказываний Пророка. Они пытались доказать, что каждое высказывание действительно принадлежало Мухаммеду. Это делалось путём изучения этимологии слов и структуры предложений, чтобы установить соответствие конкретных текстов языковому стилю Пророка. Они также проанализировали отдельные буквы, и, в частности, обнаружили, что некоторые буквы встречаются чаще, чем другие. Буквы «ﺍ» (/aː/) и «ﻝ» (/l/) являются наиболее распространёнными в арабском языке, отчасти из-за определенного артикля «ﺍﻝ» (/aːl/), тогда как буква «ﺝ» (/ʤ/) встречается в десять раз реже. Это, казалось бы, незначительное замечание, привело к огромному прорыву в криптоанализе. Неизвестно, кто первый изобрёл частотный криптоанализ, но первое известное описание этого метода принадлежит Аль-Кинди.

Аль-Кинди родился в городе Куфа приблизительно в 801 году. Является потомком аристократического рода Kindah. Его отец был эмиром (губернатором) Басры. В Басре Аль-Кинди провёл своё детство и получил начальное образование, позже отправился в Багдад, чтобы продолжить обучение под патронажем халифа аль-Мамуна [5] . После обучения халиф доверил ему руководство Домом Мудрости, где он начал работу над переводом греческих рукописей Аристотеля и других философов на арабский язык [6] . Во время этой работы Аль-Кинди впервые сталкивается с необходимостью расшифровки текстов, так как некоторые из рукописей, которые ему приходилось переводить, были зашифрованы [7] . При аль-Мутаваккиле (с 847 г.) Аль-Кинди подвергался гонениям из-за его религиозно-философских убеждений [8] . Его библиотека была конфискована, сам он был избит. Многие его рукописи были утеряны, в том числе и Трактат о дешифровке криптографических сообщений [6] . Однако до нас дошла копия рукописи, которая была случайно найдена в Библиотеке Сулеймание в Стамбуле. Эта копия содержит большое количество грубых синтаксических и тематических ошибок и, очевидно, написана писцом, который плохо разбирался в лингвистике и математической статистике [2] .

Содержание [ править | править код ]

Во введении Аль-Кинди описывает свой трактат как краткое и чёткое пособие, которое поможет читателю быстро овладеть основными приёмами криптоанализа [9] . Остальную часть книги можно условно разбить на пять частей:

  1. Алгоритмы криптоанализа — описание основных методов криптоанализа, в том числе частотного криптоанализа;
  2. Основные типы шифров — классификация моноалфавитных и некоторых полиалфавитных шифров;
  3. Алгоритмы криптоанализа некоторых типов шифров — алгоритмы взлома конкретных шифров;
  4. Арабские буквы: их порядок и повторяемость — статистические данные, которые можно использовать при расшифровке сообщений на арабском языке;
  5. Комбинации букв в арабском языке — более глубокое рассмотрение лингвистических особенностей арабского языка.

Алгоритмы криптоанализа [ править | править код ]

Аль-Кинди начинает содержательную часть своего трактата с некоторых соображений математической статистики. Он сравнивает алфавит с материалом из которого можно что-нибудь изготовить, придав ему нужную форму. Например, золото — материал, а сделанные из него чашки, браслеты и прочие украшения — разные формы этого материала. Поэтому все изделия сделанные из золота обладают схожими свойствами. Так же каждый язык обладает определёнными закономерностями, которые можно использовать при расшифровке сообщений. Например, в алфавитах многих языков (в том числе арабского) больше согласных букв, чем гласных. Однако если взять какой-либо текст и посчитать частоту появления каждой буквы в нём, то самыми частыми буквами окажутся гласные [10] (в арабском языке самая частая буква (/aː/), в английском, немецком, французском, испанском — e, в русском — о [11] ). Метод частотного криптоанализа автор описывает следующим образом [10] :

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

Затем вернемся к криптограмме, которую мы хотим расшифровать, и так же классифицируем её символы: найдём в криптограмме символ встречающийся чаще всех и заменим его на «первую» букву из проанализированного текста, затем перейдём ко второму по частоте символу и заменим его на «вторую» букву, следующий символ на «третью», и так далее, пока не переберём все символы, используемые в криптограмме.

Читайте также:  Где лучше сделать почту

Метод, предложенный Аль-Кинди легче объяснить с точки зрения русского алфавита. Прежде всего, необходимо изучить достаточно длинный отрывок текста на русском языке, или несколько отрывков разных текстов, чтобы установить частоту появлений каждой буквы алфавита. В русском языке о — самая частая буква, после неё е, затем а и так далее, как указано в таблице. Потом изучим зашифрованный текст и установим частоту появлений каждого символа в нём. Например, если самый частый символ в зашифрованном тексте Ю, то, вероятнее всего, его следуют заменить на букву о. Если второй по частоте символ зашифрованного текста Э, то его, вероятно, следует заменить на е, и так далее. Благодаря методу Аль-Кинди, известному как частотный криптоанализ, не нужно проверять каждый из миллиардов потенциальных ключей. Вместо этого можно расшифровать сообщение просто проанализировав частоту символов в нём.

Таблица относительных частот букв русского алфавита [12] .

Буква Частота % Буква Частота % Буква Частота % Буква Частота %
О 11,08 Р 4,45 Ы 1,96 Х 0,89
Е, Ё 8,41 В 4,33 Ь 1,92 Ш 0,81
А 7,92 К 3,36 З 1,75 Ю 0,61
И 6,83 М 3,26 Г 1,74 Э 0,38
Н 6,72 Д 3,05 Б 1,71 Щ 0,37
Т 6,18 П 2,81 Ч 1,47 Ц 0,36
С 5,33 У 2,80 Й 1,12 Ф 0,19
Л 5,00 Я 2,13 Ж 1,05 Ъ 0,02

Тем не менее частотный криптоанализ не решает полностью задачу взлома моноалфавитных шифров. Его применимость зависит от величины и характера текста. Средние частоты букв какого-либо языка не всегда будут соответствовать частотам букв конкретного текста. Например, краткое сообщение, в котором обсуждается влияние атмосферы на движение зебр в Африке «Из-за озоновых дыр от Занзибары до Замбии и Заира зебры бегают зигзагами», если будет зашифрованно моноалфавитным шифром, не удастся дешифровать с помощью простого частотного криптоанализа. Так как буква з в этом сообщении встречается на порядок чаще, чем в простой речи. В технических текстах редкая буква ф может стать довольно частой в связи с частым использованием таких слов, как функция, дифференциал, диффузия, коэффициент и т. п. [11] .

Если не удаётся расшифровать криптограмму с помощью простого частотного криптоанализа (например если сообщение слишком короткое), Аль-Кинди предлагает использовать характерные сочетания букв или, наоборот, несочетаемость определённых букв друг с другом [10] . Например, наиболее распространённые биграммы (группы из двух букв) русского языка: ст, но, ен, то, на, ов, ни, ра, во, ко [11] . Важна статистика сочетаемости гласных и согласных букв. Например перед буквами ь, ы, ъ и после э не могут стоять гласные, а после любой гласной буквы следует согласная с вероятностью 87 % [11] . Так же подсказкой для криптоаналитика могут быть общепринятые вступительные слова [10] , которые используются почти в каждом языке. Например в арабском часто употреблялось «Во имя Бога, милостивого и милосердного» (араб. بسم الله الرحمن الرحيم ‎). При расшифровке стихотворений можно использовать рифмы и стопы.

Арабские буквы: их порядок и повторяемость [ править | править код ]

Аль-Кинди приводит таблицу с частотами букв арабского алфавита, вычисленными в выборке из семи листов текста [13] .

Буква Частота Буква Частота Буква Частота Буква Частота
ا ‎ 600 ‎ ﺭ ‎ 155 ‎ ﺱ ‎ 91 ‎ ﺵ ‎ — ‎
ﻝ ‎ 437 ‎ ﻉ ‎ 131 ‎ ﻕ ‎ 63 ‎ ﺽ ‎ — ‎
ﻡ ‎ 320 ‎ ﻑ ‎ 122 ‎ ﺡ ‎ 57 ‎ ﺥ ‎ — ‎
ﻩ ‎ 273 ‎ ﺕ ‎ 120 ‎ ﺝ ‎ 46 ‎ ﺙ ‎ 17 ‎
ﻭ ‎ 262 ‎ ﺏ ‎ 112 ‎ ﺫ ‎ 35 ‎ ﻁ ‎ 15 ‎
ﻱ ‎ 252 ‎ ﻙ ‎ 112 ‎ ﺹ ‎ 32 ‎ ﻍ ‎ 15 ‎
ﻥ ‎ 221 ‎ ﺩ ‎ 92 ‎ ﺥ ‎ 20 ‎ ﻅ ‎ 8 ‎

По каким-то причинам автор не указал частоты букв ﺵ ‎ (/ʃ/), ﺽ ‎ (/dˁ/, /ðˤ/) и ﺥ ‎ (/x/), указав при этом их место в таблице, упорядоченной по убыванию частот.

В арабском алфавите 28 букв. Из них 27 могут обозначать согласные звуки, 3 ( ﺍ ‎ (/aː/), ﻭ ‎ (/uː/), ﻱ ‎ (/iː/)) — долгие гласные звуки, букв, обозначающих короткие гласные, — нет (например в слове Муха́ммед пишутся только четыре согласные буквы: محمد ‎). Таким образом в арабском письме преобладают чисто согласные буквы. Однако этот факт не противоречит указанному в начале трактата утверждению о том что самая частая буква на письме любого языка, как правило, гласная, так как в арабском таковой является ﺍ ‎ (/aː/) [13] .

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

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

Метод частотного анализа известен с еще IX-го века и связан и именем Ал-Кинди. Но наиболее известным случаем применения такого анализа является дешифровка египетских иероглифов Ж.-Ф. Шампольоном в 1822 году.

Данный вид анализа основывается на том, что текст состоит из слов, а слова из букв. Количество различных букв в каждом языке ограничено и буквы могут быть просто перечислены. Важными характеристиками текста являются повторяемость букв, пар букв (биграмм) и вообще m-ок (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие.

Идея состоит в подсчете чисел вхождений каждой nm возможных m-грамм в достаточно длинных открытых текстах T=t1t2…tl, составленных из букв алфавита . При этом просматриваются подряд идущие m-граммы текста:

t1t2. tm, t2t3. tm+1, . ti-m+1tl-m+2. tl.

Если – число появлений m-граммы ai1ai2. aim в тексте T, а L – общее число подсчитанных m-грамм, то опыт показывает, что при достаточно больших L частоты

Читайте также:  Домофон пиррс 1000 микро

для данной m-граммы мало отличаются друг от друга.

В силу этого, относительную частоту считают приближением вероятности P (ai1ai2. aim) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

В представленной ниже таблице приводятся частоты встречаемости букв в русском языке (в процентах):

Буква алфавита Показатель частоты встречаемости Буква алфавита Показатель частоты встречаемости
А 0,062 Р 0,04
В 0,038 Т 0,053
Д 0,025 Ф 0,002
Ж 0,007 Ц 0,004
И 0,062 Ш 0,006
К 0,028 Ъ, Ь 0,014
М 0,026 Э 0,003
О 0,09 Я 0,018

Имеется мнемоническое правило запоминания десяти наиболее частых букв русского алфавита. Эти буквы составляют слово СЕНОВАЛИТР.

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

СТ, НО, ЕН, ТО, НА, ОВ, НИ, РА, ВО, КО, СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА.

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

Результатом таких исследований является таблица, в которой слева и справа от каждой буквы расположены наиболее предпочтительные «соседи» (в порядке убывания частоты соответствующих биграмм). В таких таблицах обычно указывается также доля гласных и согласных букв (в процентах), предшествующих (или следующих за) данной букве.

Г С Слева Справа Г С
3 97 л, д, к, т, в, р, н А л, н, с, т, р, в, к, м 12 88
80 20 я, е, у, и, а, о Б о, ы, е, а, р, у 81 19
68 32 я, т, а, е, и, о В о, а, и, ы, с, н, л, р 60 40
78 22 р, у, а, и, е, о Г о, а, р, л, и, в 69 31
72 28 р, я, у, а, и, е, о Д е, а, и, о, н, у, р, в 68 32
19 81 м, и, л, д, т, р, н Е н, т, р, с, л, в, м, и 12 88
83 17 р, е, и, а, у, о Ж е, и, д, а, н 71 29
89 11 о, е, а, и З а, н, в, о, м, д 51 49
27 73 р, т, м, и, о, л, н И с, н, в, и, е, м, к, з 25 75
55 45 ь, в, е, о, а, и, с К о, а, и, р, у, т, л, е 73 27
77 23 г, в, ы, и, е, о, а Л и, е, о, а, ь, я, ю, у 75 25
80 20 я, ы, а, и, е, о М и, е, о, у, а, н, п, ы 73 27
55 45 д, ь, н, о Н о, а, и, е, ы, н, у 80 20
11 89 р, п, к, в, т, н О в, с, т, р, и, д, н, м 15 85
65 35 в, с, у, а, и, е, о П о, р, е, а, у, и, л 68 32
55 45 и, к, т, а, п, о, е Р а, е, о, и, у, я, ы, н 80 20
69 31 с, т, в, а, е, и, о С т, к, о, я, е, ь, с, н 32 68
57 43 ч, у, и, а, е, о, с Т о, а, е, и, ь, в, р, с 63 37
15 85 п, т, к, д, н, м, р У т, п, с, д, н, ю, ж 16 84
70 30 н, а, е, о, и Ф и, е, о, а, е, о, а 81 19
90 10 у, е, о, а, ы, и Х о, и, с, н, в, п, р 43 57
69 31 е, ю, н, а, и Ц и, е, а, ы 93 7
82 18 е, а, у, и, о Ч е, и, т, н 66 34
67 33 ь, у, ы, е, о, а, и, в Ш е, и, н, а, о, л 68 32
84 16 е, б, а, я, ю Щ е, и, а 97 3
100 м, р, т, с, б, в, н Ы л, х, е, м, и, в, с, н 56 44
100 н, с, т, л Ь н, к, в, п, с, е, о, и 24 76
14 86 с, ы, м, л, д, т,, р, н Э н, т, р, с, к 100
58 42 ь, о, а, и, л, у Ю д, т, щ, ц, н, п 11 89
43 57 о, н, р, л, а, и, с Я в, с, т, п, д, к, м, л 16 84

Пример: Проведем анализ текста следующего содержания

"СОКРАТ из Афин (469–399 до н.э.) – знаменитый античный философ, учитель Платона, воплощенный идеал истинного мудреца в исторической памяти человечества. С именем Сократа связано первое фундаментальное деление истории античной философии на до- и после-Сократовскую («Досократики»), отражающее интерес ранних философов VI–V вв. к натурфилософии, а последующего поколения софистов V в. – к этико-политическим темам, главная из которых – воспитание добродетельного человека и гражданина. Сократу был близок софистическому движению. Учение Сократа было устным; все свободное время он проводил в беседах с приезжими софистами и местными гражданами, политиками и обывателями, друзьями и незнакомыми на темы, ставшими традиционными для софистической практики: что есть добро и что – зло, что прекрасно, а что безобразно, что добродетель и что порок, можно ли научиться быть хорошим и как приобретается знание. Об этих беседах мы знаем в основном благодаря ученикам Сократа – Ксенофонту и Платону. Кроме их сочинений, имеются также фрагменты и свидетельства о содержании «сократических диалогов» других сократиков, пародийное изображение Сократа в комедии Аристофана Облака и ряд замечаний о Сократе у Аристотеля. Проблема достоверности изображения личности Сократа в сохранившихся произведениях – ключевой вопрос всех исследований о нем."

В современной компьютерной лингвистике биграммы, или в общем случае n-граммы, являются важным статистическим инструментом. В статье мы расскажем с какими трудностями можно столкнуться при расчёте биграмм на большом корпусе текстов и приведём алгоритм, который можно использовать на любом домашнем компьютере.

Читайте также:  Видеорегистратор аксиом для тойота

Биграмма — это два слова, которые в тексте или, в нашем случае в корпусе текстов, являются соседними. Например в предложении:

будут такие биграммы:

  • Это было
  • было жарким
  • жарким летом
  • летом .

Строго говоря биграммы состоят не из слов, а из токенов. Токеном, т.е. неделимой единицей в рамках нашей задачи, будет либо слово, либо пунктуационный знак. Токенизация — непростая тема, поэтому будем считать, что наш корпус уже токенизирован и разбит на предложения, а чтобы преобразовать предложение в список токенов, достаточно разбить его по пробелу.

Нашей задачей будет получить такой список:

  • Это было 190360
  • было жарким 1017
  • жарким летом 2621
  • летом . 42146

где число показывает сколько раз встречается биграмма во всём корпусе.

Иногда в тексте мы позволим себе использовать термин двусочетание в качестве синонима к слову биграмма.

В данной статье мы намерено опустили все детали реализации, т.к. подход интересен сам по себе и реализовать его несложно на вашем любимом языке программирования. К тому же реализация содержит в себе достаточное количество интересных деталей, чтобы поговорить о ней в отдельной статье. Минимальное количество поясняющих ремарок будет даваться на языке Java.

Наивный подход

  • бежать по корпусу
  • из каждого предложения выделять биграммы
  • считать их с помощью структуры данных мультимножество (на Java это Multiset или ConcurrentHashMultiset в многопоточном варианте)

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

Добавляем промежуточные отсечения

Наивный подход очень просто превратить в рабочий, если немного его модифицировать:

  • бежать по корпусу
  • из каждого предложения выделять биграммы
  • считать их с помощью мультимножества
  • как только видим, что заканчивается память — чистим счётчик, удаляя биграммы, которые встретились к этому моменту меньше чем пороговое число раз

Эта модификация даёт вполне рабочий алгоритм, но отсечения приносят одну неприятность: вместе с ненужным шумом, каким являются нерегулярные опечатки и ошибки, мы удалим множество полезной информации о редких словах. Например, если лексема (набор словоформ) встречается в корпусе 1000 раз, то каждая её отдельная словоформа может встречаться, скажем, меньше 200 раз на корпус, а что уже говорить о двусочетаниях.

Наша задача состоит в том, чтобы посчитать биграммы максимально честно, не используя промежуточных отсечений.

Используем диск в качестве временной памяти

Оперативная память сейчас стоит относительно недорого, но всё же стоит. К тому же на многие варианты ноутбуков больше 16 гигабайт вы не установите при всём желании — ограничение платформы. С дисковым же пространством никаких проблем нет — стоит оно существенно дешевле и при желании вы всегда можете использовать внешний накопитель.

При упоминании смысловых тегов #жёсткий_диск и #алгоритм в памяти всплывают алгоритмы сортировки слиянием (merge sort) и объединения упорядоченных списков, которые многие писали в школе ещё на языке Pascal. Идеи, заложенные в основе этих алгоритмов, как никак хорошо подходят для решения нашей задачи.

Принципиальная схема решения задачи

Прежде чем перейти к деталям, представим принципиальную схему решения поставленной задачи:

  1. Разбить корпус на примерно равные блоки, скажем по 1 гигабайту.
  2. Посчитать биграммы отдельно для каждого блока, отсортировать их в лексикографическом порядке и записать на диск.
  3. Используя алгоритм слияния упорядоченных списков, объединить отдельные файлы с двусочетаниями в один, суммируя количество вхождений для совпадающих биграмм.

Размер каждого блока можно выбирать по вкусу (читай: по количеству установленной оперативной памяти), но в большинстве задач размер в гигабайт оказывается более чем удобным. Также можно работать с монолитным корпусом, делая в программе отсечки по размеру обработанного текста, скидывая результат на диск и очищая структуры данных.

Посмотрев на алгоритм с высоты птичьего полёта можно перейти к деталям.

Считаем биграммы для каждого блока

Чтобы построить оптимальную архитектуру для счётчика двусочетаний, учтём два важных требования:

  1. Хотим считать в несколько потоков.
  2. На выходе нужно получить отсортированный в лексикографическом порядке список биграмм.

Так получается, что эти две задачи можно эффективно решать вместе. Предлагается вместо использования одноуровневой карты (мультимножество это по сути карта ключ-счётчик)

для подсчёта биграмм использовать карту карт:

Эксперимент показывает, что многопоточный расчёт двусочетаний с использованием обеих структур данных выполняется примерно за одинаковое время, а вот сортировка при использовании двухуровневой карты выполняется намного быстрее, т.к. можно сортировать ключи внешней и внутренней карты независимо.

Ещё одно важнейшее преимущество, которое даёт использование двухуровневой карты: можно очень быстро делать дополнительную фильтрацию по словам биграммы. Например проверить их вхождение в словарь или даже выполнить нормализацию (быстрой ездой -> быстрая езда). Производить эти операции до того, как вы сгруппировали одинаковые двусочетания очень накладно, т.к. одна и та же операция будет производится множество раз.

Объединяем результаты по всем блокам

Итак, на выходе предыдущего алгоритма мы имеем множество файлов с записями вида:

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

Общую задачу объединения всех файлов можно решить с использованием файла-аккумулятора, последовательно прибавляя к нему файлы отдельных блоков:

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

Для реализации отлично подходит костяк сортировки слиянием, использующий рекурсию. Схематично для 15 файлов это будет выглядеть так (у функции merge первый индекс включен, второй — исключён):

В результате алгоритм сделает те же 14 слияний, но отработает при этом гораздо эффективнее варианта с аккумулятором. Теоретические требования по памяти у алгоритма слияния O(1), а на практике память выделяется только под буферы чтения и записи.

В заключение

Используя приведённый подход можно собирать по корпусу не только биграммы, но и n-граммы для любого n. Хотя там возможно придётся использовать блоки меньшего размера и чаще скидывать промежуточные результаты на диск.

Как мы и говорили в начале, детали реализации заслуживают отдельного разговора и о них мы расскажем в следующей статье.

admin

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

0

Биграммы русского языка таблица

850 [1]

Трактат о дешифровке криптографических сообщений
مخطوط في فك رسائل التشفير
Трактат о дешифровке криптографических сообщений

Первая страница рукописи
Авторы Абу Ю́суф Яку́б ибн Исха́к ибн Саббах аль-Ки́нди
Дата написания
Язык оригинала арабский
Жанр научная литература
Объём 12 страниц,

6,5 тыс. слов [2]

Содержание криптоанализ и криптография
Хранение Библиотека Сулеймание (Турция), Документ No.4832 [2]
Оригинал неизвестен

«Трактат о дешифровке криптографических сообщений» — книга, написанная Абу Юсуфом Аль-Кинди, известная как первое упоминание о частотном криптоанализе. До середины IX века самым распространённым в мире методом шифрования сообщений был моноалфавитный шифр (в котором каждой букве кодируемого текста ставится в соответствие однозначно какая-то шифрованная буква). Арабский философ и математик Аль-Кинди в своей работе описал эффективный метод расшифровки таких сообщений, тем самым подтолкнув развитие полиалфавитных шифров [3] [4] . В европейских странах полиалфавитные шифры начали применять лишь в XV веке.

Содержание

История [ править | править код ]

В 750 году приход династии Аббасидов ознаменовал начало золотого века исламской цивилизации. Арабский халифат к тому времени простирался от Атлантического океана на западе до границ с Индией на востоке, занимая примерно половину известного мира. Халифы династии Аббасидов в меньшей степени, чем их предшественники, были заинтересованы в завоеваниях, и вместо этого сосредоточились на создании организованного и обеспеченного общества. Низкие налоги обеспечили подъём торговли и ремесленничества, в то время как строгие законы привели к снижению коррупции и защищали граждан. Всё это опиралось на эффективную систему управления, которая, в свою очередь, опирались на защищённость систем связи. Чиновники зашифровывали конфиденциальные государственные документы и документы налогового учёта [3] , что свидетельствует о широком и регулярном применении криптографии. Во многих руководствах для чиновников, таких как «Руководство для секретарей» (араб. أدب الكتـاب ‎), содержались разделы, посвящённые криптографии. Обычно использовался моноалфавитный шифр, выходной алфавит которого был простой перестановкой входного алфавита, но иногда использовали выходные алфавиты, содержащие другие символы.

Арабские учёные стремились получать знания предшествующих цивилизаций, добывая египетские, вавилонские, индийские, китайские, персидские, сирийские, армянские, ивритские, римские тексты и переводя их на арабский язык. В 815 году халиф аль-Мамун основал в Багдаде Дом Мудрости (араб. بيتالحكمة ‎) — библиотеку и центр перевода рукописей. Основные духовные школы были основаны в Басре, Куфе и Багдаде, где теологи изучали откровения Мухаммеда, содержащиеся в Коране [3] . Теологи были заинтересованы в установлении хронологии откровений, и они делали это путём подсчёта частот слов, содержащихся в каждом откровении. Считалось, что определённые слова появились в арабском языке сравнительно недавно, и, следовательно, если в откровении содержится большое количество этих новых слов, то оно появилось позже в хронологии. Теологи также изучали Хадисы, которые состоят из ежедневных высказываний Пророка. Они пытались доказать, что каждое высказывание действительно принадлежало Мухаммеду. Это делалось путём изучения этимологии слов и структуры предложений, чтобы установить соответствие конкретных текстов языковому стилю Пророка. Они также проанализировали отдельные буквы, и, в частности, обнаружили, что некоторые буквы встречаются чаще, чем другие. Буквы «ﺍ» (/aː/) и «ﻝ» (/l/) являются наиболее распространёнными в арабском языке, отчасти из-за определенного артикля «ﺍﻝ» (/aːl/), тогда как буква «ﺝ» (/ʤ/) встречается в десять раз реже. Это, казалось бы, незначительное замечание, привело к огромному прорыву в криптоанализе. Неизвестно, кто первый изобрёл частотный криптоанализ, но первое известное описание этого метода принадлежит Аль-Кинди.

Аль-Кинди родился в городе Куфа приблизительно в 801 году. Является потомком аристократического рода Kindah. Его отец был эмиром (губернатором) Басры. В Басре Аль-Кинди провёл своё детство и получил начальное образование, позже отправился в Багдад, чтобы продолжить обучение под патронажем халифа аль-Мамуна [5] . После обучения халиф доверил ему руководство Домом Мудрости, где он начал работу над переводом греческих рукописей Аристотеля и других философов на арабский язык [6] . Во время этой работы Аль-Кинди впервые сталкивается с необходимостью расшифровки текстов, так как некоторые из рукописей, которые ему приходилось переводить, были зашифрованы [7] . При аль-Мутаваккиле (с 847 г.) Аль-Кинди подвергался гонениям из-за его религиозно-философских убеждений [8] . Его библиотека была конфискована, сам он был избит. Многие его рукописи были утеряны, в том числе и Трактат о дешифровке криптографических сообщений [6] . Однако до нас дошла копия рукописи, которая была случайно найдена в Библиотеке Сулеймание в Стамбуле. Эта копия содержит большое количество грубых синтаксических и тематических ошибок и, очевидно, написана писцом, который плохо разбирался в лингвистике и математической статистике [2] .

Содержание [ править | править код ]

Во введении Аль-Кинди описывает свой трактат как краткое и чёткое пособие, которое поможет читателю быстро овладеть основными приёмами криптоанализа [9] . Остальную часть книги можно условно разбить на пять частей:

  1. Алгоритмы криптоанализа — описание основных методов криптоанализа, в том числе частотного криптоанализа;
  2. Основные типы шифров — классификация моноалфавитных и некоторых полиалфавитных шифров;
  3. Алгоритмы криптоанализа некоторых типов шифров — алгоритмы взлома конкретных шифров;
  4. Арабские буквы: их порядок и повторяемость — статистические данные, которые можно использовать при расшифровке сообщений на арабском языке;
  5. Комбинации букв в арабском языке — более глубокое рассмотрение лингвистических особенностей арабского языка.

Алгоритмы криптоанализа [ править | править код ]

Аль-Кинди начинает содержательную часть своего трактата с некоторых соображений математической статистики. Он сравнивает алфавит с материалом из которого можно что-нибудь изготовить, придав ему нужную форму. Например, золото — материал, а сделанные из него чашки, браслеты и прочие украшения — разные формы этого материала. Поэтому все изделия сделанные из золота обладают схожими свойствами. Так же каждый язык обладает определёнными закономерностями, которые можно использовать при расшифровке сообщений. Например, в алфавитах многих языков (в том числе арабского) больше согласных букв, чем гласных. Однако если взять какой-либо текст и посчитать частоту появления каждой буквы в нём, то самыми частыми буквами окажутся гласные [10] (в арабском языке самая частая буква (/aː/), в английском, немецком, французском, испанском — e, в русском — о [11] ). Метод частотного криптоанализа автор описывает следующим образом [10] :

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

Затем вернемся к криптограмме, которую мы хотим расшифровать, и так же классифицируем её символы: найдём в криптограмме символ встречающийся чаще всех и заменим его на «первую» букву из проанализированного текста, затем перейдём ко второму по частоте символу и заменим его на «вторую» букву, следующий символ на «третью», и так далее, пока не переберём все символы, используемые в криптограмме.

Читайте также:  Где лучше сделать почту

Метод, предложенный Аль-Кинди легче объяснить с точки зрения русского алфавита. Прежде всего, необходимо изучить достаточно длинный отрывок текста на русском языке, или несколько отрывков разных текстов, чтобы установить частоту появлений каждой буквы алфавита. В русском языке о — самая частая буква, после неё е, затем а и так далее, как указано в таблице. Потом изучим зашифрованный текст и установим частоту появлений каждого символа в нём. Например, если самый частый символ в зашифрованном тексте Ю, то, вероятнее всего, его следуют заменить на букву о. Если второй по частоте символ зашифрованного текста Э, то его, вероятно, следует заменить на е, и так далее. Благодаря методу Аль-Кинди, известному как частотный криптоанализ, не нужно проверять каждый из миллиардов потенциальных ключей. Вместо этого можно расшифровать сообщение просто проанализировав частоту символов в нём.

Таблица относительных частот букв русского алфавита [12] .

Буква Частота % Буква Частота % Буква Частота % Буква Частота %
О 11,08 Р 4,45 Ы 1,96 Х 0,89
Е, Ё 8,41 В 4,33 Ь 1,92 Ш 0,81
А 7,92 К 3,36 З 1,75 Ю 0,61
И 6,83 М 3,26 Г 1,74 Э 0,38
Н 6,72 Д 3,05 Б 1,71 Щ 0,37
Т 6,18 П 2,81 Ч 1,47 Ц 0,36
С 5,33 У 2,80 Й 1,12 Ф 0,19
Л 5,00 Я 2,13 Ж 1,05 Ъ 0,02

Тем не менее частотный криптоанализ не решает полностью задачу взлома моноалфавитных шифров. Его применимость зависит от величины и характера текста. Средние частоты букв какого-либо языка не всегда будут соответствовать частотам букв конкретного текста. Например, краткое сообщение, в котором обсуждается влияние атмосферы на движение зебр в Африке «Из-за озоновых дыр от Занзибары до Замбии и Заира зебры бегают зигзагами», если будет зашифрованно моноалфавитным шифром, не удастся дешифровать с помощью простого частотного криптоанализа. Так как буква з в этом сообщении встречается на порядок чаще, чем в простой речи. В технических текстах редкая буква ф может стать довольно частой в связи с частым использованием таких слов, как функция, дифференциал, диффузия, коэффициент и т. п. [11] .

Если не удаётся расшифровать криптограмму с помощью простого частотного криптоанализа (например если сообщение слишком короткое), Аль-Кинди предлагает использовать характерные сочетания букв или, наоборот, несочетаемость определённых букв друг с другом [10] . Например, наиболее распространённые биграммы (группы из двух букв) русского языка: ст, но, ен, то, на, ов, ни, ра, во, ко [11] . Важна статистика сочетаемости гласных и согласных букв. Например перед буквами ь, ы, ъ и после э не могут стоять гласные, а после любой гласной буквы следует согласная с вероятностью 87 % [11] . Так же подсказкой для криптоаналитика могут быть общепринятые вступительные слова [10] , которые используются почти в каждом языке. Например в арабском часто употреблялось «Во имя Бога, милостивого и милосердного» (араб. بسم الله الرحمن الرحيم ‎). При расшифровке стихотворений можно использовать рифмы и стопы.

Арабские буквы: их порядок и повторяемость [ править | править код ]

Аль-Кинди приводит таблицу с частотами букв арабского алфавита, вычисленными в выборке из семи листов текста [13] .

Буква Частота Буква Частота Буква Частота Буква Частота
ا ‎ 600 ‎ ﺭ ‎ 155 ‎ ﺱ ‎ 91 ‎ ﺵ ‎ — ‎
ﻝ ‎ 437 ‎ ﻉ ‎ 131 ‎ ﻕ ‎ 63 ‎ ﺽ ‎ — ‎
ﻡ ‎ 320 ‎ ﻑ ‎ 122 ‎ ﺡ ‎ 57 ‎ ﺥ ‎ — ‎
ﻩ ‎ 273 ‎ ﺕ ‎ 120 ‎ ﺝ ‎ 46 ‎ ﺙ ‎ 17 ‎
ﻭ ‎ 262 ‎ ﺏ ‎ 112 ‎ ﺫ ‎ 35 ‎ ﻁ ‎ 15 ‎
ﻱ ‎ 252 ‎ ﻙ ‎ 112 ‎ ﺹ ‎ 32 ‎ ﻍ ‎ 15 ‎
ﻥ ‎ 221 ‎ ﺩ ‎ 92 ‎ ﺥ ‎ 20 ‎ ﻅ ‎ 8 ‎

По каким-то причинам автор не указал частоты букв ﺵ ‎ (/ʃ/), ﺽ ‎ (/dˁ/, /ðˤ/) и ﺥ ‎ (/x/), указав при этом их место в таблице, упорядоченной по убыванию частот.

В арабском алфавите 28 букв. Из них 27 могут обозначать согласные звуки, 3 ( ﺍ ‎ (/aː/), ﻭ ‎ (/uː/), ﻱ ‎ (/iː/)) — долгие гласные звуки, букв, обозначающих короткие гласные, — нет (например в слове Муха́ммед пишутся только четыре согласные буквы: محمد ‎). Таким образом в арабском письме преобладают чисто согласные буквы. Однако этот факт не противоречит указанному в начале трактата утверждению о том что самая частая буква на письме любого языка, как правило, гласная, так как в арабском таковой является ﺍ ‎ (/aː/) [13] .

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

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

Метод частотного анализа известен с еще IX-го века и связан и именем Ал-Кинди. Но наиболее известным случаем применения такого анализа является дешифровка египетских иероглифов Ж.-Ф. Шампольоном в 1822 году.

Данный вид анализа основывается на том, что текст состоит из слов, а слова из букв. Количество различных букв в каждом языке ограничено и буквы могут быть просто перечислены. Важными характеристиками текста являются повторяемость букв, пар букв (биграмм) и вообще m-ок (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие.

Идея состоит в подсчете чисел вхождений каждой nm возможных m-грамм в достаточно длинных открытых текстах T=t1t2…tl, составленных из букв алфавита . При этом просматриваются подряд идущие m-граммы текста:

t1t2. tm, t2t3. tm+1, . ti-m+1tl-m+2. tl.

Если – число появлений m-граммы ai1ai2. aim в тексте T, а L – общее число подсчитанных m-грамм, то опыт показывает, что при достаточно больших L частоты

Читайте также:  Бритва braun 320s 4

для данной m-граммы мало отличаются друг от друга.

В силу этого, относительную частоту считают приближением вероятности P (ai1ai2. aim) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

В представленной ниже таблице приводятся частоты встречаемости букв в русском языке (в процентах):

Буква алфавита Показатель частоты встречаемости Буква алфавита Показатель частоты встречаемости
А 0,062 Р 0,04
В 0,038 Т 0,053
Д 0,025 Ф 0,002
Ж 0,007 Ц 0,004
И 0,062 Ш 0,006
К 0,028 Ъ, Ь 0,014
М 0,026 Э 0,003
О 0,09 Я 0,018

Имеется мнемоническое правило запоминания десяти наиболее частых букв русского алфавита. Эти буквы составляют слово СЕНОВАЛИТР.

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

СТ, НО, ЕН, ТО, НА, ОВ, НИ, РА, ВО, КО, СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА.

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

Результатом таких исследований является таблица, в которой слева и справа от каждой буквы расположены наиболее предпочтительные «соседи» (в порядке убывания частоты соответствующих биграмм). В таких таблицах обычно указывается также доля гласных и согласных букв (в процентах), предшествующих (или следующих за) данной букве.

Г С Слева Справа Г С
3 97 л, д, к, т, в, р, н А л, н, с, т, р, в, к, м 12 88
80 20 я, е, у, и, а, о Б о, ы, е, а, р, у 81 19
68 32 я, т, а, е, и, о В о, а, и, ы, с, н, л, р 60 40
78 22 р, у, а, и, е, о Г о, а, р, л, и, в 69 31
72 28 р, я, у, а, и, е, о Д е, а, и, о, н, у, р, в 68 32
19 81 м, и, л, д, т, р, н Е н, т, р, с, л, в, м, и 12 88
83 17 р, е, и, а, у, о Ж е, и, д, а, н 71 29
89 11 о, е, а, и З а, н, в, о, м, д 51 49
27 73 р, т, м, и, о, л, н И с, н, в, и, е, м, к, з 25 75
55 45 ь, в, е, о, а, и, с К о, а, и, р, у, т, л, е 73 27
77 23 г, в, ы, и, е, о, а Л и, е, о, а, ь, я, ю, у 75 25
80 20 я, ы, а, и, е, о М и, е, о, у, а, н, п, ы 73 27
55 45 д, ь, н, о Н о, а, и, е, ы, н, у 80 20
11 89 р, п, к, в, т, н О в, с, т, р, и, д, н, м 15 85
65 35 в, с, у, а, и, е, о П о, р, е, а, у, и, л 68 32
55 45 и, к, т, а, п, о, е Р а, е, о, и, у, я, ы, н 80 20
69 31 с, т, в, а, е, и, о С т, к, о, я, е, ь, с, н 32 68
57 43 ч, у, и, а, е, о, с Т о, а, е, и, ь, в, р, с 63 37
15 85 п, т, к, д, н, м, р У т, п, с, д, н, ю, ж 16 84
70 30 н, а, е, о, и Ф и, е, о, а, е, о, а 81 19
90 10 у, е, о, а, ы, и Х о, и, с, н, в, п, р 43 57
69 31 е, ю, н, а, и Ц и, е, а, ы 93 7
82 18 е, а, у, и, о Ч е, и, т, н 66 34
67 33 ь, у, ы, е, о, а, и, в Ш е, и, н, а, о, л 68 32
84 16 е, б, а, я, ю Щ е, и, а 97 3
100 м, р, т, с, б, в, н Ы л, х, е, м, и, в, с, н 56 44
100 н, с, т, л Ь н, к, в, п, с, е, о, и 24 76
14 86 с, ы, м, л, д, т,, р, н Э н, т, р, с, к 100
58 42 ь, о, а, и, л, у Ю д, т, щ, ц, н, п 11 89
43 57 о, н, р, л, а, и, с Я в, с, т, п, д, к, м, л 16 84

Пример: Проведем анализ текста следующего содержания

"СОКРАТ из Афин (469–399 до н.э.) – знаменитый античный философ, учитель Платона, воплощенный идеал истинного мудреца в исторической памяти человечества. С именем Сократа связано первое фундаментальное деление истории античной философии на до- и после-Сократовскую («Досократики»), отражающее интерес ранних философов VI–V вв. к натурфилософии, а последующего поколения софистов V в. – к этико-политическим темам, главная из которых – воспитание добродетельного человека и гражданина. Сократу был близок софистическому движению. Учение Сократа было устным; все свободное время он проводил в беседах с приезжими софистами и местными гражданами, политиками и обывателями, друзьями и незнакомыми на темы, ставшими традиционными для софистической практики: что есть добро и что – зло, что прекрасно, а что безобразно, что добродетель и что порок, можно ли научиться быть хорошим и как приобретается знание. Об этих беседах мы знаем в основном благодаря ученикам Сократа – Ксенофонту и Платону. Кроме их сочинений, имеются также фрагменты и свидетельства о содержании «сократических диалогов» других сократиков, пародийное изображение Сократа в комедии Аристофана Облака и ряд замечаний о Сократе у Аристотеля. Проблема достоверности изображения личности Сократа в сохранившихся произведениях – ключевой вопрос всех исследований о нем."

В современной компьютерной лингвистике биграммы, или в общем случае n-граммы, являются важным статистическим инструментом. В статье мы расскажем с какими трудностями можно столкнуться при расчёте биграмм на большом корпусе текстов и приведём алгоритм, который можно использовать на любом домашнем компьютере.

Читайте также:  Буржуйка дымоход в стену

Биграмма — это два слова, которые в тексте или, в нашем случае в корпусе текстов, являются соседними. Например в предложении:

будут такие биграммы:

  • Это было
  • было жарким
  • жарким летом
  • летом .

Строго говоря биграммы состоят не из слов, а из токенов. Токеном, т.е. неделимой единицей в рамках нашей задачи, будет либо слово, либо пунктуационный знак. Токенизация — непростая тема, поэтому будем считать, что наш корпус уже токенизирован и разбит на предложения, а чтобы преобразовать предложение в список токенов, достаточно разбить его по пробелу.

Нашей задачей будет получить такой список:

  • Это было 190360
  • было жарким 1017
  • жарким летом 2621
  • летом . 42146

где число показывает сколько раз встречается биграмма во всём корпусе.

Иногда в тексте мы позволим себе использовать термин двусочетание в качестве синонима к слову биграмма.

В данной статье мы намерено опустили все детали реализации, т.к. подход интересен сам по себе и реализовать его несложно на вашем любимом языке программирования. К тому же реализация содержит в себе достаточное количество интересных деталей, чтобы поговорить о ней в отдельной статье. Минимальное количество поясняющих ремарок будет даваться на языке Java.

Наивный подход

  • бежать по корпусу
  • из каждого предложения выделять биграммы
  • считать их с помощью структуры данных мультимножество (на Java это Multiset или ConcurrentHashMultiset в многопоточном варианте)

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

Добавляем промежуточные отсечения

Наивный подход очень просто превратить в рабочий, если немного его модифицировать:

  • бежать по корпусу
  • из каждого предложения выделять биграммы
  • считать их с помощью мультимножества
  • как только видим, что заканчивается память — чистим счётчик, удаляя биграммы, которые встретились к этому моменту меньше чем пороговое число раз

Эта модификация даёт вполне рабочий алгоритм, но отсечения приносят одну неприятность: вместе с ненужным шумом, каким являются нерегулярные опечатки и ошибки, мы удалим множество полезной информации о редких словах. Например, если лексема (набор словоформ) встречается в корпусе 1000 раз, то каждая её отдельная словоформа может встречаться, скажем, меньше 200 раз на корпус, а что уже говорить о двусочетаниях.

Наша задача состоит в том, чтобы посчитать биграммы максимально честно, не используя промежуточных отсечений.

Используем диск в качестве временной памяти

Оперативная память сейчас стоит относительно недорого, но всё же стоит. К тому же на многие варианты ноутбуков больше 16 гигабайт вы не установите при всём желании — ограничение платформы. С дисковым же пространством никаких проблем нет — стоит оно существенно дешевле и при желании вы всегда можете использовать внешний накопитель.

При упоминании смысловых тегов #жёсткий_диск и #алгоритм в памяти всплывают алгоритмы сортировки слиянием (merge sort) и объединения упорядоченных списков, которые многие писали в школе ещё на языке Pascal. Идеи, заложенные в основе этих алгоритмов, как никак хорошо подходят для решения нашей задачи.

Принципиальная схема решения задачи

Прежде чем перейти к деталям, представим принципиальную схему решения поставленной задачи:

  1. Разбить корпус на примерно равные блоки, скажем по 1 гигабайту.
  2. Посчитать биграммы отдельно для каждого блока, отсортировать их в лексикографическом порядке и записать на диск.
  3. Используя алгоритм слияния упорядоченных списков, объединить отдельные файлы с двусочетаниями в один, суммируя количество вхождений для совпадающих биграмм.

Размер каждого блока можно выбирать по вкусу (читай: по количеству установленной оперативной памяти), но в большинстве задач размер в гигабайт оказывается более чем удобным. Также можно работать с монолитным корпусом, делая в программе отсечки по размеру обработанного текста, скидывая результат на диск и очищая структуры данных.

Посмотрев на алгоритм с высоты птичьего полёта можно перейти к деталям.

Считаем биграммы для каждого блока

Чтобы построить оптимальную архитектуру для счётчика двусочетаний, учтём два важных требования:

  1. Хотим считать в несколько потоков.
  2. На выходе нужно получить отсортированный в лексикографическом порядке список биграмм.

Так получается, что эти две задачи можно эффективно решать вместе. Предлагается вместо использования одноуровневой карты (мультимножество это по сути карта ключ-счётчик)

для подсчёта биграмм использовать карту карт:

Эксперимент показывает, что многопоточный расчёт двусочетаний с использованием обеих структур данных выполняется примерно за одинаковое время, а вот сортировка при использовании двухуровневой карты выполняется намного быстрее, т.к. можно сортировать ключи внешней и внутренней карты независимо.

Ещё одно важнейшее преимущество, которое даёт использование двухуровневой карты: можно очень быстро делать дополнительную фильтрацию по словам биграммы. Например проверить их вхождение в словарь или даже выполнить нормализацию (быстрой ездой -> быстрая езда). Производить эти операции до того, как вы сгруппировали одинаковые двусочетания очень накладно, т.к. одна и та же операция будет производится множество раз.

Объединяем результаты по всем блокам

Итак, на выходе предыдущего алгоритма мы имеем множество файлов с записями вида:

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

Общую задачу объединения всех файлов можно решить с использованием файла-аккумулятора, последовательно прибавляя к нему файлы отдельных блоков:

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

Для реализации отлично подходит костяк сортировки слиянием, использующий рекурсию. Схематично для 15 файлов это будет выглядеть так (у функции merge первый индекс включен, второй — исключён):

В результате алгоритм сделает те же 14 слияний, но отработает при этом гораздо эффективнее варианта с аккумулятором. Теоретические требования по памяти у алгоритма слияния O(1), а на практике память выделяется только под буферы чтения и записи.

В заключение

Используя приведённый подход можно собирать по корпусу не только биграммы, но и n-граммы для любого n. Хотя там возможно придётся использовать блоки меньшего размера и чаще скидывать промежуточные результаты на диск.

Как мы и говорили в начале, детали реализации заслуживают отдельного разговора и о них мы расскажем в следующей статье.

admin

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *