Разработка методов и алгоритмов анализа характеристик текстов на естественном языке на основе теоретико-информационного подхода и применение их к задачам защиты информации тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Малашина Анастасия Геннадьевна

• Малашина Анастасия Геннадьевна
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Малашина Анастасия Геннадьевна

Глоссарий

Введение

Глава 1. Анализ известных подходов в части исследования информационных характеристик языков

1.1. Текстовые корпуса и принципы их построения

1.2. Формальные языковые модели

1.3. Методы оценки энтропии последовательности случайных величин

1.4. Подходы к изучению информационной энтропии текстов на естественном языке

1.5. Известные оценки энтропии текстов на русском и английском языках

Глава 2. Разработка методов и алгоритмов анализа информационных характеристик текстов на русском и английском языках

2.1. Алгоритмы формирования корпусов и построения словарей s-грамм

2.2. Модели покрытия словарей s-грамм

2.3. Метод оценки энтропии коротких s-грамм

2.4. Исследование границ многозначности восстановления s-граммы

2.5. Выводы по главе

Глава 3. Метод восстановления участков входных сообщений с использованием теоретико-информационного подхода

3.1. Анализ методов полного восстановления исходного сообщения

3.2. Построение алгоритма восстановления: введение теоретико-вероятностной модели появления значений символов на выходе канала, поиск подходящих s-грамм

3.3. Экспериментальные исследования по восстановлению подходящих s-грамм

3.4. Теоретические оценки доли восстановленных s-грамм

3.5. Выводы по 3 главе

Результаты, выносимые на защиту

Выводы по диссертации

Заключение

Список литературы

Приложение: результаты экспериментов

1. Состав и описание корпусов

2. Объемы словарей s-грамм

3. Численные оценки покрытия словарей s-грамм

4. Численные оценки энтропии s-грамм

5. Теоретико-вероятностные модели появления выходных множеств

6. Экспериментальные результаты восстановления подходящих s-грамм сообщения

7. Проверка адекватности применения модели 4.1 в случае конечного

8. Некоторые численные расчеты введенных моделей аппроксимации

Глоссарий

^-ограниченная s-грамма - s-грамма, для которой известно в среднем не более L возможных вариантов на знак. s-грамма - набор из s знаков алфавита.

s-граммная модель языка - вероятностная модель, позволяющая вычислить вероятность следующего знака, учитывая 5 — 1 предыдущих знаков [26]. Аналитический язык - язык, в котором грамматические отношения между словами выражаются преимущественно посредством служебных слов (предлогов, артиклей, модальных глаголов) и порядка слов, а не флексий (изменений окончаний слов).

Внесловарная (ООУ) s-грамма - допустимая s-грамма, не попавшая в словарь [26].

Внутренняя оценка языковой модели - оценка, определяемая на основе того же корпуса, который использовался для построения модели языка. [26]. Выбор s-грамм с зацеплением - последовательный выбор ^ знаков из текста со сдвигом вправо на один символ.

Доля восстановленных s-грамм - относительная доля s-грамм, которые удалось восстановить на выходе канала связи среди всех s-грамм сообщения (при разбиении сообщения на s-граммы с зацеплением).

Допустимая s-грамма - s-грамма, встречающаяся в текстах на заданном языке.

Естественный язык - язык, используемый для общения людей, не создаваемый целенаправленно. В данной работе рассматривается только письменная форма выражения языка (тексты).

Закрытый словарь - словарь, который содержит фиксированный набор лексических единиц (слов, s-грамм) и ограничивает языковую модель данным набором.

Запретная s-грамма - s-грамма, не встречающаяся ни в каких текстах на заданном языке.

Канал связи - совокупность технических устройств, обеспечивающих передачу информации.

Корпус - машиночитаемая коллекция текстов на некотором языке [26]. Модель источника сообщений - математическая модель, описывающая свойства реальных текстов, вырабатываемых определенными источниками, в том числе естественными (текст на каком-то языке).

Насыщенный корпус - языковой корпус, для которого увеличение объема не приводит к росту новых единиц корпуса [50].

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

Покрытие корпуса (словаря) - степень (широта) охвата данным корпусом (словарем) определенного языка с определенной лексикой [26]. Подходящая s-грамма - то же, что L-ограниченная s-грамма Словарь s-грамм - набор s-грамм, извлеченных из корпуса, без повторений, расположенных в лексикографическом порядке.

Специализированный корпус - корпус текстов, ограниченных конкретной тематикой, стилей или жанром.

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

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

Энтропия - теоретико-информационная характеристика распределения случайной величины.

Языковая модель - это вероятностное распределение на множестве словарных последовательностей [26].

Введение диссертации (часть автореферата) на тему «Разработка методов и алгоритмов анализа характеристик текстов на естественном языке на основе теоретико-информационного подхода и применение их к задачам защиты информации»

Введение

1. Постановка проблемы и актуальность исследования

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

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

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

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

Обладая некоторой информацией о знаках неизвестного текста и заранее ограничивая множество входных сообщений (например, с помощью закрытых словарей), можно реализовать восстановление исходного сообщения или его отдельных s-грамм [78, 85].

Объектом исследования в настоящей работе являются тексты на естественном языке. Предметом исследования являются методы и алгоритмы анализа информационных характеристик данных текстов.

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

Актуальность и значимость исследования подтверждается п. 1.4 «Разработка теоретико-информационных методов анализа систем передачи, хранения и защиты информации» паспорта области науки «Инженерные науки и прикладная математика» [66], утвержденного Ученом советом НИУ ВШЭ от 2 февраля 2018 г., а также недавними исследованиями, проводимыми в данном направлении [2].

2. Цели и задачи диссертационной работы.

Основной целью данной диссертационной работы является разработка методов и алгоритмов анализа характеристик текстов на естественном языке на основе теоретико-информационного подхода.

Для решения соответствующей цели были поставлены следующие задачи:

1. Разработать алгоритмы нормализации текстовых корпусов и построения словарей s-грамм. Сформировать различные текстовые корпуса и построить словари s-грамм.

2. Разработать математическую модель покрытия словарей s-грамм. Получить численные оценки покрытия словарей.

3. Разработать метод оценки энтропии s-грамм. Получить численные оценки энтропии коротких s-грамм.

4. Исследовать границы допустимой многозначности восстановления s-грамм сообщения.

5. Разработать метод восстановления участков входных сообщений с использованием теоретико-информационного подхода. Получить численные оценки доли восстановленных s-грамм сообщения.

