Эффективное сопоставление строк и шаблонов в C ++ (суффиксарри, trie, суффикстри?)
Я ищу эффективную структуру данных для сопоставления строк и шаблонов с огромным набором строк. Я узнал о попытках, суффикс-деревьях и суффикс-массивах. Но я до сих пор не смог найти готовую реализацию в C / C ++ (и сам по себе ее реализация кажется сложной и подверженной ошибкам). Но я все еще не уверен, что Suffix-Arrays действительно то, что я ищу … Я пробовал libdivsufsort и esaxx, но не смог выяснить, как использовать их для моих нужд:
Я хочу использовать предопределенный набор строк с подстановочными знаками (или даже регулярными выражениями), чтобы соответствовать пользовательскому вводу. Я получил огромный список предопределенных строк, т.е.
«ЧТО ЕСТЬ *?» «ЧТО ТАКОЕ XYZ?» «СКОЛЬКО *?» …
Теперь я хочу найти наиболее подходящую строку (если она есть).
То есть
Пользовательский ввод:> ЧТО ТАКОЕ XYZ?
Должен найти «ЧТО ТАКОЕ XYZ?» вместо «ЧТО ЕСТЬ *?», но «ЧТО-ТО ЧТО-ТО?» должен найти «ЧТО ЕСТЬ *?» (при условии, что * является подстановочным знаком для любого количества символов).
Построение структуры не является критичным по времени (и структура не должна быть супер-эффективной), но поиск не должен занимать слишком много времени. Как это можно сделать легко? Любой Framework / Library или пример кода приветствуется
Спасибо
Решение
Вот решение, которое, я считаю, должно работать хорошо, если у вас очень большое количество шаблонов. Всего за 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
Вы извлекаете идентификаторы шаблона для каждого токена и помещаете их во временную структуру данных, которая подсчитывает частоту каждого идентификатора, например, хэш (например, a std::unordered_map<id_type,std::size_t>).
Затем вы сортируете это по частоте, чтобы узнать, что правило 1 было найдено дважды, а правило 2 — один раз.
Ты тогда применять правила, которые вы нашли, в порядке частоты, к вводимому тексту. Здесь вы используете библиотеку регулярных выражений или что-то подобное для генерации совпадений. Самое частое правило имеет наибольшее количество общих токенов с входным текстом, поэтому оно может хорошо совпадать.
общее преимущество подход заключается в том, что вам не нужно применять все правила к входным данным, а только те, которые имеют по крайней мере один токен, общий с входным, и даже среди тех, которые вы делаете это в порядке того, сколько токенов каждое правило разделяет с вход, и как только вы нашли подходящее правило, вы, вероятно, можете прервать оставшуюся часть процедуры сопоставления (или нет — в зависимости от того, хотите ли вы все правила соответствия в каждом случае или только одно, которое очень хорошо соответствует).
улучшение Вышеизложенное выполняет предварительный выбор правила на основе токенов. Вместо этого вы можете объединить все правила следующим образом:
what is *||where is *||do * need to||...
Затем вы создаете массив суффиксов этой объединенной строки.
Затем, учитывая входную строку, вы сравниваете ее с массив суффиксов идентифицировать все совпадения подстрок, включая совпадения, которые меньше одного токена или охватывают несколько токенов. В приведенном выше примере я предполагаю, что символы подстановки * а также $ включены в массив суффиксов, хотя, конечно, ни одна часть входной строки никогда не будет соответствовать им. Вы можете хорошо исключить их из массива суффиксов или заменить их на фиктивный символ.
После определения совпадений вы сортируете их по длине. Вы также должны сопоставить позиции совпадений в объединенной строке с идентификаторами правил. Это легко сделать, поддерживая массив начальных позиций правил относительно объединенной строки; Существуют также высоко оптимизированные методы, основанные на индексированных битовых векторах (я могу уточнить это при необходимости).
Как только у вас есть идентификаторы совпадающих правил, вы делаете то же самое, что и в случае с инвертированным индексом: применяете правила сопоставления, используя стандартное сопоставление регулярных выражений (или подобное).
Опять же, этот подход является относительно сложным и имеет смысл только тогда, когда у вас есть очень большое количество правил, и если есть вероятность, что поиск на основе токенов (или на основе подстрок) значительно сократит число правил-кандидатов. Из приведенных вами примеров правил я предполагаю последнее в данном случае, но если количество правил, с которыми вы имеете дело (порядка 10 тыс.), Оправдывает такой подход, я не уверен. Это может иметь больше смысла, если общее количество правил составляет 100 тысяч или миллионы.
Другие решения
Учитывая ваш комментарий о том, что шаблоны не нужно обновлять во время выполнения, я не уверен, что вам вообще нужна структура времени выполнения.
Я бы порекомендовал использовать re2c или же Ragel скомпилировать шаблоны в код, который будет выполнять сопоставление с шаблоном.
Вы можете посмотреть на сгибать. Из руководства:
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 должен дать вам очень быстрый сканер.
Проверять, выписываться CritBit деревья:
пример исходный код Это тривиально для C ++, если вы действительно чувствуете необходимость.
Чтобы найти все совпадения вы используете функцию critbit0_allprefixed
например
// Find all strings that start with, or are equal to, "WHAT IS"`
critbit0_allprefixed(tree, "WHAT IS", SomeCallback);`
SomeCallback называется для каждого матча.
Ты пытался Троичное поисковое дерево? Вот реализация C ++: http://code.google.com/p/ternary-search-tree/
У меня нет опыта того, как медленно построить троичное дерево, но я знаю, что поиск очень быстрый.
[редактировать]
Для сопоставления подстановочного знака внутри дерева вpartalMatchSearch:
(отказ от ответственности: это всего лишь предложение и никоим образом не проверено)
Вы можете добавить символы * в дерево и выражение if, например, в начале функцииpartalMatchSearch:
if ( ( *key != 0 ) && tree->splitChar == '*' )
{
this->partialMatchSearch( tree, key+1 );
}
Другими словами, просто рекурсивно вызывайте partMatchSearch с тем же узлом, но со строкой, установленной на следующий символ.
Если пространство не имеет значения, то вы можете сделать следующее, с моей головы.
Создайте дерево, у которого есть дочерние элементы возможных символов в этой точке дерева, где текущий уровень является индексом строки. Первым уровнем дерева является индекс уровня 0 или, вернее, индекс массива 0 в строке.
Каждый уровень будет индексом в строке, поэтому корневой узел будет индексом 0, а его дочерние элементы будут индексом 1. Каждый узел будет иметь N дочерних элементов, равных количеству возможных символов в этой точке в строке.
Итак, скажем, у вас есть корень, у которого есть набор возможных [«a», «b», «c»], у него будет три ребенка. Затем скажите, что вы хотите найти возможное совпадение для строки «ab», которую вы вернете ребенку, у которого есть маршрут «a», и перейдите оттуда.
Если вы достигнете конца строки до того, как доберетесь до конечного узла, тогда список возможных строк — это полное поддерево всех дочерних узлов вашего текущего узла.
Надеюсь, это имело какой-то смысл, но это выглядело бы как дерево Хаффмана, но каждый лист представлял бы собой потенциальную строку для выбора.
Я бы взял совет Кернигана и Пайка и выбрал разумный алгоритм, а затем перебил его.
Все ваши примеры ищут «самый длинный префикс», который подсказывает мне простое дерево, а не дерево суффиксов. Поскольку вам нужно хранить только ~ 10 тыс. Строк, вы сможете реализовать чартри максимум за пару часов, используя вложенные карты STL.
Если память не ограничена или производительность действительно критична, это должно быть хорошо.
Это не тот вопрос, который вы задаете. Вы хотели что-то предварительно приготовленное. Но…
Насколько сложным это должно быть? Если бы я пытался сделать то, что вы просите, я бы попытался сделать что-то немного больше места, но гораздо меньше времени.
Я бы (и должен) начать с дерева с индексом 0 алфавита.
Тогда каждый дочерний узел будет словом (словарем).
Тогда каждый дочерний узел этого будет потенциальным совпадением сегмента строки, зная, например, что «раунд» почти никогда НЕ ПРЯМО следует за «квадратом». Вы можете сказать: «Поместите круглый колышек в квадратное отверстие», но слово, которое следует за «раунд» — это «колышек». Таким образом, сегмент соответствует «круглый», «круглый колышек», «круглый мяч». Я бы вычеркнул статьи также потому, что они ничего не значат для предложения (обычно). Приведенный выше абзац будет переводиться как «каждый дочерний узел — это слово».
Однако я бы добавил эвристику, поскольку даже сложное B-дерево может работать медленно, когда у вас так много данных. Я видел их замедление до минуты или более при поиске очень больших наборов данных.
Это предполагает, что вы на самом деле не хотите использовать базу данных, которая, вероятно, будет самой быстрой из всех, если вы не захотите кодировать в ASM.