Введение Данный текст можно рассматривать как обзор библиотеки Strutext, задуманной автором как набор эффективных алгоритмов лингвистической обработки текста на языке C++.
Код библиотеки находится в репозитории по адресу Гитхаб .
Библиотека имеет открытый исходный код и распространяется по лицензии Apache License 2.0, т.е.
может использоваться совершенно бесплатно без каких-либо существенных ограничений.
Последний коммит в репозиторий был сделан 16 февраля 2014 года, то есть библиотека не разрабатывалась более полугода.
Но, тем не менее, как кажется автору, в библиотеке уже достаточно интересных реализованных алгоритмов, чтобы быть полезными тем разработчикам, которые занимаются обработкой текста на естественных языках.
Сборка Strutext реализована на основе cmake. Почти весь код библиотеки реализован на C++ 2003, но есть небольшой скрипт, написанный на Python версии 2.7. Библиотека использует boost версии 1.53 и выше, а также библиотеку Log4Cplus в качестве инструмента ведения журналов.
На данный момент библиотека скомпилирована для Linux с помощью компилятора gcc, но автору кажется, что скомпилировать ее для Windows довольно легко.
Вероятно, возникнет закономерный вопрос: зачем нужна такая библиотека, если есть, например, отделение интенсивной терапии ? С точки зрения автора, некоторые компоненты библиотеки реализованы недостаточно эффективно.
Стиль реализации основан на низкоуровневом C или высокоуровневом Java. Данное обстоятельство, с точки зрения автора, не позволяет удобно и эффективно использовать библиотеку ICU на языке C++.
Кроме того, в ОИТ не реализован такой важный компонент, как морфология.
Также одним из основных преимуществ библиотеки Strutext является наличие эффективных алгоритмов текстового поиска на основе реализованной библиотеки конечных автоматов.
В целом ICU реализует только один компонент — обработку символов UNICODE, и в этом смысле библиотека Strutext предоставляет более расширенные возможности.
Структура библиотеки Strutext спроектирован как инструмент для обработки текстов на естественных языках на различных уровнях представления этих языков.
Обычно выделяют следующие уровни языковой репрезентации:
- Уровень персонажа.
На этом уровне текст документа рассматривается просто как последовательность символов.
Символы должны быть каким-то образом классифицированы, т. е.
хотелось бы отличать буквы от цифр, знаки препинания от пробелов и т. д. Также хотелось бы иметь подобную классификацию для как можно большего числа языков.
- Лексический уровень.
Последовательность символов разбивается на слова.
Слова, в свою очередь, можно каким-то образом классифицировать.
Класс набора слов еще называют лексическим типом.
В классической традиции лексическим типом является слово (например, мама), а сами слова называются словоформами (для слова мама это будет: мама, мама, мамы и т. д.).
Совокупность словоформ слова называется парадигмой, а само слово — лексемой.
- Синтаксический уровень.
На этом уровне текст разбивается на предложения и исследуются связи между словами в предложении.
Связи в основном иерархичны, т.е.
представлены в виде дерева, но существуют и более сложные и запутанные отношения.
- Семантический уровень.
Это уровень выявления смысловых структур, которые строятся на основе синтаксических структур, извлеченных из текста документа.
Основные компоненты библиотеки:
- символы — реализация символьного уровня представления языка на базе UNICODE32.
- encode — набор итераторов для перекодирования текста.
- автоматы — это реализация библиотеки конечных автоматов, предназначенная для поиска последовательностей символов в тексте.
- morpho — библиотека морфологического анализа для русского и английского языков.
Поэтому в тексте ниже будет описан только компонент символов.
Если аудитория проявит интерес к библиотеке, автор будет рад продолжить описание в других статьях.
Описание компонента также можно рассматривать как введение в соответствующую область программирования, т.е.
учебное пособие по тому, как программно реализовать этот компонент обработки текста.
В этом смысле автор постарался не ограничиваться простым описанием интерфейса библиотеки, но и изложить идеи и методы реализации, лежащие в его основе.
Символы библиотеки обработки символов
Немного о Юникоде
Как известно, консорциум ЮНИКОД был создан для разработки стандарта представления символов языков мира в памяти компьютера.С момента своего образования консорциум выпустил уже семь версий этой презентации.
В памяти машины символы могут быть закодированы по-разному, в зависимости от цели использования.
Например, для представления символов в файлах, когда важна экономия размера, используется представление UTF-8. Если нет необходимости использовать определенные возможности языка, то можно использовать двухбайтовое представление UTF-16. Чтобы полностью представить весь спектр спецификации UNICODE, лучше использовать четырехбайтовое представление UTF-32. Символы (буквы) в стандарте UNICODE разделены на классы.
Классов сравнительно немного, перечислим некоторые из них:
- Лу — заглавная буква.
- Лл — строчная буква.
- Nd — десятичная цифра.
- Zs — пробел, используемый в качестве разделителя
- По - знак препинания без дополнительного уточнения
- Cc — управляющий символ.
Для реализации данного функционала удобно использовать файл Юникоддата.
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 также указаны коды соответствующих строчных (прописных) букв.
Это дает возможность реализовать в библиотеке функции преобразования регистров.
Реализация библиотеки символов
Библиотека символов реализует определение классов символов 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 и генерирует файл символов.
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. Это то, что делает компонент кодирования.
Послесловие Одной из основных мотиваций как для написания текста, так и для разработки библиотеки Strutext было желание автора поделиться своим опытом разработки приложений для обработки текста на C++ с другими разработчиками.
Код библиотеки можно рассматривать как материальное воплощение профессионального опыта автора (автор надеется, что весь его опыт не исчерпывается этим кодом).
Конечно, глагол «делить» подразумевает две стороны: ту, которая делится, и ту, которая хочет принять это разделение.
Если всем ясно, что с первой стороной проблем нет, то наличие второй стороны предстоит обнаружить, в том числе и с помощью этой публикации.
Если есть отклики на текст, то автор готов потрудиться и описать другие компоненты библиотеки Strutext. Теги: #C++ #лингвистика #обработка текста #обработка текста #программирование #C++ #Алгоритмы
-
Проект К28А Или Велосипед Нового Поколения
19 Oct, 24 -
Компьютерра И Порнографы
19 Oct, 24 -
Провайдеры, Не «Спите»!
19 Oct, 24