3. Степень разработанности темы.

Теоретико-информационные аспекты защиты информации подробно описаны в монографиях многих мировых ученых, в том числе К. Шеннона [52, 88].

Отдельные случаи построения методов восстановления текстовой информации на выходе канала связи с использованием теоретико-информационного подхода в настоящее время исследуются А. В. Бабашом [2], а также исследовались В. М. Деундяком, Е. А. Пашковой [65]. В этих работах применяется метод «чтения в колонках» для полного восстановления выходного сообщения при наличии информации на выходе канала связи, которая значительно ограничивает число неизвестных символов сообщения (с вероятностью их появления близкой к 1).

Согласно ранее проведенным исследованиям [85], полное восстановление сообщения возможно, если количество предполагаемых значений исходных символов ограничено (например, для русского языка - не более 16 при алфавите в 32 символа), при этом вероятность появления среди них истинного знака близка к единице. Тогда для каждого входного символа можно зафиксировать множество его возможных значений (например, наиболее вероятных). Восстановление исходного текста представляет собой поиск варианта из множества входных сообщений среди всех возможных комбинаций. Такой подход может привести к потере истинного варианта восстановления, вероятность которой оценивается исходя из введенной теоретико-вероятностной модели исследуемого процесса. С увеличением количества значений на выходе канала связи восстановление исходного текста становится затруднительным из-за значительного количества возможных вариантов восстановления и неопределенности выбора, возникающей в процессе перебора. Таким образом, когда количество символов на выходе

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

Основой теоретико-информационного подхода к информационной безопасности является понятие энтропии. Текст и язык также являются системами, обладающими информационной энтропией. Более того, энтропия текстов на естественном языке значительно ниже максимальной энтропии алфавита [89]. Поскольку количество допустимых s-грамм в языке значительно меньше, чем запретных, такой подход значительно снижает сложность восстановления по сравнению с полным перебором. Аналогичный подход, например, может быть использован при подборе паролей [17].

Существуют различные методы оценки энтропии s-грамм текстов. Наиболее известным среди них является метод Шеннона [53], основанный на угадывании возможного продолжения текста по известному отрывку Метод позволяет получить нижнюю и верхнюю оценки. Вместо метода угадывания, можно использовать представление текста с помощью цепи Маркова глубины s, чтобы приблизительно оценить вероятности s-грамм и использовать формулу Шеннона для расчета информационной энтропии [52].

В данной диссертационной работе используется метод определения энтропии s-грамм, основанный на составлении словарей, идеи которого восходят к комбинаторного подходу Колмогорова [33] и предлагаются методы асимптотической оценки покрытия создаваемых словарей s-грамм.

4. Научная новизна исследования

1. Разработаны алгоритмы нормализации текстовых корпусов и построения словарей s-грамм, позволяющие сформировать прикладную базу для проведения анализа характеристик текстов на естественном языке на основе теоретико-информационного подхода.

2. Предложены и исследованы математические модели покрытия словарей s-грамм, основанные на теоретико-информационных свойствах текстов на естественном языке.

3. Разработан метод оценки энтропии коротких s-грамм, основанный на мощностных характеристиках словарей s-грамм.

4. Проведены исследования границ допустимой многозначности восстановления s-грамм сообщения.

5. Разработан метод восстановления участков входных сообщений с использованием теоретико-информационного подхода.

5. Теоретическая и практическая значимость исследования

Теоретическая значимость данного диссертационного исследования заключается в развитии теоретико-информационного и алгоритмического подходов для решения задач информационной безопасности и развитии методов анализа и синтеза современных алгоритмов защиты информации.

Практическая значимость результатов диссертационной работы заключается в следующем:

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

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

3. Методы построения словарей и оценки энтропии коротких s-грамм могут быть использованы для анализа стойкости алгоритмов аутентификации, построенных на основе парольных систем.

6. Методы исследования

В диссертации использованы методы статистического анализа, предельные теоремы теории вероятностей, включая центральную предельную теорему и теоремы о распределении (в том числе, условных и многомерных) нормальных, биномиальных и гипергеометрических величин, неравенство Берри-Эссена. Использованы основополагающие понятия из теории информации (дискретный канал связи, энтропия дискретного стационарного источника, вторая теорема Шеннона и др.). Для создания и проведения исследования текстовых корпусов и словарей s-грамм разработана программная реализация на языке C++ и применены теоретические аспекты корпусной лингвистики, в том числе принципы о полноте и репрезентативности составляемых корпусов.

Для исследования возможности восстановления отдельных s-грамм сообщения разработана программная реализация алгоритма восстановления с помощью методов объектно-ориентированного программирования на языке C++. Для получения ряда численных оценок и экстраполяции эмпирических результатов использованы средства компьютерной алгебры (численные методы) в составе программного пакета Wolfram Mathematica.

7. Личный вклад

Все результаты и положения, выносимые на защиту, получены автором лично. В ходе диссертационного исследования разработаны алгоритмы нормализации текстовых корпусов и построения словарей s-грамм, позволяющие сформировать прикладную базу для проведения анализа характеристик текстов на естественном языке на основе теоретико-информационного подхода. Разработаны подходы, которые позволяют оценивать покрытие словарей s-грамм и энтропию коротких s-грамм. Проведены экспериментальные исследования ряда информационных характеристик русского и английского языков (объемов словарей s-грамм для корпусов различных стилей и размеров, покрытия словарей, энтропии s-грамм).

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

8. Публикации и апробация работы

Публикации автора в Scopus/WoS:

1. Malashina A. Possibility of Recovering Message Segments Based on Side Information about Original Characters // Doklady Mathematics. 2024. Vol. 108. No. Suppl 2. (Scopus Q2, WoS Q3, MathSciNet) (перевод с русского)

2. Малашина А. Г. О возможности восстановления отрезков сообщения по информации о значениях исходных символов // Доклады Российской академии наук. Математика, информатика, процессы управления. 2023. Т. 514. № 2. С. 138-149. (Список В)

3. Malashina A. The Combinatorial Analysis of n-Gram Dictionaries, Coverage and Information Entropy based on the Web Corpus of English // Baltic Journal of Modern Computing, 2021, Т.9, №3, С. 363-376. (Scopus Q4, WoS Q4, Список С)

