Библиотека Strutext обработки текстов на языке C++

    Введение



    Этот текст можно рассматривать как обзор библиотеки 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.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 32

      +4
      На мой взгляд, стоило бы лучше рассказать про какую-то другую часть библиотеки. Обработка текста посимвольно — достаточно тривиальная и неинтересная задача.
        +1
        поддерживаю. Очень интересен модуль морфологии…
          0
          Я бы сказал, что и морфология — это стандартная и давно решенная задача. Интересен синтаксис, и, конечно, семантика. Ну или морфология, но со снятием омонимии (ну это уже ближе к синтаксису). Кстати, я не увидел в компонентах библиотеки задачу токенизации текста на предложения, а это, во-первых, нетривиальная задача, а во-вторых, от качества ее решения зависит точность работы остальных лингвистических функций библиотеки.
            +2
            Синтаксис я в Strutext не перенес. У меня есть реализация синтаксического анализатора на основе алгоритма Эрли. Я из него сделал инструмент, примерно аналогичный по функционалу Томита парсеру от Яндекса. Код рабочий, но какие-то вещи надо конечно доработать, что-то в интерфейсе добавить. Самому мне это делать трудно, сейчас времени мало. Если бы были энтузиасты, то я бы выложил код, написал бы про принципы реализации, ну и вместе что-то полезное сделали бы.
            +2
            Про морфологию напишу. Там есть несколько интересных вещей по аотовской модели. Ну и с технической точки зрения тоже наверное интересно кому-то будет.
          +1
          Одно интересно, зачем таким образом реализована функция Is, хотелось тупо побольше когда сгенерировать? Вообще нет никакого смысла в шаблонном параметре.
            0
            Там же чуть ниже есть примеры использования, например:
            return Is<LETTER>(code);
            
              0
              Текст прочитал, а в коде просмотрел inline, мой косяк, но всё равно, тут смысла в шаблонах нет. Можно и обычным аргументом прокинуть, будет Is(LETTER, code).
                0
                Думаю, автор посчитал свой вариант записи более красивым/понятным.
                  0
                  Там еще и неконсистентность в static const в том же заголовочном файле. Одна константа объявлена как static, а остальные нет. Хотя static вообще нигде там не нужен.
                  Но это мелочи :-)
                  –2
                  Ваш вариант гоняет на рантайме через стек два параметра, а вариант автора — один.
                    0
                    Почти наверняка функция будет заинлайнена и никаких параметров не будет в принципе.
                    P.S. Но на мой взгляд шаблон лучше хотя бы тем, что параметр class_name по сути является compile-time параметром и по природе ближе к non-type template parameter.
                      –1
                      Поддерживаю мысль по поводу шаблона. В одной из задач столкнулся с подобной дилеммой и после обдумывания тоже пришёл к выводу, что параметр, хоть и шаблонный, даёт больше гибкости, чем часть названия функции. А IsNumber() без шаблонных альтернатив может потом кого-нибудь и на макросы типа Is##type() спровоцировать.
                        0
                        Тут речь шла не о выборе между Is<NUMBER> и IsNumber, а о выборе между Is<NUMBER>(code) и Is(NUMBER, code).
                          0
                          Вообще упоминались в дискуссии и inline-функции автора, в форме IsNumber, о выборе между функциями такой сигнатурой и шаблонной функцией мне и хотелось сказать.
            • UFO just landed and posted this here
                0
                Ну, предполагалось, что для более полного представления юникода. Всякие там сурогаты можно класть. Хотя, на самом деле, хотел полной поддержки работы UTF-8 итератора, код которого (в виде синшных функций) я взялс unicode.org. Там есть такой код:
                // Go to loop of UTF-8 sequence reading.
                    uint32_t decoded_symbol = 0;
                    switch (extra_bytes_to_read) {
                      case 5:
                        symbol_.chain_[0] = *iter_;
                        decoded_symbol += static_cast<uint8_t>(*iter_);
                        decoded_symbol <<= 6;
                        if (not Next()) {
                          return;
                        }
                      case 4:
                        symbol_.chain_[extra_bytes_to_read-4] = *iter_;
                        decoded_symbol += static_cast<uint8_t>(*iter_);
                        decoded_symbol <<= 6;
                        if (not Next()) {
                          return;
                        }
                      case 3:
                        symbol_.chain_[extra_bytes_to_read-3] = *iter_;
                        decoded_symbol += static_cast<uint8_t>(*iter_);
                        decoded_symbol <<= 6;
                        if (not Next()) {
                          return;
                        }
                      case 2:
                        symbol_.chain_[extra_bytes_to_read-2] = *iter_;
                        decoded_symbol += static_cast<uint8_t>(*iter_);
                        decoded_symbol <<= 6;
                        if (not Next()) {
                          return;
                        }
                      case 1:
                        symbol_.chain_[extra_bytes_to_read-1] = *iter_;
                        decoded_symbol += static_cast<uint8_t>(*iter_);
                        decoded_symbol <<= 6;
                        if (not Next()) {
                          return;
                        }
                      case 0:
                        symbol_.chain_[extra_bytes_to_read] = *iter_;
                        decoded_symbol += static_cast<uint8_t>(*iter_);
                    }
                
                    // Magic numbers to process decoding.
                    static const uint32_t OFFSETS_FROM_UTF8[6] = {
                      0x00000000UL, 0x00003080UL, 0x000E2080UL, 0x03C82080UL, 0xFA082080UL, 0x82082080UL
                    };
                    decoded_symbol -= OFFSETS_FROM_UTF8[extra_bytes_to_read];
                
                    symbol_.len_ = extra_bytes_to_read + 1;
                
                    // Is the sequence legal?
                    if (IsLegalUtf8((const uint8_t*)symbol_.chain_, symbol_.len_)) {
                      // Increase symbol counter only, if correct symbol extracted.
                      symbol_.utf32_ = decoded_symbol;
                      ++sym_pos_;
                    }
                
                • UFO just landed and posted this here
                    0
                    Не очень понял комментарий. В таблице UnicodeData.txt используются коды, которые в два байта не помещаются. Например:
                    2FA1C;CJK COMPATIBILITY IDEOGRAPH-2FA1C;Lo;0;L;9F3B;;;;N;;;;;
                    2FA1D;CJK COMPATIBILITY IDEOGRAPH-2FA1D;Lo;0;L;2A600;;;;N;;;;;
                    E0001;LANGUAGE TAG;Cf;0;BN;;;;;N;;;;;
                    E0020;TAG SPACE;Cf;0;BN;;;;;N;;;;;
                    E0021;TAG EXCLAMATION MARK;Cf;0;BN;;;;;N;;;;;
                    


                    Старший код это
                    10FFFD;<Plane 16 Private Use, Last>;Co;0;L;;;;;N;;;;;
                    


                    Хотелось такие коды представлять естественным образом. Экономить на памяти 12 Мб против 24 Мб в наше время полагаю анахронизмом. Кому это надо, если chromium-browse у меня сейчас жрет 150 Мб, а thunderbird — 250?
                      0
                      Ну в каких-нибудь аналитических базах данных это может иметь весомое значение.
                        0
                        Mozilla, кстати, пошла в обратном направлении: раньше все строки были в UTF-16, а теперь чисто Latin1 строки хранятся в однобайтовой кодировке.
                        • UFO just landed and posted this here
                            0
                            Я не знаток JavaScript, просто так было написано в заметке, на которую я дал ссылку.
                            • UFO just landed and posted this here
                                +1
                                Там пишут про 2 разные вещи: JavaScript строки и Gecko строки. Заметка о том, что представление JavaScript строк изменилось, и как авторы сопрягали новое представление JavaScript строк с двухбайтовыми Gecko строками.

                                After converting all of SpiderMonkey’s string code, I had to make Gecko work with Latin1 JS strings and unstable string characters. Gecko has its own TwoByte string types and in many cases it used to avoid copying the JS characters by using a nsDependentString.


                                Так что прежде чем обвинять кого-то что он «не понял» неплохо бы вам самому убедиться, что вы сами поняли.
                                • UFO just landed and posted this here
                                    0
                                    Вы категорически не правы (цитата из стандарта):

                                    8.4
                                    The String Type

                                    The String type is the set of all finite ordered sequences of zero or more 16-bit unsigned integer values (―elements‖). The String type is generally used to represent textual data in a running ECMAScript program, in which case each element in the String is treated as a code unit value (see Clause 6). Each element is regarded as occupying a position within the sequence. These positions are indexed with nonnegative integers. The first element (if any) is at position 0, the next element (if any) at position 1, and so on. The length of a String is the number of elements (i.e., 16-bit values) within it. The empty String has length zero and therefore contains no elements.

                                    When a String contains actual textual data, each element is considered to be a single UTF-16 code unit. Whether or not this is the actual storage format of a String, the characters within a String are numbered by their initial code unit element position as though they were represented using UTF-16. All operations on Strings (except as otherwise stated) treat them as sequences of undifferentiated 16-bit unsigned integers; they do not ensure the resulting String is in normalised form, nor do they ensure language-sensitive results.
                                    • UFO just landed and posted this here
                                        0
                                        Если вы дочитаете до конца статью, откуда, возможно, взяли пример до исправления (который на моей системе показывался корректно, то есть проблема не в хабре, скорее всего), то обнаружите:

                                        Conclusion

                                        JavaScript engines are free to use UCS-2 or UTF-16 internally. Most engines that I know of use UTF-16, but whatever choice they made, it’s just an implementation detail that won’t affect the language’s characteristics.

                                        The ECMAScript/JavaScript language itself, however, exposes characters according to UCS-2, not UTF-16.


                                        Что никаким образом не противоречит исходному утверждению, что в Mozilla строки в JavaScript были в UTF-16.
                                      0
                                      utf-8 является де-факто стандартом для исходников в web-разработке, но не в строковом типе.
                          • UFO just landed and posted this here
                              +1
                              Тон какой-то выбран излишне агрессивный, что-то личное? По теме, я не специалист по UNICODE, понятное дело, но вроде UTF-8 кодировку от UTF-16 отличить могу. Ниже я приводил код из программы, которая перекодирует UTF-8 последовательности в UTF-32 коды. Из кода видно, что в UTF-8 может использоваться до шести байтов включительно (даже не четыре, бывает и шесть), чтобы закодировать символ UNICODE. Именно для этой цели я и приводил код. Рассчитывал, что человек, который понимает UNICODE, видел и их код на C для перекодирования UTF-8 в UTF-32. Ну, наверное, просто опыта с C++ нет, потому и весь код мимо.

                              В кодировке UTF-16 для некоторых символов, коды которых не вмещаются в 2^16, используется четыре байта. Для эффективного кодирования классификатора символов на UTF-16 надо сделать нечто более сложное, чем просто обращение к ячейке памяти по коду (как это делается в UTF-32). Наверное, надо сделать сравнение на определенное число, если код больше этого числа, перейти на вектор дополнительных кодов для данного кода и найти соответствующий класс. Это все займет время и будет не так эффективно.

                              Вообще, в массиве классов хранятся не коды символов, а флаги классов для каждого символа, которые в любом случае занимают 4 байта и, собственно, к коду символа не имеют никакого отношения. А дискуссию относительно преимуществ и недостатков использования UTF-32 для классификации можно прочитать на сайте UNICODE, там приведены соответствующие соображения.

                    Only users with full accounts can post comments. Log in, please.