The development of stemming algorithm for the Uzbek language

Bakaev Ilkhom Izatovich Senior Scientific Associate,  Science and Innovation Center for Information and Communication Technologies at the Tashkent University of Information Technologies 100124, Uzbekistan, respublika 100124, g. Tashkent, ul. M-V buz-2, 17A bakayev2101@gmail.com

1. Введение

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

В настоящее время, в мире насчитывается более 7000 живых языков ^[1], из них немногим более 100 имеют письменность и только 40 считаются самыми распространёнными – на которых говорит примерно две трети населения планеты. Сколь разнообразны естественные языки, столь же разнообразны их семантические и грамматические свойства. По этой причине уже существующие алгоритмы обработки текстов, весьма эффективные для одного языка, часто бывают совершенно неприменимы для текстов на другом языке. Причем речь идёт не только об алгоритмах семантического анализа, считающегося AI-полной задачей ^[2], но и об алгоритмах решения более узких задач нормализации текста.

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

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

Нормализация текста, как правило, подразумевает выполнение ряда базовых процессов, в том числе, токенизацию, стемминг и/или лемматизацию. Токенизация – это процесс разбиения текста до наименьших атомарных единиц (токенов). Стемминг – процесс определения неизменяющейся основы заданного слова (стеммы), которая необязательно совпадает с его морфологическим корнем. Лемматизация – процесс приведения заданного слова к лемме, то есть к его нормальной (словарной) форме.

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

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

К числу наиболее популярных реализаций алгоритмов стемминга, разработанных к настоящему времени, относятся стеммеры Д.Б. Ловинс, М. Портера, К. Пэйса и Г. Хаска (алгоритм Ланкастера). Большинство алгоритмических стеммеров в той или иной степени являются производными от них или их модификациями. Кроме того, имеют место алгоритмы стемминга, основанные на статистическом, стохастическом и гибридном подходах, например, Stemka, N-грамм стеммеры, Brute force стеммеры и т.д.

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

Авторы ^[3] сравнивают алгоритмы стемминга Портера и Ланкастера. Оценка выполнялась на основе ошибок результатов стемминга и визуализации текстовых данных. В качестве исходных данных авторы использовали 10 текстовых документов, которые были выбраны случайным образом из Интернет газет. Полученные авторами результаты показывают, что алгоритм Портера работает эффективнее на 43%, чем алгоритм Ланкастера.

В работе ^[4] описывается алгоритм нормализации слов на основе классификации окончаний и суффиксов. Общее количество которых составляет 26526 суффиксов и 3565 окончаний. Для всех частей речи построен конечный автомат с учетом морфологических свойств казахского языка. Также авторами разработан алгоритм стемминга без словаря на основе классификации суффиксов и окончаний. Алгоритм протестирован на текстовых корпусах казахского языка.

Авторами работы ^[5] предложен алгоритм на основе морфологических правил персидского языка, работающий по принципу снизу вверх. Алгоритм состоит из трех этапов: подстроковые теги, соответствие правил, соответствие антиправил. Всего задано 252 правил и 20 антиправил. На первом этапе извлекаются морфологические свойства для всех возможных подстрок. Определяются морфемы и их кластеры, а также основы слов (ядра). На этапе соответствия правил для каждого ядра извлекаются соответствующие правила. Неподходящие к правилам ядра переходят на следующий этап соответствия антиправил. Алгоритм тестировался с помощью текстового корпуса «Hamshahri» и показал корректное извлечение 90,1% основ слов.

В статье ^[6] разработан новый метод получения основы слов для разных языков. Хотя эксперимент был проведён авторами только для английского и персидского языков. Утверждается, что метод не зависит от морфологических правил языка. В методе используется двуязычный словарь для определения основ слов. Предложенный метод разделён на несколько этапов. На первом этапе проводится кластеризация структурных и семантических сходств слов из словаря. Далее из каждого кластера выбирается слово - кандидат. Эти кандидаты используются для идентификации новых слов. Проведенные эксперименты показывают, что для английского языка метод работает с точностью до 69,52%, а для персидского языка - 70,32%.

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

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

Целью данной работы является разработка метода нормализации текстов на узбекском языке на основе стемминг алгоритма для обработки слов, структурный тип которых известен заранее.

2. Постановка задачи

Морфологический состав слов узбекского языка включает две основных части: корневая и аффиксальная морфемы. Корень (o‘zak) – это морфема, которая имеет лексическое значение и не имеет аффиксов в своём составе. Аффикс – это морфема, которая может иметь несколько функций. Присоединяясь к корню аффикс образует новое слово или грамматические значение.

