Алгоритм Крускала для невзвешенного графа на haskell

Очередная задачка от 1HaskellADay. В условии задан список ребер графа. Многие пути вдоль ребер предположительно зациклены, то есть если есть два пути от a к b и от b к c, то, возможно, в списке присутствует также путь от a к c; сюда же относятся вырожденные циклы, когда имеется несколько путей от a к b, либо имеются обратные пути от b к a. Целью задачи является удаление лишних (redundant) ребер графа, которые приводят к появлению циклов. Очевидно, разрешение цикла всегда связано с удалением произвольного ребра: скажем, в случае цикла (a, b, c) его разрешением может стать удаление любого из трех ребер (a, b), (b, c) и (a, c). Алгоритм Крускала находит минимальное остовное дерево (minimum spanning tree) для взвешенного неориентированного графа. Давайте предположим, что нам неважны направления ребер. В этом случае, принимая во внимание, что невзвешенный граф — это частный случай взвешенного, а дерево — это связный ациклический граф, алгоритм Крускала идеально подходит для решения нашей задачи. Напомню его суть. В случае взвешенного графа все ребра предварительно сортируются по весу (этот шаг гарантирует построение минимального дерева). Затем проходом по всем ребрам строится лес, постепенно объединяющийся в единое дерево, либо в список крупных деревьев, если исходный граф несвязан. В процессе прохода может оказаться, что очередное ребро сформирует цикл — в этом случае оно просто отбрасывается. Как определить, что ребро может сформировать цикл? Перед началом прохода все вершины (vertices) графа заносятся в специальную структуру, которая называется disjoint set. Эта структура представляет собой один или более наборов чисел, каждый из которых имеет своего представителя (representative) — это число, которое является меткой набора. На старте алгоритма все вершины разъединены и, составляя отдельные наборы, выставляют в качестве представителя самих себя. В процессе прохода по всем ребрам отдельные наборы будут объединяться, выбирая в качестве представителя одну из вершин в объединенном наборе. Соответственно, если в процессе прохода обеим вершинам очередного ребра соответствует один и тот же представитель, то это ребро отбрасывается, иначе обе вершины объединяются. Структура disjoint set гарантирует, что если одна из вершин уже была объединена в некоторый набор, то в случае ее объединения с другой вершиной, эта другая вершина вместе с набором, к которому она относится, объединится с первым набором, возможно сформировав нового представителя. Так постепенно формируется единый набор вершин (или несколько крупных). Алгоритм для работы с disjoint set часто называют union-find. Он гарантирует константное время объединения и поиска представителя. Я не собираюсь его здесь реализовывать, а лучше возьму одну из многочисленных существующих реализаций для языка haskell: Data.UnionFind.IO. Представленная в этом модуле реализация disjoint set не поддерживает поиск представителя для произвольного числа: только числа, уже добавленные в набор, корректно возвращают своего представителя. Поскольку мы добавляем все вершины в набор на старте, нам достаточно создать Map, ключами которого будут числа-вершины, а значениями — представления этих чисел в наборе disjoint set. Таким образом, мы сможем находить представителей вершин в процессе прохода по ребрам графа за логарифмическое время. Учитывая линейность прохода по ребрам, общий класс алгоритма должен соответствовать $O(n\log{}m)$, где n — число ребер исходного графа, а m — число вершин. Вот исходный код функции deredundancify, которая из исходного списка ребер строит список всех вершин графа и остовное дерево.

deredundancify :: [Edge] -> IO ([Vertex], [Edge])
deredundancify es = do
    let vs = map head . group . sort $ foldr (\(a, b) c -> a : b : c) [] es
    ps <- mapM fresh vs
    m  <- liftM M.fromList $ mapM (\a -> do b <- descriptor a; return (b, a)) ps
    let testNotCycle (a, b) = do
            let pa = fromJust $ M.lookup a m
                pb = fromJust $ M.lookup b m
            da <- descriptor pa
            db <- descriptor pb
            if da == db
                then return False
                else do
                    pa `union` pb
                    return True
    rs <- filterM testNotCycle es
    return (vs, rs)

Для того, чтобы все скомпилировалось, перед определением функции нужно добавить импорт некоторых модулей и определить синонимы типов Vertex и Edge.

import            Control.Monad               (liftM, filterM)
import            Data.List                   (sort, group)
import qualified  Data.Map                    as M
import            Data.UnionFind.IO
import            Data.Maybe                  (fromJust)

type Vertex = Int
type Edge   = (Int, Int)

