Эффективное сопоставление строк и шаблонов в C++ (суффиксарри, trie, суффикстри?)
Я ищу эффективную структуру данных для сопоставления строк и шаблонов с огромным набором строк. Я узнал о попытках, суффикс-деревьях и суффикс-массивах. Но я пока не смог найти готовую реализацию в C/C++ (и сам по себе ее реализация кажется сложной и подверженной ошибкам). Но я до сих пор не уверен, что Suffix-Arrays действительно то, что я ищу... Я пробовал libdivsufsort и esaxx, но не смог выяснить, как использовать их для своих нужд:
Я хочу использовать предопределенный набор строк с подстановочными знаками (или даже регулярными выражениями), чтобы соответствовать пользовательскому вводу. Я получил огромный список предопределенных строк, т.е.
"ЧТО ТАКОЕ *?" "ЧТО ТАКОЕ XYZ?" "СКОЛЬКО *?" ...
Теперь я хочу найти наиболее подходящую строку (если она есть). Т.е. ввод пользователя: > ЧТО ТАКОЕ XYZ? Должен найти "ЧТО ТАКОЕ XYZ?" вместо "ЧТО ЕСТЬ *?", но "ЧТО-ТО ЧТО-ТО?" должен найти "ЧТО ЕСТЬ *?" (при условии, что * является подстановочным знаком для любого количества символов).
Построение структуры не является критичным по времени (и структура не должна быть супер-эффективной), но поиск не должен занимать слишком много времени. Как это можно сделать легко? Любой Framework/Library или пример кода приветствуется
Спасибо
8 ответов
Вот решение, которое, я считаю, должно работать хорошо, если у вас очень большое количество шаблонов. Всего за 10 тыс. Это может быть излишним, и его реализация означает относительно большую работу, но, тем не менее, вас это может заинтересовать.
Основная идея заключается в создании инвертированного индекса, который отображает подстроки шаблонов в идентификаторы шаблонов. Во-первых, каждый шаблон получает идентификатор:
1: what is *
2: where is *
3: do * need to
etc.
И затем мы создаем инвертированный индекс. В простейшем случае мы разбиваем шаблоны на токены и сопоставляем каждый токен со списком идентификаторов шаблонов, в которых он встречается. Мы можем проявлять гибкость в том, что мы определяем как токен, но один метод заключается в предположении, что каждое слово, разделенное пробелами это один токен. Итак, вот индекс:
what -> 1
is -> 1,2
where -> 2
do -> 3
need -> 3
to -> 3
Затем, когда вы получаете входную строку от пользователя, вы разделяете ее на токены и ищите их в индексе. Вы объединяете все идентификаторы паттернов, которые вы получаете из индекса. Пример:
INPUT: what is something?
TOKENS:
what -> 1
is -> 1,2
something -> n/a
Вы извлекаете идентификаторы шаблона для каждого токена и помещаете их во временную структуру данных, которая подсчитывает частоту каждого идентификатора, например, хэш (например, std::unordered_map<id_type,std::size_t>).
Затем вы сортируете это по частоте, чтобы узнать, что правило 1 было найдено дважды, а правило 2 - один раз.
Затем вы применяете найденные правила в порядке частоты к вводимому тексту. Здесь вы используете библиотеку регулярных выражений или что-то подобное для генерации совпадений. Самое частое правило имеет наибольшее количество общих токенов с входным текстом, поэтому оно может хорошо совпадать.
Общее преимущество этого подхода заключается в том, что вам не нужно применять все правила к входным данным, а только те, которые имеют хотя бы один общий токен с входными данными, и даже среди тех, которые вы делаете это в порядке количества токенов в каждом правиле. делится с вводом, и как только вы найдете подходящее правило, вы, вероятно, можете прервать оставшуюся часть процедуры сопоставления (или нет - в зависимости от того, хотите ли вы, чтобы в каждом случае были все правила сопоставления, или только одно, которое очень хорошо соответствует).
Улучшение Вышеуказанное выполняет предварительный выбор правила на основе токенов. Вместо этого вы можете объединить все правила следующим образом:
what is *||where is *||do * need to||...
Затем вы создаете массив суффиксов этой объединенной строки.
Затем, учитывая входную строку, вы сравниваете ее с массивом суффиксов, чтобы идентифицировать все совпадения подстрок, включая совпадения, которые меньше одного токена или охватывают несколько токенов. В приведенном выше примере я предполагаю, что символы подстановки * а также $ включены в массив суффиксов, хотя, конечно, ни одна часть входной строки никогда не будет соответствовать им. Вы можете полностью исключить их из массива суффиксов или заменить их фиктивным символом.
После определения совпадений вы сортируете их по длине. Вы также должны сопоставить позиции совпадений в объединенной строке с идентификаторами правил. Это легко сделать, поддерживая массив начальных позиций правил относительно объединенной строки; Существуют также высоко оптимизированные методы, основанные на индексированных битовых векторах (я могу уточнить это при необходимости).
Как только у вас есть идентификаторы совпадающих правил, вы делаете то же самое, что и в случае с инвертированным индексом: Применяете правила сопоставления, используя стандартное сопоставление регулярных выражений (или подобное).
Опять же, этот подход является относительно сложным и имеет смысл только тогда, когда у вас есть очень большое количество правил, и если есть вероятность, что поиск на основе токенов (или на основе подстрок) значительно сократит количество правил-кандидатов. Из приведенных вами примеров правил я предполагаю последнее в данном случае, но если количество правил, с которыми вы имеете дело (порядка 10 тыс.), Оправдывает такой подход, я не уверен. Это может иметь больше смысла, если общее количество правил составляет 100 тысяч или миллионы.
Многие из приведенных выше ответов не будут хорошо работать на практике или не являются наиболее известным ответом на ваш вопрос: например, использование генераторов сканера из конструкции компилятора (re2c, lex, flex,...), скорее всего, не сработает для большой словарный запас, поскольку эти инструменты были разработаны для языков программирования, которые обычно имеют не более нескольких сотен встроенных ключевых слов.
Я могу порекомендовать два альтернативных подхода:
(1) выберите класс Trie C++, который отображает строки в идентификаторы size_t, используемые во втором массиве для хранения данных полезной нагрузки. Используйте поисковый запрос системы веб-поиска, например:
c++ trie c++14 implementation fast "small footprint" site:github.com
найти подходящих кандидатов - на момент написания, например, https://github.com/Tessil/hat-trie выглядит неплохо (чистый, переносимый, современный код, и к нему прилагается научная статья, что добавляет достоверности); или
(2) представляют преобразование из строкового словаря в данные полезной нагрузки в виде преобразователя конечного состояния (FST), расширения NFA (автоматов с выходом), реализованного с помощью FOMA, XFST или OpenFST.
Первый вариант означает, что вам нужно будет протестировать доступные библиотеки на простоту использования и масштабируемость. Второй вариант означает, что вам нужно будет ознакомиться с FST и существующими библиотеками реализации и их лицензиями.
(Второй подход используется компьютерными лингвистами для моделирования больших списков слов, а также правительствами для сканирования всего, что вы пишете в Интернете, поэтому он очень хорошо масштабируется.)
Возможно, вы захотите посмотреть на flex. Из руководства:
flex это инструмент для генерации сканеров. Сканер - это программа, которая распознает лексические шаблоны в тексте. Программа flex считывает заданные входные файлы или их стандартный ввод, если имена файлов не указаны, для описания генерируемого сканера. Описание в форме пар регулярных выражений и кода на C, называемых правилами. flex по умолчанию генерирует исходный файл C, lex.yy.c, который определяет процедуру yylex(). Этот файл может быть скомпилирован и связан с библиотекой времени исполнения flex для создания исполняемого файла. Когда исполняемый файл запускается, он анализирует свои входные данные на наличие регулярных выражений. Всякий раз, когда он находит его, он выполняет соответствующий код C.
Также это:
Основная цель разработки Flex - создавать высокопроизводительные сканеры. Он был оптимизирован для работы с большими наборами правил.
Например, этот сканер соответствует трем шаблонам в вашем посте:
%%
"WHAT IS XYZ?" puts("matched WHAT-IS-XYZ");
"WHAT IS ".*"?" puts("matched WHAT-IS");
"HOW MUCH ".*"?" puts("matched HOW-MUCH");
Flex работает, генерируя дискретный конечный автомат (DFA). DFA просматривает каждый входной символ ровно один раз. Нет возврата, даже при сопоставлении с подстановочными знаками. Время выполнения - O(N), где N - количество вводимых символов. (Чем больше шаблонов, тем больше таблиц DFA, что приведет к большему количеству пропаданий в кеше, поэтому для большего количества шаблонов будет определенное наказание. Но это справедливо для любой подходящей системы, о которой я могу подумать.)
Тем не менее, вам придется перечислить ваши шаблоны в правильном порядке, чтобы соответствовать им правильно. Флекс может сказать вам, если есть проблема. Например, если вы измените порядок шаблонов WHAT-IS-XYZ и WHAT-IS в вышеупомянутом сканере, flex скажет вам:
:; flex matcher.l
matcher.l:3: warning, rule cannot be matched
Если вы можете удовлетворить требования Flex, Flex должен дать вам очень быстрый сканер.
Вы пробовали троичное поисковое дерево? Вот реализация C++: http://code.google.com/p/ternary-search-tree/
У меня нет опыта того, как медленно построить троичное дерево, но я знаю, что поиск очень быстрый.
[редактировать]
Для сопоставления подстановочного знака внутри дерева в partalMatchSearch: (заявление об отказе: это всего лишь предложение и никоим образом не проверено)
Вы можете добавить символы * в дерево и выражение if, например, в начале функции partalMatchSearch:
if ( ( *key != 0 ) && tree->splitChar == '*' )
{
this->partialMatchSearch( tree, key+1 );
}
Другими словами, просто рекурсивно вызывайте partMatchSearch с тем же узлом, но со строкой, установленной на следующий символ
Проверьте деревья CritBit:
Пример исходного кода, который тривиален для C++, - если вы действительно чувствуете необходимость.
Чтобы найти все совпадения вы используете функцию critbit0_allprefixed
например
// Find all strings that start with, or are equal to, "WHAT IS"`
critbit0_allprefixed(tree, "WHAT IS", SomeCallback);`
SomeCallback называется для каждого матча.
Это не тот вопрос, который вы задаете. Вы хотели что-то предварительно приготовленное. Но...
Насколько сложным это должно быть? Если бы я пытался сделать то, что вы просите, я бы попробовал что-то более интенсивное, но гораздо менее затратное время.
Я бы (и имел) начать с дерева с индексом 0 алфавита.
Тогда каждый дочерний узел будет словом (словарем).
Тогда каждый дочерний узел этого будет потенциальным совпадением сегмента строки, зная, например, что "раунд" почти никогда НЕ ПРЯМО следует за "квадратом". Вы можете сказать: "Поместите круглый колышек в квадратное отверстие", но слово, которое следует за "раунд" - это "колышек". Таким образом, сегмент соответствует "круглый", "круглый колышек", "круглый мяч". Я бы вычеркнул статьи также потому, что они ничего не значат для предложения (обычно). Приведенный выше абзац будет переводиться как "каждый дочерний узел - слово".
Я бы добавил эвристику, так как даже сложное B-дерево может работать медленно, когда у вас так много данных. Я видел их замедление до минуты или более при поиске очень больших наборов данных.
Это предполагает, что вы на самом деле не хотите использовать базу данных, которая, вероятно, будет самой быстрой из всех, если вы не захотите кодировать в ASM.
Если пространство не имеет значения, то вы можете сделать следующее, с моей головы.
Создайте дерево, у которого есть дочерние элементы возможных символов в этой точке дерева, где текущий уровень является индексом строки. Первый уровень дерева - это индекс уровня 0 или, вернее, индекс массива 0 в строке.
Каждый уровень будет индексом в строке, поэтому корневой узел будет индексом 0, а его дочерние элементы будут индексом 1. Каждый узел будет иметь N дочерних элементов, равных количеству возможных символов в этой точке в строке.
Итак, скажем, у вас есть корень, у которого есть набор возможных ["a", "b", "c"], у него будет три ребенка. Затем скажите, что вы хотите найти возможное совпадение для строки "ab", которую вы вернете ребенку, у которого есть маршрут "a", и перейдите оттуда.
Если вы достигнете конца строки до того, как доберетесь до конечного узла, то список возможных строк - это полное поддерево всех дочерних узлов вашего текущего узла.
Надеюсь, это имело какой-то смысл, но это выглядело бы как дерево Хаффмана, но каждый лист был бы потенциальной строкой на выбор.
Я бы взял совет Кернигана и Пайка и выбрал разумный алгоритм, а затем перебил его.
Все ваши примеры ищут "самый длинный префикс", который подсказывает мне простое дерево, а не дерево суффиксов. Поскольку вам нужно хранить только ~10 тыс. Строк, вы сможете реализовать чартри максимум за пару часов, используя вложенные карты STL.
Если память не ограничена или производительность действительно критична, это должно быть хорошо.