Как при научном исследовании, так и в реальной жизни постоянно приходится иметь дело с последовательностями некоторых знаков (или символов). Самый близкий для всех людей случай - это язык и продуцируемые в его стихии тексты. Но лингвистическую (семиотическую) природу имеют и другие, не менее важные, серии знаков. Например, последовательность оснований молекул ДНК, РНК или протеиновые серии. Еще пример - серии показаний какого-то прибора, записываемые через определенные промежутки времени. Во всех таких случаях главное - умение выделять информацию, которую такие последовательности кодируют.
Недавно итальянские ученые Дарио Бенедетто, Эмануэле Кальоти и Витторио Лорето из Римского университета La Sapienza задались несколько необычными вопросами. В частности, можно ли автоматически определить язык, на котором написан некоторый текст, автоматически угадать автора этого текста, определить тему и на этой основе автоматически классифицировать текст в некотором корпусе текстов и т.п.? И для рассмотренного класса задач лингвистического анализа их ответ был однозначно положителен, о чем и было сообщено в недавнем выпуске журнала Physical Review Letters (28 января 2002).
Их главная идея заключалась в том, чтобы использовать для текстуального анализа теорию информации и, в частности, понятие энтропии, связанное с проблемой эффективного кодирования. Как было показано еще Шенноном в 1948 г., кодирование данной последовательности имеет предел, и им как раз и является энтропия этой последовательности. Последнюю итальянские ученые определяют по Чайтину-Колмогорову как длину (в битах) наименьшей программы, исполнение которой имеет своим результатом данную последовательность знаков. Как показали авторы, алгоритмы для достижения трудно определимого в общем случае теоретического предела давно существуют и реализуются они в хорошо всем знакомых программах сжатия файлов или архиваторах.
Одним из первых был разработан
алгоритм сжатия Лемпеля-Зива (Lempel and
Ziv algorithm или LZ77), используемый,
например, в архиваторах gzip, zip и Stacker.
Принцип архивирования, если не
входить в детали, заключается в том,
что частые последовательности
символов кодируются несколькими
байтами, тогда как для кодировки
более редких серий требуется
большее количество байтов.
Оказывается, что алгоритм имеет
одно замечательное свойство -
"если кодируется
последовательность длиной L,
производимая эргодическим
источником1 с удельной
энтропией s, т.е. энтропией на один
символ, то длина архивированного
файла, поделенная на длину
исходного файла, стремится к s,
когда длина текста стремится к . Т.е.
архивирование тем эффективнее, чем
больше длина сжимаемого текста.
Сами же алгоритмы архивирования
могут, таким образом,
использоваться для определения
меры энтропии текста.
Именно этот метод используется в статье для определения "удаленности" между парой последовательностей знаков на основе определения относительной энтропии двух эргодических источников. В лингвистических терминах относительная энтропия оказывается мерой трудности для носителя языка А понять текст на языке В. Авторы провели экспериментальное архивирование достаточно большого английского текста с добавкой небольшого текста на итальянском языке и получили замечательное совпадение экспериментальных результатов с теоретическими предсказаниями.
Для автоматического распознавания языка, на котором написан некоторый текст, ученые брали достаточно большой массив текстов на самых разных языках и делали в них небольшие добавки из текста на определяемом языке. Упомянутым выше способом измерялись относительные энтропии разных текстов. Минимальному значению соответствовал язык, наиболее близкий или совпадающий с распознаваемым. Для текстов на 10 языках Евросоюза достигалось 100% автоматическое определение искомого языка при длине текстовых добавок на нем, по крайней мере, в 20 символов.
Определение авторства проводится по той же методике, только теперь в качестве опорного выступает как можно большая коллекция текстов разных авторов, написанных на том же языке, что и исследуемый текст. В этом случае была достигнута степень распознаваемости 93,3%, хотя наблюдались некоторые флуктуации, связанные с такими трудно определимыми характеристиками текста, как авторский стиль.
Несколько усложнив процедуру, авторы проанализировали один текст на 50 различных языках. Это была "Всеобщая декларация прав человека". В результате было построено дерево "родства" языков разных языковых семей, которое отлично соответствовало как интуитивным представлениям, так и общепринятым лингвистическим классификациям.
Как отмечают авторы, предложенный ими метод имеет высокую степень общности и позволяет анализировать любые кодовые последовательности без предварительного знания алфавита, грамматики, синтаксиса и даже статистики. Так, метод вполне применим не только в лингвистике, но и в теории динамических систем, генетике и других отраслях, где применим текстуальный анализ.
Вот, оказывается, что можно сделать с помощью всем привычных архиваторов файлов. Это не просто удобные утилиты, но еще и мощный аналитический инструмент.
Сергей САНЬКО
1 Для эргодических систем усреднение по фазовому пространству может быть заменено усреднением по времени.
![Версия для печати Версия для печати](https://www.kv.by/sites/all/modules/print/icons/print_icon.png)
Комментарии