В статье рассматривается метод автоматического определения языка текста, основанный на относительной энтропии языка и анализе кодировки текста.
В настоящее время проблема автоматического определения языка текстовых документов являет-ся весьма актуальной для задач, связанных с обработкой больших объемов информации. Например, в системах тематического сбора информации в Интернет необходимо проводить автоматическую фильтрацию (классификацию) входного потока документов, которые могут быть представлены на самых разных языках.
Для решения данной проблемы могут использоваться различные лингвистические, математиче-ские (статистические) методы или системы искусственного интеллекта. В данной статье рассматри-вается алгоритм автоматического определения языка текста, использующий смешанный подход, сочетающий методы инженерного анализа с относительной энтропией языка текста.
Энтропию языка текста можно определить как численную меру гибкости языка, которая отра-жает количество возможных вариантов текста с учётом вероятностей этих вариантов [1]. Согласно А. Н. Колмогорову, энтропия любого языка складывается из двух величин: смысловой емкости, т. е. способности языка передать некоторую смысловую информацию в тексте определенной длины, и гибкости языка, т. е. возможности одну и ту же информацию передать несколькими различными способами. Понятно, что для научно технических и художественных текстов в рамках одного языка эти составляющие будут различны.
А. Н. Колмогоров ввел определение энтропии через понятие относительной сложности. «Отно-сительной сложностью объекта y при заданном x будем считать минимальную длину l(p) програм-мы p для получения y из x» [2]. Применительно к текстовой информации можно сказать, что слож-ность текста А определяется длиной (в двоичном алфавите) минимальной программы, которая вы-водит A, а энтропия A – это её сложность, делённая на длину A в битах. Конечно, вычислить энтро-пию произвольного текста через относительную сложность (по Колмогорову) практически невоз-можно. В то же время существует целый класс программ, которые «получают» текст y из x – это программы архиваторы. Текст, сжатый, например, программой zip, является, по сути, некоторой программой, которая интерпретируется программой unzip таким образом, что на выходе получается исходный текст.
Если теперь принять, что размер сжатого текста характеризует его энтропию, то можно вычис-лить энтропию текста А по отношению к тексту В, или относительную энтропию H(В|А) [3]. Для этого необходимо сжать текст A и определить длину L(A) получившегося архива, а затем сжать конкатенацию текстов A и B и для этого архива определить длину L(A+B). Тогда оценить относи-тельную энтропию текстов А и В можно по формуле:
H(B | A) = L(A+B) – L(В).
Рассмотрим вкратце принцип работы программ архиваторов на примере популярного алгоритма сжатия LZ77 (Лемпеля Зива).
Общий принцип архивирования заключается в кодировании частых последовательностей сим-волов наименьшим количеством байт, а редких последовательностей – большим. Основу алгоритма LZ77 составляет так называемое «скользящее окно» фиксированного размера, которое представля-ет собой ранее обработанные данные. Окно размером N байт, по сути, является N байтами инфор-мации от текущей позиции сжатия обратно к началу потока. По ходу процесса сжатия ок-но перемещается («скользит») вслед за указателем текущей позиции в сжимаемом потоке данных. Принцип кодирования заключатся в том, что алгоритм ищет наибольшее совпадение следующих обрабатываемых данных с данными в скользящем окне. При нахождении таковых в выходной поток добавляется не сама последовательность символов, а ее смещение от начала буфера и количество совпавших символов. В случае если хотя бы один символ обрабатываемой последовательности не найден в окне, в выходной поток добавляется код первого несовпавшего символа. В этом случае смещение и количество символов будут записаны как последовательность 0:0, после которой следу-ет код ненайденного символа. На подобном принципе построены и другие алгоритмы сжатия тек-ста.
Анализ принципов работы алгоритмов сжатия показывает, что чем больше в сжимаемом тексте повторяющихся последовательностей символов, тем меньше будет длина архивированного файла. И, соответственно, значение относительной энтропии текстов А и В будет тем меньше, чем более «похожи» эти тексты в смысле последовательностей символов. Понятно, что относительная энтро-пия двух текстов на одном языке будет меньше относительной энтропии текстов на разных языках, поскольку в любом языке имеется характерный для этого языка набор символов и их сочетаний.
Впервые на это свойство сжатых текстов обратили внимание итальянские ученые Д. Бенедетто, Э. Кальоти и В. Лорето. Они провели ряд экспериментов и установили, что с помощью обычных программ архиваторов можно успешно проводить анализ текстов для целого класса лингвистиче-ских задач, таких как определение языка, авторства или тематики документов [4].
Теперь рассмотрим, каким образом можно практически реализовать задачу автоматического оп-ределения языка на основе понятия относительной энтропии. В первую очередь, необходимо соз-дать набор текстов образцов на всех языках, предполагаемых для анализа. Данные тексты должны быть преобразованы к набору символов Unicode. Каждый символ в таком представлении определя-ется двумя байтами и позволяет кодировать до 65 000 различных символов. В набор Unicode в на-стоящее время входят наборы символов национальных алфавитов для представления текстов на большинстве наиболее распространенных языков.
От качества текстов образцов во многом зависит точность определения языка. Данные тексты должны содержать по возможности полный набор символов языка, а также наиболее распростра-ненные в этом языке частицы, предлоги и т. д. Кроме этого, точность зависит от длины тек-стов образцов и длины определяемого текста. Очевидно, что чем больше будут длины тек-стов образцов, тем выше будет вероятность определения, но тем больше будет время определения. С другой стороны, если брать относительно небольшие фрагменты текстов, то алгоритм будет рабо-тать достаточно быстро, но в этом случае уменьшается вероятность правильного определения язы-ка. При этом, как правило, длина определяемого текста намного меньше длины текста образца.
Таким образом, для автоматического определения языка входного текста Т относительно набора текстов образцов Si (i = 1….n) необходимо выполнить следующее:
1. Преобразовать текст Т в кодировку Unicode.
2. Для каждого Si определить его относительную энтропию с текстом Т.
3. Найти Si, для которого относительная энтропия с Т минимальна. Язык данного текста образца будет соответствовать языку документа Т.
Количество операций в данном алгоритме можно сократить, а быстродействие повысить, если заранее вычислить и сохранить размеры сжатых текстов образцов.
Очевидно, что при большом количестве потенциально возможных языков время работы данного алгоритма будет достаточно большим, поскольку алгоритм предполагает последовательную конка-тенацию входного текста с каждым текстом образцом.
Для увеличения производительности алгоритма предлагается использовать следующее инженер-ное (программное) решение. Поскольку тексты представляются с помощью набора символов Uni-code, то перед сжатием можно произвести предварительное определение языковой группы, исполь-зуя знания о распределении кодов национальных символов по диапазону Unicode.
В Unicode кодировка организована не по языкам, а по скриптам. Если несколько языков исполь-зуют близкие наборы знаков, набор символов, достаточный для этой группы идентифицируется как один набор. К примеру, латинский набор содержит все знаки, используемые в английском, фран-цузском, испанском, немецком и близких языках. Каждому набору символов соответствует свой диапазон кодов, например, для кириллических символов, которые используются в русском, бело-русском, болгарском и т.п. языках, выделен диапазон [0x0400, 0x052F]. Для греческого языка опре-делены диапазоны [0x0370, 0x03FF] и [0x1F00, 0x1FFF], а для иврита – [0x0590, 0x05FF] и [0xFB00, 0xFB4F]. Таким образом, предварительно определив языковую группу анализируемого текста по кодам используемых в тексте символов, можно значительно сократить количество итераций алго-ритма определения языка. В некоторых случаях, например, для греческого, китайского, японского язык текста может быть однозначно установлен по одному только диапазону символов. С помощью разработанной авторами программы автоматического определения языка текста (свидетельство об официальной регистрации программ для ЭВМ № 2005611324) было проведено экспериментальное подтверждение эффективности предложенного метода. Эксперименты проводились для набора из 67 наиболее распространенных языков, при этом тексты образцы выбирались достаточно случай-ным образом без какой либо лингвистической проработки. Среднее время определения языка текста составило от 1 сек. (для документов, содержащих около 2000 слов), до 6 сек. (для документов, со-держащих около 150 000 слов). Для европейских языков, использующих латиницу и кириллицу, точность определения оказалась достаточно высокой – порядка 90%. При этом ошибки определения наблюдались в основном для родственных языков: так датские тексты были определены как нор-вежские, один из двух текстов на ирландском определен как английский, некоторые испанские оп-ределены как португальские, а один из сербских как боснийский. По группе арабских, кавказских и юго восточных языков выборка была менее представительна, чем по европейским, и охватила 18 языков. При проведении эксперимента не учитывался кодовый диапазон символов, тем не менее, точность определения оказалась около 70%. Больше всего ошибок наблюдалось при определении вьетнамского и грузинского языков.
Отметим еще одну особенность рассмотренного в данной статье метода – относительную про-стоту и скорость добавления новых языков для анализа. В системах, основанных на обучении, таких как метод опорных векторов (SVM) или системы искусственного интеллекта, при добавлении ново-го языка необходимо заново проводить обучение всей системы, что может занять достаточно много времени. В рассмотренном методе добавление нового языка заключается в добавлении нового тек-ста образца и весь процесс занимает не более двух минут.
Таким образом, проведенные эксперименты показывают эффективность применения свойств от-носительной энтропии и особенностей кодировки Unicode для определения языка текста не только в исследовательских целях, но и в реально действующих системах автоматической классификации документов.
Свои услуги предлагает Свадебный фотограф - самый светлый миг вашей жизни будет запечатлен на пленке настоящим профессионалом своего дела.
С теннисными пушками lobster можно играть в теннис на даче. Тренируйтесь везде, где вам удобно это делать!
Интересный и познавательный блог про СЕО: http://shakin.ru/. Все что нужно знать для успешного продвижения сайтов я нашел именно там.
