search - 字符串模糊查找

Question

这是一道面试题。

给定一个由名称组成的文件，您将使用什么数据结构来验证名称是否在列表中。如果我们说一个名称与文件中的名称相差不超过一个字符，那么它是有效的怎么办？

Answer 1

For the first question (exact search), you can use a hash table or a trie. Bloom filters may tell you "No" earlier with a space overhead, but can never tell you a definite "Yes."

For the second question (fuzzy search), much more advanced techniques are needed. Check the blog at http://blog.srch2.com/2012/03/fuzzy-search.html to discuss different solutions to this problem.

Answer 2

我会说这取决于上下文：如果你有数百万个名字，一份要履行的合同和一个为你做的产品，那么我会说去吧，忘记自己写它。

但是，在面试问题的背景下，我的建议是包含所有可能错误的DAWG 。

很久以前，我听说拼写检查器包含一个可能有错误的单词列表（而不是尝试匹配一个有效单词列表），但我不知道这是多么真实。

我曾经做过一次在单词列表中查找单词的问题（有错误），但它不仅限于一个错误，而且没有很多可用的内存。所以这些词被简单地存储为一个列表（DAWG 需要节点和指针，这将需要太多开销）。

Answer 3

我建议将文件中的名称存储到 trie 或 DAWG 中（更好的空间效率）。名称到达后，开始遍历数据结构。您将有 4 个变体：

1. 找到名称 --> 名称有效
2. 数据结构中的死胡同 --> 检查名称中剩余的字符数，如果不超过 1 --> 名称有效；否则无效。
3. 名称已结束且尚未到达结构中的叶子 --> 检查当前位置是否至少有一个叶子（将占用 O（字母大小）） --> 如果是，则名称有效；否则无效。
4. 在单词中间遇到的差异 --> 从下一个字符继续遍历 --> 不允许更多错误（从此时起，第 2 和第 3 段不再有效）。