0

缩写是一串字母数字字符。数字代表要跳过的字母数，例如 i18n 是国际化的缩写。inter15 和 20 也是如此。假设您有一本单词词典，在词典中找到与给定缩写匹配的所有单词的最快方法是什么？你可以为你的字典使用你喜欢的任何数据结构，但是查找匹配单词的算法必须比 O(n) 更好，其中 n 是字典中的单词数。

4

3 回答 3

1

所以你有一个查询是prefix - count - suffix. 有几种方法可以解决这个问题。

如果前缀永远不会为空，那么您可以构建一个前缀树（它只是一个 trie），并查询以该前缀开头的所有单词，过滤那些具有请求长度和后缀的单词。

您可以通过构建一个通用的后缀树来做同样的事情。

或者，由于前缀或后缀可能为空，您可以构建前缀树和后缀树。查询两者，过滤长度，然后合并结果。

您可以想象构建一个单一的前缀-后缀树。数据结构比拥有两棵独立的树要复杂一些，但它需要的内存更少。

我记得（已经有几年了），您可以使用有向无环词图 (DAWG) 完成所有这些以及更多操作（搜索缺少字母的词等）。

于 2014-01-09T17:36:19.053 回答
0

这是 a10n 树的一个想法（缩写树，或者应该是 a10n t2e？）。

丢失的字母被丢失的块的长度替换，所以匹配的长度是事先知道的。将字典细分为包含恒定长度单词的子字典是有意义的：

dict -> dict2 -> {ad, ah, am, an, as, at, ...}
     -> dict3 -> {abe, abo, abu, ace, act, ada, add, ... }
     -> dict4 -> {abba, abbe, abby, ...}
     -> ...

每个字典都包含一个有序的单词列表。如果缩写是“5”，则返回长度为 5 的子字典的列表。如果缩写是“green”，即根本没有缩写，则使用二进制搜索检查该单词是否在列表中。

处理了琐碎的案例，我们必须找到一种快速搜索此列表的方法。让我们介绍一个位置和字母树。树的第一层指的是字母的位置，第二层指的是字母本身，就像在 trie 中一样，例如：

dict3 ->  i == 0 -> a   -> {ant}
                 -> b   -> {bat, bee}
                 -> c   -> {cat, cod, cow}
                 -> ...
          i == 1 -> a   -> {bat, cat, rat}
                 -> b   -> {}
                 -> c   -> {}
                 -> ...

现在找到所有给定字母的列表的交集。如果我们正在寻找“c2”，我们会在 (0, c) 处获取列表。如果我们正在寻找“b1t”，我们在 (0, b) 和 (2, t) 处取列表的交集。当列表被排序时，找到交叉点应该相当快。

还有其他方法。Tries 是一种数据结构，可以让我们快速搜索字典。我在对现已删除的帖子的评论中说过，在这种情况下，我认为尝试不是一种合适的数据结构，因为尝试在第一个字母已知的情况下有助于查找单词。但我现在不太确定：当找到通配符（即丢失的字母）时，可以遍历 trie 的所有分支。对于像 'i18n' 这样的词，分支的数量似乎很大，但实际上，会有很多空分支。在我大约 45,000 个单词的（小）测试字典中，没有匹配“i18n”的单词，甚至没有国际化。因此，对于真正的字典，尝试甚至可能是一种选择。

（向删除答案的用户道歉，但我在评论中提到了字典的单个尝试。如果字典不庞大，每个长度的子尝试都可能有效。）

于 2014-01-09T10:06:49.267 回答
0

一种解决方案是对多个数组中的所有单词进行分类。每个数组都包含具有特定数量字母的所有单词。例如，一个包含 4 个字母的单词的数组，例如：food、wood、like、pike 等，另一个包含 5 个字母的单词等。

因此，使用您的缩写 i18n，您拆分字符和数字：“in”“18”并将字符数量添加到数字：2+18 =20。现在您知道您的单词在包含 20 个字母的单词数组中。

我认为我们可以做得更好，但这比在整个字典中寻找一个单词要好。

于 2014-01-09T09:46:57.067 回答