Биграмма

Биграмма — это последовательность из двух элементов, обычно символов, букв, звуков или слов, рассматриваемая как единая единица анализа. В лингвистике, компьютерной лингвистике, криптографии и теории информации биграммы используются для изучения статистических закономерностей текста, построения языковых моделей и решения задач, связанных с обработкой естественного языка. Биграмма является частным случаем n-граммы, где n = 2.

История и происхождение

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

В 1948 году Клод Шеннон в своей работе «Математическая теория связи» заложил основы информационной теории, в рамках которой n-граммы, включая биграммы, стали использоваться для оценки энтропии языка и моделирования последовательностей символов. С развитием компьютерной лингвистики в 1950–1960-х годах биграммы стали ключевым инструментом для автоматической обработки текста, распознавания речи и машинного перевода.

Классификация биграмм

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

По типу элементов

• Символьные биграммы (буквенные): Состоят из двух последовательных букв или символов. Например, в слове «дом» символьные биграммы: «до», «ом». В английском слове «hello»: «he», «el», «ll», «lo». Используются в криптоанализе, орфографических проверках и анализе стиля.
• Звуковые биграммы (фонемные): Состоят из двух последовательных фонем. Применяются в фонетике, распознавании речи и синтезе речи.
• Словесные биграммы: Состоят из двух последовательных слов. Например, в предложении «кот сидит на окне» словесные биграммы: «кот сидит», «сидит на», «на окне». Широко используются в языковых моделях, машинном переводе и анализе тональности текста.
• Биграммы символов (в информатике): В контексте программирования и кодирования биграммой может называться пара байтов или других единиц данных.

По способу выделения

• Пересекающиеся (скользящие): Биграммы выделяются со сдвигом на один элемент. Это наиболее распространённый способ, при котором каждый элемент (кроме первого и последнего) входит в две биграммы. Пример для слова «книга»: «кн», «ни», «иг», «га».
• Непересекающиеся: Биграммы выделяются без перекрытия, то есть текст разбивается на пары элементов, не имеющих общих элементов. Пример для слова «книга»: «кн», «иг» (буква «а» остаётся вне рассмотрения, если длина нечётная). Этот метод реже используется в лингвистике, но применяется в некоторых алгоритмах сжатия данных.

Применение биграмм

Лингвистика и компьютерная лингвистика

• Языковые модели: Биграммы являются основой для построения простых вероятностных моделей языка, которые оценивают вероятность появления следующего слова или символа на основе предыдущего. Такие модели используются в системах автодополнения текста (например, на смартфонах), в поисковых системах для предсказания запросов и в системах распознавания речи.
• Анализ частотности: Изучение частотности биграмм в тексте позволяет выявлять стилистические особенности автора, определять язык текста (например, для русского языка характерны биграммы «ст», «но», «то», «на»), а также обнаруживать заимствования или плагиат.
• Машинный перевод: В статистическом машинном переводе биграммы используются для оценки качества перевода (метрика BLEU частично основана на совпадении n-грамм, включая биграммы) и для выбора наиболее вероятного варианта перевода.
• Орфографические и грамматические проверки: Биграммы помогают обнаруживать опечатки и грамматические ошибки. Например, если в тексте встречается биграмма, которая крайне редко встречается в данном языке, система может предложить исправление.

Криптография

• Криптоанализ: Анализ частотности биграмм является одним из основных методов взлома шифров простой замены и некоторых видов шифров перестановки. Зная частотность биграмм в языке (например, в русском языке самые частые биграммы: «ст», «но», «то», «на», «ен»), криптоаналитик может сопоставить их с частотностью биграмм в зашифрованном тексте и восстановить ключ.
• Шифрование: Некоторые шифры, например, шифр Плейфера, работают с биграммами как с единицами шифрования. В шифре Плейфера открытый текст разбивается на пары букв (биграммы), и каждая пара заменяется на другую пару по определённому правилу с использованием ключевой таблицы.

Биоинформатика

• Анализ последовательностей ДНК и РНК: В геномике биграммы (динуклеотиды) используются для изучения частоты встречаемости пар нуклеотидов (например, «AT», «GC», «CG»). Это помогает в идентификации генов, изучении эволюционных связей и анализе структуры ДНК.

Информационный поиск и обработка текстов

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

Примеры

В русском языке

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

• «ст» (встречается в словах «стол», «мост», «статья»)
• «но» («ночь», «окно», «норма»)
• «то» («тот», «сто», «топор»)
• «на» («надо», «рана», «наука»)
• «ен» («день», «меня», «стена»)

Пример словесных биграмм: «в течение», «для того», «на основе», «по мнению», «в связи».

В английском языке

Наиболее частотные символьные биграммы: «th», «he», «in», «er», «an». Словесные биграммы: «of the», «in the», «to be», «is a», «as well».

Критика и ограничения

Использование биграмм имеет ряд ограничений. Основным недостатком является то, что биграммы учитывают только локальный контекст (два соседних элемента) и не способны улавливать долгосрочные зависимости в тексте. Например, в предложении «Кот, который сидел на окне, спал» биграммы не свяжут слово «кот» и «спал», так как между ними находится много других слов. Для решения этой проблемы используются более сложные модели, такие как триграммы (n=3) или рекуррентные нейронные сети.

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

Источники

1. Шеннон, К. «Математическая теория связи» (1948).
2. Маннинг, К. Д., Шютце, Х. «Основы статистической обработки естественного языка» (1999).
3. Захаров, В. П., Хохлова, М. В. «Корпусная лингвистика» (2013).
4. Шнайер, Б. «Прикладная криптография» (1996).
5. Jurafsky, D., Martin, J. H. «Speech and Language Processing» (2023).