АВТОМАТИЧЕСКАЯ ИДЕНТИФИКАЦИЯ ЯЗЫКА ДОКУМЕНТА ДЛЯ ПОСЛЕДУЮЩЕГО CROSS-LANGUAGE АНАЛИЗА

Введение

Определение языка является важной стадией работы с текстовыми документами, так как от нее зависит эффективность приложений по обработке естественных языков (NLP): информационный поиск (IR), вопросно-ответные системы (QA), автоматическое реферирование (Summarization).

В зависимости от применяемых правил построения поисковых образов и стратегий их сравнения различают следующие основные методы определения языка текстовых документов:

• коротких слов,
• частотных слов,
• N-грамм,
• статистический,
• алфавитный,
• грамматических слов,
• неграмматических слов.

Алгоритм N-грамм

Алгоритм N-грамм для опреде­ления языка и кодировки документа по его содержимо­му, основывается на статистиках документов, для которых язык и кодировка известны заранее. В данном методе подсчитыва­ются частоты N-грамм (сочетаний символов или под­строк, длиной не более N) и предполагается, что при­мерно 300 самых часто используемых N-грамм сильно зависят от языка.

После этого среди всех тес­товых документов находим тот, для которого расстоя­ние от его N-граммной статистики до статистики тести­руемого документа минимально. После этого языком тестируемого документа считается язык найденного тестового документа.

Расстояние между статистиками подсчитывается следующим образом: все N-граммы сортируются в по­рядке убывания частоты их появления, затем для каж­дой N-граммы вычисляется разница её позиций в отсор­тированном списке N-грамм тестового и тестируемого документов. Расстояние между статистиками определя­ется как сумма разностей позиций каждой N-граммы: , где  - позиции i-й N-граммы в текстовом и тестируемом документах соответственно[1].

Основными недостатками описанного выше ал­горитма являются: неустойчивость определения языка малых текстовых фрагментов — отдельные предложе­ния на похожих языках распознаются неуверенно, и часто с ошибками.

Иногда поступают еще проще. Например, в AB­BYY RME, как минимум до четвертой версии, морфо­логическая машина при словарной лемматизации пере­бирала все загруженные языковые словари.

Следует также отметить, что процесс морфоло­гической обработки является сравнительно трудоемким, сами словари занимают в памяти от единиц до десятков мегабайт на один язык, поэтому перебор даже по десят­ку возможных языков становится весьма медленным[2].

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

Предварительный разбор текстового документа

На этапе предварительного разбора производит­ся разбор корпуса документов и выявление в нем:

1. Уникальных для языка N-грамм с длиной до 3-х символов включительно (включая и одиночные символы).
2. Часто встречающихся (но не уникальных по всему корпусу) в языке N-грамм с длиной до 3-х симво­лов включительно.

Из тонкостей разбора можно отметить следую­щие моменты:

1. Тексты предварительно разбиваются на слова (мо­нолитные последовательности из символов, соот­ветствующих данному языку).
2. Все слова приводятся к одному регистру (напри­мер, к верхнему).
3. Сочетания кодируются следующим образом – если мощность N-граммы меньше, чем 3, то отсутст­вующие символы заменяются на символ с кодом 0.
4. К словам слева и справа добавляется по пробелу (или любой другой символ, гарантировано не яв­ляющийся буквой из какого-то алфавита). Это по­зволяет в дальнейшем отличить сочетание с мощ­ностью до 2-х включительно, стоящее в конце, от такового же, стоящего в середине и в конце слова. Такая мелочь позволила увеличить точность распо­знавания языка примерно в 1.5 раза и более[3].
5. Уникальные N-граммы для того, чтобы попасть в окончательный список N-грамм, должны превы­сить определенный порог встречаемости (на прак­тике использовался уровень в 10-15 раз). Это по­зволяет убрать случайные сочетания, нехарактер­ные для данного языка.
6. Часто встречающиеся сочетания сортировались по частоте, и выбиралось определенное их количество - N_freq. Эта процедура выполнялась отдельно для сочетаний разной длины. Т.е., при N_freq =16, в ко­нечную таблицу сочетаний попадало 16 триграмм, 16 би­грамм. Для одиночных символов сделано исключе­ние - для них количество выбирается как меньшее значение из N_freq, либо 1/8 от размера алфавита (учитывается количество символов одного регист­ра). Эксперименты показали, что оптимальное зна­чение N_freq (для разных текстов и языковых набо­ров), лежит, как правило, в промежутке 64.. .128.

Подстройка весовых коэффициентов

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

Если найденная N-грамма являлась уникальной по отношению ко всем остальным языкам, то весовой коэффициент увеличивался на W_U. В текущей реализа­ции W_U=10. Если N-грамма просто являлась часто встречающейся в соответствующем языке, то весовой коэффициент увеличивался на a_N. В текущей реализа­ции было принято, что a_N=N. Данный выбор весовых коэффициентов является эмпирическим, и на практике он показал себя надежно.

Было произведено исследование 3-х вариантов алгоритма оценки текстов:

1. Учитываются все найденные сочетания - как уни­кальные, так и неуникальные.
2. Учитываются все уникальные сочетания. Неуни­кальные учитываются только в том случае, если в других языках такие сочетания не прошли в часто встречающиеся (т.е., остались за пределами, кото­рые очерчиваются параметром N_freq).
3. Учитываются только уникальные сочетания.

Эксперименты показали, что результаты 1-го ал­горитма, учитывающего все, как уникальные, так и час­то встречающиеся сочетания, самые неубедительные.

Лучше всего проявляет себя алгоритм 3, который работает только с уникальными сочетаниями. Од­нако у него имеется один изъян - из-за очень большой требовательности к используемым данным, на коротких последовательностях он может просто не успеть вы­брать главный язык. Т.е., если встречается предложение из двух-трех слов, то очень часто все языки имеют ве­совой коэффициент 0. Кроме того, исследование пока­зало, что имеются языки, имеющие мало уникальных сочетаний (например, испанский), что также затрудняет его применение.

В связи с этим наиболее надежной видится сле­дующая схема работы алгоритма распознавания языка - на первом этапе текст обрабатывается по 3-му алгорит­му. Если отношение коэффициентов 1-го и 2-го по зна­чимости языков больше, чем 2, а абсолютные значения весовых коэффициентов выше некоторого порога (на­пример, 30-50), то на этом и останавливаемся. В про­тивном случае, обрабатываем текст повторно, исполь­зуя алгоритм 2. В этом случае, для принятия решения о провале на каком-то языке попадают отдельные слова на другом, их вполне можно считать инвариантами для основного языка.

Построение модуля приложения по заданному алгоритму позволит на высоком уровне решить задачу автоматической идентификации языка текстового документа.

Список литературы

1. Крапивин, Ю.Б. Автоматическое определение языка текстового документа для основных европейских языков / Ю.Б. Крапивин / Информа­тика. - 2011.
2. Cowie, J. Language recognition for mono- and multilingual documents / J. Cowie, Y. Ludovic, R. Zacharski // Proc. of the Vextal Conference. - Venice, 1999.
3. Natural Language Identification using Corpus-based Models / C. Souter [et al.] // Hermes Journal of Linguistics. - 1994. - № 13. - P. 183-203.\