Біграми

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Посилання

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