Привет, Хабр. Будущих студентов курса "C++ Developer. Professional" приглашаем записаться на открытый урок по теме "Backend на современном C++"

А пока делимся традиционным переводом полезного материала.

Регулярные выражения (Regular expressions или, вкратце, regex регулярки) это пока что непопулярная и недооцененная тема в современном C++. Но в то же время разумное использование регулярных выражений может избавить вас от написания множества строчек кода. Если у вас уже есть какой-никакой опыт работы в индустрии, но вы не умеете использовать регулярные выражения вы разбазариваете 20-30% своей продуктивности. Я настоятельно рекомендую вам освоить регулярные выражение, так как это единовременная инвестиция в себя (по известному принципу learn once, write anywhere).

/!\: Изначально эта статья была опубликована в моем личном блоге. Если вам станет интересно и дальше читать мои самые актуальные статьи, вы можете подписаться на мою рассылку.

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

Примечание: стандартная библиотека C++ предлагает несколько различных разновидностей ("flavours") синтаксиса регулярных выражений, но вариант по умолчанию (тот, который вы всегда должны использовать, и который я демонстрирую здесь) был полностью позаимствован из стандарта ECMAScript.

Мотивация

Я понимаю, инструментарий регулярок скуден и достаточно запутан. Рассмотрим приведенный ниже шаблон регулярного выражения, который извлекает время в 24-часовом формате (т.е. ЧЧ:ММ), в качестве примера.

\b([01]?[0-9]|2[0-3]):([0-5]\d)\b

Вот да! Кто захочет возиться с этим непонятным текстом?

И все, что приходит вам в голову, глядя на это, на 100% небезосновательно. Я сам дважды откладывал изучение регулярных выражений по той же причине. Но, поверьте, этот неприглядный инструмент не так уж и плох.

Подход (), который я здесь описываю, не отнимет у вас больше 2-3 часов на изучение регулярных выражений, которые, по правде говоря, интуитивно понятны. После того, как вы их освоите, вы увидите, что с течением времени ваша инвестиция дает стабильные дивиденды.

Изучение регулярных выражений

Не нужно много гуглить и пытаться анализировать, какой учебник лучше. Вообще не тратьте время на такой анализ. Потому что в этом нет смысла. На данный момент (ну, если вы еще не знаете регулярные выражения) больше смысла имеет не пытаться угадать, где же лучше начать, а собственно начать изучение.

Просто не задумываясь перейдите на https://regexone.com. И пройдите все уроки. Поверьте мне, я перелопатил множество статей, курсов (<= этот бесплатный, кстати) и книг. Но это лучший вариант чтобы начать и не потерять мотивацию.

После этого, если у вас осталось желание порешать побольше задач и упражнений, рассмотрите приведенные ниже ссылки:

1. Упражнения на regextutorials.com

2. Практические задачи с регулярными выражениями на hackerrank

Пример std::regex и std::regexerror

