Біграми

Біграмний шифр — це криптографічний алгоритм, призначений для шифрування груп з двох букв (біграм).

«Батьком» біграмних шифрів вважають німецького абата Йоганеса Трісемуса, який ще 1508 року у своїй роботі з криптології, яка називалася «Поліграфія», вперше згадав про можливість шифрування біграм, тобто, дволітерних поєднань. Їх стійкість до розкриття виявилася значно вищою, ніж у попередників, тому деякі біграмні шифри зберегли актуальність аж до Другої світової війни.

В роки Першої світової війни Велика Британія використовувала біграмний «Шифр Плейфера».

Біграмний шифр «Подвійний квадрат», винайдений англійцем Чарльзом Вітстоном 1854 року, в роки Другої світової війни використовували німці.

Характеристика

Біграми використовують в одній з найуспішніших мовних моделей для розпізнавання мовлення.^[1] Вони є частковим випадком N-грам.

Частоти біграм можна використати в криптографії для розв'язання криптограм. (Див. Частотний аналіз)

Частоти біграм є одним з підходів до статистичної ідентифікації мови.

Біграми допомагають отримати умовну ймовірність символу з урахуванням попереднього символу, застосовуючи відношення умовної ймовірності: ${\displaystyle P(W_{n}|W_{n-1})={P(W_{n-1},W_{n}) \over P(W_{n-1})}}$

Тобто, ймовірність ${\displaystyle P()}$ символу ${\displaystyle W_{n}}$, якому передує символ ${\displaystyle W_{n-1}}$, дорівнює ймовірності їх біграми ${\displaystyle P(W_{n-1},W_{n})}$, поділеній на ймовірність попереднього символу.

Біграми слів української мови

Статистика біграм в українських словах, з файлу /usr/share/dict/ukrainian.
Крапка позначає кінець і початок слова. Перший рядок містить ймовірності для кожної букви почати слово. Наприклад для и чи м'якого знака вона нульова. Другий рядок - з якою ймовірністю певна буква буде в слові після букви "а", і т.д. Також включені апостроф і дефіс. З передостаннього рядка можна побачити що з 69% ймовірності після апострофа буде "я", 14% - "є", 9% - "ї", 7% - "ю", а решка - винятки на в межах похибки, на зразок "О'Ніл". Якщо зустрічається буква "ї", то в 70% випадків слово далі закінчується.

Частота біграм в англійській мові

Частота найпоширеніших біграм у невеликому англомовному корпусі:^[2]

th 1.52       en 0.55       ng 0.18
he 1.28       ed 0.53       of 0.16
in 0.94       to 0.52       al 0.09
er 0.94       it 0.50       de 0.09
an 0.82       ou 0.50       se 0.08
re 0.68       ea 0.47       le 0.08
nd 0.63       hi 0.46       sa 0.06
at 0.59       is 0.46       si 0.05
on 0.57       or 0.43       ar 0.04
nt 0.56       ti 0.34       ve 0.04
ha 0.56       as 0.33       ra 0.04
es 0.56       te 0.27       ld 0.02
st 0.55       et 0.19       ur 0.02

Доступні також повні таблиці частоти біграм для більших корпусів.^[3][4]

Див. також

• Диграф
• N-грама
• Індекс Соренсена

Примітки

1. Collins, Michael John (24 червня 1996). A new statistical parser based on bigram lexical dependencies. Proceedings of the 34th annual meeting on Association for Computational Linguistics -. Association for Computational Linguistics. с. 184—191. arXiv:cmp-lg/9605012. doi:10.3115/981863.981888. S2CID 12615602. Архів оригіналу за 8 жовтня 2018. Процитовано 9 жовтня 2018.
2. Cornell Math Explorer's Project – Substitution Ciphers. Архів оригіналу за 5 червня 2011. Процитовано 18 квітня 2018.
3. Jones, Michael N; D J K Mewhort (August 2004). Case-sensitive letter and bigram frequency counts from large-scale English corpora. Behavior Research Methods, Instruments, and Computers. 36 (3): 388—396. doi:10.3758/bf03195586. ISSN 0743-3808. PMID 15641428.
4. English Letter Frequency Counts: Mayzner Revisited or ETAOIN SRHLDCU. norvig.com. Архів оригіналу за 19 жовтня 2018. Процитовано 28 жовтня 2019.

Посилання

• Digraph Frequency (based on a sample of 40,000 words) [Архівовано 5 червня 2011 у Wayback Machine.]
• Double, Triple, and Quadruple Bigrams [Архівовано 19 квітня 2018 у Wayback Machine.]