Содержание

Применение частотных характеристик текстов
Исследование Методика исследования
Материалы
Результаты Технический текст
Литературный текст (произведения А. С. Пушкина)
Текст из рефератов студентов
Выводы
Литература
 

Применение частотных характеристик текстов

Во многих случаях возникает потребность выявить частотные характеристики того или иного текста. Такие данные встречаются в литературе (например [4]), но в основном для английского языка.

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

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

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

Другая часть работы повещена оценки энтропии источника сообщений на один знак. Данный параметр, также зависящий от конкретного источника, определяется как , где n - длина текста, c - открытый текст. Энтропия на 1 знак используется при оценки расстояния единственности, по Шеннону определяющейся как , L - мощность алфавита открытого текста. Данная оценка была уточнена в работе [2]:

 

Исследование

Методика исследования

Методику исследования выберем, исходя из следующих соображений.
  1. Желательно провести анализ текстов по частоте встречаемости букв, так как для русского языка мало опубликованных данных такого рода.
  2. Для расчёта энтропии источника на 1 знак используем сообщения длины 2, то есть биграммы, так как их число невелико и вычислительно несложно осуществлять обработру полученных объёмов данных.
  3. Подберём исследуемые тексты размером 200-300 Кб для того, чтобы хватило статистического материала.

Материалы

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

Первый источник представлял собой файл, созданный путём слияния нескольких файлов, содержавших текст технического характера, а именно документацию фирмы Microsoft на её программный продукт - операционную систему MS Windows 95 OSR2 RUS. Размер файла 257539 байт, вероятно, позволил набрать необходимый статистический материал.

Второй источник представлял собой файл, также созданный путём слияния нескольких файлов, содержавших текст произведений А. С. Пушкина, полученных из сети Интернет из Публичной электронной библиотеки (библиотеки Евгения Пескина). Размер файла составил 258329 байт, однако данный источник имел существенный недостаток - все буквы Ъ были заменены на букву Ь, что не могло не сказаться на результате.

Третий источник был составлен из 15 рефератов студентов различных ВУЗов на нетехнические темы. Все рефераты были написаны в 1992-1995-х годах студентами 1-го - 4-го курсов. Длина файла составила 333177 байт, что дало самый богатый материал для статистики из всех рассмотренных.

Результаты

Ниже приводятся полученные результаты для всех исследованных текстов.

    Технический текст

При анализе технического текста получены следующие результаты:
  1. Энтропия источника на 1 знак составляет 3,841465бита на знак при подсчёте для биграмм.
  2. Частоты встречаемости букв приводятся в нижеследующей таблице:
Таблица 1
Буква
Частота встречаемости
Буква
Частота встречаемости
[Ъ]
0,000299143315436310000
[Я]
0,015256309087251800000
[Ц]
0,002145579641750090000
[У]
0,022152078272395700000
[Э]
0,002300308942837830000
[Д]
0,026546390423287700000
[Ш]
0,002589136971534960000
[М]
0,027469608586444600000
[Ф]
0,003625823288822870000
[Л]
0,029919489187000600000
[Щ]
0,004182848772738760000
[К]
0,030239263075915300000
[Х]
0,004806923620459330000
[П]
0,032993444635277200000
[Ж]
0,007860248495257540000
[В]
0,035479428739420300000
[Ю]
0,008071711873410800000
[С]
0,040420451087489100000
[Г]
0,008319278755151190000
[Р]
0,045949444779691200000
[Ч]
0,009407541506135010000
[Н]
0,048992454367750200000
[Б]
0,011429337707014900000
[Т]
0,054913428956041400000
[Й]
0,012466024024302800000
[И]
0,057739817522577500000
[З]
0,013342823397133300000
[А]
0,062881987962060300000
[Ь]
0,013812168943766200000
[Е]
0,073223062918091400000
[Ы]
0,014255726273551000000
[О]
0,076364067730172700000
[ ]
0,200544647139828000000

    Литературный текст (произведения А. С. Пушкина)

