Правильное нестрогое сопоставление юникодных строк в C++

Я имею в виду поиск алгоритма из набора существующих библиотек, который посчитает, что строки Семён зна́ет и семен знает равны, и сможет найти строку Знает в первой из них. Никакие strncasecmp() и iequals() в таком сравнении строк не помогут, я уже молчу о поиске подстроки — представьте, как вы будете искать подстроку с возможно измененными символами возможно другой длины в байтах! Вообще говоря, приведенный выше тип сравнения сравнением не является. В самом деле, игнорирование умляутов и преобразование произвольных букв из набора Unicode в разные регистры должны предполагать некоторую эвристику. Я не зря не использовал термин сравнение в заголовке статьи. Потому что это сопоставление, или, по-латински, коллация (collation). Объект, выполняющий коллацию, называется коллатором. Обычно существует несколько уровней коллации, начиная от самого либерального (первичный или primary) и заканчивая самым жестким, требующим полной идентичности всех символов (identical). Я не в курсе, кто изобрел эту концепцию, но она точно присутствует в библиотеке интернационализации ICU (см. документацию к классу icu::Collator). Библиотека boost::locale тоже предоставляет такой интерфейс (см. здесь), но это и не удивительно, поскольку libboost_locale, будучи слинкована с библиотеками libicuuc и libicui18n, по-видимому, просто оборачивает алгоритмы ICU. Давайте реализуем предложенное в начале статьи сравнение строк с помощью boost::locale.

#include <boost/locale.hpp>
#include <iostream>

using namespace  boost::locale;


namespace
{
    generator                 gen;
    std::locale               loc( gen( "" ) );
    const collator< char > &  col( std::use_facet< collator < char > >( loc ) );
}


int  main( void )
{
    std::string  a( "Семён зна́ет" );
    std::string  b( "семен знает" );

    bool  eq( col.compare( collator_base::primary, a, b ) == 0 );

    std::cout << a << " and " << b << " are " <<
            ( eq ? "identical" : "different" ) << " on primary comparison" <<
            std::endl;

    eq = col.compare( collator_base::secondary, a, b ) == 0;

    std::cout << a << " and " << b << " are " <<
            ( eq ? "identical" : "different" ) << " on secondary comparison" <<
            std::endl;

    std::string  c( "приём!" );

    std::cout << to_upper( c, loc ) << std::endl;
}

Внутри анонимного пространства имен определены базовые объекты boost::locale: генератор локалей gen, локаль loc, инициализируемая системной локалью (да, я предполагаю, что системной локалью является UTF-8), и ссылка на коллатор col. Внутри функции main() мы сравниваем строки с Семёном, используя первичный и вторичный уровни коллации в предположении, что в первом случае строки должны оказаться равными, а во втором нет за счет замены ё на е и снятия ударения над а. В самом низу мы также проверим, что функция boost::locale::to_upper() правильно переводит строку приём! в верхний регистр. Поместим данный исходный код в файл test.cc и скомпилируем.

g++ -Wall -o test test.cc -lboost_locale

Теперь запустим программу на выполнение.

./test
Семён зна́ет and семен знает are identical on primary comparison
Семён зна́ет and семен знает are different on secondary comparison
ПРИЁМ!

Работает! Теперь давайте искать подстроки в строке Семён зна́ет. Идею я взял из этого комментария. Вверху программы добавим новые инклюды.

#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

Ниже определим тело функции find().

bool  find( const std::vector< std::string > &  p, const std::string &  s,
            collator_base::level_type  level = collator_base::primary )
{
    std::size_t  pos( 0 );
    std::string  snorm( col.transform( level, s ) ); 

    std::size_t  ssize( snorm.size() - 1 );
    std::size_t  len( ssize );

    for ( std::vector< std::string >::const_iterator  k( p.begin() );
          k != p.end(); ++k )
    {
        std::string  pnorm( col.transform( level, *k ) );
        std::size_t  psize( pnorm.size() - 1 );

        if ( psize > len )
            return false;

        std::string  scur( std::string( snorm, pos, len ) );
        std::size_t  scur_pos( scur.find( pnorm.c_str(), 0, psize ) );

        if ( scur_pos == std::string::npos )
            return false;

        std::size_t  shift( scur_pos + psize );

        pos += shift;
        len -= shift;
    }

    return true;
}