4. Малашина А. Г. Построение и анализ моделей русского языка в связи с исследованиями криптографических алгоритмов / Малашина А. Г., Лось А. Б. // Чебышевский сборник, 2022, Т.23, №2, С. 151-160. (Scopus Q3, Список С)

Публикации в иных изданиях:

1. Малашина А. Г. Разработка инструментальных средств для исследования информационных характеристик естественного языка // Промышленные АСУ и контроллеры. 2021. № 2. С. 9-15. (ВАК К2)

2. Малашина А. Г. Модификация одного алгоритма восстановления текстовых сообщений и математическая модель распределения числа осмысленных текстов // Электронные средства и системы управления: материалы докладов XVI Международной научно-практической конференции (18-20 ноября 2020 г.): в ч. 2. Томск: В-спектр, 2020. С. 8588. (РИНЦ)

3. Малашина А. Г. Построение и анализ моделей русского языка в связи с исследованиями криптографических алгоритмов / Малашина А. Г., Лось А. Б. // Алгебра, теория чисел и дискретная геометрия: современные

проблемы, приложения и проблемы истории. Тула: ТГПУ, 2020. С. 177181. (РИНЦ)

Доклады на конференциях:

1. Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского, Россия, Москва, 27.02.2023 - 07.03.2023, доклад: «Исследование энтропии текстов на естественном языке методом составления словарей n-грамм».

2. Entropy 2021: The Scientific Tool of the 21st Century, Португалия, Порту, 05.05.2021 - 07.05.2021, доклад: «Entropy analysis of n-grams and estimation of the number of meaningful language texts».

3. Всероссийский конкурс-конференция студентов и аспирантов по информационной безопасности «SIBINF0-2021», Россия, Томск, 22.04.2021, доклад: «Математическая модель алгоритма восстановления отдельных частей текстового сообщения».

4. XXIII научно-практическая конференция «РусКрипто'2021», Россия, Солнечногорск, 23.03.2021 - 26.03.2021, доклад: «Алгоритм восстановления отдельных частей текстовых сообщений по информации о возможных вариантах его знаков».

5. Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского, Россия, Москва, 10.03.2021 - 17.03.2021, доклад: «Предельные распределения, возникающие в задаче восстановления отдельных отрезков текстового сообщения».

6. XVI Международная научно-практическая конференция «Электронные средства и системы управления», Россия, Томск, 18.11.2020 -20.11.2020, доклад: «Модификация одного алгоритма восстановления текстовых сообщений и математическая модель распределения числа осмысленных текстов».

7. XVIII Международная научная конференция «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы

истории», посвященная 100-летию со дня рождения профессоров Б. М. Бредихина, В. И. Нечаева и С. Б. Стечкина, Россия, Тула, 23.09.2020 -26.09.2020, доклад: «Построение и анализ моделей русского языка в связи с исследованиями криптографических алгоритмов».

8. Всероссийский конкурс-конференция студентов и аспирантов по информационной безопасности <^ЮШЕ0-2020», Россия, Томск, 16.04.2020, доклад: «Модификация одного алгоритма восстановления текстовых сообщений и математическая модель распределения числа осмысленных текстов».

9. Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского, Россия, Москва, 25.02.2020 - 04.03.2020, доклад: «Статистический анализ языковых моделей русского языка на основе текстового новостного корпуса».

Доклады на семинарах научного руководителя МИЭМ НИУ ВШЭ и кафедры компьютерной безопасности НИУ ВШЭ:

1. Семинар от 23 апреля 2024 г., доклад: «Исследование информационных характеристик естественных языков в связи с разработкой методов оценки защищенных информационных систем».

2. Семинар от 18 апреля 2023 г., доклад: «Исследование информационных характеристик естественных языков в связи с разработкой методов оценки защищенных информационных систем».

3. Семинар от 25 ноября 2021 г., доклад: «Исследование информационных характеристик естественных языков в связи с разработкой методов оценки защищенных информационных систем».

Результаты интеллектуальной деятельности:

1. Свидетельство №2022662474 о регистрации программы для ЭВМ «Программа для восстановления отельных участков сообщения по информации о возможных символах его знаков», 2022 г.

2. Свидетельство № 2020665906 о регистрации программы для ЭВМ «Программа для создания словарей п-грамм и вычисления их информационных характеристик», 2020 г.

Проекты:

Результаты диссертационного исследования были также использованы при выполнении проектов под руководством автора:

1. Студенческий проект МИЭМ №338, «Исследование информационных характеристик естественных языков1», 2020-2021 гг.

2. Проект «Исследование информационных характеристик естественных языков» в рамках «Ярмарки проектов», 2020 г.

9. Содержание работы

Диссертация состоит из глоссария, введения, 3-х глав, заключения, списка литературы, приложения и содержит 116 страниц, 45 таблиц и 20 рисунков:

1. В первой главе проводится анализ известных подходов в части исследования информационных характеристик языков.

2. Во второй главе разрабатываются методы и алгоритмы анализа информационных характеристик текстов на русском и английском языках: построение корпусов и словарей s-грамм, исследование энтропии, разработка моделей покрытия словарей.

3. В третьей главе разрабатывается и исследуется метод восстановления участков входных сообщений с использованием теоретико-информационного подхода. При этом изложение третий главы начинается с анализа известных подходов восстановления сообщения по информации о значениях его знаков.

1 Результаты проекта доступны в публикации Нагаева И. Э., Савченкова Д. М. Исследование информационных характеристик художественных текстов и их переводов //Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов имени ЕВ Арменского. - 2021. - С. 241-244.

Глава 1. Анализ известных подходов в части исследования информационных характеристик языков

1.1. Текстовые корпуса и принципы их построения

Корпус - машиночитаемая коллекция текстов на некотором языке [26]. Текстовые корпуса представляют собой большие и систематически собранные данные, которые используются для анализа языков и создания языковых моделей.

Языковые корпуса должны составляться с учетом принципов:

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

• Сбалансированности, то есть пропорциональности текстов из разных категорий (стилей, жанров) во избежание доминирования текстов одного типа.

• Оптимальности объема. Малый размер корпуса может привести к получению недостоверных оценок тех или иных характеристик текстов.

И включать этап:

• Нормализации текстов, то есть очистку данных и приведение текстов к единообразию в корпусе.

Самое большое количество текстовых корпусов создано на основе

английского языка (см. Таблица 1).

Таблица 1 - Некоторые известные корпуса английского языка

Корпус Объем, слов Состав корпуса