Нормальная форма (основа) слов в узбекском языке (negiz) может состоять только из корневой морфемы либо из корневой и аффиксальной морфем одновременно. Основа слов может быть производной и непроизводной. Производная основа состоит из корня и словообразующего аффикса. Например, «gul» (цветок) является непроизводной основой, «guldon» (ваза) – производная основа.

Словообразование может происходить различными способами, в том числе, путем присоединения аффикса к корню «gul+chi» (флорист), путем конкатенации двух простых слов через дефис «baxt-saodat» (счастье), «tez-tez» (часто).

Таким образом, в современном узбекском языке слова по своей структуре бывают: простые, сложные, парные, повторяющиеся (рис. 1).

Рис.1. Типы слов по структуре

Отметим, что соответствующее программное средство для определения типов слов узбекского языка, основанное на применении регулярных выражений, было создано нами ранее ^[7].

Задача состоит в том, чтобы привести к нормальной форме все слова заданного текста, который после предварительного этапа токенизации был размечен по типам слов и подвергнут очистке от стоп-слов.

3. Метод решения

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

w_s – простые слова (с производной или непроизводной основой);

w_c – сложные слова;

w_p– парные слова;

w_r – повторяющие слова.

Наибольший интерес представляет задача нормализации слов типа w_c и w_p, например, соответственно «2021-yillar» и «sixat-salomatlik». Суть алгоритма сводится к тому, что из словоформы удаляются аффиксы, встречающиеся после знака дефис. Если исходное слово не имеет аффиксов, то оно считается стеммой. То есть, «2021-yillar» усекается до «2021-yil» (2021 год), «sixat-salomatlik» усекается до «sixat-salomat» (здравствующий) (рис. 2).

Рис.2. Блок схема алгоритма StemWCWP

Далее опишем переменные и функции алгоритма «StemWCWP» для типов w_c и w_p :

- «S» – строка;

- «Spart» – строка, содержащая часть строки S;

- «b» – логическая метка;

- «i» – Итерационная переменная;

- «HyphenAfterStr(S)» – пользовательская функция, вырезающая часть строки после знака дефиса;

- «Length(string S)» - стандарная функция возвращения длины строки;

- «dbStemShow(string S)» – пользовательская функция, которая проводит поиск по базе данных;

- «SubStr(firstindex:int, lastindex:int)» – стандарная функция, извлекающая символы, начиная с индекса firstindex до индекса lastindex;

Слова типа w_p - «последовательность символов алфавита + знак дефис + последовательность символов алфавита», где слова разлеленные дефисом могут быть идентичными либо первое слово может быть подстрокой второго слова. Во втором случае из второго слова отсекаются любые аффиксы (рис.3).

Рис.3. Блок схема алгоритма StemWP

Описание переменных и функций алгоритма StemWP:

- «S» – строка;

- «SS» – строка, содержащая дубликат строки S;

- «b» – логическая метка;

- «SpartBefore» – содержит результат функции HyphenBeforeStr (string S);

- «SpartAfter» – содержит результат функции «HyphenAfterStr(string S)»;

- «HyphenBeforeStr (string S)» – пользовательская функция, вырезающая часть строки до знака дефиса;

- «HyphenAfterStr(string S)» – пользовательская функция, вырезающая часть строки после знака дефиса;

- «SearchStr(string str1, string str2)» – пользовательская функция, проверяющая является ли "str2" частью "str1", если да то возвращает значение true, в противном случае - false.

- «dbStemShow(string S)» – пользовательская функция, которая проводит поиск по базе данных;

Слова типа w_s состоят из «последовательность символов алфавита». Иногда в этих словах встречается знак апострофа. Например, «a’lo», «kitob». Чтобы найти основу для такого типа слов удаляется префикс, а не производные аффиксы (рис.4).

Рис.4. Блок схема алгоритма StemWS

Далее опищем переменные и функции алгоритма StemWS

- «S» – строка;

- «SS» – строка, содержащая дубликат строки S;

- «b» – логическая метка;

- «i» – итерационная переменная;

- «pref» – строка для префиксов;

- «Length (string S)» – стандарная функция, возвращающая длину строки;

- «dbStemShow(string S)» – пользовательская функция, которая проводит поиск по базе данных;

- «preffunc(string S)» – пользовательская функция, извлекающая префиксы из строковой переменной;

- «SubStr(firstindex:int, lastindex:int)» – стандарная функция, извлекающая символы, начиная с индекса firstindex до индекса lastindex;

Обсуждение результатов. Для тестирования алгоритма использовался текстовые корпуса по жанрам: сказки, законодательные документы, узбекские пословицы и религиозные произведения табл.1.

Таблица №1

Заключение

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