Внутри функции deredundancify сначала строится список вершин vs, затем все вершины заносятся в структуру ps с помощью функции fresh из модуля Data.UnionFind.IO. Затем строится Map m, ключами которого являются представители (descriptor) исходного набора ps (которые вначале должны просто соответствовать вершинам vs), а значениями — исходные наборы из ps. Основная работа функции deredundancify заключается в формировании списка ребер rs, который будет соответствовать искомому остовному дереву. Список rs строится за счет применения фильтра testNotCycle к исходному списку ребер es. Фильтр testNotCycle ищет наборы pa и pb внутри m, получает их дескрипторы da и db и сравнивает их. Если дескрипторы равны, то данное ребро отбрасывается (функция возвращает False), иначе — pa и pb объединяются (union) и данное ребро заносится в список для остовного дерева (функция возвращает True). Собственно, это и есть решение задачи. Но давайте подумаем, как мы его проверим. Из большого списка ребер мы получим список чуть поменьше. И что нам с ним делать? Нужна какая-то визуализация. Очевидное решение — использовать GraphViz. В haskell есть байндинг для GraphViz. Давайте напишем функцию, которая будет выводить текст в формате dot, который GraphViz сможет использовать для изображения графов. Прежде всего, подключим модули GraphViz.

import            Data.Graph.Inductive        hiding (Edge)
import            Data.GraphViz
import            Data.GraphViz.Attributes
import            Data.GraphViz.Printing      (renderDot)
import            Data.Text.Lazy              (Text, unpack, pack)
import            System.Environment          (getArgs)

Последний импорт понадобится в функции main для парсинга аргументов командной строки. Вот функция mkDot.

mkDot :: [Vertex] -> [Edge] -> [GlobalAttributes] -> DotGraph Node
mkDot vs es attrs =
    let lvs = map (\a -> (a, pack $ show a)) vs
        les = map (\(a, b) -> (a, b, ())) es
        gr  = mkGraph lvs les :: Gr Text ()
    in graphToDot nonClusteredParams {globalAttributes = attrs} gr

Она принимает список вершин, список ребер и атрибуты GraphViz и возвращает промежуточное представление для данных dot. Давайте напишем функцию main, которая сможет выводить данные dot на экран.

main = do
    args     <- getArgs
    (vs, rs) <- deredundancify theGraph
    let attrs = [EdgeAttrs
                    [edgeEnds $ if "-l" `elem` args then NoDir else Forward]]
        dot   = mkDot vs (if "-o" `elem` args then theGraph else rs) attrs
    putStrLn $ unpack $ renderDot $ toDot dot

Теперь, после компиляции исходного кода, предварительно включив в него список ребер исходного графа theGraph, можно вывести исходный граф и искомое остовное дерево на картинку. Получение картинки исходного графа.

./deredundancify -o | dot -Tpng > original.png

Получение картинки остовного дерева исходного графа.

./deredundancify | dot -Tpng > deredundancified.png

Картинки для исходного дерева, представленного в оригинальном примере, получаются очень большими, поэтому я их положил на Google Drive: исходный граф, остовное дерево. Посмотрите и сравните: по картинкам становится понятно, что такое большое остовное дерево. Кстати, на выложенных картинках все ребра направлены, но по условиям нашей задачи граф неориентирован, поэтому по-хорошему стрелки на ребрах должны отсутствовать. Не проблема, если хотите картинки без стрелок — используйте опцию -l при вызове deredundancify. Исходный код решения задачи можно загрузить отсюда или отсюда. Update. Как обычно, ряд улучшений в исходном коде уже после публикации статьи. Все они касаются функции deredundancify. Во-первых, создание структуры ps для uninon-find и ассоциативного массива m можно объединить. Это потому, что вначале все наборы внутри ps состоят из отдельных вершин и их представителями являются собственно сами эти вершины. Во-вторых, я предпочитаю избегать конструкцию if-then-else в haskell. В данном случае в функции testNotCycle вместо нее можно определить логическую константу, применив оператор liftM2 (==) или liftM2 (/=) к значениям представителей вершин ребра, а необходимость объединения вершин определять с помощью функции when из модуля Control.Monad. Функция liftM2 определена в этом же модуле. Чтобы не плодить список импортированных из него функций, лучше переписать его импорт как

import            Control.Monad

В-третьих, поиск внутри m можно переписать в стрелочном стиле. Для этого нужно включить еще один импорт.

import            Control.Arrow

Я писал про стрелки в haskell в предыдущей статье. Теперь функция deredundancify выглядит так.

deredundancify :: [Edge] -> IO ([Vertex], [Edge])
deredundancify es = do
    let vs = map head . group . sort $ foldr (\(a, b) c -> a : b : c) [] es
    m  <- liftM M.fromList $ mapM (\v -> do p <- fresh v; return (v, p)) vs
    let testNotCycle e = do
            let ve = both (fromJust . flip M.lookup m) e
            notCycle <- uncurry (liftM2 (/=)) $ both descriptor ve
            when notCycle $ uncurry union ve
            return notCycle
            where both = join (***)
    rs <- filterM testNotCycle es
    return (vs, rs)