При анализе текста произведений А. С. Пушкина получены следующие результаты:
  1. Энтропия источника на 1 знак составляет 4,0321685 бита на знак при подсчёте для биграмм. Однако необходимо учитывать, что это не оригинальный текст, а полученный по каналам сети интернет, что накладываёт свой отпечаток: например все буквы Ъ заменены на Ь ввиду особенностей источника, что не могло не исказить результат.
  2. Частоты встречаемости букв приводятся в нижеследующей таблице:
Таблица 2
Буква
Частота встречаемости
Буква
Частота встречаемости
[Ъ]
0,000000000000000000000
[Ы]
0,019874807867946800000
[Э]
0,000788576774854647000
[П]
0,021371767169365700000
[Ф]
0,000819763426967543000
[К]
0,024307767703994100000
[Щ]
0,001715265866209260000
[У]
0,024984963578445500000
[Ц]
0,003087478559176670000
[М]
0,028085807845670600000
[Ю]
0,006023479093804990000
[Д]
0,029734245171637900000
[Ш]
0,006892250116949940000
[Р]
0,037553184379942500000
[Х]
0,008781270187788190000
[В]
0,037878416609119800000
[Ж]
0,009480742242320280000
[Л]
0,040413445902296600000
[Ч]
0,011075716736094000000
[С]
0,042289100265086500000
[З]
0,014399322804125500000
[Т]
0,047443808335746500000
[Б]
0,014448330400302900000
[И]
0,050727317279632800000
[Г]
0,015628967944576800000
[Н]
0,059633334075872600000
[Я]
0,016466552315608900000
[А]
0,060894165868436800000
[Ь]
0,017696197456060200000
[Е]
0,071203582009756900000
[Й]
0,018270922902140700000
[О]
0,080180882582254700000
[ ]
0,177848566527811000000

    Текст из рефератов студентов

Также анализировался текст, полученный слиянием 15 рефератов на нетехнические темы.
  1. Энтропия источника на 1 знак составляет 3,794777 бита на знак при подсчёте для биграмм.
  2. Частоты встречаемости букв приводятся в нижеследующей таблице:
Таблица 3
Буква
Частота встречаемости
Буква
Частота встречаемости
[Ъ]
0,00039109527080796800
[ ]
0,015038463369676800000
[Ф]
0,00234317079640600000
[Я]
0,015082674139420300000
[Э]
0,00261183624330887000
[У]
0,017500663161546100000
[Щ]
0,00305394394074396000
[П]
0,020870884147378200000
[Ш]
0,00378172122729096000
[Д]
0,022853567128952600000
[Ц]
0,00419322146874978000
[М]
0,024275113417628500000
[Ю]
0,00505703189296912000
[К]
0,026791726464566700000
[Ж]
0,00714514055623950000
[Л]
0,029100888976554600000
[Х]
0,00788652115655373000
[В]
0,037120042442338900000
[Й]
0,00891017051753807000
[Р]
0,040629697394285200000
[Ч]
0,01038953088972470000
[С]
0,042316508301422200000
[Ь]
0,01088605184222870000
[Т]
0,048278160559912300000
[З]
0,01141998190759260000
[Н]
0,052665229249845200000
[Б]
0,01178727137930800000
[А]
0,055130829870156300000
[Г]
0,01275990831366520000
[И]
0,060922440706556100000
[Ы]
0,01483441366316830000
[Е]
0,068230821028002400000
[О]
0,082864585813104000000

Выводы

По результатам проведённого исследования можно сделать следующие выводы:

Литература

  1. Hellman, M. E. , An extension of the Shannon Theory Approach to Cryptography, IEEE Transactions, on Information Theory, vol. IT-23, 1977, pp 289-294.
  2. P Beauchemin and G Brassard. A Generalization of Hellman?s Extension to Shannon?s Approach to Cryptography.
  3. У. Узерелл. Этюды для программистов. Москва, ?Мир?, 1982г.
  4. А. А. Варфоломеев, В. М. Фомичёв. Информационная безопасность. Методические основы криптологии. Москва, ?МИФИ?, 1995г.