На вход find() подается ссылка на вектор искомых подстрок p, строка s, в которой будет осуществляться поиск, а также уровень коллации level. Внутри функции find() из строки s с помощью метода transform() коллатора col формируется новая бинарная строка snorm, внутри которой в цикле по всем элементам вектора p формируются соответствующие бинарные строки pnorm, которые последовательно ищутся в строке snorm обычным методом std::string::find(). Согласно автору приведенного комментария, строки snorm и pnorm содержат в конце ненужные нулевые символы, поэтому все сравнения производятся с подстроками snorm и pnorm без последнего символа (для этого объявлены дли́ны ssize и psize). Внизу функции main() добавляем код, тестирующий функцию find().

    std::vector< std::string >  parts;

    parts.push_back( "емен" );
    parts.push_back( "Зн" );
    parts.push_back( "ет" );

    bool  in( find( parts, a ) );

    std::cout << a << ( in ? " contains " : " does not contain " );
    std::copy( parts.begin(), parts.end(),
               std::ostream_iterator< std::string >( std::cout, " " ) );
    std::cout << "on primary comparison" << std::endl;

Вектор искомых подстрок parts состоит из трех элементов: емен, Зн и ет. Они должны быть найдены в строке a при использовании первичной коллации. Я не стал добавлять проверку вторичной коллации, потому что … Скомпилируем и запустим программу.

./test
Семён зна́ет and семен знает are identical on primary comparison
Семён зна́ет and семен знает are different on secondary comparison
ПРИЁМ!
Семён зна́ет does not contain емен Зн ет on primary comparison

Потому что наша find() не работает! Если вы думаете, что я где-то ошибся, попробуйте вставить поиск подстроки емен в строке Семён зна́ет в исходный код оригинального примера. Этот поиск не сработает. В этом треде автор вопроса утверждает, что после трансформации строки методом transform() на ее хвосте появляется не одиночный нулевой символ, а сразу несколько разных, в том числе не нулевых, символов. Главным результатом является один из ответов на этот вопрос, в котором утверждается, что transform() не гарантирует возможность поиска подстрок, являясь лишь инструментом для сопоставления строк. Получается, boost::locale не предоставляет возможности для нестрого поиска подстрок внутри юникодной строки. Что же тогда делать? А давайте обратимся к ICU, на которой, как мы увидели, основан boost::locale. Добавляем новые инклюды

#include <unicode/unistr.h>
#include <unicode/stsearch.h>
#include <unicode/coll.h>

, объявляем использование нового пространства имен

using namespace  icu;

, пишем новую функцию find_icu().

bool  find_icu( const std::vector< std::string > &  p, const std::string &  s,
                Collator::ECollationStrength  strength = Collator::PRIMARY )
{
    int32_t        pos( 0 );
    UnicodeString  su( UnicodeString::fromUTF8( StringPiece( s ) ) );

    for ( std::vector< std::string >::const_iterator  k( p.begin() );
          k != p.end(); ++k )
    {
        UnicodeString  pu( UnicodeString::fromUTF8( StringPiece( *k ) ) );
        UErrorCode     status( U_ZERO_ERROR );

        StringSearch   it( pu, UnicodeString( su, pos ), Locale::getDefault(),
                           NULL, status );

        it.getCollator()->setStrength( strength );

        int32_t        scur_pos( it.first( status ) );

        if ( scur_pos == USEARCH_DONE )
            return false;

        pos += scur_pos + it.getMatchedLength();
    }

    return true;
}

