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

1. Определение языка сообщения

В "живых" языках буквы встречаются с разной частотой, другими словами, можно построить диаграммы распределения частот символов, характерные для каждого языка. Производится так называемая частотная селекция, текст сообщения анализируется как поток символов и высчитывается частота встречаемости (вес) каждого символа. Иногда таблицу для удобства нормализуют: "веса" делят на общее количество символов в обработанном сообщении. При анализе можно абстрагироваться от букв и их семантической нагрузки, взяв только номера символов и рассчитывая таблицу частот по номерам. Это позволит обойти наличие нескольких, временами несовместимых кодировок. Для принятия решения полученная таблица распределения сравнивается с эталонными таблицами, и по близости к тому или иному распределению делается предположительный вывод о языке сообщения. Для анализа минимальная длина текста должна равняться длине трех алфавитов, что для русского языка будет, соответственно, около сотни символов.

2. Взлом шифров

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

Для взлома более сложных шифров анализ усложняется. Рассматривается предыстория символа, то есть зависимость частоты появления от предыстории. Анализируются цепочки символов, по два символа (биграмма), по три (триграмма) и т.д. Для анализа биграмм вычисляется вероятность Pij появления символа j при условии, что перед ним находится знак i. Это также носит название марковости первого порядка - по фамилии петербургского математика XIX века, предложившего этот метод анализа. Анализ биграмм позволяет вскрыть табличные шифры перестановки, в частности, построенные на решетках Кардана. Решетки Кардана использовались большевиками для закрытия сообщений при переписке. Но будущим создателям "пролетарской геометрии" было невдомек, что жандармский криптоаналитик Фетти вскрывал сообщения за полчаса "на бумажке", восстанавливая расположение недостающих ячеек решетки, используя инструмент анализа биграмм.

Далее возможно усложнение анализа путем увеличения "марковости" до 5-го или 6-го порядков и далее и учета более глубокой зависимости предыстории появления символа от предшествовавших ему букв. Тексты "живых" языков имеют неравномерное распределение символов в сообщении и явно выраженные пики в марковских матрицах. Это является базисом для построения математической модели в системах распознавания осмысленности текстовых сообщений, другими словами, отбрасывания откровенного "словесного мусора" из потока текстовых сообщений. Система выдает результат в виде: "осмысленный"/"неосмысленный" текст.

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

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

3. Установление авторства

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

4. Построение роботов-поисковиков и снифферов

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

5. Построение роботов-автоответчиков

Имея готовую матрицу рассчитанных марковостей с порядком, как минимум, выше пятого, можно построить подобие автоответчика. Генерируется псевдослучайная последовательность с большим периодом, например, используя математический аппарат конечных полей Галуа. С помощью случайной последовательности матрица марковостей "обращается вспять", то есть, используя значение "выброшенного" последовательностью случайного числа, статистический вес (вероятность появления того или иного символа, взятого из матрицы) и предысторию символа, высчитывается следующий символ сообщения. Такое случайное моделирование на выходе выдает осмысленный текст. Уже вполне осмысленный текст получается при обращении марковости четвертого порядка. Среднее количество символов в словах русского языка равно восьми, и марковости шестого порядка вполне достаточно для генерации осмысленного текста. Для построения программного робота, способного к диалогу, нужно усложнить анализ введением расчета корреляций (или зависимостей, выражаясь бытовым языком). Производится расчет корреляций в зависимости от отклика человека на задаваемые ему фразы. Или берется литературное произведение, изобилующее диалогами, и рассчитываются корреляции в потоках сообщений "вопрос - ответ". Программный робот "обучается" диалогу. Это можно применить для эмуляции присутствия в html-чате, irc-цепях или ICQ. Так что следует критически отнестись к тому, что собеседник выдает осмысленные, но бестолковые ответы: возможно, вы разговариваете с хорошо построенным роботом. Или повторить вопрос, заданный собеседнику. Программа обычно "зацикливается" и начинает "как попугай" повторять одно и то же на один и тот же вопрос.

Black Prince,
www.geocities.com/SiliconValley/Way/5801