8

我正在寻找一种有效的数据结构来对一组非常庞大的字符串进行字符串/模式匹配。我发现了尝试、后缀树和后缀数组。但是到目前为止，我在 C/C++ 中找不到一个现成的实现（而且我自己实现它似乎很困难并且容易出错）。但我仍然不确定 Suffix-Arrays 是否真的是我正在寻找的东西......我已经尝试过 libdivsufsort 和 esaxx，但无法找到如何使用它们来满足我的需求：

我想使用一组预定义的字符串，带有通配符（甚至是正则表达式）来匹配用户输入。我有一大堆预定义的字符串，即

“什么是 *？” “什么是 XYZ？” “多少 *？” ...

现在我想找到最匹配的字符串（如果有的话，那就完全匹配了）。即用户输入：>什么是XYZ？应该找到“什么是 XYZ？” 而不是“什么是*？”，而是“什么是什么？” 应该找到“什么是*？” （假设 * 是任何字符数的通配符）。

构建结构不是时间紧迫的（并且结构不必非常节省空间），但搜索不应该花费太长时间。怎么能轻易做到呢？欢迎任何框架/库或代码示例

谢谢

4

9 回答 9

3

鉴于您认为模式不需要在运行时更新，我不确定您是否需要运行时结构。

我建议使用re2c或ragel将模式编译为执行模式匹配的代码。

于 2012-11-19T00:27:02.460 回答
3

你可能想看看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 表，这会导致更多的缓存未命中，所以更多的模式会受到一些惩罚。但对于我能想到的任何匹配系统都是如此。）

但是，您必须以正确的顺序列出您的模式以正确匹配它们。如果有问题，Flex 可能会告诉您。例如，如果您颠倒上述扫描仪中 WHAT-IS-XYZ 和 WHAT-IS 模式的顺序，flex 会告诉您：

:; flex matcher.l
matcher.l:3: warning, rule cannot be matched

如果你能满足 flex 的要求，flex 应该会给你一个非常快速的扫描仪。

于 2012-11-22T09:10:10.557 回答
3

上述许多答案在实践中都不能很好地工作，或者不构成您问题的最知名答案：例如，使用编译器构造中的扫描仪生成器（re2c，lex，flex，...）可能会失败大型词典，因为这些工具是为编程语言设计的，通常最多有几百个内置关键字。

我可以推荐两种替代方法：

(1) 选择一个 C++ trie 类，将字符串映射到第二个数组中使用的 size_t id，以存储有效负载数据。使用 Web 搜索引擎搜索查询，例如：

c++ trie c++14 implementation fast "small footprint" site:github.com

找到合适的候选人 - 在撰写本文时，例如https://github.com/Tessil/hat-trie看起来相当不错（干净、可移植、现代的代码，并且有一篇科学论文可供参考，这增加了可信度）；或者

(2) 将字符串词典到有效载荷数据的映射表示为有限状态转换器 (FST)，它是 NFA（带输出的自动机）的扩展，由FOMA、XFST或OpenFST实现。

第一个选项意味着您必须测试可用的库以确保易用性和可扩展性。第二个选项意味着您必须让自己熟悉 FST 和现有的实现库及其许可证。

（第二种方法被计算语言学家用来模拟大型单词列表，政府也用来扫描你在互联网上写的所有东西，所以它的扩展性很好。）

于 2020-04-19T11:06:33.803 回答
2

查看CritBit树：

如果您真的觉得需要，对 C++-ise 来说微不足道的示例源代码。

要查找所有匹配项，请使用该功能critbit0_allprefixed

例如

