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

Недавно итальянские ученые Дарио Бенедетто, Эмануэле Кальоти и Витторио Лорето из Римского университета La Sapienza задались несколько необычными вопросами. В частности, можно ли автоматически определить язык, на котором написан некоторый текст, автоматически угадать автора этого текста, определить тему и на этой основе автоматически классифицировать текст в некотором корпусе текстов и т.п.? И для рассмотренного класса задач лингвистического анализа их ответ был однозначно положителен, о чем и было сообщено в недавнем выпуске журнала Physical Review Letters (28 января 2002).

Их главная идея заключалась в том, чтобы использовать для текстуального анализа теорию информации и, в частности, понятие энтропии, связанное с проблемой эффективного кодирования. Как было показано еще Шенноном в 1948 г., кодирование данной последовательности имеет предел, и им как раз и является энтропия этой последовательности. Последнюю итальянские ученые определяют по Чайтину-Колмогорову как длину (в битах) наименьшей программы, исполнение которой имеет своим результатом данную последовательность знаков. Как показали авторы, алгоритмы для достижения трудно определимого в общем случае теоретического предела давно существуют и реализуются они в хорошо всем знакомых программах сжатия файлов или архиваторах.

Одним из первых был разработан алгоритм сжатия Лемпеля-Зива (Lempel and Ziv algorithm или LZ77), используемый, например, в архиваторах gzip, zip и Stacker. Принцип архивирования, если не входить в детали, заключается в том, что частые последовательности символов кодируются несколькими байтами, тогда как для кодировки более редких серий требуется большее количество байтов. Оказывается, что алгоритм имеет одно замечательное свойство - "если кодируется последовательность длиной L, производимая эргодическим источником¹ с удельной энтропией s, т.е. энтропией на один символ, то длина архивированного файла, поделенная на длину исходного файла, стремится к s, когда длина текста стремится к . Т.е. архивирование тем эффективнее, чем больше длина сжимаемого текста. Сами же алгоритмы архивирования могут, таким образом, использоваться для определения меры энтропии текста.

Именно этот метод используется в статье для определения "удаленности" между парой последовательностей знаков на основе определения относительной энтропии двух эргодических источников. В лингвистических терминах относительная энтропия оказывается мерой трудности для носителя языка А понять текст на языке В. Авторы провели экспериментальное архивирование достаточно большого английского текста с добавкой небольшого текста на итальянском языке и получили замечательное совпадение экспериментальных результатов с теоретическими предсказаниями.

Для автоматического распознавания языка, на котором написан некоторый текст, ученые брали достаточно большой массив текстов на самых разных языках и делали в них небольшие добавки из текста на определяемом языке. Упомянутым выше способом измерялись относительные энтропии разных текстов. Минимальному значению соответствовал язык, наиболее близкий или совпадающий с распознаваемым. Для текстов на 10 языках Евросоюза достигалось 100% автоматическое определение искомого языка при длине текстовых добавок на нем, по крайней мере, в 20 символов.

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

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

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

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

Сергей САНЬКО

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