Введение
Этот текст можно рассматривать как обзор библиотеки Strutext, задуманной автором как набор эффективных алгоритмов лингвистической обработки текста на языке C++. Код библиотеки находится в репозитории на Github. Библиотека имеет открытый исходный код и поставляется под лицензией Apache License 2.0, т.е. может быть использована совершенно бесплатно без каких-либо существенных ограничений.
Последний коммит в репозиторий был произведен 16 февраля 2014 года, иначе говоря, разработка библиотеки не ведется уже более полугода. Но, тем не менее, как представляется автору, библиотека имеет уже достаточно интересных реализованных алгоритмов, чтобы быть полезной тем разработчикам, которые занимаются обработкой текстов на естественных языках.
Сборка Strutext реализована на основе cmake. Почти весь код библиотеки реализован на C++ 2003, однако имеется небольшой скрипт, написанный на Python версии 2.7. Библиотека использует boost версии 1.53 и выше, а также библиотеку Log4Cplus как инструмент для логирования. На данный момент библиотека собирается под Linux с помощью компилятора gcc, но как представляется автору, для сделать сборку под Windows достаточно нетрудно.
Вероятно, возникнет законный вопрос: зачем нужна такая библиотека, если есть, например, ICU? С точки зрения автора, некоторые компоненты библиотеки реализованы недостаточно эффективно. Стиль реализации основан на низкоуровневом C или высокоуровневом Java. Это обстоятельство, с точки зрения автора, не дает возможности удобного и эффективного использования библиотеки ICU в языке C++. Кроме того, в ICU не реализован такой важный компонент, как морфология. Также, одним из основных достоинств библиотеки Strutext является наличия эффективных алгоритмов поиска по тексту на основе реализованной библиотеки конечных автоматов. В общем, ICU реализует только один компонент, обработку символов в UNICODE, и в этом смысле библиотека Strutext предоставляет более широкие возможности.
Структура библиотеки
Strutext задумана как инструмент для обработки текстов на естественных языках на различных уровнях представления этих языков. Обычно выделяют следующие уровни представления языка:
- Символьный уровень. На этом уровне текст документа рассматривается просто как последовательность символов. Символы должны быть каким-то образом классифицированы, т.е. хотелось бы отличать буквы от цифр, знаки пунктуации от пробелов и т.п. Также, подобную классификацию хотелось бы иметь для как можно большего количества языков.
- Лексический уровень. Последовательность символов разделяется на слова. Слова, в свою очередь, можно каким-то образом классифицировать. Класс множества слов называют еще лексическим типом. В классической традиции лексический тип это слово (например, мама), а сами слова называют словоформами (для слова мама это будет: мама, мамой, мамами и т.д.). Набор словоформ слова называют парадигмой, а само слово — лексемой.
- Синтаксический уровень. На этом уровне текст делится на предложения и рассматриваются связи между словами в предложении. Связи в своей основе иерархические, т.е. представляются в виде дерева, но также имеются и более сложные и запутанные отношения.
- Семантический уровень. Это уровень выделения смысловых конструкций, которые строятся на основе синтаксических структур, выделенных из текста документа.
Выделяют еще и другие уровни представления языка, например, прагматический, но здесь это обсуждаться не будет.
Библиотека Strutext на данный момент реализует символьный и лексический уровни представления языка. Основные компоненты библиотеки:
- symbols — реализация символьного уровня представления языка на основе UNICODE32.
- encode — набор итераторов для перекодировки текста.
- automata — реализация библиотеки конечных автоматов, предназначенных для поиска символьных последовательностей в тексте.
- morpho — библиотека морфологического анализа для русского и английского языков.
Описание каждого компонента займет достаточно много места. Поэтому в данном тексте ниже будет описан только компонент symbols. Если аудитория выскажет интерес к библиотеке, то автор с удовольствием продолжит описание в других статьях. Описание компонента можно также рассматривать и как введение в соответствующую область программирования, т.е. пособие, как программно можно реализовать данную компоненту обработки текста. В этом смысле, автор постарался не ограничится простым описанием интерфейса библиотеки, но изложить также идеи и методы реализации, лежащие в ее основе.
Библиотека обработки символов symbols
Немного о UNICODE
Как известно, консорциум UNICODE был создан для выработки стандарта представления символов языков мира в памяти компьютера. Со времени своего образования консорциум выпустил уже семь версия такого представления. В памяти машины символы могут быть закодированы различным образом, в зависимости от целей использования. Например, для представления символов в файлах, когда важно сэкономить на размере, используется представление UTF-8. Если нет необходимости использовать специфические языковые особенности, то можно использовать двухбайтовое представление UTF-16. Для полного представления всей гаммы спецификации UNICODE лучше использовать четырехбайтовое представления UTF-32.
Символы (letters) в стандарте UNICODE подразделяются на классы. Классов сравнительно немного, перечислим некоторые из них:
- Lu — буква в верхнем регистре.
- Ll — буква в нижнем регистре.
- Nd — десятичная цифра.
- Zs — пробел, используемый как разделитель
- Po — знак пунктуации без дополнительной спецификации
- Cc — управляющий символ.
Одна из функций библиотеки symbols состоит в эффективном сопоставлении коду символа в UTF-32 его класса. Для реализации этой функциональности удобно использовать файл UnicodeData.txt. Этот файл содержит перечисление всех символов стандарта, вместе с их четырехбайтовыми кодами (в шестнадцатеричном предствлении) и классами. Файл предназначен для обработки машиной, но понятен и человеку. Например, символ пробела задается строкой вида:
0020;SPACE;Zs;0;WS;;;;;N;;;;;
В файле в качестве разделителей полей используется символ ';'. Соответственно, десятичные цифры задаются следующим образом:
0030;DIGIT ZERO;Nd;0;EN;;0;0;0;N;;;;;
0031;DIGIT ONE;Nd;0;EN;;1;1;1;N;;;;;
0032;DIGIT TWO;Nd;0;EN;;2;2;2;N;;;;;
0033;DIGIT THREE;Nd;0;EN;;3;3;3;N;;;;;
0034;DIGIT FOUR;Nd;0;EN;;4;4;4;N;;;;;
0035;DIGIT FIVE;Nd;0;EN;;5;5;5;N;;;;;
0036;DIGIT SIX;Nd;0;EN;;6;6;6;N;;;;;
0037;DIGIT SEVEN;Nd;0;EN;;7;7;7;N;;;;;
0038;DIGIT EIGHT;Nd;0;EN;;8;8;8;N;;;;;
0039;DIGIT NINE;Nd;0;EN;;9;9;9;N;;;;;
Перечислим также несколько определений букв:
0041;LATIN CAPITAL LETTER A;Lu;0;L;;;;;N;;;;0061;
0042;LATIN CAPITAL LETTER B;Lu;0;L;;;;;N;;;;0062;
0043;LATIN CAPITAL LETTER C;Lu;0;L;;;;;N;;;;0063;
0061;LATIN SMALL LETTER A;Ll;0;L;;;;;N;;;0041;;0041
0062;LATIN SMALL LETTER B;Ll;0;L;;;;;N;;;0042;;0042
0063;LATIN SMALL LETTER C;Ll;0;L;;;;;N;;;0043;;0043
Интересно заметить, что для букв с классами Lu и Ll задаются также коды соответствующих букв нижнего (верхнего) регистров. Это дает возможность реализовать в библиотеке функции преобразования регистров.
Реализация библиотеки symbols
В библиотеке symbols реализована определение UNICODE классов символов, а также преобразование к верхнему или нижнему регистру.
Для задания классов используется перечислитель SymbolClass:
enum SymbolClass {
UPPERCASE_LETTER = 0x00000001,
LOWERCASE_LETTER = 0x00000002,
TITLECASE_LETTER = 0x00000004,
CASED_LETTER = UPPERCASE_LETTER | LOWERCASE_LETTER | TITLECASE_LETTER,
MODIFIER_LETTER = 0x00000008,
OTHER_LETTER = 0x00000010,
LETTER = CASED_LETTER | MODIFIER_LETTER | OTHER_LETTER,
NONSPACING_MARK = 0x00000020,
...
Элементы перечислителя задаются степенями двойки, поэтому их можно использовать как битовые флаги. В реализации библиотеки для каждого символа задается четырехбайтовое значение, в котором соответствующие его классам биты установлены в единицы. Тогда, проверка на принадлежность символа тому или иному классу — это просто значения соответствующего бита:
template<SymbolClass class_name>
inline bool Is(const SymbolCode& code) {
return static_cast<uint32_t>(class_name) & GetSymbolClass(code);
}
Для наиболее часто используемых классов реализованы соответствующие функции:
inline bool IsLetter(const SymbolCode& code) {
return Is<LETTER>(code);
}
inline bool IsNumber(const SymbolCode& code) {
return Is<NUMBER>(code);
}
inline bool IsPunctuation(const SymbolCode& code) {
return Is<PUNCTUATION>(code);
}
Для преобразования в верхний/нижний регистр используются функции ToLower и ToUpper. Следует отметить, что эти функции могут применяться не только к буквам, но и к любым другим символам. Для символа, к которому не применимо понятие регистра, функция возвращает тот же код, который был передан на входе.
Технически все это реализовано достаточно эффективно. На этапе конфигурирования запускает скрипт, написанные на языке Python, который читает файл UnicodeData.txt и генерирует файл symbols.cpp, в котором определены три массива, для классов символов, верхнего и нижнего регистров. Объявлены эти массивы следующим образом:
namespace details {
// The symbol tables declarations.
extern uint32_t SYM_CLASS_TABLE[];
extern SymbolCode SYM_UPPER_TABLE[];
extern SymbolCode SYM_LOWER_TABLE[];
} // namespace details.
Функции преобразования в верхний и нижний регистры задаются просто:
inline SymbolCode ToLower(const SymbolCode& code) {
return details::SYM_LOWER_TABLE[code];
}
inline SymbolCode ToUpper(const SymbolCode& code) {
return details::SYM_UPPER_TABLE[code];
}
Для получения набора классов символа используется следующая функция:
inline const uint32_t& GetSymbolClass(const SymbolCode& code) {
return details::SYM_CLASS_TABLE[code];
}
Как видно из определения, индексом в массиве служит код символа, поэтому обращение к элементу массива не требует никаких дополнительных затрат. Размер каждого массива ограничен числом символов, определенных в UnicodeData.txt. На данный момент это число равно 0x200000, т.е. каждый массив занимает в памяти 8 Мб, а все вместе — 24 Мб. Это представляется небольшой платой за эффективность.
Конечно, в файлах символы почти никогда не хранятся в UTF-32, неэффективно использовать 4 байта для хранения кода символа, который умещается в один байт. Для хранения используются однобайтовые кодировки, пришедшие их «доюникодного мира» (CP1251, Koi8-r и т.п.), а также кодировка UTF-8, специально разработанная для эффективного хранения символов в файлах. Библиотека Strutext предоставляет эффективные инструменты для анализа кодов символов в UTF-8. Этим занимается компонент encode.
Послесловие
Одним из главных побудительных мотивов, как для написания текста, так и для разработки библиотеки Strutext, было желание автора поделиться своим опытом разработки приложений обработки текстов на языке C++ с другими разработчиками. Код библиотеки можно рассматривать как материальное воплощение профессионального опыта автора (автор надеется, что этим кодом весь его опыт не исчерпывается).
Разумеется, глагол «делиться» подразумевает две стороны: ту, которая делится, и ту, которая желает это деление принять. Если с первой стороной, всем понятно, проблем нет, то наличие второй стороны подразумевается обнаружить в том числе и этой публикацией. Если на текст будут отклики, то автор готов потрудится и описать другие компоненты библиотеки Strutext.
Автор: mefrill