// Find all strings that start with, or are equal to, "WHAT IS"`
critbit0_allprefixed(tree, "WHAT IS", SomeCallback);`

SomeCallback为每场比赛调用。

于 2012-11-13T17:06:35.790 回答
2

您是否尝试过三元搜索树？这是一个 c++ 实现：http ://code.google.com/p/ternary-search-tree/

我没有任何关于构建三叉树有多慢的经验，但我知道搜索非常快。

[编辑]

在 partialMatchSearch 中匹配树内的通配符：（免责声明：这只是一个建议，未经任何测试）

您可以将 * 符号添加到树中，并在 partialMatchSearch 函数的开头添加这样的 if 子句：

  if ( ( *key != 0 ) && tree->splitChar == '*' )
  {
     this->partialMatchSearch( tree, key+1 );
  }

换句话说，只需递归调用具有相同节点但字符串设置为下一个字符的 partialMatchSearch。

于 2012-11-20T08:21:25.240 回答
2

我相信，如果您有大量模式，这是一个解决方案应该可以很好地工作。仅仅 10k 可能有点过头了，实现它意味着相对大量的工作，但你可能仍然感兴趣。

基本思想是创建一个倒排索引，将模式的子字符串映射到模式 ID。首先，每个模式都有一个 ID：

1: what is *
2: where is *
3: do * need to
etc.

然后我们创建一个倒排索引。在最简单的情况下，我们将模式拆分为标记并将每个标记映射到它出现的模式 ID 列表。我们可以灵活地定义标记，但一种方法是假设每个空格分隔的单词是一个令牌。所以这里是索引：

what  -> 1
is    -> 1,2
where -> 2
do    -> 3
need  -> 3
to    -> 3

然后，当您从用户那里获得输入字符串时，您将其拆分为标记并在索引中查找它们。您可以组合从索引中获得的所有模式 ID。例子：

INPUT: what is something?

TOKENS:
   what      -> 1
   is        -> 1,2
   something -> n/a

您检索每个标记的模式 ID 并将它们放入一个临时数据结构中，该数据结构计算每个 ID 的频率，例如哈希（例如 a std::unordered_map<id_type,std::size_t>）。

然后，您按频率对其进行排序，以发现规则 1 被找到了两次，而规则 2 被找到了一次。

然后，您按照频率的顺序将找到的规则应用于输入文本。在这里，您使用正则表达式库或类似的东西来生成匹配项。最频繁的规则与输入文本有最多的共同标记，因此它很可能匹配得很好。

该方法的总体优势是您不需要将所有规则应用于输入，而只需将那些与输入至少具有一个共同标记的规则应用，甚至在那些您按照每个规则有多少标记的顺序执行的规则中与输入共享，一旦找到匹配规则，您可能会中断匹配过程的其余部分（或不 - 取决于您是否想要每种情况下的所有匹配规则，或者只需要一个非常好的匹配）。

改进以上执行基于令牌的规则预选。相反，您可以像这样连接所有规则：

what is *||where is *||do * need to||...

然后你构造这个连接字符串的后缀数组。

然后，给定一个输入字符串，将其与后缀数组进行匹配，以识别所有子字符串匹配项，包括小于一个标记或跨越多个标记的匹配项。在上面的例子中，我假设通配符*和$包含在后缀数组中，当然输入字符串的任何部分都不会匹配它们。您可以很好地将它们从后缀数组中排除或用虚拟字符替换它们。

一旦确定了匹配项，就可以按长度对它们进行排序。您还必须将连接字符串中的匹配位置映射到规则 ID。这很容易通过维护规则相对于连接字符串的起始位置数组来实现；还有一些基于索引位向量的高度优化的方法（如有必要，我可以详细说明）。

获得匹配规则 ID 后，您可以执行与倒排索引案例相同的操作：使用标准正则表达式匹配（或类似方法）应用匹配规则。

同样，这种方法相对复杂，并且仅在您拥有大量规则时才有意义，并且基于标记（或基于子字符串）的查找可能会显着减少候选规则的数量。从您给出的示例规则中，我假设在这种情况下是后者，但是如果您正在处理的规则数量（大约 10k）证明这种方法是合理的，我不确定。如果规则的总数在 100ks 或数百万个，这可能更有意义。

于 2012-11-22T15:38:50.467 回答
0

如果空间不是问题，那么您可以在我的脑海中执行以下操作。

在树中的这一点上创建一个具有可能字符的子级的树，其中当前级别是字符串的索引。树的第一级是索引级别 0，或者更确切地说是字符串中的数组索引 0。

每个级别都是字符串的索引，因此根节点的索引为 0，它的子节点的索引为 1。每个节点的 N 个子节点的数量等于字符串中此时可能出现的字符数。

所以，假设你有一组可能的 [ "a", "b", "c" ] 它会有三个孩子。然后假设您想找到字符串“ab”的可能匹配项，您将递归到具有“a”路径的孩子并从那里开始。

如果在到达叶节点之前到达字符串的末尾，那么可能的字符串列表就是当前节点上所有子节点的整个子树。

希望这有任何意义，但它看起来有点像一棵霍夫曼树，但每片叶子都有一个潜在的字符串可供选择。

于 2012-11-13T16:52:40.717 回答
0

我会接受 Kernighan 和 Pike 的建议，选择一个合理的算法，然后蛮力进行。

你所有的例子都在寻找“最长的前缀”，这对我来说是一个简单的树而不是后缀树。鉴于您只需要存储约 10k 字符串，您应该能够使用嵌套的 STL 映射在最多几个小时内实现一个 char-trie。

除非内存很紧或性能确实很关键，否则这应该没问题。

于 2012-11-22T06:07:17.790 回答
0

这不是你要问的问题。你想要一些预先煮好的东西。但...

这需要有多复杂？如果我试图做你所要求的，我会尝试一些空间密集但时间密集的东西。

我会（并且已经）从字母表索引为 0 的树开始。

然后每个子节点将是一个单词（字典）。

然后，它的每个子节点都将是一个潜在的字符串段匹配，例如，知道“圆形”几乎从不直接跟随“方形”。你可能会说，“把圆钉放在方孔里”，但“圆”后面的词是“钉”。所以“round”的段匹配将是“round peg”、“round cup”、“round ball”。我也会删除文章，因为它们对句子没有任何意义（通常）。上面的段落将翻译为“每个子节点都是单词”。

不过，我会添加一个启发式方法，因为当您拥有这么多数据时，即使是高级 B 树也会变慢。在搜索非常大的数据集时，我已经看到它们减慢到一分钟或更长时间。

这是假设您不想实际使用数据库，除非您想在 ASM 中编码，否则这可能是最快的。

于 2012-11-22T12:32:09.050 回答