int main() {    try {        static const auto r = std::regex(R"(\)"); // Escape sequence error    } catch (const std::regex_error &e) {        assert(strcmp(e.what(), "Unexpected end of regex when escaping.") == 0);        assert(e.code() == std::regex_constants::error_escape);    }    return EXIT_SUCCESS;}

Вот видите! Я использую сырые строковые литералы. Вы также можете использовать обычную строку, но в таком случае вы должны использовать двойной бэкслеш (\) для escape-последовательности.

Текущая реализация std::regex медленная (так как требует интерпретации регулярных выражений и создания структуры данных во время выполнения), раздувается и неизбежно требует динамического выделения памяти (не allocator aware). Будьте осторожны, если вы используете std::regex в цикле (см. C++ Weekly - Ep 74 - std::regex optimize by Jason Turner). Кроме того, в ней есть только одна функция-член, которая, как я думаю, действительно может быть полезной это std::regex::markcount(), которая возвращает несколько групп захвата.

Более того, если вы используете несколько строк для создания шаблона регулярного выражения во время выполнения, то вам может потребоваться обработка исключений (например, std::regexerror), чтобы проверить его правильность.

Пример std::regex_search

int main() {    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;    const regex r(R"((\w+):(\w+);)");    smatch m;    if (regex_search(input, m, r)) {        assert(m.size() == 3);        assert(m[0].str() == "PQR:2;");                // Entire match        assert(m[1].str() == "PQR");                   // Substring that matches 1st group        assert(m[2].str() == "2");                     // Substring that matches 2nd group        assert(m.prefix().str() == "ABC:1->   ");      // All before 1st character match        assert(m.suffix().str() == ";;   XYZ:3<<<");   // All after last character match        // for (string &&str : m) { // Alternatively. You can also do        //     cout << str << endl;        // }    }    return EXIT_SUCCESS;}

smatch это специализация std::match_results, которая хранит информацию о найденных совпадениях (матчах).

Пример std::regex_match

Лаконичный и приятный пример, который вы всегда можете найти в каждой книге о регулярках, - это валидация электронной почты. И именно здесь идеально подходит функция std::regexmatch.

bool is_valid_email_id(string_view str) {    static const regex r(R"(\w+@\w+\.(?:com|in))");    return regex_match(str.data(), r);}int main() {    assert(is_valid_email_id("vishalchovatiya@ymail.com") == true);    assert(is_valid_email_id("@abc.com") == false);    return EXIT_SUCCESS;}

return EXITC14Cmatch, а не std::regexC15Cmatch сопоставляет (матчит) всю входную последовательность.

Еще одна примечательная вещь это статический объект регулярного выражения (static const regex), чтобы избежать создания (компиляции/интерпретации) нового объекта регулярного выражения каждый раз при заходе в функцию.

Вся ирония этого крошечного фрагмента кода заключается в том, что он генерирует порядка 30 тысяч строк сборки с флагом -O3. И это просто смешно. Но не волнуйтесь, это уже было доведено до комитета ISO C++. И в скором времени мы можем получить обновление, устраняющее проблему. Между тем у нас есть и другие альтернативы (упомянутые в конце этой статьи).

Разница между std::regex_match и std::regex_search

Вам может быть интересно, почему у нас есть две функции, выполняющие почти одинаковую работу? Даже я изначально не понимал этого. Но после многократного прочтения описания, предоставляемого cppreference, я нашел ответ. И чтобы объяснить этот ответ, я создал пример (очевидно, не без помощи StackOverflow):

int main() {    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;    const regex r(R"((\w+):(\w+);)");    smatch m;    assert(regex_match(input, m, r) == false);    assert(regex_search(input, m, r) == true && m.ready() == true && m[1] == "PQR");    return EXIT_SUCCESS;}

std::regexmatch возвращает true только тогда, когда совпадает вся входная последовательность, в то время как std::regexsearch вернет true, даже если только часть последовательности соответствует регулярному выражению.

Пример std::regex_iterator

std::regex_iterator полезен, когда требуется очень подробная информация о соответствиях и сабматчах.

#define C_ALL(X) cbegin(X), cend(X)int main() {    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;    const regex r(R"((\w+):(\d))");    const vector<smatch> matches{        sregex_iterator{C_ALL(input), r},        sregex_iterator{}    };    assert(matches[0].str(0) == "ABC:1"         && matches[0].str(1) == "ABC"         && matches[0].str(2) == "1");    assert(matches[1].str(0) == "PQR:2"         && matches[1].str(1) == "PQR"         && matches[1].str(2) == "2");    assert(matches[2].str(0) == "XYZ:3"         && matches[2].str(1) == "XYZ"         && matches[2].str(2) == "3");    return EXIT_SUCCESS;}

Ранее (в C++11) существовало ограничение, заключающееся в том, что std::regex_interator нельзя было вызывать с временным объектом регулярного выражения. Что было исправлено с помощью перегрузки в C++14.

Пример std::regex_token_iterator

std::regextokeniterator это утилита, которую вы будете использовать в 80% случаев. Она немного отличается от std::regexiterator. Разница между td::regexiterator и std::regextokeniterator заключается в том, что

• std::regexiterator указывает на соответствующие результаты.

• std::regextokeniterator указывает на сабматчи.

В std::regextoken_iterator каждый итератор содержит только один соответствующий результат.

#define C_ALL(X) cbegin(X), cend(X)int main() {    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;    const regex r(R"((\w+):(\d))");    // Note: vector<string> here, unlike vector<smatch> as in std::regex_iterator    const vector<string> full_match{        sregex_token_iterator{C_ALL(input), r, 0}, // Mark `0` here i.e. whole regex match        sregex_token_iterator{}    };    assert((full_match == decltype(full_match){"ABC:1", "PQR:2", "XYZ:3"}));    const vector<string> cptr_grp_1st{        sregex_token_iterator{C_ALL(input), r, 1}, // Mark `1` here i.e. 1st capture group        sregex_token_iterator{}    };    assert((cptr_grp_1st == decltype(cptr_grp_1st){"ABC", "PQR", "XYZ"}));    const vector<string> cptr_grp_2nd{        sregex_token_iterator{C_ALL(input), r, 2}, // Mark `2` here i.e. 2nd capture group        sregex_token_iterator{}    };    assert((cptr_grp_2nd == decltype(cptr_grp_2nd){"1", "2", "3"}));    return EXIT_SUCCESS;}

Инверсия соответствия с std::regex_token_iterator

#define C_ALL(X) cbegin(X), cend(X)int main() {    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;    const regex r(R"((\w+):(\d))");    const vector<string> inverted{        sregex_token_iterator{C_ALL(input), r, -1}, // `-1` = parts that are not matched        sregex_token_iterator{}    };    assert((inverted == decltype(inverted){                            "",                            "->   ",                            ";;;   ",                            "<<<",                        }));    return EXIT_SUCCESS;}

Пример std::regex_replace

string transform_pair(string_view text, regex_constants::match_flag_type f = {}) {    static const auto r = regex(R"((\w+):(\d))");    return regex_replace(text.data(), r, "$2", f);}int main() {    assert(transform_pair("ABC:1, PQR:2"s) == "1, 2"s);    // Things that aren't matched are not copied    assert(transform_pair("ABC:1, PQR:2"s, regex_constants::format_no_copy) == "12"s);    return EXIT_SUCCESS;}

Вы видите, что во втором вызове transformpair мы передали флаг std::regexconstants::formatnocopy, который говорит не копировать те части, которые не соответствуют регулярке. В std::regexconstant есть много подобных полезных флагов.

Кроме того, мы создали новую строку, содержащую результаты. Но что, если нам не нужна новая строка, а нужно добавить результаты куда-нибудь, возможно, в контейнер, поток или уже существующую строку. Угадайте, что! Стандартная библиотека уже реализует такую потребность также с помощью перегруженного std::regexreplace следующим образом:

int main() {    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;    const regex r(R"(-|>|<|;| )");    // Prints "ABC:1     PQR:2      XYZ:3   "    regex_replace(ostreambuf_iterator<char>(cout), C_ALL(input), r, " ");    return EXIT_SUCCESS;}

Примеры использования

Разделение строки с помощью разделителя (delimiter)

std::strtok является наиболее подходящим и оптимальным кандидатом для такой задачи, но в целях демонстрации продемонстрируем как это можно сделать с помощью регулярного выражения:

#define C_ALL(X) cbegin(X), cend(X)vector<string> split(const string& str, string_view pattern) {    const auto r = regex(pattern.data());    return vector<string>{        sregex_token_iterator(C_ALL(str), r, -1),        sregex_token_iterator()    };}int main() {    assert((split("/root/home/vishal", "/")                == vector<string>{"", "root", "home", "vishal"}));    return EXIT_SUCCESS;}

Удаление пробелов из строки

string trim(string_view text) {    static const auto r = regex(R"(\s+)");    return regex_replace(text.data(), r, "");}int main() {    assert(trim("12   3 4      5"s) == "12345"s);    return EXIT_SUCCESS;}

Поиск строк, содержащих или НЕ содержащих определенные слова, из файла

string join(const vector<string>& words, const string& delimiter) {    return accumulate(next(begin(words)), end(words), words[0],            [&delimiter](string& p, const string& word)            {                return p + delimiter + word;            });}vector<string> lines_containing(const string& file, const vector<string>& words) {    auto prefix = "^.*?\\b("s;    auto suffix = ")\\b.*$"s;    //  ^.*?\b(one|two|three)\b.*$    const auto pattern = move(prefix) + join(words, "|") + move(suffix);    ifstream        infile(file);    vector<string>  result;    for (string line; getline(infile, line);) {        if(regex_match(line, regex(pattern))) {            result.emplace_back(move(line));        }    }    return result;}int main() {   assert((lines_containing("test.txt", {"one","two"})                                        == vector<string>{"This is one",                                                          "This is two"}));    return EXIT_SUCCESS;}/* test.txtThis is oneThis is twoThis is threeThis is four*/

То же самое касается поиска строк, которые не содержат слов с шаблоном ^((?!(one|two|three)).)*$.

Поиск файлов в папке

namespace fs = std::filesystem;vector<fs::directory_entry> find_files(const fs::path &path, string_view rg) {    vector<fs::directory_entry> result;    regex r(rg.data());    copy_if(        fs::recursive_directory_iterator(path),        fs::recursive_directory_iterator(),        back_inserter(result),        [&r](const fs::directory_entry &entry) {            return fs::is_regular_file(entry.path()) &&                   regex_match(entry.path().filename().string(), r);        });    return result;}int main() {    const auto dir        = fs::temp_directory_path();    const auto pattern    = R"(\w+\.png)";    const auto result     = find_files(fs::current_path(), pattern);    for (const auto &entry : result) {        cout << entry.path().string() << endl;    }    return EXIT_SUCCESS;}

Общие советы по использованию регулярных выражений

• Для описания шаблона регулярного выражения в C++ лучше используйте сырые строковые литералы.

• Пользуйтесь инструментом проверки регулярных выражений, например https://regex101.com. Что мне нравится в regex101, так это функция генерации кода и вычисление затраченного времени (будет полезна при оптимизации регулярного выражения).

• Кроме того, хорошим тоном будет добавление объяснения, сгенерированного инструментом проверки, в виде комментария над шаблоном регулярного выражения в вашем коде.

  Производительность:

  • Если вы используете чередование (alternation), попробуйте расположить параметры в порядке наивысшей вероятности, например com|net|org.

  • Старайтесь использовать ленивые квантификаторы.

  • По возможности используйте группы без захвата.

  • Отключайте бэктрекинг.

  • Использование отрицательного класса символов более эффективно, чем использование ленивой точки.

Заключение

Дело не в том, будете ли вы использовать регулярные выражения исключительно на C++ или любым другим языком. Я сам использую их в основном в IDE (в vscode для анализа файлов логов) и на терминале Linux. Имейте в виду, что чрезмерное использование регулярных выражений дает чрезмерное ощущение собственной сообразительности. И это отличный способ рассердить на вас ваших коллег (и всех, кому нужно работать с вашим кодом). Кроме того, регулярные выражения являются излишними для большинства задач синтаксического анализа, с которыми вы столкнетесь в своей повседневной работе.

Регулярные выражения действительно подходят для сложных задач, где рукописный код синтаксического анализа в любом случае будет столь же медленным; и для чрезвычайно простых задач, когда удобочитаемость и надежность регулярных выражений перевешивают их затраты на производительность.

Еще одна примечательная вещь текущая реализация регулярных выражений (до 19 июня 2020 года) в стандартных библиотеках имеет проблемы с производительностью и раздутием кода. Так что выбирайте с умом между версиями библиотек Boost, CTRE и Std. Скорее всего, вы согласитесь с работой Ханы Дусиковой над регулярным выражением времени компиляции. Кроме того, ее выступление на CppCon в 2018 и 2019 было бы для вас полезно, особенно если вы планируете использовать регулярное выражение во встроенных системах.

Узнать подробнее о курсе "C++ Developer. Professional"

Записаться на открытый урок по теме "Backend на современном C++"

Как много в вашем городе иностранных туристов? В моём мало, но встречаются, как правило стоят потерянные посреди улицы и повторяют одно единственное слово название чего бы то ни было. А прохожие пытаются им на пальцах объяснить куда пройти, а когда моя твоя не понимать берут за руку и ведут к пункту назначения. Как это не удивительно, обычно цель в пяти минутах ходьбы, т.е. какое-то примерное представление о городе эти туристы всё же имели. Может по бумажной карте ориентировались.

А как часто лично вы оказывались в такой ситуации, в незнакомом городе в другой стране?

Появление смартфонов и приложений для навигации решило много проблем. Ура, можно посмотреть свою геолокацию, можно найти куда идти, прикинуть в каком направлении и даже проложить маршрут.

Осталась одна проблема: все улицы в приложении подписаны местными иероглифами на местном наречии, и ладно если в стране пребывания принята латиница, клавиатура на латинице есть во всех смартфонах и мир к ней привык, и то я испытывал дискомфорт, из-за диакритических знаков, принятых в чешском алфавите. А боль и страдания иностранцев, видящих кириллицу, могу только представить, посмотрите псевдокириллицу и поймёте. Если бы я оказался на их месте, я бы писал названия и адреса латиницей, пытаясь воспроизвести звучание - фонетический поиск.

В публикации опишу как реализовать фонетические алгоритмы поиска Soudex на движке Sphinx Search. Одной транслитерацией здесь не обойдётся, хотя и без неё никуда. Получившийся конфигурационный файл, доступен на GitHub Gist.

Вступление

Понадобится база адресов, например, ФИАС или база названий чего-то, в общем то, что будем искать, и Sphinx Search.

Решение удобно тем, что ничего не придётся доделывать, достраивать дорабатывать в самой базе, т.е. данные останутся как есть, - всё сделает Sphinx.

Если мы решили, что, пользователи будут искать названия так, как они их на слух воспринимают, то наша беда в том, что слух у всех разный. Мы можем придумывать сколько угодно различных стандартов транслитераций, и они нам все в одинаковой степени и подходят, и нет.

Но, ничто не ново под луной и решение уже найдено до нас. Распространены два подхода Soundex и Metaphone, плюс их вариации. В публикации рассмотрим только Soundex и его варианты, Metaphone затрагивать не будем.

Более того, Sphinx уже поддерживает Soundex, как говорится, из коробки. Но рано бить баклуши, почивать на лаврах и стричь купоны, для кириллицы он не работает. Т.е. по сути не подходит для задачи. Придётся допиливать.

Для начала неплохо разобраться с тем что из себя представляют фонетические алгоритмы. На хабре есть статьи, лично мне нравятся: фонетический поиск краткая и лаконичная, подойдёт для тех кто хочет в двух словах понять идею не вдаваясь в детали реализации, и вторая фонетические алгоритмы, наоборот, для тех кому нужно подробнее. Я буду опираться на материал, написанный в них, стараясь как можно меньше его дублировать дабы не раздувать статью, для полноты картины, советую ознакомиться с ними, прежде чем продолжать.

А теперь подумаем, как завезти поддержку кириллицы в Soundex, реализовать и его, и улучшенную версию, и NYSIIS, и Daitch-Mokotoff.

К реализации

Будут приведены некоторые примеры работы на SphinxQL, для этого использую подключение в духе:

mysql -h 127.0.0.1 -P 9306 --default-character-set=utf8

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

Оригинальный Soundex и Транслитерация

Начнём с самого простого в реализации. Простоты добавляет тот факт, что Sphinx Search, как я уже писал выше, поддерживает из коробки реализацию для английского языка, т.е. половина дела уже в шляпе.

Кстати, делает это он не совсем канонично: не обрезает все коды до четырёх символов, а если символов меньше четырёх не дополняет всё нулями. Но я в этом ни каких проблем не вижу.

Всё что от нас требуется сделать транслитерацию на великий и могучий, остальное Sphinx сделает сам.

Сделать транслитерацию несложно, сложно выбрать правила, по которым она будет проходить, стандартов уйма, и скорее всего это ещё не всё, ознакомиться с ними можно в Википедии: транслитерация русского алфавита латиницей. Выбор чистая вкусовщина, если вам не навязывается стандарт каким-нибудь приказом МВД, то берите тот который больше нравится или скомбинируйте их в свой ни на что не похожий, в конце концов задача всех этих фонетических алгоритмов избавить нас от этих разночтений. Можно ещё посмотреть публикацию "всё о транслитерации", вдруг поможет определиться с выбором. Как ни выбирай, всё равно найдётся ситуация, когда все эти ухищрения не помогут, да и лошадиную фамилию всё равно не найдёт.

Прописываем в конфигурации Sphinx все правила транслита с помощью регулярных выражений:

regexp_filter = (А|а) => a

а для Ъ и Ь можно написать

regexp_filter = (Ь|ь) =>

Не буду приводить текст для всего алфавита, если что можно скопировать всё там же, с GitHub Gist.

И не забудьте включить soundex для латиницы:

morphology = soundex

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

Всё настроили, проиндексировали данные, создали подключение к Sphinx. Давайте попробуем найти что-нибудь. Раз уж наша цель - коммунизм интернационализм поисковой выдачи, то и искать будем улицы названные в честь деятелей интернационала, и сочувствующих. Поищем Ленина. Искать будем именно Ленина, а не Ленин, я почему-то уверен, что интуристы прямо так и будут искать Lenina, может даже ulitsa Lenina.

Чтобы понять что с ним происходит воспользуемся командой CALL KEYWORDS:

mysql> call keywords('Ленин Ленина Lenina Lennina Lenin', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | lenin     | l500       || 2    | lenina    | l500       || 3    | lenina    | l500       || 4    | lennina   | l500       || 5    | lenin     | l500       |+------+-----------+------------+

Обратите внимание, в tokenized хранится то, что было получено после применения всех регулярных выражений. А в normalized, то по какому ключу Sphinx будет осуществлять поиск, и результат обусловлен тем, что включена morphology. 'Lenina' преобразуется в ключевое слово l500, и 'Ленина' в l500, спасибо транслиту, - уровнял, теперь на каком бы языке не искали найдётся одно и то же. Всё тоже самое и для Lennina, и для Lenena, и даже Lennona. Так что, если в вашем городе есть улица Джона Леннона, то тут может накладочка выйти.

Выполним поиск, наконец:

mysql> select * from STREETS where match('Lenena'); +------+--------------------------------------+-----------+--------------+| id   | aoguid                               | shortname | offname      |+------+--------------------------------------+-----------+--------------+|  387 | 4b919f60-7f5d-4b9e-99af-a7a02d344767 | ул        | Ленина       |+------+--------------------------------------+-----------+--------------+

Sphinx вернул нам один результат, даже если ввели с ошибкой. Вот с Плехановым посложнее. Тут уже в зависимости от того, какой мы способ транслитерации выберем:

mysql> call keywords('Плехановская Plechanovskaya Plehanovskaja Plekhanovska', 'STREETS', 0);+------+----------------+------------+| qpos | tokenized      | normalized |+------+----------------+------------+| 1    | plekhanovskaja | p42512     || 2    | plechanovskaya | p42512     || 3    | plehanovskaja  | p4512      || 4    | plekhanovska   | p42512     |+------+----------------+------------+

plehanovskaja -выбивается. Sphinx ничего не вернёт. Но, можно воспользоваться CALL QSUGGEST:

mysql> CALL QSUGGEST('Plehanovskaja', 'STREETS');+----------------+----------+------+| suggest        | distance | docs |+----------------+----------+------+| plekhanovskaja | 1        | 1    || petrovskaja    | 4        | 1    |+----------------+----------+------+

Функция вернёт предложения по исправлению запроса, и расстояние Левенштейна между запросом, и возможным результатом. Т.е. можно попробовать опять взять напильник в руки.

Не забудьте включить инфикс, для работы этой функции:

min_infix_len = 2

suggest содержит запись аналогичную по смыслу колонке tokenized, т.е. то, что получилось после применения регулярных выражений. В этом случае регулярные выражения касались только транслитерации, в других реализациях Soudex регулярные выражения будут применяться в том числе и для генерации кода, поэтому QSUGGEST работать не будет.

Попробуем что-нибудь ещё найти:

mysql> select * from STREETS where match('30 let Pobedy');+------+--------------------------------------+-----------+------------------------+| id   | aoguid                               | shortname | offname                |+------+--------------------------------------+-----------+------------------------+|  677 | 87234d80-4098-40c0-adb2-fc83ef237a5f | ул        | 30 лет Победы          |+------+--------------------------------------+-----------+------------------------+mysql> select * from STREETS where match('30 лет Побуды');+------+--------------------------------------+-----------+------------------------+| id   | aoguid                               | shortname | offname                |+------+--------------------------------------+-----------+------------------------+|  677 | 87234d80-4098-40c0-adb2-fc83ef237a5f | ул        | 30 лет Победы          |+------+--------------------------------------+-----------+------------------------+

Хорошо справляется, заодно и опечатки может исправить.

Спойлер: именно этот вариант в итоге и окажется самым приемлемым. Если лень читать полотенце ниже, то сразу переходите к итогам, всё равно вывод в пользу оригинального Soundex.

Улучшенный Soundex

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

Вначале копируем транслитерацию.

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

Можно убрать morphology = soundex из конфигурации она нам уже ничем не поможет, только под ногами путается. Придётся всё прописывать самим, опять через регулярные выражения.

Sphinx будет их применять последовательно, в том порядке, в котором они в конфигурации прописаны! Это важно. Для регулярных выражений используется движок RE2.

Сразу после блока с транслитерацией запишем сохранение первого символа, например: regexp_filter = \A(A|a) => a

Затем остальные символы заменяются на числовой код, Гласные на 0.

regexp_filter = \B(A|a) => 0regexp_filter = \B(Y|y) => 0...

Хотя, гласные можно просто удалять regexp_filter = \B(Y|y) =>

Решайте сами какой вариант нравится больше, хозяин - барин. Но я гласные выкидываю, хотя бы для того чтобы ВЛКСМ и Veelkaseem давали один результат.

mysql> call keywords('ВЛКСМ Veelkaseem', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | v738      | v738       || 2    | v738      | v738       |+------+-----------+------------+

иначе будет что-то такое:

mysql> call keywords('ВЛКСМ Veelkaseem', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | v738      | v738       || 2    | v0730308  | v0730308   |+------+-----------+------------+

Далее, согласные H и W просто выкидываются.

Идущие подряд символы, или входящие в одну и ту же группу, или символы/группы, разделенные буквами H или W, записываются как один. Это самое последнее действие.

regexp_filter = 0+ => 0regexp_filter = 1+ => 1...

Проверяем что получается:

mysql> call keywords('Ленин Ленина Lenina Lennina Lenin', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | l8        | l8         || 2    | l8        | l8         || 3    | l8        | l8         || 4    | l8        | l8         || 5    | l8        | l8         |+------+-----------+------------+mysql> select * from STREETS where match('Lenina');+------+--------------------------------------+-----------+--------------+| id   | aoguid                               | shortname | offname      |+------+--------------------------------------+-----------+--------------+|  387 | 4b919f60-7f5d-4b9e-99af-a7a02d344767 | ул        | Ленина       |+------+--------------------------------------+-----------+--------------+

Вроде всё нормально, и Ленина мы находим во всех вариациях. Но обратите внимание, поле tokenized теперь содержит не индексируемый текс, а soundex-код. QSUGGEST отказывается работать. Если кто-то знает, как включить пишите. Я пытался добавить юникод для цифр в ngram_chars. Но это не помогло.

Проверим на Плеханове:

mysql> call keywords('Плехановская Plechanovskaya Plehanovskaja Plekhanovska', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | p738234   | p738234    || 2    | p73823    | p73823     || 3    | p78234    | p78234     || 4    | p73823    | p73823     |+------+-----------+------------+

Стало вариантов много, а правильный всего один, и QSUGGEST не придёт на помощь:

mysql> CALL QSUGGEST('Plehanovskaja', 'STREETS');Empty set (0.00 sec)mysql> CALL QSUGGEST('p73823', 'STREETS');Empty set (0.00 sec)mysql> CALL QSUGGEST('p78234', 'STREETS');Empty set (0.00 sec)

Хотели, как лучше, а получилось, как всегда. Сам алгоритм реализовали, вроде правильно, но непрактично. Хотя нерабочим его тоже не назовёшь. Например, вот как он побеждает 30 лет Победы:

mysql> call keywords('30 let Podedy', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | 30        | 30         || 2    | l6        | l6         || 3    | p6        | p6         |+------+-----------+------------+mysql> select * from STREETS where match('30 let Pobedy');+------+--------------------------------------+-----------+------------------------+| id   | aoguid                               | shortname | offname                |+------+--------------------------------------+-----------+------------------------+|  677 | 87234d80-4098-40c0-adb2-fc83ef237a5f | ул        | 30 лет Победы          |+------+--------------------------------------+-----------+------------------------+

И даже так работает:

mysql> select * from STREETS where match('Вэлкасэем');+------+--------------------------------------+--------------+----------------------+| id   | aoguid                               | shortname    | offname              |+------+--------------------------------------+--------------+----------------------+|  873 | abdb0221-bfe8-4cf8-9217-0ed40b2f6f10 | проезд       | 30 лет ВЛКСМ         || 1208 | f1127b16-8a8e-4520-b1eb-6932654abdcd | ул           | 50 лет ВЛКСМ         |+------+--------------------------------------+--------------+----------------------+

Может подойти, если механизма исправления запросов, на которые ничего не вернулось, не предусмотрено.

NYSIIS

Ходят слухи что разработан он был для работы с американскими фамилиями. Американские это вообще какая-то условность. Да и фамилии тоже, подойдёт и для поиска по названиям улиц и другим именам собственным, тем более в России многие улицы названы чьей-то фамилией, хотя американцами эти люди не стали.

Далее будет использоваться модификатор (?i) для работы регулярных выражений без учёта регистра.

Начинаем с транслитерации, как всегда. Затем:

1. Преобразовать начало слова

   regexp_filter = (?i)\b(mac) => mcc

2. Преобразовать конец слова

   regexp_filter = (?i)(ee)\b => y

3. После гласных: удалить H, преобразовать W в А

   regexp_filter = (?i)(a|e|i|o|u|y)h => \1

   regexp_filter = (?i)(a|e|i|o|u|y)w => \1a

4. Преобразовываем все буквы кроме первой

   regexp_filter = (?i)\B(e|i|o|u) => a

   regexp_filter = (?i)\B(q) => g

5. Удалить S на конце

   regexp_filter = (?i)s\b =>

6. Преобразуем AY на конце в Y

7. Удалить A на конце

Напоминаю что регулярные выражения приведены не все, а минимум, для примера!!!

Самое замечательное, - это то, что код не числовой, а буквенный, а значит снова заработает CALLQSUGGEST.

Проверяем:

mysql> call keywords('Ленин Ленина Lenina Lennina Lenin', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | lanan     | lanan      || 2    | lanan     | lanan      || 3    | lanan     | lanan      || 4    | lannan    | lannan     || 5    | lanan     | lanan      |+------+-----------+------------+mysql> call keywords('Плехановская Plechanovskaya Plehanovskaja Plekhanovska', 'STREETS', 0);+------+---------------+---------------+| qpos | tokenized     | normalized    |+------+---------------+---------------+| 1    | plachanavscaj | plachanavscaj || 2    | plachanavscay | plachanavscay || 3    | plaanavscaj   | plaanavscaj   || 4    | plachanavsc   | plachanavsc   |+------+---------------+---------------+

Пробуем понять что имел в виду пользователь, используем для этого CALL QSUGGEST Plehanovskaja, преобразовавшуюся в plaanavscaj:

mysql> CALL QSUGGEST('plaanavscaj', 'STREETS');+---------------+----------+------+| suggest       | distance | docs |+---------------+----------+------+| paanarscaj    | 2        | 1    || plachanavscaj | 2        | 1    || latavscaj     | 3        | 1    || sladcavscaj   | 3        | 1    || pacravscaj    | 3        | 1    |+---------------+----------+------+

И тут возникают коллизии. Да ещё и без пол-литра не разберёшься что тут такое.

С таким подходом мы любой адрес из-под земли достанем, даже если пользователь искал не его и ему туда не надо. Зато шансов что-то НЕ найти не осталось. Берите, если на неправильный запрос нужно возвращать много разных вариантов исправления. Может пользователь туда и не хотел, но вдруг передумает, глядя на предложенные варианты.

Daitch-Mokotoff Soundex

И последний по списку, но не по значению, из алгоритмов Soundex.

Чувствителен к порядку преобразования. Например, если преобразование выполняется по принципу за гласной, то нам не нужно запоминать что гласную удалили ещё не предыдущем шаге, раз удалили, - значит там её уже нет, и правило не сработает и не должно, - так и задумано.

Как всегда, в начале транслитерация.

Потом выполняем пошаговую трансформацию.

Каждый шаг состоит из трёх условий, т.е. три разных регулярных выражения:

• если буквосочетание в начале слова

  regexp_filter = (?i)\b(au) => 0

• если за гласной

  regexp_filter = (?i)(a|e|i|o|u|y)(au) => \17

• и остальные случаи, здесь даже \B в регулярном выражении можно не писать, потому что другие варианты уже были ранее обработаны

  regexp_filter = (?i)au =>

Иногда нет никакой разницы между двумя или тремя разными ситуациями и одного-два регулярных выражения на шаг хватит:

regexp_filter = (?i)j => 1

Глянем что получается:

mysql> call keywords('Ленин Ленина Lenina Lennina Lenin', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | 866       | 866        || 2    | 866       | 866        || 3    | 866       | 866        || 4    | 8666      | 8666       || 5    | 866       | 866        |+------+-----------+------------+mysql> call keywords('Плехановская Plechanovskaya Plehanovskaja Plekhanovska', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | 7856745   | 7856745    || 2    | 7856745   | 7856745    || 3    | 786745    | 786745     || 4    | 7856745   | 7856745    |+------+-----------+------------+

Опять исключительно числовой код, и опять QSUGGEST не поможет понять пользователя. Со всякими непонятками всё ещё справляется неплохо.

mysql> select * from STREETS where match('Veelkaseem'); show meta;+------+--------------------------------------+--------------+----------------------+| id   | aoguid                               | shortname    | offname              |+------+--------------------------------------+--------------+----------------------+|  873 | abdb0221-bfe8-4cf8-9217-0ed40b2f6f10 | проезд       | 30 лет ВЛКСМ         || 1208 | f1127b16-8a8e-4520-b1eb-6932654abdcd | ул           | 50 лет ВЛКСМ         |+------+--------------------------------------+--------------+----------------------+2 rows in set (0.00 sec)+---------------+-------+| Variable_name | Value |+---------------+-------+| total         | 2     || total_found   | 2     || time          | 0.000 || keyword[0]    | 78546 || docs[0]       | 2     || hits[0]       | 2     |+---------------+-------+

Ну и всё на этом, никакого чуда не произошло, - мы уже это видели.

Итоги

Реализовать Soundex, в целом получилось, из всех вариантов предпочтительнее оригинальный Soundex и NYSIIS, по той простой причине что работаем мы напрямую с буквенным кодом и можно вызвать CALL QSUGGEST, а Sphinx предложит варианты исправления, при том в NYSIIS много и всяких-разных. Улучшенный Soundex и Daitch-Mokotoff Soundex, должны снизить количество коллизий, охотно верю, что так и происходит, но проиндексировав 1286 названий улиц своего города, я не заметил, чтобы коллизии были хоть какой-то проблемой. Хотя встречаются:

mysql> call keywords('Воровского Вербовая', 'STREETS', 0);+------+------------+------------+| qpos | tokenized  | normalized |+------+------------+------------+| 1    | vorovskogo | v612       || 2    | verbovaja  | v612       |+------+------------+------------+

Это был оригинальный Soundex, в улучшенном уже нормально:

mysql> call keywords('Воровского Вербовая', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | v9234     | v9234      || 2    | v9124     | v9124      |+------+-----------+------------+

Зато алгоритмы стали менее терпимы к опечаткам, особенно если она допущена в согласной. Например, оригинальный Soundex:

mysql> select * from STREETS where match('Ордхоникидзе');+------+--------------------------------------+-----------+--------------------------+| id   | aoguid                               | shortname | offname                  |+------+--------------------------------------+-----------+--------------------------+|   12 | 0278d3ee-4e17-4347-b128-33f8f62c59e0 | ул        | Орджоникидзе             |+------+--------------------------------------+-----------+--------------------------+

А остальные реализации ничего не возвращают.

Невозможность вызова QSUGGEST, тоже кажется существенной проблемой. Хотя, может я просто не умею её готовить. Если знаете, как делитесь рецептом.

В общем, не мудрствуя лукаво, мой совет: используйте оригинальный Soundex с транслитерацией. Единственный риск - коллизии, чтобы их разрешить, просто-напросто возьмите оригинальный запрос, и подсчитайте расстояние Левенштейна между ним, и теми несколькими записями что вам предлагает Sphinx.

Если возможности проводить постобработку нет, ни для исправления, ни для разрешения коллизий, то выбирайте улучшенный Soundex или Daitch-Mokotof - хотя бы Вербовую, вместо Воровского не получите. NYSIIS подойдёт если вы хотите пользователю, на запрос с ошибкой, предложить, как можно больше самых непохожих друг на друга вариантов.

Всё написанное испытано на sphinx-3.3.1, но должно работать на всём с версии 2.1.1-beta, в которой появились регулярные выражения. В том числе на Manticore. Разработчики ManticoreSearch, хвастаются что прогресс идёт в гору семимильными шагами. Может там будет поддержка и прочих алгоритмов, хотя бы для латиницы, а может и сразу для кириллицы.

И по большому счёту этот подход приемлем для всего, к чему можно прикрутить транслит. Можно хоть китайскую грамоту индексировать, только транслитерацию знай прикручивай.

P.S.

Статья получилось неожиданно большой, сам не ожидал. Поэтому про Metaphone не написал. Для него будет, или не будет, отдельная статья. Хотя принцип тот же:

1. Транслит-регулярки

2. Ещё регулярки

3. ????

4. PROFIT

Это продолжение публикации Интернационализация поиска по городским адресам. Реализуем русскоязычный Soundex на Sphinx Search, в которой я разбирал, как реализовать поддержку фонетических алгоритмов Soundex в Sphinx Search, для текста написанного кириллицей. Для текста на латинице поддержка Soundex уже есть. С Metphone аналогично, для латиницы есть, для кириллицы не очень, но попытаемся исправить этот досадный факт с помощью транслитерации, регулярных выражений и напильника.

Это прямое продолжение, в котором разберём как реализовать оригинальный Metaphone, русскийMetaphone (в том смысле что транслитерация не понадобится), Caverphone, и не сможем сделать DoubleMetaphone.

Реализация подойдёт как для использования на платформе SphinxSearch, так и ManticoreSearch.

В конце, в качестве бонуса, посмотрим как Metaphone воспримет "ракомакофон".

Описание алгоритмов, всё так же, брал из публикации "фонетические алгоритмы". Постараюсь как можно меньше дублировать текст, написанный в ней.

Оригинальный Metaphone

Реализуется элементарно, создаются регулярные выражения для транслитерации:

regexp_filter = (А|а) => aregexp_filter = (Б|б) => bregexp_filter = (В|в) => v

И включаем metaphone:

morphology = metaphone

Всё, как и с оригинальным Soundex. В прошлый раз, мы пришли к выводу, что лучше всего, из всех Soundex алгоритмов, использовать именно оригинальный Soundex, единственный недостаток которого коллизии, разрешается вычислением расстояния Левенштейна.

В этот раз, забегая вперёд, скажу, что снова сделал бы свой выбор в пользу оригинального Metaphone + транслит. А вот причина небанальна.

Дело в том что у Sphinx есть в такой параметр blend_chars. Смысл следующий, Sphinx индексирует по словам, а слова он находит по разделителям, например, если между буквами есть пробел, значит буквы два разных слова, перенос строки, табуляция, знаки препинания и т.д., и т.п. Но могут быть символы, которые одновременно разделяют слова, а могут быть и частью одного слова, например, &. M&Ms это сколько слов? А Рога&Копыта? Для таких случаев и существует blend_chars.

И тут можно пойти на хитрость, и добавить в blend_chars пробел:

blend_chars = U+0020

Теперь, когда кто-то будет искать улицу Мориса Тореза, то найдёт её, даже если подумает, что это одно слово. Да что там слитное написание, он её найдёт даже если решит, что Мать Тереза и Морис Торез родственники.

mysql> select * from metaphone where match('Морисатереза');+------+--------------------------------------+-----------+---------------------------+| id   | aoguid                               | shortname | offname                   |+------+--------------------------------------+-----------+---------------------------+| 1130 | e21aec85-0f63-4367-b9bb-1943b2b5a8fb | ул        | Мориса Тореза             |+------+--------------------------------------+-----------+---------------------------+

Можем увидеть, как работает индекс для Мориса Тореза, вызвав call keywords:

mysql> call keywords ('Мориса Тореза', 'metaphone');+------+---------------+------------+| qpos | tokenized     | normalized |+------+---------------+------------+| 1    | morisa toreza | MRSTRS     || 1    | morisa        | MRS        || 2    | toreza        | TRS        |+------+---------------+------------+

Обратите внимание, что два слова было воспринято как три: morisa, toreza и morisa toreza, притом при создании кода Metaphone, пробел был съеден.

Это особенность реализации Metaphone в Sphinx Search. Самостоятельно, с помощью регулярных выражений её не реализовать. Нет, конечно мы можем добавить регулярное выражение, удаляющее пробелы:

regexp_filter = [ ] => 

но тогда Мориса Тореза, и другие, будут всегда восприниматься как одно слово, а нам этого не надо.

Давайте сравним как работают другие индексы, в том числе те, которые ещё разобрать не успели, но они будут ниже.

Caverphone пробел сохраняет, поэтому при слитном написании просто не находит.

mysql> call keywords ('Мориса Тореза', 'caverphone');+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | mrsa trza | mrsa trza  || 1    | mrsa      | mrsa       || 2    | trza      | trza       |+------+-----------+------------+mysql> select * from caverphone where match('Морисатереза');Empty set (0.00 sec)

Оригинальный Soundex (из предыдущей публикации), в котором используется базовая реализация Sphinx, просто сходит с ума, и не понимает, как кодировать слово, в котором встретился пробел, morisa и toreza закодирован, а morisa toreza нет:

mysql> call keywords ('Мориса Тореза', 'simple_soundex');+------+---------------+---------------+| qpos | tokenized     | normalized    |+------+---------------+---------------+| 1    | morisa toreza | morisa toreza || 1    | morisa        | m620          || 2    | toreza        | t620          |+------+---------------+---------------+

Потому не включайте пробел в blend_chars в большинстве случаем это не просто бесполезно, но и вредно. Единственно исключение metaphone. И это позволяет решить самую сложную для исправления опечатку (с машинной точки зрения) опечатку в пробелах: как наличие лишних, так и отсутствие нужных.

А это дорогого стоит.

Double Metaphone

Для двойного Metaphone планировал использовать два индекса, вместо одного, как обычно, а затем искать поочерёдно в обоих.

К сожалению, я не понял, как реализовать двойной Metaphone с помощью регулярных выражений. Когда я начал искать по нему описание, меня как будто в гугле забанили, зато нашёл много реализаций на различных языках программирования, например, DoubleMetaphone.java. Я даже попытался понять этот алгоритм и реализовать его в виде регулярок, но дошёл до буквы C, и понял, что рассудок покидает меня.

Если Вы гуру гуглапоиска, или просто знаете способ, как сделать реализацию с помощью регулярных выражений пишите, пишите мне, пишите публикацию на хабр, придумаем как прикрутить его к Sphinx и Manticore.

Но будет нечестно, если про двойной Metaphone совсем ничего не написать. Опишу как бы я его сделал, если было бы ну очень нужно. Sphinx не понадобится. Но придётся программировать.

Для начала я бы подключил уже готовую библиотеку в которой он реализован, благо их нашлось множество для разных языков, я использую Java, поэтому подключаю Commons Codec. Библиотека не работает с кириллицей требуется транслитерация, и кодирует только первое слово. Поэтому если вам надо реализовать кодирование большого текста, разделённого пробелами то самостоятельно придётся разбивать строку на слова, и в цикле их перебирать.

В таблице БД, где хранятся данные, я бы добавил две новые колонки, в которых бы хранил закодированное значение. Это один из недостатков данной реализации требуется допиливать таблицы в БД.

Затем, перед вставкой новых записей в таблицу, я бы вызывал:

DoubleMetaphone dm = new DoubleMetaphone();String metaphone1 = dm.doubleMetaphone("Text", false);String metaphone2 = dm.doubleMetaphone("Text", true);

И сохранял metaphone1 и metaphone2 вместе с данными.

Это вторая большая проблема вся вставка теперь должна проходить через эту процедуру.

При поиске значений в таблице, кодируем поисковой запрос с помощью CommonsCodec. И теперь ищем по столбцам, в которых код сохранялся. Особенность двойного Metaphone в том, что кода мы кодируем поисковый запрос двумя реализациями, то мы получившиеся оба результата ищем и в первом столбце и во втором. А не первый код в первом столбце, второй код во втором: и первый, и второй код в первом столбце и первый и второй код во втором, и все их комбинации.

Без Sphinx всё стало очень неудобно.

Русский Metaphone

Не подойдёт для целей интернационализации.

Зато подразумевает отсутствие транслитерации. А это может быть весьма удобно, ибо транслитерация сама по себе несёт небольшое искажение. Получает как в игре глухой телефон, только глухой Metaphone.

Если вы создаёте поиск исключительно для тех, кто печатает кириллицей, то разумно прибегнуть именно этой версии, а не городить транслитерации всякие.

Ну и ещё один момент, который нужно учесть при выборе, алгоритм не сжимает окончания. Значит, если улица Ленина, то надо так и писать Ленина, Ленин без окончания, не найдётся:

mysql> call keywords ('Ленина Ленин', 'rus_metaphone');+------+--------------+--------------+| qpos | tokenized    | normalized   |+------+--------------+--------------+| 1    | линина       | линина       || 2    | линин        | линин        |+------+--------------+--------------+

Реализуем регулярные выражения. Полный конфигурационный файл, как и ранее, лежит на GitHub Gist manticore.conf.

• Переделываем гласные:

regexp_filter = (?i)(йо|ио|йе|ие) => иregexp_filter = (?i)(о|ы|я) => аregexp_filter = (?i)(е|ё|э) => иregexp_filter = (?i)(ю) => у

• Для всех согласных букв, за которыми следует любая согласная, кроме Л, М, Н или Р, провести оглушение:

regexp_filter = (?i)(б)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => п\2regexp_filter = (?i)(г)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => к\2regexp_filter = (?i)(в)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => ф\2regexp_filter = (?i)(д)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => т\2regexp_filter = (?i)(ж)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => ш\2regexp_filter = (?i)(з)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => с\2

• Для согласных на конце слова, провести оглушение

regexp_filter = (?i)б\b => пregexp_filter = (?i)г\b => кregexp_filter = (?i)в\b => фregexp_filter = (?i)д\b => тregexp_filter = (?i)ж\b => шregexp_filter = (?i)з\b => з

• Склеиваем ТС и ДС в Ц

regexp_filter = (?i)(тс|дс|ц) => ц

Caverphone

Здесь сначала транслитерация.

• Затем, нужно перевести транслитерированное в нижний регистр:

regexp_filter = (A|a) => aregexp_filter = (B|b) => b

Это необходимо, потому что алгоритм для некоторых букв делает различие между тем, в каком она регистре, если в верхнем, то она считается как бы замороженной для любых изменений.

• Удалить e на конце

regexp_filter = e\b =>

• Происходит преобразование начала слова, но это актуально для новозеландских фамилий, этот шаг можно и пропустить:

regexp_filter = \b(cough) => cou2fregexp_filter = \b(rough) => rou2f

• Провести замены символов

regexp_filter = (cq) => 2qregexp_filter = (ci) => si

• Заменить все гласные в начале слова на a, в остальных случаях на 3

regexp_filter = (?i)\b(a|e|i|o|u|y) => Aregexp_filter = (?i)(a|e|i|o|u|y) => 3

• Провести очередные замены

regexp_filter = (j) => yregexp_filter = \b(y3) => Y3

• Удалить все цифры 2

regexp_filter = 2 => 

• Если на конце слова осталась цифра 3, то заменить её на A

regexp_filter = 3\b => A

• Удалить все цифры 3

regexp_filter = 3 =>

До 10 символов не сокращаю и не дополняю.

Проверим:

mysql> select * from caverphone where match ('Ленина');+------+--------------------------------------+-----------+------------------+| id   | aoguid                               | shortname | offname          |+------+--------------------------------------+-----------+------------------+|    5 | 01339f2b-6907-4cb8-919b-b71dbed23f06 | ул        | Линейная         ||  387 | 4b919f60-7f5d-4b9e-99af-a7a02d344767 | ул        | Ленина           |+------+--------------------------------------+-----------+------------------+

Кроме Ленина находит и Линейная. Согласен, некоторое сходство есть, другие алгоритмы так не смогли, ну разве что Daitch Mokotoff Soundex из предыдущей публикации выкинул что-то подобное с Лунная:

mysql> select * from daitch_mokotoff_soundex where match ('Ленина');+------+--------------------------------------+-----------+--------------+| id   | aoguid                               | shortname | offname      |+------+--------------------------------------+-----------+--------------+|  387 | 4b919f60-7f5d-4b9e-99af-a7a02d344767 | ул        | Ленина       ||  541 | 69b8220e-a42d-4fec-a346-1df56370c363 | ул        | Лунная       |+------+--------------------------------------+-----------+--------------+

Можем посмотреть как это всё кодируется:

mysql> call keywords ('Ленина Линейная Лунная', 'caverphone');+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | lnna      | lnna       || 2    | lnna      | lnna       || 3    | lna       | lna        |+------+-----------+------------+mysql> call keywords ('Ленина Линейная Лунная', 'daitch_mokotoff_soundex');+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | 866       | 866        || 2    | 8616      | 8616       || 3    | 866       | 866        |+------+-----------+------------+

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

Бонус: ищем ракомакофон. Вместо заключения

Это лишено практического смысла, но наблюдение забавное, поэтому напишу. Just for fun.

Помните ракомакофон, который слышится вместо rock the microphone?! Было интересно, сможет ли Metaphone понять ракомакофон. И ведь почти!

Во-первых, добавляем пробел в blend_chars, ведь нам надо чтобы три слова rock the microphone, воспринимались как одно:

blend_chars = U+0020

Поскольку у нас только один алгоритм умеет адекватно работать в такой ситуации - оригинальный metaphone, то его и применим.

Проверим с помощью keywords как оно воспринимается Sphinx:

mysql> call keywords ('ракомакофон', 'metaphone');+------+-------------+------------+| qpos | tokenized   | normalized |+------+-------------+------------+| 1    | rakomakofon | RKMKFN     |+------+-------------+------------+

И rock the microphone:

mysql> call keywords ('rock the microphone', 'metaphone');+------+---------------------+------------+| qpos | tokenized           | normalized |+------+---------------------+------------+| 1    | rock the microphone | RK0MKRFN   || 1    | rock                | RK         || 2    | the                 | 0          || 3    | microphone          | MKRFN      |+------+---------------------+------------+

Получилось RK0MKRFN, и RKMKFN, расстояние Левенштейна между ними всего 2(!). А если найти способ исключить the из кодирования, то получится RKMKRFN:

mysql> call keywords ('rock microphone', 'metaphone');+------+-----------------+------------+| qpos | tokenized       | normalized |+------+-----------------+------------+| 1    | rock microphone | RKMKRFN    || 1    | rock            | RK         || 2    | microphone      | MKRFN      |+------+-----------------+------------+

Между RKMKRFN и RKMKFN, расстояние Левенштейна всего 1! Мы почти у цели.

Проблема убрать the, параметр stopwords здесь не поможет, ибо из-за blend_chars = U+0020 the не будет восприниматься самостоятельно. Но даже если удастся сделать предобработку, то всё равно расстояние в 1, не позволит обнаружить похожий.

Надежда на qsuggest не оправдалась, - не даст подсказок. Почему? Можно заметить, что при вызове keywords есть два столбца tokenized и normalized, qsuggest даёт подсказку по столбцу tokenized и измеряет расстояние Левенштейна относительно него, qsuggest всё равно, что там, в normalized, расстояние равно 1.

Поэтому наблюдение забавное, но не практичное.

Регулярные выражения (их еще называют regexp, или regex) это механизм для поиска и замены текста. В строке, файле, нескольких файлах... Их используют разработчики в коде приложения, тестировщики в автотестах, да просто при работе в командной строке!

Чем это лучше простого поиска? Тем, что позволяет задать шаблон.

Например, на вход приходит дата рождения в формате ДД.ММ.ГГГГГ. Вам надо передать ее дальше, но уже в формате ГГГГ-ММ-ДД. Как это сделать с помощью простого поиска? Вы же не знаете заранее, какая именно дата будет.

А регулярное выражение позволяет задать шаблон найди мне цифры в таком-то формате.

Для чего применяют регулярные выражения?

1. Удалить все файлы, начинающиеся на test (чистим за собой тестовые данные)

2. Найти все логи

3. grep-нуть логи

4. Найти все даты

5. ...

А еще для замены например, чтобы изменить формат всех дат в файле. Если дата одна, можно изменить вручную. А если их 200, проще написать регулярку и подменить автоматически. Тем более что регулярные выражения поддерживаются даже простым блокнотом (в Notepad++ они точно есть).

В этой статье я расскажу о том, как применять регулярные выражения для поиска и замены. Разберем все основные варианты.

Содержание

1. Где пощупать

2. Поиск текста

3. Поиск любого символа

4. Поиск по набору символов

5. Перечисление вариантов

6. Метасимволы

7. Спецсимволы

8. Квантификаторы (количество повторений)

9. Позиция внутри строки

10. Использование ссылки назад

11. Просмотр вперед и назад

12. Замена

13. Статьи и книги по теме

14. Итого

1. Поиск текста

2. Поиск любого символа

3. Поиск по набору символов

4. Перечисление вариантов

5. Метасимволы

6. Спецсимволы

7. Квантификаторы (количество повторений)

8. Замена

9. Итого

Где пощупать

Любое регулярное выражение из статьи вы можете сразу пощупать. Так будет понятнее, о чем речь в статье вставили пример из статьи, потом поигрались сами, делая шаг влево, шаг вправо. Где тренироваться:

1. Notepad++ (установить Search Mode Regular expression)

2. Regex101 (мой фаворит в онлайн вариантах)

3. Myregexp

4. Regexr

Инструменты есть, теперь начнём

Поиск текста

Самый простой вариант регэкспа. Работает как простой поиск ищет точно такую же строку, как вы ввели.

Текст: Море, море, океан

Regex: море

Найдет: Море, море, океан

Выделение курсивом не поможет моментально ухватить суть, что именно нашел regex, а выделить цветом в статье я не могу. Атрибут BACKGROUND-COLOR не сработал, поэтому я буду дублировать регулярки текстом (чтобы можно было скопировать себе) и рисунком, чтобы показать, что именно regex нашел:

Обратите внимание, нашлось именно море, а не первое Море. Регулярные выражения регистрозависимые!

Хотя, конечно, есть варианты. В JavaScript можно указать дополнительный флажок i, чтобы не учитывать регистр при поиске. В блокноте (notepad++) тоже есть галка Match case. Но учтите, что это не функция по умолчанию. И всегда стоит проверить, регистрозависимая ваша реализация поиска, или нет.

А что будет, если у нас несколько вхождений искомого слова?

Текст: Море, море, море, океан

Regex: море

Найдет: Море, море, море, океан

По умолчанию большинство механизмов обработки регэкспа вернет только первое вхождение. В JavaScript есть флаг g (global), с ним можно получить массив, содержащий все вхождения.

А что, если у нас искомое слово не само по себе, это часть слова? Регулярное выражение найдет его:

Текст: Море, 55мореон, океан

Regex: море

Найдет: Море, 55мореон, океан

Это поведение по умолчанию. Для поиска это даже хорошо. Вот, допустим, я помню, что недавно в чате коллега рассказывала какую-то историю про интересный баг в игре. Что-то там связанное с кораблем... Но что именно? Уже не помню. Как найти?

Если поиск работает только по точному совпадению, мне придется перебирать все падежи для слова корабль. А если он работает по включению, я просто не буду писать окончание, и все равно найду нужный текст:

Regex: корабл

Найдет:

На корабле

И тут корабль

У корабля

Это статический, заранее заданный текст. Но его можно найти и без регулярок. Регулярные выражения особенно хороши, когда мы не знаем точно, что мы ищем. Мы знаем часть слова, или шаблон.

Поиск любого символа

. найдет любой символ (один).

Текст:

Аня

Ася

Оля

Аля

Валя

Regex: А.я

Результат:

Аня

Ася

Оля

Аля

Валя

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

А6я

А&я

А я

Учтите это при поиске! Точка очень удобный символ, но в то же время очень опасный если используете ее, обязательно тестируйте получившееся регулярное выражение. Найдет ли оно то, что нужно? А лишнее не найдет?

Точку точка тоже найдет!

Regex: file.

Найдет:

file.txt

file1.txt

file2.xls

Но что, если нам надо найти именно точку? Скажем, мы хотим найти все файлы с расширением txt и пишем такой шаблон:

Regex: .txt

Результат:

file.txt

log.txt

file.png

1txt.doc

one_txt.jpg

Да, txt файлы мы нашли, но помимо них еще и мусорные значения, у которых слово txt идет в середине слова. Чтобы отсечь лишнее, мы можем использовать позицию внутри строки (о ней мы поговорим чуть дальше).

Но если мы хотим найти именно точку, то нужно ее заэкранировать то есть добавить перед ней обратный слеш:

Regex: \.txt

Результат:

file.txt

log.txt

file.png

1txt.doc

one_txt.jpg

Также мы будем поступать со всеми спецсимволами. Хотим найти именно такой символ в тексте? Добавляем перед ним обратный слеш.

Правило поиска для точки:

. любой символ

\. точка

Поиск по набору символов

Допустим, мы хотим найти имена Алла, Анна в списке. Можно попробовать поиск через точку, но кроме нормальных имен, вернется всякая фигня:

Regex: А..а

Результат:

Анна

Алла

аоикА74арплт

Аркан

А^&а

Абба

Если же мы хотим именно Анну да Аллу, вместо точки нужно использовать диапазон допустимых значений. Ставим квадратные скобки, а внутри них перечисляем нужные символы:

Regex: А[нл][нл]а

Результат:

Анна

Алла

аоикА74арплт

Аркан

А^&а

Абба

Вот теперь результат уже лучше! Да, нам все еще может вернуться Анла, но такие ошибки исправим чуть позже.

Как работают квадратные скобки? Внутри них мы указываем набор допустимых символов. Это может быть перечисление нужных букв, или указание диапазона:

[нл] только н и л

[а-я] все русские буквы в нижнем регистре от а до я (кроме ё)

[А-Я] все заглавные русские буквы

[А-Яа-яЁё] все русские буквы

[a-z] латиница мелким шрифтом

[a-zA-Z] все английские буквы

[0-9] любая цифра

[В-Ю] буквы от В до Ю (да, диапазон это не только от А до Я)

[А-ГО-Р] буквы от А до Г и от О до Р

Обратите внимание если мы перечисляем возможные варианты, мы не ставим между ними разделителей! Ни пробел, ни запятую ничего.

[абв] только а, б или в

[а б в] а, б, в, или пробел (что может привести к нежелательному результату)

[а, б, в] а, б, в, пробел или запятая

Единственный допустимый разделитель это дефис. Если система видит дефис внутри квадратных скобок значит, это диапазон:

• Символ до дефиса начало диапазона

• Символ после конец

Один символ! Не два или десять, а один! Учтете это, если захотите написать что-то типа [1-31]. Нет, это не диапазон от 1 до 31, эта запись читается так:

• Диапазон от 1 до 3

• И число 1

Здесь отсутствие разделителей играет злую шутку с нашим сознанием. Ведь кажется, что мы написали диапазон от 1 до 31! Но нет. Поэтому, если вы пишете регулярные выражения, очень важно их тестировать. Не зря же мы тестировщики! Проверьте то, что написали! Особенно, если с помощью регулярного выражения вы пытаетесь что-то удалить =)) Как бы не удалили лишнее...

Указание диапазона вместо точки помогает отсеять заведомо плохие данные:

Regex: А.я или А[а-я]я

Результат для обоих:

Аня

Ася

Оля

Аля

Результат для А.я:

А6я

А&я

А я

^ внутри [] означает исключение:

[^0-9] любой символ, кроме цифр

[^ёЁ] любой символ, кроме буквы ё

[^а-в8] любой символ, кроме букв а, б, в и цифры 8

Например, мы хотим найти все txt файлы, кроме разбитых на кусочки заканчивающихся на цифру:

Regex: [^0-9]\.txt

Результат:

file.txt

log.txt

file_1.txt

1.txt

Так как квадратные скобки являются спецсимволами, то их нельзя найти в тексте без экранирования:

Regex: fruits[0]

Найдет: fruits0

Не найдет: fruits[0]

Это регулярное выражение говорит найди мне текст fruits, а потом число 0. Квадратные скобки не экранированы значит, внутри будет набор допустимых символов.

Если мы хотим найти именно 0-левой элемент массива фруктов, надо записать так:

Regex: fruits\[0\]

Найдет: fruits[0]

Не найдет: fruits0

А если мы хотим найти все элементы массива фруктов, мы внутри экранированных квадратных скобок ставим неэкранированные!

Regex: fruits\[[0-9]\]

Найдет:

fruits[0] = апельсин;

fruits[1] = яблоко;

fruits[2] = лимон;

Не найдет:

cat[0] = чеширский кот;

Конечно, читать такое регулярное выражение становится немного тяжело, столько разных символов написано...

Без паники! Если вы видите сложное регулярное выражение, то просто разберите его по частям. Помните про основу эффективного тайм-менеджмента? Слона надо есть по частям.

Допустим, после отпуска накопилась гора писем. Смотришь на нее и сразу впадаешь в уныние:

Ууууууу, я это за день не закончу!

Проблема в том, что груз задачи мешает работать. Мы ведь понимаем, что это надолго. А большую задачу делать не хочется... Поэтому мы ее откладываем, беремся за задачи поменьше. В итоге да, день прошел, а мы не успели закончить.

А если не тратить время на размышления сколько времени это у меня займет, а сосредоточиться на конкретной задаче (в данном случае первом письме из стопки, потом втором...), то не успеете оглянуться, как уже всё разгребли!

Разберем по частям регулярное выражение fruits\[[0-9]\]

Сначала идет просто текст fruits.

Потом обратный слеш. Ага, он что-то экранирует.

Что именно? Квадратную скобку. Значит, это просто квадратная скобка в моем тексте fruits[

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

Нашли. Наш набор: [0-9]. То есть любое число. Но одно. Там не может быть 10, 11 или 325, потому что квадратные скобки без квантификатора (о них мы поговорим чуть позже) заменяют ровно один символ.

Пока получается: fruits[любое однозназначное число

Дальше снова обратный слеш. То есть следующий за ним спецсимвол будет просто символом в моем тексте.

А следующий символ ]

Получается выражение: fruits[любое однозназначное число]

Наше выражение найдет значения массива фруктов! Не только нулевое, но и первое, и пятое... Вплоть до девятого:

Regex: fruits\[[0-9]\]

Найдет:

fruits[0] = апельсин;

fruits[1] = яблоко;

fruits[9] = лимон;

Не найдет:

fruits[10] = банан;

fruits[325] = абрикос ;

Как найти вообще все значения массива, см дальше, в разделе квантификаторы.

А пока давайте посмотрим, как с помощью диапазонов можно найти все даты.

Какой у даты шаблон? Мы рассмотрим ДД.ММ.ГГГГ:

• 2 цифры дня

• точка

• 2 цифры месяца

• точка

• 4 цифры года

Запишем в виде регулярного выражения: [0-9][0-9]\.[0-9][0-9]\.[0-9][0-9][0-9][0-9].

Напомню, что мы не можем записать диапазон [1-31]. Потому что это будет значить не диапазон от 1 до 31, а диапазон от 1 до 3, плюс число 1. Поэтому пишем шаблон для каждой цифры отдельно.

В принципе, такое выражение найдет нам даты среди другого текста. Но что, если с помощью регулярки мы проверяем введенную пользователем дату? Подойдет ли такой regexp?

Давайте его протестируем! Как насчет 8888 года или 99 месяца, а?

Regex: [0-9][0-9]\.[0-9][0-9]\.[0-9][0-9][0-9][0-9]

Найдет:

01.01.1999

05.08.2015

Тоже найдет:

08.08.8888

99.99.2000

Попробуем ограничить:

• День недели может быть максимум 31 первая цифра [0-3]

• Максимальный месяц 12 первая цифра [01]

• Год или 19.., или 20.. первая цифра [12], а вторая [09]

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

Однако если мы присмотримся внимательнее к регулярному выражению, то сможем найти в нем дыры:

Regex: [0-3][0-9]\.[0-1][0-9]\.[12][09][0-9][0-9]

Не найдет:

08.08.8888

99.99.2000

Но найдет:

33.01.2000

01.19.1999

05.06.2999

Мы не можем с помощью одного диапазона указать допустимые значения. Или мы потеряем 31 число, или пропустим 39. И если мы хотим сделать проверку даты, одних диапазонов будет мало. Нужна возможность перечислить варианты, о которой мы сейчас и поговорим.

Перечисление вариантов

Квадртатные скобки [] помогают перечислить варианты для одного символа. Если же мы хотим перечислить слова, то лучше использовать вертикальную черту |.

Regex: Оля|Олечка|Котик

Найдет:

Оля

Олечка

Котик

Не найдет:

Оленька

Котенка

Можно использовать вертикальную черту и для одного символа. Можно даже внутри слова тогда вариативную букву берем в круглые скобки

Regex: А(н|л)я

Найдет:

Аня

Аля

Круглые скобки обозначают группу символов. В этой группе у нас или буква н, или буква л. Зачем нужны скобки? Показать, где начинается и заканчивается группа. Иначе вертикальная черта применится ко всем символам мы будем искать или Ан, или ля:

Regex: Ан|ля

Найдет:

Аня

Аля

Оля

Малюля

А если мы хотим именно Аня или Аля, то перечисление используем только для второго символа. Для этого берем его в скобки.

Эти 2 варианта вернут одно и то же:

• А(н|л)я

• А[нл]я

Но для замены одной буквы лучше использовать [], так как сравнение с символьным классом выполняется проще, чем обработка группы с проверкой на все её возможные модификаторы.

Давайте вернемся к задаче проверить введенную пользователем дату с помощью регулярных выражений. Мы пробовали записать для дня диапазон [0-3][0-9], но он пропускает значения 33, 35, 39... Это нехорошо!

Тогда распишем ТЗ подробнее. Та-а-а-ак... Если первая цифра:

• 0 вторая может от 1 до 9 (даты 00 быть не может)

• 1, 2 вторая может от 0 до 9

• 3 вторая только 0 или 1

Составим регулярные выражения на каждый пункт:

• 0[1-9]

• [12][0-9]

• 3[01]

А теперь осталось их соединить в одно выражение! Получаем: 0[1-9]|[12][0-9]|3[01]

По аналогии разбираем месяц и год. Но это остается вам для домашнего задания

Раннее утро, десятая чашка кофе, безуспешные попытки понять почему ваше клиентское (или еще хуже серверное) java-приложение намертво зависло при вычислении простого регекспа на небольшой строке Если подобная ситуация уже возникала в вашей жизни, вы уже наверняка знаете про бэктрекинг и темную сторону регулярных выражений. Остальным добро пожаловать под кат!

Бэктрекинг, или вечное ожидание результата

Проблема бэктрекинга при матчинге регулярных выражений уже неоднократно поднималась в различных статьях на хабре (раз, два, три), поэтому опишем ее суть без погружения в детали. Рассмотрим простой синтетический пример типичный экземпляр из так называемых "evil regexes" (аналог изначально представлен тут):

@Testpublic void testRegexJDK8Only() {  final Pattern pattern = Pattern.compile("(0*)*1");  Assert.assertFalse(pattern.matcher("0000000000000000000000000000000000000000").matches());}

Напомню: символ * в регулярных выражениях ("ноль или несколько символов") называется квантификатором. Им же являются такие символы, как ?, +, {n} (n количество повторений группы или символа).

Если запустить код на JDK8 (почему на более актуальных версиях воспроизводиться не будет опишем далее), то JVM будет очень долго вычислять результат работы метода matches(). Едва ли вам удастся его дождаться, не состарившись на несколько месяцев или даже лет.

Что же пошло не так? Стандартная реализация Pattern/Matcher из пакета java.util.regex будет искать решение из теста следующим образом:

1. * - жадный квантификатор, поскольку всегда будет пытаться захватить в себе как можно большее количество символов. Так, в нашем случае группа (0)захватит полностью всю строку, звезда снаружи группы увидит, что может повториться ровно один раз, а единицы в строке не окажется. Первая проверка на соответствие провалилась.

2. Произведем откат (backtrack) к начальному состоянию. Мы попытались захватить максимальную группу из нулей и нас ждал провал; давайте теперь возьмём на один нолик меньше. Тогда группа (0) захватит все нули без одного, снаружи группы укажет на наличие единственной группы, а оставшийся ноль не равен единице. Снова провал.

3. Снова откатываемся к начальному состоянию и забираем группой (0) все нули без двух последних. Но ведь оставшиеся два нуля тоже могут заматчиться группой (0)! И теперь эта группа тоже попытается сначала захватить два нуля, после чего попытается взять один ноль, и после этого произойдет откат и попытка матчинга строки уже без трех нулей.

Легко догадаться, что по мере уменьшения "начальной" жадной группы будет появляться множество вариаций соседних групп (0), которые также придется откатывать и проверять все большее количество комбинаций. Сложность будет расти экспоненциально; при наличии достаточного количества нулей в строке прямо как в нашем примере возникнет так называемый катастрофический бэктрекинг, который и приведет к печальным последствиям.

"Но ведь пример абсолютно синтетический! А в жизни так бывает?" - резонно спросите вы. Ответ вполне ожидаем: бывает, и очень часто. Например, для решения бизнес-задачи программисту необходимо составить регулярку, проверяющую, что в строке есть не более 10 слов, разделенных пробелами и знаками препинания. Не заморачиваясь с аккуратным созданием регекспа, на свет может появиться следующий код:

@Testpublic void testRegexAnyJDK() {final Pattern pattern = Pattern.compile("([A-Za-z,.!?]+( |\\-|\\')?){1,10}");  Assert.assertFalse(pattern.matcher("scUojcUOWpBImlSBLxoCTfWxGPvaNhczGpvxsiqagxdHPNTTeqkoOeL3FlxKROMrMzJDf7rvgvSc72kQ").matches());}

Представленная тестовая строка имеет длину 80 символов и сгенерирована случайным образом. Она не заставит JVM на JDK8+ работать вечно всего лишь около 30 минут но этого уже достаточно, чтобы нанести вашему приложению существенный вред. В случае разработки серверных приложений риск многократно увеличивается из-за возможности проведения ReDoS-атак. Причиной же подобного поведения, как и в первом примере, является бэктрекинг, а именно сочетание квантификаторов "+" внутри группы и "{1,10}" снаружи.

Война с бэктрекингом или с разработчиками Java SDK?

Чем запутаннее паттерн, тем сложнее для неопытного человека увидеть проблемы в регулярном выражении. Причем речь сейчас идет вовсе не о внешних пользователях, использующих ваше ПО, а о разработчиках. Так, с конца нулевых было создано значительное количество тикетов с жалобой на бесконечно работающий матчинг. Несколько примеров: JDK-5026912, JDK-7006761, JDK-8139263. Реже можно встретить жалобы на StackOverflowError, который тоже типичен при проведении матчинга (JDK-5050507). Все подобные баги закрывались с одними и теми же формулировками: "неэффективный регексп", "катастрофический бектрекинг", "не является багом".

Альтернативным предложением сообщества в ответ на невозможность "починить" алгоритм было внедрение таймаута при применении регулярного выражения или другого способа остановить матчинг, если тот выполняется слишком долго. Подобный подход можно относительно легко реализовать самостоятельно (например, часто его можно встретить на сервисах для проверки регулярных выражений - таких как этот), но предложение реализации таймаута в API java.util.regex также неоднократно выдвигалось и к разработчикам JDK (тикеты JDK-8234713, JDK-8054028, JDK-7178072). Первый тикет все еще не имеет исполнителя; два остальных были закрыты, поскольку "правильным решением будет улучшить реализацию, которая лучше справляется с кейсами, в которых наблюдается деградация" (пруф).

Доработки алгоритма действительно происходили. Так, в JDK9 реализовано следующее улучшение: каждый раз, когда применяется жадный квантификатор, не соответствующий данным для проверки, выставляется курсор, указывающий на позицию в проверяемом выражении. При повторной проверке после отката достаточно убедиться, что если для текущей позиции проверка уже была провалена, продолжение текущего подхода лишено смысла и проводиться не будет (JDK-6328855, пояснение). Это позволило исключить бесконечный матчинг в тесте testRegexJDK8Only() начиная с версии jdk9-b119, однако второй тест вызывает задержки вне зависимости от версии JDK. Более того, при наличии обратных ссылок в регулярных выражениях оптимизация не используется.

Опасный враг: внешнее управление

Публикации, упомянутые в самом начале статьи, отлично раскрывают варианты оптимизации регулярных выражений, в результате чего катастрофический бектрекинг перестает быть опасным врагом; для сложных случаев потребуется дополнительная экспертиза, но в целом регулярное выражение можно почти всегда записать "безопасным" образом. Да и проверить себя тоже можно, например, на npmjs.com. Проблема остается при составлении очень сложных регулярок, а также в тех сценариях, когда регулярное выражение задается не программистом, а аналитиком, заказчиком после передачи решения, или же пользователем. В последнем случае управление сложностью регулярного выражения оказывается снаружи и вам придется позаботиться о том, чтобы при любых условиях приложение продолжало корректную работу.

Использование стандартной библиотеки в таком случае, очевидно, не лучший выбор. К счастью, существуют сторонние фреймворки, позволяющие производить матчинг за линейное время. Одним из таких фреймворков является RE2, под капотом которого используется DFA - подход. Не будем вдаваться в детали реализации и подробно описывать разницу подходов; отметим лишь его растущую популярность RE2 используется как дефолтный движок в Rust, а также активно применяется во множестве продуктов экосистемы Google. Для JDK7+ существует RE2/J, которая является прямым портом из C++ - версии библиотеки.

В конце января 2021 года был опубликован драфт JEP-а, в котором предлагается создать движок для регулярных выражений с матчингом за линейное время, и одним из основных подходов в реализации является именно RE2.

RE2/J - серебряная пуля?

Может показаться, что переход на RE2/J отличный выбор практически для каждого проекта. Какова цена линейного времени выполнения?

• У RE2/J отсутствует ряд методов API у Matcher;

• Синтаксис регулярных выражений совпадает не полностью (у RE2/J отствутет часть конструкций, в том числе обратные ссылки, backreferences). Вполне вероятно, после замены импорта ваша регулярка перестанет корректно распознаваться;

• Несмотря на то, что формально код принадлежит Google, библиотека не является официальной, а основным ее мейнтейнером является единственный разработчик Джеймс Ринг.

• Разработчик фреймворка подчеркивает: "Основная задача RE2/J заключается в обеспечении линейного времени выполнения матчинга при наличии регулярных выражений от внешних источников. Если все регулярные выражения находятся под контролем разработчика, вероятно, использование java.util.regex является лучшим выбором".

Надеюсь, этих пунктов достаточно, чтобы убедиться: RE2/J не серебряная пуля; фреймворк не является бескомпромиссным решением для проверки на соответствие регулярным выражениям. Реализация при создании кода повлечет ограниченный функционал, а прямая замена импорта в уже существующем коде может негативно сказаться на стабильности работы приложения.

Итоги

1. Даже простые регулярные выражения при невнимательном написании могут сделать ваш продукт уязвимым для ReDoS.

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

3. Если все регулярные выражения в приложении находятся под контролем разработчика обязательно тестируйте их, чтобы убедиться в отсутствии риска падения.

Если возможность самостоятельно задавать регулярное выражение есть не только у разработчика, то стоит реализовать защиту от вечной проверки с помощью создания таймаута или использования сторонних решений, позволяющих решать задачу матчинга за линейное время например, таких, как RE2/J.