Британский национальный корпус (BNC) 100 млн 90% - письменные тексты, 10% - устные

Оксфордский корпус английского языка (Oxford English Corpus) 2 млрд Тексты из Интернета, созданные с 2000 года

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

Национальный корпус американского английского (ANC) 22 млн Американский вариант современного английского языка

«Банк английского языка» (The Bank of English) 4,5 млрд Различные типы письменных текстов и устной речи на британском и американском английском

Кембриджский международный корпус (Cambridge International Corpus) 800 млн Британские и американские тексты разных типов, записи устной речи носителей британского и американского вариантов английского языка ля составления учебных материалов и словарей

Международный корпус английского языка (ICE) 1 млн Совокупность национальных подкорпусов, отражающих словоупотребление в различных вариантах английского языка

Веб-корпус английского языка (iWeb) 14 млрд Тексты с веб-страниц

Источник: составлено автором на основе открытых источников.

Для русского языка существует значительно меньше языковых корпусов. Многие корпуса являются закрытыми без доступа к скачиванию, что затрудняет их использование в исследовательских целях (см. Таблица 2).

Таблица 2 - Некоторые известные корпуса русского языка

Корпус Объем, слов Состав корпуса

Национальный корпус русского языка (НКРЯ) 2 млрд Литературные тексты, научные статьи, СМИ, интернет-ресурсы, разговорная речь

Taiga Corpus 5 млрд Новости, интернет-форумы, блоги, научные статьи, технические тексты

Открытый корпус (OpenCorpora) 2 млн Литературные произведения, научные тексты, новости, форумы

SynTagRus 1,5 млн Аннотированные тексты, включая литературу, научные статьи, СМИ

Источник: составлено автором на основе открытых источников.

1.2. Формальные языковые модели

Для описания и анализа структуры текстов на естественных языках используются формальные языковые модели.

Лексические модели.

Анализ текстов в рамках лексической модели сосредоточен на отдельных словах, называемых токенами. Лексические модели наиболее просты для построения и исследования и представляют особый интерес для систем распознавания речи. Однако применение данных моделей неэффективно при рассмотрении вопросов анализа текстов в задачах защиты информации. В том числе, для выходных текстов сообщений, преобразованных с помощью математических алгоритмов защиты, построение лексических моделей затруднительно из-за отсутствия у них смысловой структуры и высокой энтропии [80].

Модели на основе s-грамм.

На практике для описания текстов на естественном языке наиболее широко используются s-граммные языковые модели, в которых вероятность появления следующего элемента зависит только от фиксированного количества предыдущих элементов в последовательности. Вероятности появления s-грамм могут быть оценены путем подсчета их числа в языковом корпусе и последующей нормализации с помощью оценки максимального правдоподобия. Если численные оценки для s-граммовой модели языка определяются на основе того же корпуса, в котором они появляются, то такая оценка считается внутренней [26].

Существуют различные алгоритмы, которые используются для повышения точности определения вероятностей s-грамм и сглаживания покрытия корпуса. Эти алгоритмы основаны на подсчете ^-7 )-грамм, ^-2)-грамм и т.д. путем обратного отслеживания или интерполяции.

Проблема оценки вероятностей s-грамм заключается в том, что любой эмпирический текстовый материал ограничен и не включает в себя все допустимые s-граммы языка (отсутствующие в словаре допустимые s-граммы

называются внесловарными, или OOV). То есть возникает проблема оценки покрытия корпуса или словаря, связанная с определением относительной доли внесловарных элементов, то есть коэффициента ООУ. В некоторых задачах проблема элементов, отсутствующих в словаре, часто решается с помощью закрытых словарей, то есть существование ООУ s-грамм игнорируется.

Проблема оценки и оптимизации покрытия периодически рассматривается в различных подзадачах. Проблема покрытия словарей s-грамм часто возникает в машинном обучении и задачи машинного перевода. Методы увеличения покрытия словаря s-грамм, основанные на энтропии, предложены в [47], но этот подход требует наличия параллельной пары текстовых корпусов и неприменим в случае оценки покрытия корпуса в рамках внутренней модели языка.

Розенфельд в работе [50] установил, что оптимизация покрытия зависит от рассматриваемой проблемы. Во-первых, на покрытие влияет объем корпуса текстов, который используется для составления словарей. Но по мере увеличения объема корпуса эта зависимость становится менее выраженной и может быть экстраполирована для последующих объемов словарей [5]. Например, для английского языка рост объема словаря значительно замедляется, когда размер корпуса достигает 30 - 50 миллионов слов. Во-вторых, оптимальный размер корпуса зависит от источников и новизны данных [11]. В целом, корпус считается насыщенным, когда резкий рост новых слов прекращается с увеличением объема корпуса [50].

Марковские модели.

Марковские модели языка часто используются в качестве приближенных моделей естественного языка [12]. Как описано в [14], марковский процесс стационарен, то есть распределение вероятности s-грамм в момент времени t такое же, как распределение вероятности в момент времени t + 1. Однако любой естественный язык не является стационарным, поскольку вероятность следующих s-грамм может зависеть от событий, сколь угодно отдаленных от момента времени t. Кроме того, разные письменные источники на одном и том

же литературном языке обладают несколько разными уровнями энтропии, что говорит о том, что естественный язык неэргодичен. Как отметил Н. Хомский в [12], никакой марковский процесс с конечным числом состояний не является английской грамматикой2. Таким образом, эти статистические модели дают лишь приблизительное представление о правильных распределениях и энтропии естественного языка [26].

Список литературы диссертационного исследования кандидат наук Малашина Анастасия Геннадьевна, 2024 год

Источники:

1. Российские новостные ресурсы (РИА Новости, ТАСС, Коммерсантъ, Ведомости, Интерфакс, Лента.ру, РБК, Известия, Комсомольская правда, Аргументы и факты) - новости из раздела «Политика» (2016-2019 гг.).

2. «Литературная газета»14, статьи из раздела «Политика» (2017 г.).

3. Журнал «Политическое просвещение»15, статьи 2017 г.

4. Центральный комитет КПРФ16, новостные статьи 2017 г.

Корпус доступен на ресурсе:

https://github.com/Nastasian/entropy/releases/download/v2/Russian_political_new s_corpus.txt.

14 Литературная газета. Политика. URL: https ://lgz. ru/policv/ (дата обращения: 09.07.2024).

15 Политическая экспертиза: ПолитПрос. Журнал. URL: https://www.politpros.com/iournal/ (дата обращения: 09.07.2024).

