Біграми

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

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

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

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

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

Біграми використовують в одній з найуспішніших мовних моделей для розпізнавання мовлення. Вони є частковим випадком 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% випадків слово далі закінчується.

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

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

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-грама
• Індекс Соренсена

Примітки

1. Collins, Michael John (24 червня 1996). . 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. . Архів оригіналу за 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. . 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.]