Правильное нестрогое сопоставление юникодных строк в 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

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