16 Центральный комитет КПРФ. Новости ЦК КПРФ. URL: https://mkkprf.ru/novosti-ck-kprf/ (дата обращения: 09.07.2024).

Художественный корпус - коллекция значительных работ русской классической литературы, охватывающая несколько различных жанров. Корпус включает романы, пьесы, повести и рассказы, написанные с начала XIX века до середины XX века.

Язык - русский

Объем корпуса - 106 символов

Алфавит - 35 символов

Стиль - художественный

Жанр - романы, повести, рассказы и др.

Источники:

1. Михаил Булгаков - «Мастер и Маргарита».

2. Александр Грин «Алые паруса».

3. Михаил Булгаков - «Собачье сердце».

4. Максим Горький - «На дне».

5. Александр Куприн - «Гранатовый браслет».

6. Лев Толстой - «Анна Каренина».

7. Иван Тургенев - «Отцы и дети».

8. Александр Пушкин - «Евгений Онегин».

9. Александр Пушкин - «Капитанская дочка».

10. Михаил Шолохов - «Тихий Дон».

Корпус доступен на ресурсе:

https://github.com/Nastasian/entropy/releases/download/v2/Russian_literary.texts_ corpus.txt.

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

Язык - русский Объем корпуса - 107 символов Алфавит - 35 символов Стиль - смешанные:

- художественный - 15%

- публицистический - 30%

- научный - 28%

- официально-деловой - 13%

- разговорный - 14% Жанр - смешанные

Источник: «Открытый корпус русского языка».17 Корпус доступен на ресурсе:

https://github.com/Nastasian/entropy/releases/download/v2/Russian_common_cor pus.txt.

17 Открытый корпус русского языка. URL: https://www.opencorpora.org (дата обращения: 09.07.2024).

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

Язык - английский Объем корпуса - 108 символов Алфавит - 29 символов Стиль - смешанные Жанр - смешанные

Источник: iWeb Corpus.18 Корпус доступен на ресурсе:

https://github.com/Nastasian/entropy/releases/download/v2/English_corpus.txt.

18 iWeb Corpus. URL: https://www.english-corpora.org/iweb/ (дата обращения: 09.07.2024).

2. Объемы словарей s-грамм

На текстовом материале 106 символов:

Таблица 19 - Объемы словарей s-грамм для корпусов 106 символов

Длина s-граммы Русский язык Английский язык

Газетно-публицистический корпус Художественный корпус (литература XIX - XX вв.) Общеязыковой корпус (смешанные стили текстов) Общеязыковой корпус (тексты с вебстраниц)

10-граммы 692709 825718 795840 431200

15-граммы 889954 966090 955193 715392

20-граммы 941653 988741 983828 839360

25-граммы 958192 994923 990430 895440

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

На текстовом материале 107 символов:

Таблица 20 - Объемы словарей s-грамм для корпусов 107 символов

Длина s-граммы Русский язык Английский язык

Общеязыковой корпус (смешанные стили текстов) Художественный корпус (литература XIX - XX вв.) Общеязыковой корпус (тексты с веб-страниц)

10-граммы 5697498 5812584 4268660

15-граммы 8669757 9068897 7851607

20-граммы 9459865 9795919 8892532

25-граммы 9682256 9916028 9168804

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

На текстовом материале 108 символов:

Таблица 21 - Объемы словарей s-грамм для корпусов 108 символов

Длина s-граммы Английский язык

Общеязыковой корпус (тексты с веб-страниц)

10-граммы 22855480

15-граммы 62576310

20-граммы 80573533

25-граммы 85694340

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

3. Численные оценки покрытия словарей s-грамм

Описание тестовых образцов текстов, использованных для экспериментальной оценки покрытия:

1) Для газетно-публицистического корпуса русского языка: статья из газеты «Известия» от 08.05.2024 - «Майский наказ»19 (фрагмент - 10 тыс. символов).

2) Для художественного корпуса русского языка: Б. Л. Пастернак «Доктор Живаго» (отрывок произведения - 10 тыс. символов).

3) Для общеязыкового корпуса русского языка: текст из «Открытого корпуса русского языка» (фрагмент - 10 тыс. символов)20.

4) Для английского корпуса: статья из газеты «The Guardian» - «Girls do better in exams at all-girls schools than mixed, research finds» (фрагмент -10 тыс. символов)21.

На текстовом материале 106 символов:

Таблица 22 - Покрытие словарей s-грамм для газетно-публицистического корпуса русского языка_

Длина s-граммы Русский язык

Газетно-публицистический корпус

Модель 2.1 Модель 2.2 Эксперимент

10-граммы 16% 21% 28%

15-граммы 7% 8% 5,2%

20-граммы 4% 4% 0,74%

25-граммы 3% 3% 0,11%

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

19 URL: https://iz.ru/1693385/alena-nefedova-iana-shturma-marüa-kolobova/maiskü-nakaz-putin-nazval-glavnve-tceli-razvitiia-stranv (дата обращения: 08.05.2024)

20 URL: https://www.opencorpora.org (дата обращения: 08.05.2024)

21 URL: https://www.theguardian.com/education/article/2024/mav/12/girls-do-better-in-exams-at-all-girls-schools-than-mixed-research-finds (дата обращения: 12.05.2024)

Таблица 23 - Покрытие словарей s-грамм для художественного корпуса русского языка_

Длина s-граммы Русский язык

Художественный корпус (литература XIX - XX вв.)

Модель 2.1 Модель 2.2 Эксперимент

10-граммы 10% 11% 14%

15-граммы 2% 2% 1,5%

20-граммы 0,8% 1% 0,35%

25-граммы 0,5% 0,48% 0,14%

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

Таблица 24 - Покрытие словарей s-грамм для корпуса английского языка

Длина s-граммы Английский язык

Общеязыковой корпус (тексты с веб-страниц)

Модель 2.1 Модель 2.2 Эксперимент

10-граммы 31% 51% 25%

15-граммы 16% 20% 3,5%

20-граммы 10% 11% 0,7%

25-граммы 7% 8% 0,12%

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

На текстовом материале 107 символов:

Таблица 25 - Покрытие словарей s-грамм для общеязыкового корпуса русского языка _

Длина s-граммы Русский язык

Общеязыковой корпус (смешанные стили текстов)

Модель 2.1 Модель 2.2 Эксперимент

10-граммы 20% 30% 40%