Здесь много новых типов, но логика не отличается от логики функции find(). Вместо строки snorm здесь мы создаем юникодную строку su, в цикле по элементам вектора p вместо строк pnorm создаются юникодные строки pu. Собственно поиск осуществляется с помощью метода first() итератора it типа StringSearch. Вместо длины строки pu к значению pos прибавляется значение, возвращаемое методом getMatchedLength() итератора it. Уровень коллации в ICU называется строгостью (strength), поэтому мы заменили название переменной level на strength. Вставим полноценную проверку поиска подстрок функцией find_icu() в main().

    in = find_icu( parts, a );

    std::cout << a << ( in ? " contains " : " does not contain " );
    std::copy( parts.begin(), parts.end(),
               std::ostream_iterator< std::string >( std::cout, " " ) );
    std::cout << "on ICU primary comparison" << std::endl;

    in = find_icu( parts, a, Collator::SECONDARY );

    std::cout << a << ( in ? " contains " : " does not contain " );
    std::copy( parts.begin(), parts.end(),
               std::ostream_iterator< std::string >( std::cout, " " ) );
    std::cout << "on ICU secondary comparison" << std::endl;

Компилируем программу

g++ -Wall -o test test.cc -lboost_locale -licuuc -licui18n

(заметили линковку новых библиотек?), и запускаем ее на выполнение.

./test
Семён зна́ет and семен знает are identical on primary comparison
Семён зна́ет and семен знает are different on secondary comparison
ПРИЁМ!
Семён зна́ет does not contain емен Зн ет on primary comparison
Семён зна́ет contains емен Зн ет on ICU primary comparison
Семён зна́ет does not contain емен Зн ет on ICU secondary comparison

Вот теперь все работает! Исходный код тестовой программы можно скачать отсюда.

Несколько трюков с пакетом Latex Listings

Здесь я хочу показать три трюка с пакетом Listings, которые мне очень пригодились при определении “языка” для подсветки действий пользователя внутри командных оболочек и REPLов. Этот виртуальный язык, который я назвал shelloutput, может быть использован в плагине publish-helper. Некоторые сведения о реализации подсветки shelloutput в Listings приведены в разделе Highlighting shells and REPLs на главной странице проекта в github, там же приведен пример с картинками. Итак, определение псевдоязыка shelloutput — это и есть первый трюк, о котором я расскажу. Постановка задачи такова: обеспечить декоративное выделение блоков текста, изображающих действия пользователя внутри любых командных оболочек и REPLов, а также разделение текста с вводом пользователя (промпта) и выводом оболочки. Первая часть задачи решается без определения свойств языка и, соответственно, без участия пакета Listings. Простейший способ — определить новое окружение, внутри которого использовать какой-либо рамочный пакет, например пакет Framed.

\usepackage{framed}
\newenvironment{Leftbar}{
  \setlength\parskip{0pt}
  \setlength\OuterFrameSep{4pt}
  \setlength\partopsep{-\topsep}
  \begin{leftbar}
    \scriptsize
}{\end{leftbar}}

Это окружение, которое я назвал Leftbar, поскольку оно использует стиль leftbar из пакета Framed, должно находиться в преамбуле документа. Теперь, чтобы выделить блок текста с действиями пользователя в оболочке, нужно обернуть этот текст в тэги \begin{Leftbar} ... \end{Leftbar}. Перейдем к решению второй части задачи. Нам нужно определить новый язык, который мы сможем использовать в окружении lstlisting, которое, в свою очередь, мы будем помещать внутрь окружения Leftbar. Пусть основной стиль (basicstyle) языка shelloutput будет относиться к выводу оболочки, а стиль для ввода оболочки мы определим отдельно. Самое сложное здесь — это понять, как мы (и Listings) будем отличать ввод оболочки от вывода: промпты у всех оболочек разные и могут отсутствовать вообще. Поэтому мы не будем ориентироваться на промпт, а введем собственный виртуальный промпт, который будем вставлять в начало каждой строки, соответствующей вводу оболочки — ведь мы то знаем, где у нее ввод и вывод! В Listings есть опция moredelim, с помощью которой мы определим внешний вид ввода оболочки, передав ей наш виртуальный промпт (пусть это будет три бара и пробел — ‘||| ’) с флагами il, которые устанавливают, что Listings не должен показывать виртуальный промпт (i), и установки будут действовать в пределах всей строки (l). Вот как это может выглядеть в преамбуле документа:

\usepackage{listings}
\definecolor{shellpromptcolor}{HTML}{000000}
\definecolor{shelloutputcolor}{HTML}{666666}
\lstdefinelanguage{shelloutput}
  {basicstyle=\color{shelloutputcolor}
    \scriptsize
    \ttfamily\itshape,
   moredelim=[il][\color{shellpromptcolor}\upshape]{|||\ }}

В данном случае вывод оболочки будет подсвечен серым цветом и иметь наклонное начертание, в то время как ввод будет черным и прямым. Давайте добавим сюда небольшой, но красивый бонус — декоративные переносы строк. Для этого в преамбулу документа нужно добавить

\usepackage{MnSymbol}
\lstset{prebreak=\raisebox{0ex}[0ex][0ex]
  {\ensuremath{\rhookswarrow}}}
\lstset{postbreak=\raisebox{0ex}[0ex][0ex]
  {\ensuremath{\rcurvearrowse\space}}}

Пример использования подсветки виртуального языка shelloutput можно найти в разделе An example на странице разработки проекта vim-publish-helper. В этом примере документ, представленный на втором изображении, генерируется не напрямую из документа TeX, а опосредованно, через pandoc flavoured markdown, но результат будет совпадать независимо от языка исходного документа. Второй трюк. Listings преобразует символ переноса (-) в знак минус. Это разумно для многих языков, однако для нашего псевдоязыка shelloutput это выглядит некрасиво, во всяком случае в опциях команд оболочки, таких как ls -l --inode. Вернуть исходный символ переноса достаточно просто — определив опцию literate={-}{-}1 в преамбуле документа или внутри окружения lstlisting, однако этот простой подход ломает настройки alsoletter={-} и breakatwhitespace для символов переноса, что приводит к возможности обрыва строк при переносе на этих символах, а это выглядит очень некрасиво. Лучше всего определить макрос lst@CCPutMacro для символа переноса (фактически переопределить его, так как он уже определен — и в этом-то и проблема — в исходном коде listings.sty). Определение следует поместить в нашем окружении Leftbar, чтобы оно не повлияло на другие языки. Теперь Leftbar будет выглядеть так:

\makeatletter
\newenvironment{Leftbar}{
  \setlength\parskip{0pt}
  \setlength\OuterFrameSep{4pt}
  \setlength\partopsep{-\topsep}
  \lst@CCPutMacro\lst@ProcessLetter {"2D}{\lst@ttfamily{-{}}{-{}}}
  \@empty\z@\@empty
  \begin{leftbar}
    \scriptsize
}{\end{leftbar}}
\makeatother

Третий трюк. Русские символы (и вообще UTF-8) в выводе (и вводе) языка shelloutput. Оказывается, Listings до сих пор не поддерживает нормальную обработку национальных символов в формате UTF. Если в shelloutput встретятся русские символы, то они будут переставлены всевозможными способами с удалением пробелов и добавлением неожиданных новых строк. Проблема известная и есть вариант ее решения с помощью опции literate (см. здесь и здесь). Однако, этот способ очень verbose — лично мне он не нравится. Более простое и рабочее решение — использовать опцию escapeinside=|| в объявлении lstlisting, а внутри блока с текстом обрамлять участки с проблемными символами соответствующими эскейп-символами, в данном случае барами (|) и, возможно, внутри них тэгом \verb, который не позволит слипнуться множественным пробелам.