4

我的问题是，我的词典大约有 200,000 字左右。该文件大小为 1.8mbs。我想要来自用户的输入，比如 **id，并且我想要显示所有可能的匹配项，其中 * 可以是任何字母 AZ。（说，女仆等）

我正在寻找有关最有效方法的一些建议，因为我希望用户能够添加更具体的字母并实时更新单词匹配。

我的想法是尝试使用 RegexKitLite，但我感觉会非常慢。

感谢您的任何意见！

编辑：您认为可以使用 NSPredicates 来实现这一目标吗？

4

1 回答 1

4

您可以采取哪些措施来优化搜索性能，很大程度上取决于您希望如何限制这些通配符的使用。

准确地说：你的通配符有什么特点？

  • 仅前缀通配符 (m/.+foobar/)
  • 仅后缀通配符 (m/foobar.+/)
  • 原子通配符 ( m/./)
  • 动态通配符 ( m/.+/)

仅前缀通配符

使用前缀树或DAWG

仅后缀通配符

使用后缀树或DAWG

原子通配符

大幅减少您必须运行的比赛数量的一种方法是：

从您的单词集合中构建一个BKTree。

只要（并且只要）您的通配符具有固定长度（在您的情况下为 1），您就可以简单地在 BKTree 中查询具有精确编辑距离的节点n，其中n通配符的数量。传统的 BKTree 查询有一个方差上限。在您的情况下，您需要引入一个额外的下限，将可接受的方差范围缩小到精确[n,1]（与传统上相比[0,n]）。你会得到一个单词数组，这些单词与你的查询单词不同，只是n字符不同。

对于查询，**id一些可能的匹配项是：

  • void（2x 加法）
  • laid（2x 加法）
  • bad（1x 替换，1x 添加）
  • to（2x 替换）

虽然这些还不是您查询的正确匹配项，但它们仅代表您的全部单词集合的一小部分。

所以最后但并非最不重要的是，您运行 Regex 匹配这些结果并返回所有剩余的匹配项。

BKTrees引入levenshtein 距离作为一些空间启发式方法，以大幅（取决于您的单词集合中的熵）减少所需比较/匹配的数量。

要获得额外的优化，您可以使用多个 BKTrees：

将您的收藏分为子集。一组用于 length 的单词，一组1用于 length 2，一组用于3，以此类推。然后从每个子集构建一个 BKTree。对于查询**id，您将查询BKTree的长度为 4（通配符被视为字符）。
这适用于通配符被解释为m/./. 但是，如果您的通配符将被解释为m/.?/您将查询BKTrees的长度为 3 和 4。

除了BKTrees ，您还可以使用GADDAG，这是一种专门用于拼字游戏样式查找的数据结构（Trie 的专门化）。

如果我没记错的话，你的通配符也需要被严格解释m/./。

动态通配符

现在想不出比针对您的单词集合运行您的正则表达式更好的解决方案。

于 2011-06-12T21:13:13.027 回答