15-граммы 7% 7% 12%

20-граммы 3% 3% 3%

25-граммы 2% 2% 0,8%

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

Таблица 26 - Покрытие словарей s-грамм для английского языка (корпус 107 символов)__

Длина s-граммы Английский язык

Общеязыковой корпус (тексты с веб-страниц)

Модель 2.1 Модель 2.2 Эксперимент

10-граммы 33% 57% 54%

15-граммы 16% 20% 12%

20-граммы 10% 11% 2,2%

25-граммы 8% 9% 0,38%

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

Таблица 27 - Покрытие словарей s-грамм для английского языка (корпус 108 символов)__

Длина s-граммы Английский язык

Общеязыковой корпус (тексты с веб-страниц)

Модель 2.1 Модель 2.2

10-граммы 51% 99%

15-граммы 32% 49%

20-граммы 21% 24%

25-граммы 16% 16%

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

4. Численные оценки энтропии s-грамм

На текстовом материале 106 символов:

Таблица 28 - Оценки энтропии s-грамм для русского газетно-публицистического корпуса_

Длина s-граммы Русский язык

Газетно-публицистический корпус

Энтропия, Я, (эксперимент) Энтропия Я® (с учетом покрытия Энтропия Я,2) (с учетом покрытия Энтропия //^эксп) (с учетом (эксп)ч покрытия )

10-граммы 1,94 2,20 2,17 2,12

15-граммы 1,31 1,57 1,55 1,59

20-граммы 0,99 1,22 1,22 1,34

25-граммы 0,79 0,99 0,99 1,18

50-граммы и более - 0,59 0,61 0,89

Источник: получено автором на основе созданных корпусов и расчётов моделей покрытия.

Таблица 29 - Оценки энтропии s-грамм для русского художественного корпуса _

Длина s-граммы Русский язык

Художественный корпус (литература XIX - XX вв.)

Энтропия, Н5 (эксперимент) Энтропия Я® (с учетом (-)л покрытия ) Энтропия Я® (с учетом покрытия .(2)) Энтропия Я(эксп) (с учетом покрытия т(эксп))

10-граммы 1,97 2,30 2,29 2,25

15-граммы 1,33 1,71 1,71 1,73

20-граммы 0,96 1,31 1,29 1,37

25-граммы 0,80 1,11 1,11 1,18

50-граммы и более - 0,81 0,84 0,97

Источник: получено автором на основе созданных корпусов и расчётов моделей покрытия.

Таблица 30 - Оценки энтропии s-грамм для русского общеязыкового корпуса

Длина s-граммы Русский язык

Общеязыковой корпус (смешанные стили текстов)

Энтропия, Н5 (эксперимент) Энтропия Н(1 (с учетом покрытия ) Энтропия Я® (с учетом покрытия т<2)) Энтропия Н(эксп) (с учетом покрытия т(эксп))

10-граммы 2,24 2,48 2,47 2,37

15-граммы 1,54 1,80 1,80 1,74

20-граммы 1,16 1,41 1,41 1,41

25-граммы 0,93 1,16 1,16 1,21

50-граммы и более - 0,78 0,79 0,91

Источник: получено автором на основе созданных корпусов и расчётов моделей покрытия.

Таблица 31 - Оценки энтропии s-грамм для английского корпуса объемом 107 символов

Длина s-граммы Английский язык

Общеязыковой корпус (тексты с веб-страниц)

Энтропия, Н5 (эксперимент) Энтропия Н(1) (с учетом (1) покрытия ) Энтропия Я® (с учетом покрытия Энтропия Н(эксп) (с учетом покрытия т(эксп))

10-граммы 2,19 2,35 2,27 2,28

15-граммы 1,52 1,70 1,67 1,72

20-граммы 1,15 1,29 1,31 1,43

25-граммы 0,92 1,04 1,06 1,24

50-граммы и более - 0,55 0,67 0,87

Источник: получено автором на основе созданных корпусов и расчётов моделей покрытия.

На текстовом материале 108 символов:

Таблица 32 - Оценки энтропии s-грамм для английского корпуса объемом 108 символов

Длина s-граммы Английский язык

Общеязыковой корпус (тексты с веб-страниц)

Энтропия, Н5 (эксперимент) Энтропия Я® ! (1)л (с учетом покрытия ) Энтропия Я® ! (2)\ (с учетом покрытия )

10-граммы 2,34 2,44 2,34

15-граммы 1,70 1,81 1,77

20-граммы 1,31 1,43 1,41

25-граммы 1,06 1,17 1,17

Источник: получено автором на основе созданных корпусов и расчётов моделей покрытия.

5. Теоретико-вероятностные модели появления выходных множеств

1. Дискретное равномерное распределение

Таблица 33 - Частоты появления выходных множеств мощностью k в

к Р; = Р(/г = £) к Р; = Р(/г = £)

1 0,035 19 0,034

2 0,027 20 0,026

3 0,037 21 0,025

4 0,029 22 0,025

5 0,035 23 0,030

6 0,034 24 0,023

7 0,019 25 0,027

8 0,037 26 0,040

9 0,025 27 0,027

10 0,028 28 0,018

11 0,027 29 0,030

12 0,040 30 0,028

13 0,021 31 0,030

14 0,023 32 0,036

15 0,032 33 0,020

16 0,030 34 0,031

17 0,023 35 0,022

18 0,026

Источник: экспериментально получено автором. 2. Полиномиальное распределение

Таблица 34 - Частоты появления выходных множеств мощностью k в сообщении на русском языке длиной 104 символов

к Р; = Р(/б = £) к Р; = Р(/б = £)

1 0 19 0,117

2 0 20 0,100

3 0 21 0,061

4 0 22 0,043

5 0 23 0,016

6 0 24 0,016

7 0,001 25 0,002

8 0,003 26 0,006

9 0 27 0

10 0,006 28 0,001

11 0,015 29 0

12 0,035 30 0

13 0,045 31 0

14 0,086 32 0

15 0,085 33 0

16 0,108 34 0

17 0,131 35 0

18 0,123

Источник: экспериментально получено автором.

3. Случай многократного применения ключа поточного преобразования

Таблица 35 - Экспериментальное исследование вероятностей совпадения символов в случае многократного применения ключа поточного

Кратность применения ключа М = 2 Кратность применения ключа М = 3 Кратность применения ключа М = 4 Кратность применения ключа М = 5

к Р(к = к) к Р(к = к) к Р(к = к) к Р(к = к)

1 0,053 1 0,107 1 0,165 1 0,192

- - - - - - 31 0,518

- - - - 32 0,706 32 0,262

- - 33 0,791 33 0,126 33 0,025

34 0,947 34 0,102 34 0,003 34 0,003

Источник: экспериментально получено автором.

6. Экспериментальные результаты восстановления подходящих s-грамм сообщения

В рамках заданной теоретико-вероятностной модели появления значений символов на выходе канала:

Группа экспериментов №1

Материал для словарей:

- газетно-публицистический корпус русского языка (106 символов)

- общеязыковой корпус английского языка (106 символов) Объемы словарей s-грамм: см. Таблица 19.

Сообщение: фрагмент исходного корпуса (104 символов) Вероятностное распределение на выходе: дискретное равномерное.

В данной группе экспериментов исследуется восстановление отдельных s-грамм сообщения длиной 104 символов на русском и английском языках. Используются словари s-грамм на материале 106 символов (см. Таблица 19). Сообщение является частью исходного корпуса словарей, поэтому в данной группе экспериментов, истинная s-грамма всегда присутствует в словарях.

Значение критической границы L менялось от 8 до 20 символов ^ увеличивалась, пока доля восстановленных s-грамм не приблизилась к 1). При рассмотрении L менее 8 символов не удалось найти L-ограниченные s-граммы в сообщении.

Таблица 36 - Доля восстановленных s-грамм (эксперимент №1) для русского языка

L Русский язык, т=35 (газетно-публицистический корпус)

5 = 10 5 = 15 5 = 20 5 = 25

8 0,019 0,012 0,004 0,001

12 0,049 0,163 0,139 0,116

16 0,053 0,483 0,761 0,808

18 0,053 0,492 0,914 0,961

20 0,053 0,492 0,928 0,990

Источник: экспериментально рассчитано автором для сообщения длиной 10 тыс. символов с помощью программной реализации алгоритма.

Таблица 37 - Доля восстановленных s-грамм (эксперимент №1) для английского языка

L Английский язык, т =29 (общеязыковой корпус)

5 = 10 5 = 15 5 = 20 5 = 25

12 0,050 0,226 0,570 0,630

16 0,050 0,239 0,829 0,974

Источник: экспериментально рассчитано автором для сообщения длиной 10 тыс. символов с помощью программной реализации алгоритма.

Таблица 38 - Экспериментальное восстановление подходящих s-грамм в рамках дискретной равномерной модели

Длина s- Общее Доля подходящих Вероятность Доля Граница допустимой Средняя

граммы количество s- s-грамм восстановления восстановленных s- многозначности многозначность

грамм подходящей s-граммы грамм восстановления s-граммы восстановления s-граммы

Критическая граница отбора Ь = 20

10-граммы 9991 0,913 0,058 0,053 2 1787

15-граммы 9986 0,960 0,513 0,492 3 137

20-граммы 9981 0,979 0,948 0,928 4 8

25-граммы 9976 0,990 1 0,990 6 1

Критическая граница отбора Ь = 16

10-граммы 9991 0,682 0,077 0,053 2 118

15-граммы 9986 0,728 0,665 0,484 3 5

20-граммы 9981 0,768 0,991 0,762 4 1

25-граммы 9976 0,809 1 0,809 6 1

Критическая граница отбора Ь = 12

10-граммы 9991 0,218 0,226 0,049 2 15

15-граммы 9986 0,173 0,946 0,164 3 1

20-граммы 9981 0,139 0,999 0,139 4 1

25-граммы 9976 0,117 1 0,117 6 1

Критическая граница отбора Ь = 8

10-граммы 9991 0,034 0,592 0,020 2 3

15-граммы 9986 0,013 0,992 0,013 3 1

20-граммы 9981 0,004 1 0,004 4 1

25-граммы 9976 0,001 1 0,001 6 1

Источник: экспериментально рассчитано автором для сообщения длиной 10 тыс. символов с помощью программной реализации алгоритма.

Группа экспериментов №2

Материал для словарей:

- газетно-публицистический корпус русского языка (106 символов)

- общеязыковой корпус английского языка (106 символов) Объемы словарей s-грамм: см. Таблица 19.

Сообщение: произвольный текст не из исходного корпуса (104 символов) Вероятностное распределение на выходе: дискретное равномерное.

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

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

Описание текстов сообщений, используемых для экспериментального исследования:

1) Для русского языка: статья из газеты «Известия» от 08.05.2024 -«Майский наказ»22 (фрагмент - 104 символов).

