Библиотека Strutext обработки текстов на C++ — реализация лексического уровня
Этот текст является продолжением поста о библиотеке Strutext обработки текстов на языке C++. Здесь будет описана реализация лексического уровня представления языка, в частности, реализация морфологии.По представлению автора, имеются следующие основных задачи, которые необходимо решить при реализации программной модели лексического уровня представления языка:
Выделение из исходного текста цепочек символов, имеющих смысл, т.е. представления текста в виде последовательности слов. Отождествление выделенных цепочек как элементов лексических типов. Определение для выделенной цепочки его лексических атрибутов (о них чуть ниже). Лексические типы обычно представляют как конечные множества цепочек символов, имеющие в предложениях языка один и тот же смысл. Элементы лексического класса обычно называют словоформами, само множество словоформ — парадигмой, а лексический тип — словом или леммой. Например, лексический тип «мама» состоит из словоформ { мама, мамы, мамой, …, мамы, мамам, … }.Лексический типы разделяются на синтаксические категории — части речи. Часть речи задает роль, которую слово играет в предложении языка. Эта роль важна при определении правильности места слова в предложении и, следовательно, определении смысла предложения. Известные части речи русского языка: существительное, прилагательное, глагол, наречие и т.д.
Словоформы лексического типа могут иметь свойства. Такие свойства еще называют лексическими атрибутами или лексическими признаками. Виды этих свойств зависят от синтаксической категории, которой принадлежит данный лексический тип. Например, для существительных важную роль играет падеж словоформы, а для глаголов такого атрибута не имеется.
Какие конкретно синтаксические категории используются для группирования лексических типов и какие у них имеются лексические атрибуты зависит как от реализуемого языка, так и от конкретной реализуемой модели лексического анализа. Ниже будет рассмотрена лексическая модель АОТ.
Лексические неоднозначности Может так случиться, что в процессе извлечения слов из исходного текста, возникнут неоднозначности. Здесь рассматриваются неоднозначности двух родов: Неоднозначности первого рода возникают в процессе присваивания выделенной из текста цепочке символов лексического типа. Рассмотрим пример «мама мыла раму». Здесь цепочка символов «мыла» может быть глаголом «мыть», а также может быть существительным «мыло». Такие случаи неоднозначности называются еще лексической омонимией. Неоднозначности второго рода возникают в процессе нарезки исходного текста на цепочки слов. В большинстве естественных языков слова отделены друг от друга пробелами, хотя этот принцип иногда может нарушаться (в качестве примера можно привести композиты в немецком языке). Но в языках программирования имеются интересные примеры. Рассмотрим, например, выражение вида «a >> b» в языке C++. В классическом C это выражение трактуется однозначно: идентификатор «a», оператор правого побитового сдвига »>>», идентификатор «b». Но в последних версиях языка C++ это выражение может означать конец списка шаблонных параметров, когда в качестве последнего параметра в списке также выступает шаблон. В этом случае последовательность слов будет такова: идентификатор «a», конец списка параметров шаблона »>», конец списка параметров шаблона »>», идентификатор «b». В этом тексте мы рассматриваем только лексические неоднозначности первого рода. В библиотеке Strutext реализована морфологическая модель от АОТ. Поэтому уделим ее описание некоторое место.В словаре АОТ каждый лексический тип задается двумя параметрами:
Строкой основы (корня слова), к которой присоединяются суффиксы для образования словоформ. Номером парадигмы склонения, которая представляет собой список пар (суффикс, набор лексических признаков). Комбинаций наборов лексических признаков имеется относительно немного, они перечислены в специальном файле и каждая такая комбинация закодирована двухбуквенным кодом. Например:
аа A С мр, ед, им аб A С мр, ед, рд Эф A С мр, ед, рд,2 … иа Y П прев, мр, ед, им, од, но иб Y П прев, мр, ед, рд, од, но … кб a Г дст, нст,1л, ед кв a Г дст, нст,1л, мн кг a Г дст, нст,2л, ед … Здесь первый элемент каждой строки — это двухбуквенный код набора, третий элемент — код части речи (С — существительное, П — прилагательное, Г — глагол и т.д), далее через запятую перечислены коды грамматических признаков.Файл описания словаря состоит из пяти разделов, из которых два раздела наиболее важны. Это раздел описания парадигм склонения и раздел основ (лексических типов). Каждая строка в этом разделе представляет собой парадигму склонения. В разделе описания лексических типов вместе с основой задается номер строки парадигмы склонения.
Рассмотрим, например, слово «зеленка». Лексический тип этого слова в словаре АОТ задается строкой вида
ЗЕЛЕН 15 12 1 Фа - Здесь число 15 — это номер парадигмы склонения в разделе парадигм. Выглядит строка данной парадигмы следующим образом: %КА*га%КИ*гб%КЕ*гв%КУ*гг%КОЙ*гд%КОЮ*гд%КЕ*ге%КИ*гж%ОК*гз%КАМ*ги%КИ*гй%КАМИ*гк%КАХ*гл Каждая пара в парадигме отделена от другой символом »%», а элементы пар отделяются друг от друга символом »*». Первая пара (КА, га) задает словоформу зелен + ка = зеленка и имеет набор лексических атрибутов: га = G С жр, ед, им = существительное, женского рода, единственного числа, именительного падежа. Соответствующим образом можно расшифровать и другие пары парадигмы.Способ кодирования слов, который используется в АОТ, имеет свои преимущества и недостатки. Обсуждать их здесь мы не будем, заметим только интересный факт: в словаре имеются лексические типы с пустой основой. Например, слово «человек» в множественном числе представлена словоформой «люди», которая не имеет общей основы с формой «человек». Поэтому это слово приходится задавать простым перечислением словоформ:
%ЧЕЛОВЕК*аа%ЧЕЛОВЕКА*аб%ЧЕЛОВЕКУ*ав%ЧЕЛОВЕКА*аг%ЧЕЛОВЕКОМ*ад%ЧЕЛОВЕКЕ*ае%ЛЮДИ*аж%ЛЮДЕЙ*аз%ЧЕЛОВЕК*аз%ЛЮДЯМ*аи%ЧЕЛОВЕКАМ*аи%ЛЮДЕЙ*ай%ЛЮДЬМИ*ак%ЧЕЛОВЕКАМИ*ак%ЛЮДЯХ*ал%ЧЕЛОВЕКАХ*ал Эту парадигму можно использовать и с другими словами (имеющими непустой корень), таким как богочеловек и обезьяночеловек.Рассмотрим чуть подробнее набор синтаксических категорий и соответствующих им лексических атрибутов словаря АОТ.
Синтаксические категории словаря АОТ Как уже было указано выше, синтаксические категории словаря АОТ задаются в отдельном файле и представляют собой наборы строк, в которых двухбуквенным кодам задаются часть речи и набор лексических атрибутов. В библиотеке Strutext части речи и их атрибуты представлены в виде иерархии классов на C++. Рассмотрим эту реализацию подробнее.Модели синтаксических категорий словаря АОТ заданы в директории «morpho/models». Представлены модели для русского и английского языков. Рассмотрим некоторые фрагменты файлы morpho/models/rus_model.h, в котором представлено описание модели русского языка.
Базовый класс для всех моделей — это абстрактный класс PartOfSpeech, который содержит метку языка в виде перечислителя, а также задает виртуальный метод для возврата этой метки:
class PartOfSpeech: private boost: noncopyable {
public:
/// Type of smart pointer to the class object.
typedef boost: shared_ptr
/// Language tag definitions. enum LanguageTag { UNKNOWN_LANG = 0 ///< Unknown language.
, RUSSIAN_LANG = 1 ///< Russian language. , ENGLISH_LANG = 2 ///< English language. };
/// Language tag. virtual LanguageTag GetLangTag () const = 0;
/// Virtual destruction for abstract class. virtual ~PartOfSpeech () {} }; От этого класса унаследован базовый класс для всех синтаксических категорий русского языка:
struct RussianPos: public PartOfSpeech {
/// Type of smart pointer to the class object.
typedef boost: shared_ptr
/// Possible parts of speech. enum PosTag { UNKNOWN_PS = 0 ///< Unknown part of speech.
, NOUN_PS = 1 ///< существительное , ADJECTIVE_PS = 2 ///< прилагательное , PRONOUN_NOUN_PS = 3 ///< местоимение-существительное , VERB_PS = 4 ///< глагол в личной форме , PARTICIPLE_PS = 5 ///< причастие , ADVERB_PARTICIPLE_PS = 6 ///< деепричастие , PRONOUN_PREDICATIVE_PS = 7 ///< местоимение-предикатив , PRONOUN_ADJECTIVE_PS = 8 ///< местоименное прилагательное , NUMERAL_QUANTITATIVE_PS = 9 ///< числительное (количественное) , NUMERAL_ORDINAL_PS = 10 ///< порядковое числительное , ADVERB_PS = 11 ///< наречие , PREDICATE_PS = 12 ///< предикатив , PREPOSITION_PS = 13 ///< предлог , CONJUCTION_PS = 14 ///< союз , INTERJECTION_PS = 15 ///< междометие , PARTICLE_PS = 16 ///< частица , INTRODUCTORY_WORD_PS = 17 ///< вводное слово
, UP_BOUND_PS };
/// Number. enum Number { UNKNOUN_NUMBER = 0 ///< Unknown number.
, SINGULAR_NUMBER = 0×01 ///< Единственное. , PLURAL_NUMBER = 0x02 ///< Множественное. };
/// Language. enum Lang { NORMAL_LANG = 0 // Normal language.
, SLANG_LANG = 1 , ARCHAIZM_LANG = 2 , INFORMAL_LANG = 3 };
/// Gender definitions. enum Gender { UNKNOWN_GENDER = 0 ///< Unknown gender value.
, MASCULINE_GENDER = 0×01 ///< мужской , FEMININE_GENDER = 0x02 ///< женский , NEUTER_GENDER = 0x04 ///< средний };
/// Case definition. enum Case { UNKNOWN_CASE = 0 ///< Unknown case.
, NOMINATIVE_CASE = 1 ///< именительный , GENITIVE_CASE = 2 ///< родительный , GENITIVE2_CASE = 3 ///< второй родительный , DATIVE_CASE = 4 ///< дательный , ACCUSATIVE_CASE = 5 ///< винительный , INSTRUMENTAL_CASE = 6 ///< творительный , PREPOSITIONAL_CASE = 7 ///< предложный , PREPOSITIONAL2_CASE = 8 ///< второй предложный , VOCATIVE_CASE = 9 ///< звательный };
/// Time. enum Time { UNKNOWN_TIME = 0 ///< Unknown time.
, PRESENT_TIME = 0×01 ///< настоящее , FUTURE_TIME = 0x02 ///< будущее , PAST_TIME = 0x04 ///< прошедшее };
/// Person. enum Person { UNKNOWN_PERSON = 0 ///< Unknown person.
, FIRST_PERSON = 0×01 ///< первое , SECOND_PERSON = 0x02 ///< второе , THIRD_PERSON = 0x04 ///< третье };
/// Entity kind. enum Entity { UNKNOWN_ENTITY = 0 ///< Unknown entity, for ordinal words.
, ABBREVIATION_ENTITY = 1 ///< аббревиатуры. , FIRST_NAME_ENTITY = 2 ///< имена. , MIDDLE_NAME_ENTITY = 3 ///< отчества. , FAMILY_NAME_ENTITY = 4 ///< фамилии. };
/// Animation. enum Animation { UNKNOWN_ANIMATION = 0
, ANIMATE_ANIMATION = 0×01 ///< одушевленный. , INANIMATE_ANIMATION = 0x02 ///< неодушевленный. };
/// Voice defintion. enum Voice { UNKNOWN_VOICE = 0 ///< Unknown voice.
, ACTIVE_VOICE = 0×01 ///< действительный залог. , PASSIVE_VOICE = 0x02 ///< страдательный залог. };
/// Language tag. LanguageTag GetLangTag () const { return RUSSIAN_LANG; }
/// Class is absract one — virtual destruction. virtual ~RussianPos () {}
/// Get part of speech tag. virtual PosTag GetPosTag () const = 0;
/// Serialization implementaion. virtual void Serialize (uint32_t& out) const = 0;
/// Desirialization implementation. virtual void Deserialize (const uint32_t& in) = 0;
/// Write POS signature.
static void WritePosSign (PosTag pos, uint32_t& out) {
// Write to lower 5 bits.
out |= static_cast
/// Read POS signature. static PosTag ReadPosSign (const uint32_t& in) { return PosTag (in & 0×1f); } }; В классе заданы метки синтаксических категорий в виде перечислителя PosTag, а также определены лексические атрибуты. Кроме, собственно, грамматической составляющей, в классе определены методы Serialize и Deserialize для преобразования в/из бинарный формат. Для каждого синтаксического типа определено преобразование в четыре байта, представленные типом uint32_t.Класс RussianPos абстрактный, от него унаследованы классы, представляющие конкретные синтаксические категории. Например, класс Noun задает существительное:
struct Noun: public RussianPos { Noun () : number_(UNKNOUN_NUMBER) , lang_(NORMAL_LANG) , gender_(UNKNOWN_GENDER) , case_(UNKNOWN_CASE) , entity_(UNKNOWN_ENTITY) {}
/// Get part of speech tag. PosTag GetPosTag () const { return NOUN_PS; }
/**
* \brief Serialization implementaion.
*
* Binary map of the object:
* 13 3 4 3 2 2 5
* -----------------------------------------------------------
* Unused | Entity | Case | Gender | Lang | Number | POS tag |
* -----------------------------------------------------------
*
* \param[out] ob The buffer to write to.
*/
void Serialize (uint32_t& ob) const {
ob |= static_cast
/**
* \brief Desirialization implementaion.
*
* Binary map of the object:
* 13 3 4 3 2 2 5
* -----------------------------------------------------------
* Unused | Entity | Case | Gender | Lang | Number | POS tag |
* -----------------------------------------------------------
*
* \param ib The buffer to write to.
*/
void Deserialize (const uint32_t& ib) {
number_ = static_cast
Number number_; Lang lang_; Gender gender_; Case case_; Entity entity_; }; В классе существительного хранятся лексические атрибуты: число, вид языка (обычный, анахронизм, разговорный и т.п.), пол, падеж и признак имени или аббревиатуры. Для хранения словарей, а также эффективного извлечения из словаря данных слова, в библиотеке Strutext используются конечные автоматы. Конечные автоматы задаются соответствующими C++ типами в директории automata.Напомним, конечный автомат задается функцией переходов, которая некоторым парам (состояние, символ) сопоставляет некоторое состояние: delta: Q x V --> Q. Имеется одно начальное состояние, в котором автомат начинает свою работу и некоторое количество «допускающих» состояний. Автомат читает входную строку посимвольно, если для текущего состояния и прочитанного символа функция переходов дает в соответствие некоторое состояние, то автомат «переходит» в это новое состояние, после чего цикл чтения нового символа начинается заново. Автомат может остановится в двух случаях: если нет перехода по паре (текущее состояние, прочитанный символ) и если прочитана вся цепочка символов до конца. В первом случае входная цепочка считается не допускаемой данный автоматом, во втором случае цепочка допускается, если после остановки автомат находится в одном из допускающих состояний.
Таким образом, каждый раз, когда прочитан новый символ входной цепочки, автомат сталкивается с задаче поиска соответствия паре (состояние, символ) нового состояния. В библиотеке Strutext реализация этой функции поиска выделена в отдельный класс под названием Transition. Автомат представляет собой массив объектов класса Transition, заданных для каждого состояния (automata/fsm.h):
template
/// Default initialization.
explicit State (bool is_accepted = false) : is_accepted_(is_accepted) {}
};
/// Type of states' list.
typedef std: vector
Класс FiniteStateMachine не в состоянии сказать о входной цепочке что-нибудь, кроме того, что данная цепочка допускается. Для хранения дополнительной информации о допускаемых цепочках необходимо добавить атрибуты к допускающим состояниям. Это сделано в шаблонном классе AttributeFsm. Класс берет в качестве параметра шаблона реализацию функции переходов и тип атрибута для допускающего состояния. Следует отметить, что атрибуты можно присоединять не только к допускающим состояниям (хотя непонятно, имеет ли это смысл), а также, что к состоянию можно присоединить более одного атрибута, все они хранятся в векторе.
Хранение словаря в конечном автомате задает для функции переходов конечного автомата этого словаря древовидную структуру. Для такой структуры используется также термин trie, введенный Д. Кнутом. В библиотеке Strutext имеется реализация такого конечного автомата в файле automata/trie.h:
template
/// Attribute FSM type.
typedef AttributeFsm
/// Default initialization. explicit Trie (size_t rsize = AttributeFsmImpl: kReservedStateTableSize) : AttributeFsmImpl (rsize) {}
/// It may be base class. virtual ~Trie () {}
/**
* \brief Adding chain of symbols.
*
* \param begin Iterator of the chain’s begin.
* \param end Iterator of the chain’s end.
* \param id Chain identifier.
*
* \return The number of last state of the chain.
*/
template
/**
* \brief Adding chain of symbols.
*
* \param begin Iterator of the chain’s begin.
* \param end Iterator of the chain’s end.
*
* \return The number of last state of the chain.
*/
template
Следует также отметить, что все автоматы могут быть сериализованы/десериализованы в std: stream. Это позволяет хранить автоматы в файлах на диске, т.е. использовать как хранилища словарей в бинарном формате.
Морфологический анализатор представляет собой библиотеку, расположенную в директории morpho/morpholib. Основной интерфейсный класс, Morphologist, располагается в файле morpho/morpholib/morpho.h.Прежде чем описывать интерфейс и реализацию класса, опишем сначала основные принципы, на которых основана эта реализация.
Во-первых, имеется словарь основ, которые реализованы в объекте класса Trie.Во-вторых, каждой основе в допускающем состоянии даны в соответствие парадигма склонения (по прежнему, это вектор пар (суффикс, набор лексических атрибутов). Набор атрибутов представлен экземпляром класса, унаследованного от PartOfSpeech).В-третьих, каждому лексическому типу дан в соответствие уникальный числовой идентификатор, номер основы в словаре.
Таким образом, для распознавания переданной словоформы как слова необходимо поискать по автомату основу (будет найден идентификатор лексического типа, соответствующего данной основе), затем по окончанию найти соответствующие атрибуты. Все это надо делать с учетом неоднозначностей, как при поиске основ, так и при определении окончаний. Код для поиска следующий:
/** * \brief Implementation of morphological analysis of passed form. * * \param text Input text in UTF-8 encoding. * \param[out] lem_list List of lemmas within morphological attributes. */ void Analize (const std: string& text, LemList& lem_list) const { // The first phase. Go throw the passed word text, encode symbol // and remember symbol codes in the string. If found word base on // some position, remember attribute and position for an each // attribute.
// Try starts with empty bases
typedef std: list
// Permorm the first phase.
std: string code_str;
typedef strutext: encode: Utf8Iterator
// The second phase. Go throuth the found base list and find suffixes for them. // If suffixes have been found then add them to the lemma list. lem_list.clear (); for (BaseList: iterator base_it = base_list.begin (); base_it!= base_list.end (); ++base_it) { AttrMap attr; attr.auto_attr_ = base_it→first; SuffixStorage: AttrList att_list; std: string suffix = code_str.substr (base_it→second); // If suffix is empty (empty suffix passed), add zero symbol to it. if (suffix.empty ()) { suffix.push_back ('\0'); } if (const SuffixStorage: AttrList* att_list = suff_store_.SearchAttrs (attr.line_id_, suffix)) { for (size_t i = 0; i < att_list->size (); ++i) { lem_list.push_back (Lemma (attr.lem_id_, (*att_list)[i])); } } } } Как видно, алгоритм определения разделяется на два этапа. Сначала выделяются основы (здесь еще надо учитывать существование пустых основ). Для каждой основы запоминается ее позиция во входной цепочке, чтобы потом можно было выделить окончание. На втором этапе производится поиск окончаний, соответствующих выделенным основам. Если окончание найдено в соответствующей данной основе парадигме склонения, то лексические атрибуты этого окончания возвращаются вместе с идентификатором слова.Класс Morphologist предоставляет также сервис по генерации словоформ по номеру основы и переданным лексическим атрибутам. Этим занимается метод Generate:
/** * \brief Generate form. * * \param lem_id The lemma identifier. * \param attrs The attributes of the form. * \return Generated text in UTF-8 encoding. */ std: string Generate (uint32_t lem_id, uint32_t attrs) const; Также имеется метод GenAllForms порождения всех форм данного слова и метод GenMainForm, возвращающий главную форму слова. Для существительного это, очевидно, форма единственного числа именительного падежа.В директории morpho/aot в файле main.cpp реализован парсер представления словаря АОТ в оригинальном формате, который в качестве результата возвращает представление в бинарном формате, совместимое с библиотекой морфологии. Результирующий бинарный словарь можно использовать в классе Morphologist. Сами бинарные словари не хранятся в репозитории, но могут быть сгенерированы пользователем при необходимости. Для реализации русского словаря можно использовать следующую команду:
./Release/bin/aot-parser -t …/morpho/aot/rus_tabs.txt -d …/morpho/aot/rus_morphs.txt -m rus -b aot-rus.bin В бинарном виде словарь размер словаря чуть менее 20 Мб.Для выделения словорформ из исходного текста можно использовать определенный в utility/word_iterator.h класс WordIterator. Этот класс считает словами последовательности символов (symbols: IsLetter). Итератор возвращает слово как юникодную строку. Перекодировать эту строку в UTF-8 можно с помощью функции GetUtf8Sequence, определенной в encode: utf8_generator.h.
Текст получился довольно объемным и, вероятно, сложным для чтения. Автор постарался упростить изложение, где это только было возможно, но учитывая сложность материала, таких мест в тексте видимо было не много.Все же автор питает надежды, что описываемая в тексте библиотека Strutext будет полезна и труд по ее реализации не будет напрасным.
