高效的数据结构用于带通配符的单词查找

Question

高效的数据结构用于带通配符的单词查找

performancealgorithmdata-structuresmemory-management

24

我需要将一系列用户输入的单词与大型单词字典进行匹配（以确保输入的值存在）。

因此，如果用户输入了：

"orange" it should match an entry "orange' in the dictionary.

现在的问题是用户也可以输入通配符或一系列通配符字符，比如说

"or__ge" which would also match "orange"

关键要求包括：

* this should be as fast as possible.

* use the smallest amount of memory to achieve it.

如果词汇列表的大小很小，我可以使用包含所有单词的字符串并使用正则表达式。

但是，考虑到该单词列表可能包含数十万条记录，我认为这种方法行不通。

那么，某种形式的“树”是否是解决这个问题的方式呢？

对此的任何想法或建议都将非常感激！

提前致谢， Matt

- Sway

1

我不确定，但我认为后缀树可能是你正在寻找的 - http://en.wikipedia.org/wiki/Suffix_tree - Rubys

1

你需要支持所有grep风格的通配符，还是只需要支持?（在你的情况下是下划线_）？ - Michael Dorgan

通配符只匹配单个字符还是可以匹配任意长度的字符串？ - drawnonward

只需下划线，每个下划线代表一个字符。 - Sway

6个回答

4

我首先会测试正则表达式的解决方案，并查看它是否足够快-你可能会感到惊讶！ :-)

但是，如果这不够好，我可能会使用前缀树。

基本结构是一棵树，其中：

顶层节点是所有可能的第一个字母（即假设您正在使用完整的字典，则可能有26个从a-z的节点）。
下一级包含每个给定第一个字母的所有可能的第二个字母
依此类推，直到对于每个单词都到达“单词结束”标记

然后，测试带通配符的给定字符串是否包含在您的字典中只是一个简单的递归算法，其中您要么具有每个字符位置的直接匹配，要么在通配符的情况下检查每个可能的分支。

在最坏的情况下（所有通配符，但只有一个单词恰好在字典的末尾），您将遍历整个树，但这仍然只是字典大小的O（n），因此不比完全的正则表达式扫描更糟糕。在大多数情况下，要么找到匹配项，要么确认没有这样的匹配项，都需要很少的操作，因为随着每个连续字母的到来，搜索树的大分支都被“修剪”。

- mikera

3

无论你选择哪个算法，都需要在速度和内存消耗之间做出权衡。

如果你能够承受 ~O(N*L) 的内存消耗（其中 N 是字典的大小，L 是一个单词的平均长度），你可以尝试这个非常快的算法。为了简单起见，我们假设拉丁字母表有 26 个字母，MAX_LEN 是单词的最大长度。

创建一个 2D 数组，其中每个元素是一个整数集合：set<int> table[26][MAX_LEN]。

对于字典中的每个单词，将该单词的索引添加到与单词中每个字母对应的位置的集合中。例如，如果“orange”是字典中的第 12345 个单词，则将 12345 添加到与 [o][0]、[r][1]、[a][2]、[n][3]、[g][4] 和 [e][5] 相对应的集合中。

然后，要检索与“or..ge”相应的单词，找到 [o][0]、[r][1]、[g][4] 和 [e][5] 位置处集合的交集即可。

- Igor Krivokon

1

你可以尝试使用字符串矩阵：

0,1: A
1,5: APPLE
2,5: AXELS
3,5: EAGLE
4,5: HELLO
5,5: WORLD
6,6: ORANGE
7,8: LONGWORD
8,13:SUPERLONGWORD

我们称之为不规则索引矩阵，以节省一些内存。按长度排序，然后按字母顺序排序。要访问字符，我使用符号x，y：z：x是索引，y是条目的长度，z是位置。您字符串的长度为f，字典中的条目数为g。

创建列表m，其中包含潜在匹配索引x。
从0到f迭代z。
- 它是通配符并且不是搜索字符串的最新字符吗？
  - 继续循环（所有匹配）。
- m是否为空？
  - 搜索所有x从0到g以匹配长度的y。!!A!!
    - z字符与该z处的搜索字符串匹配吗？将x保存在m中。
  - m是否为空？退出循环（无匹配）。
- m不为空吗？
  - 搜索m的所有元素。!!B!!
    - 与搜索不匹配吗？从m中删除。
  - m是否为空？退出循环（无匹配）。

通配符将始终通过“与搜索字符串匹配？”。而m与矩阵一样有序。