2) Для английского корпуса: статья из газеты «The Guardian» - «Girls do better in exams at all-girls schools than mixed, research finds» (фрагмент -104 символов)23.

Таблица 39 - Доля восстановленных s-грамм (эксперимент №2) для русского языка

L Русский язык, m=35 (газетно-публицистический корпус)

s = 10 s = 15 s = 20 s = 25

12 0,024 0,028 0,021 0,011

16 0,049 0,168 0,101 0,050

Источник: экспериментально рассчитано автором для сообщения длиной 10 тыс. символов с помощью программной реализации алгоритма.

22 URL: https://iz.ru/1693385/alena-nefedova-iana-shturma-marüa-kolobova/maiskü-nakaz-putin-nazval-glavnve-tceli-razvitiia-stranv (дата обращения: 08.05.2024)

23 URL: https://www.theguardian.com/education/article/2024/mav/12/girls-do-better-in-exams-at-all-girls-schools-than-mixed-research-finds (дата обращения: 12.05.2024)

Таблица 40 - Доля восстановленных s-грамм (эксперимент №2) для английского языка

L Английский язык, т=29 (общеязыковой корпус)

5 = 10 5 = 15 5 = 20 5 = 25

12 0,02 0,13 0,04 0,002

16 0,02 0,16 0,17 0,03

Источник: экспериментально рассчитано автором для сообщения длиной 10 тыс. символов с помощью программной реализации алгоритма.

Группа экспериментов №3

Материал для словарей:

- газетно-публицистический корпус русского языка (106 символов)

- общеязыковой корпус английского языка (106 символов) Объемы словарей s-грамм: см. Таблица 19.

Сообщение: фрагмент исходного корпуса (104 символов) Вероятностное распределение на выходе: полиномиальное.