Я заменил запись аргумента функции testNotCycle (a, b) на e, поскольку стрелочная нотация прекрасно работает с кортежами и в ней не требуется знать его (кортежа) отдельные элементы. Функция both заворачивает стрелочный комбинатор (***) в функцию join из модуля Control.Monad, таким образом применяя свой аргумент-функцию к обоим элементам кортежа. И еще одна техника, которая позволит переписать монадные вычисления внутри отображения mapM при вычислении m в бесточечном стиле. Это стрелки Клейсли. Они импортируются из модуля Control.Arrow по умолчанию. Основная идея заключается в оборачивании всех функции, возвращающих монадные значения в тип Kleisli, а само монадное вычисление — в конструктор runKleisli, который возвращает монадный тип из комбинации стрелок.

m  <- liftM M.fromList $ mapM (runKleisli $ arr id &&& Kleisli fresh) vs

Здесь из функции id создается обычная стрелка с помощью явного конструктора arr. Несмотря на то, что функции являются стрелками, и мы ни разу до этого не использовали явные конструкторы стрелок в отношении функций, в данном случае без них не обойтись — ghc откажется компилировать код. Другая стрелка — стрелка Клейсли — создается из функции fresh, возвращающей монадное значение IO (Point a). Обе стрелки комбинируются стрелочным комбинатором (&&&). На выходе runKleisli получаем монадное вычисление пары (входное значение (то есть вершина), элемент структуры union-find). Не думаю, что новое тело функции deredundancify понятней, чем предыдущее (скорее наоборот), зато оно явно лаконичней. Ну и напоследок упражнение: записать тело функции правой свертки (\(a, b) c -> a : b : c), которую мы использовали для получения списка всех вершин графа, в бесточечном стиле с помощью стрелок. Причем с сохранением семантики и эффективности: то есть числа a и b должны стыковаться со списком c в заданном порядке, а конструкторы списка (:) нельзя заменять на операции конкатенации (++). Я напишу ответ, но не стану его объяснять.

curry $ fst . fst &&& uncurry ((:) . snd) >>> uncurry (:)

А это бесточечное решение без использования стрелок, тоже без объяснения.

let (<:) = flip (:) in flip $ uncurry . flip . ((<:) .) . (<:)

Update 2. Я все-таки решил привести здесь уменьшенные варианты изображений оригинального графа и его осто́вного дерева в дополнение к приведенным выше ссылкам на большие изображения, которые оказались настолько большими, что вставлять их в статью было бы просто безумием. Новые изображения обязаны своей компактностью выбору движка для рендеринга sfdp вместо стандартного dot, отказу от прорисовки форм вершин графа (вернее, теперь это форма point) и их идентификаторов, а также выбору полупрозрачных цветов для ребер и вершин. Чтобы достичь этого, мне пришлось внести небольшие дополнения в исходный код программы. Итак, изображение исходного графа без идентификаторов вершин, полученное как

./deredundancify -o -t | sfdp -Tpng > original_tiny.png

А это осто́вное дерево, полученное как

./deredundancify -t | sfdp -Tpng > deredundancified_tiny.png

На первой картинке много синих линий-ребер, на второй их практически не видно, зато красные кружки́-вершины связаны в более длинные цепочки. Все это выглядит здо́рово и весьма достоверно.

Стрелки (arrows) и бесточечная (pointfree) нотация в haskell на конкретном примере

Стрелка — это модель обобщения вычислительного процесса, когда на вход вычисления может подаваться сразу несколько входных данных (например, в виде кортежа), а сам процесс вычисления строится с помощью комбинаторов типа first, second, (***), (&&&) и (>>>). Бесточечная нотация — это когда при записи функции в выражении (в том числе в ее определении), аргументы опускаются и, соответственно, не связываются (bind) в выражении. Поскольку стрелка абстрагирует входные данные, она выглядит хорошим кандидатом для применения в бесточечной нотации. Рассмотрим применение стрелки и бесточечной нотации на простом примере. Я взял его из очередного твита в 1HaskellADay. Задача простейшая — вывести на экран счет от целого числа from до целого числа to без использования явных циклов. Явные циклы в haskell, да и вообще в функциональном программировании, очень не приветствуются, поскольку относятся к миру императивного программирования. Поэтому данная задача выглядит простой и, в общем-то, таковой и является. Так как я собираюсь привести несколько решений, имеет смысл написать осто́вную функцию count, которая будет принимать основную функцию вычисления счета, передавать ей входные значения from и to, и выводить счет на экран.

count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count f from to = mapM_ print $ f from to

Здесь можно добавить проверку на то, что from меньше to, но я этого не сделал для простоты. Самую очевидную реализацию функции f я назвал cheating, поскольку в ней используется синтаксический сахар, предоставленный самим языком как раз для создания непрерывно возрастающего списка от некоторого числа m до некоторого числа n.