!!A!!：二分查找搜索字符串的长度。O(log n)
!!B!!：按字母顺序进行二分查找。O(log n)

使用字符串矩阵的原因是您已经存储了每个字符串的长度（因为它使搜索更快），但它还为您提供了每个条目的长度（假设其他常量字段），以便您可以轻松地在矩阵中找到下一个条目，以进行快速迭代。对矩阵进行排序不是问题：因为这只需要在字典更新时完成，而不是在搜索时间内完成。

- Pindatjuh

0

如果您可以忽略大小写，我假设是这样的话，在任何其他操作之前，请将字典中的所有单词和所有搜索术语的大小写设置为相同。大小写不重要。如果您有一些区分大小写的单词和其他不区分大小写的单词，则将单词分成两组并分别搜索。

您只匹配单词，因此可以将字典拆分为字符串数组。由于您仅对已知长度进行精确匹配，因此将单词数组拆分为每个单词长度的单独数组。因此，byLength [3]是所有长度为3的单词的数组。每个单词数组都应该排序。

现在，您有一个单词数组和一个具有潜在通配符的单词要查找。根据通配符的位置和是否存在，有几种方法可供选择。

如果搜索术语没有通配符，则在已排序的数组中执行二进制搜索。在此时可以进行哈希，这将更快，但不会快很多。如果绝大多数搜索术语没有通配符，则考虑使用哈希表或由哈希键控的关联数组。

如果搜索词在某些文字字符后有通配符，则在排序数组中进行二分查找以找到上限和下限，然后在该范围内进行线性搜索。如果通配符都是尾随的，则找到非空范围就足够了。

如果搜索词以通配符开头，则排序数组无法帮助您，除非您保留按反向字符串排序的数组的副本，否则需要进行线性搜索。如果制作这样的数组，则在尾随文字比前导文字多时选择它。如果不允许前导通配符，则没有必要。

如果搜索词既以通配符开头又以通配符结尾，则您将被困在等长单词内的线性搜索中。

因此，一个字符串数组的数组。每个字符串数组都是排序的，并包含相同长度的字符串。可选地，对于前导通配符的情况，基于反向字符串的排序可以复制整个结构。

总体空间为每个单词一个或两个指针，加上单词。如果您的语言允许，您应该能够将所有单词存储在单个缓冲区中。当然，如果您的语言不允许，grep可能更快。对于一百万个单词，数组的大小为4-16MB，实际单词的大小类似。

对于没有通配符的搜索词，性能会非常好。有了通配符，偶尔会对大量单词进行线性搜索。通过长度分解和单个前导字符，即使在最坏情况下，您也不应该需要搜索超过总字典的几个百分点。仅比较已知长度的整个单词将始终比通用字符串匹配更快。

- drawnonward

1

如果搜索词既以通配符开头又以通配符结尾，则您将被困在等长单词的线性搜索中。请查看我的答案：我仅在搜索字符串中不是最后一个字符时跳过通配符（在全通配符搜索的情况下，这是线性的），这将强制它使用二分搜索，无论是否使用通配符。 - Pindatjuh

0

尝试构建一个广义后缀树，如果字典将被序列查询匹配。有一种线性时间算法可以用来构建这样的树(Ukkonen后缀树构造)。

您可以通过从根节点遍历并使用通配符字符来匹配任何字符(如后缀树中的典型模式查找)，轻松地匹配每个查询(它的O(k)，其中k是查询的大小)。

- monn

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Norman Ramsey · Accepted Answer

将单词列表放入DAWG（有向无环词图）中，如Appel和Jacobsen在《世界上最快的Scrabble程序》一文中所述（哥伦比亚大学有免费副本）。对于搜索，您将遍历此图并保持指针集：在字母上，您会对具有该字母的子代进行确定性转换；对于通配符，您将所有子代添加到集合中。

效率与Thompson的grep NFA解释大致相同（它们是相同的算法）。 DAWG结构非常节省空间-比仅存储单词本身更节省得多。而且很容易实现。

最坏情况成本将是字母表大小（26？）的幂次，等于通配符的数量。但是除非您的查询以N个通配符开头，在实践中简单的从左到右搜索将有效。我建议不要允许查询以太多通配符开头，否则创建多个DAWG，例如镜像的DAWG，向左旋转三个字符的DAWG等。

匹配任意顺序的通配符，例如______始终会很昂贵，因为解决方案组合很多。DAWG将非常快速地枚举所有解决方案。