В данной группе экспериментов исследуется восстановление отдельных s-грамм сообщения длиной 104 символов на русском и английском языках. Используются словари s-грамм на материале 106 символов (см. Таблица 19). Сообщение является частью исходного корпуса словарей, поэтому в данной группе экспериментов, истинная s-грамма всегда присутствует в словарях.

Таблица 41 - Экспериментальное восстановление подходящих s-грамм в рамках полиномиальной модели

Длина s-граммы Общее количество s-грамм Доля подходящих s-грамм Вероятность восстановления подходящей s-граммы Доля восстановленных s-грамм Граница допустимой многозначности восстановления s-граммы Средняя многозначность восстановления s-граммы

Критическая граница отбора Ь = 20

10-граммы 9991 0,991 0 0 2 1507

15-граммы 9986 0,998 0,0401 0,0401 3 91

20-граммы 9981 0,999 0,9012 0,9004 4 5

25-граммы 9976 1 1 1 6 1

Критическая граница отбора Ь = 16

10-граммы 9991 0,100 0 0 2 283

15-граммы 9986 0,057 0,2028 0,0116 3 9

20-граммы 9981 0,033 0,997 0,0333 4 1

25-граммы 9976 0,017 1 0,0165 6 1

Критическая граница отбора Ь = 12

10-граммы 9991 0 - - 2 -

15-граммы 9986 0 - - 3 -

20-граммы 9981 0 - - 4 -

25-граммы 9976 0 - - 6 -

Критическая граница отбора Ь = 8

10-граммы 9991 0 - - 2 -

15-граммы 9986 0 - - 3 -

20-граммы 9981 0 - - 4 -

25-граммы 9976 0 - - 6 -

Источник: экспериментально рассчитано автором для сообщения длиной 10 тыс. символов с помощью программной реализации алгоритма.

В случаях многократного применения ключа поточного преобразования: Группа экспериментов №4

Сообщения: тексты из газетно-публицистического корпуса русского языка и общеязыкового корпуса английского языка длиной 105 символов.

В данной группе экспериментов исследуется вероятность совпадения символов неизвестного сообщения с одним из символов известного, то есть вероятность р = Р(17 = 1). Для этого тексты нескольких сообщений одинаковой длины посимвольно сопоставляются.

Таблица 42 - Вероятность совпадения символов сообщения при повторном использовании ключа

Кратность использования ключа Вероятность совпадения символов, р

Русский язык Английский язык

2-кратное 0,06 0,07

3-кратное 0,12 0,14

4-кратное 0,18 0,21

5-кратное 0,23 0,27

Источник: экспериментально рассчитано автором на основе сообщений длиной 100 тыс. символов.

Группа экспериментов №5

Материал для словарей:

- газетно-публицистического корпуса русского языка (106 символов) Объемы словарей s-грамм: см. Таблица 19. Сообщение: фрагмент исходного корпуса (103 символов)

В данной группе экспериментов исследуется восстановление отдельных s-грамм сообщения длиной 103 символов на русском языке в случае многократного применения ключа поточного преобразования. Восстанавливаемое сообщение является частью исходного корпуса словарей (истинная s-грамма всегда присутствует в словарях).

Таблица 43 - Доля восстановленных s-грамм при многократном применении ключа

Длина s- Кратность Русский

граммы повтора L = 12 L = 16

2 - -

10 3 0,0020 0,0020

4 0,0121 0,0121

5 0,0595 0,0595

2 - -

15 3 0,0051 0,0162

4 0,0446 0,0720

5 0,1886 0,2769

2 - 0,0001

20 3 0,0041 0,0428

4 0,0326 0,1927

5 0,2630 0,5780

2 - 0,0001

25 3 0,0072 0,0482

4 0,0410 0,2213

5 0,1732 0,6557

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

7. Проверка адекватности применения модели 4.1 в случае конечного 5

Для ряда вероятностных распределений (например, равномерного) сумма независимых величин сближается с нормальным законом быстрее, чем подсказывает теоретическая оценка Берри-Эссена даже при «средних» значениях 5* (десятки) [68]. Поэтому при суммировании, например, равномерно распределенных случайных величин уже при 6-10 слагаемых удается добиться достаточной для практических целей близости к нормальному закону [61].

Для проверки адекватности модели 4.1 проводится сравнение результатов моделирования с экспериментальными результатами по отбору подходящих (Ь-ограниченных) s-грамм, полученными при одинаковых условиях. Рассматривается сообщение длиной 105 символов на русском языке. В качестве теоретико-вероятностного распределения на выходе канала связи рассматривается дискретное равномерное распределение, то есть рк = Р(17 = к) = \; VI = 1, ...,103; к = 1,... ,т; где т=35. Для всех 25-грамм посчитываются их среднегеометрические значения и строится эмпирическая

функция распределения по частоте попадания значений в интервалы (построено 17 интервалов согласно правилу Стёрджеса [68]).

Рисунок 18 - Эмпирическая функция распределения вероятностей появления

¿-ограниченных s-грамм Источник: экспериментально рассчитано автором.

Для оценки близости реального распределения к нормальному используется расстояние Колмогорова (статистика Колмогорова-Смирнова [68]):

D = max IF(x) - Ф(х) I,

X

где F(x) — эмпирическая функция распределения.

Максимальное отклонение теоретически нормальной и эмпирической вероятностей попадания в заданный интервал составило D = 0,012. Такая малая величина отклонения (погрешности) позволяет использовать данную модель аппроксимации для оценки вероятности появления ¿-ограниченной s-граммы в сообщении в практических целях в случае конечного s.

8. Некоторые численные расчеты введенных моделей аппроксимации

Приведем некоторые численные расчеты построенных моделей при рассмотрении. Для этого воспользуемся полученными оценками энтропии s-грамм, учитывающими неполноту покрытия экспериментальных словарей (см. Таблица 30 и Таблица 31). Кроме того, введем предположение, что истинный вариант восстановления s-граммы всегда присутствует в словаре.

В рамках заданной теоретико-вероятностной модели появления значений символов на выходе канала:

Таблица 44 - Оценка доли восстановленных Б-грамм

ь Русский язык Английский язык

5 = 10 5 = 15 5 = 20 5 = 25 5 = 10 5 = 15 5 = 20 5 = 25

<8 0,014 0,006 0,002 0,001 0,004 0,038 0,021 0,117

<10 0,016 0,065 0,041 0,027 0,004 0,070 0,203 0,177

<12 0,016 0,213 0,219 0,193 0,004 0,070 0,559 0,566