cheating from to = [from .. to]

Совершенно очевидное и незамысловатое решение. Его можно проверить в ghci или в функции main с помощью вызова

count cheating 1 10

Теперь простое решение без использования сахара haskell.

simple from to = takeWhile (<= to) . iterate succ $ from

Тоже несложно. Функция iterate succ строит бесконечный непрерывно увеличивающийся список, который начинается со значения from. Этот список трассируется функцией takeWhile до тех пор, пока выполняется предикат в скобках, то есть пока очередное значение в списке не превысит to. Обе функции cheating и simple просты и хороши. Но я бы хотел видеть их в бесточечной нотации, то есть без явного указания и связывания аргументов from и to. К сожалению, это невозможно, поскольку в первом случае синтаксис построения списка-диапазона требует указания обоих значений, а во втором случае значение to используется внутри предиката в самом центре тела функции. И здесь на помощь приходят стрелки! Для их использования необходимо импортировать модуль Control.Arrow.

import Control.Arrow

Я приведу тело функции arrowedPointfree, а ниже объясню, что в нем происходит.

arrowedPointfree = curry $ iterate succ *** (>=) >>> uncurry (flip takeWhile)

Видите, никаких from и to. Они неявно присутствуют в определении функции, но не связаны внутри ее тела. Оба аргумента склеиваются функцией curry в кортеж и передаются в вычислительный процесс, собранный из функций и стрелок, который начинается за символом $. Следуя традиции графического изображения стрелочных вычислений (см. здесь), я представлю (в меру своих художественных способностей) этот процесс вычисления на картинке.

Итак, кортеж (from, to) поступает на вход стрелочного комбинатора (***). Первый элемент кортежа (from) поступает на вход функции iterate succ, формируя бесконечный возрастающий список [from ..], второй (to) — на вход функции (>=), формируя новую функцию (>=) to. Заметьте, в функции simple мы использовали сечение (<= to). Наша новая функция эквивалентна сечению (to >=), что соответствует предикату из simple. На выходе комбинатора (***) новый кортеж ([from ..], (>=) to) поступает на оператор композиции (>>>), который передает вычисление в функцию uncurry. Функция uncurry декомпонует кортеж в последовательность двух аргументов (я изобразил это сужением вычислительного конвейера) и вызывает функцию flip takeWhile. Функция flip нужна для того, чтобы переставить аргументы [from ..] и (>=) to местами, сформировав takeWhile ((>=) to) [from ..]. Дело сделано! Не находите это решение красивым? Лично я нахожу. Это несмотря на то, что функции cheating и simple выглядят и проще, и понятнее. Но здесь нам удалось абстрагироваться от входных данных и сосредоточиться на потоке вычислений. Да, поначалу стрелки выглядят сложными, но только до тех пор, пока процесс вычисления не представлен графически. Есть еще один аспект. Часто в погоне за возможностью выразить код в бесточечном стиле (pointfree), программисты вынужденно усложняют понимание исходного кода, превращая его в pointless (бессмысленный). Поначалу я случайно назвал функцию arrowedPointfree arrowedPointless, и не сразу оценил всю глубину смысловой нагрузки этой оговорки. В этой статье приводится пример подобного усложнения (по мнению автора) и также обыгрываются синонимы pointfree и pointless. С другой стороны, невозможность записать выражение в бесточечном стиле может свидетельствовать об излишней монолитности функции. Попробуйте записать определение нашей осто́вной функции count в бесточечном стиле. Например,

count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count = mapM_ print

Этот вариант просто не скомпилируется: ghc пожалуется на то, что в функцию map передается слишком много аргументов. Максимальный уровень бесточечности, который можно выжать в определении функции count с такой сигнатурой, заключается в возможности опустить последний аргумент to, соединив mapM_ print и f from оператором (.).

count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count f from = mapM_ print . f from

Почему мы не можем выразить определение count в бесточечном стиле? Потому что мы намеренно усложнили ее определение, фактически объединив две разные функции в одну. Но в общем случае, зачем функции count знать о какой-то другой функции, принимающей какие-то аргументы и возвращающей список [Int]? Ей достаточно знать последний факт, то есть то, что она работает со списком целых чисел. Исходя из этого, определение count можно переписать в виде

count :: [Int] -> IO ()
count = mapM_ print

Вот и бесточечная нотация! Глядя на такое простое определение, мы можем заключить, что функция count нам вообще не нужна, это же просто mapM_ print, которую можно комбинировать напрямую в месте вызова. Например,

mapM_ print $ arrowedPointfree 1 10

Правда, в этом варианте пропало слово счет (count), но это уже вопрос правильного именования функций: при отсутствии осто́вной функции все функции счета следует переименовать.

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

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