data-structures - 哈希中的高效模糊查找

Question

我有很多数据需要非常快速地进行模糊查询(当然，这是相对的，但是对于大约 1 亿个键，在几秒的量级内，但理想情况下更快)。它采用键/值对的形式，其中键是一个唯一的字符串，值是一个字符串数组。这是实际数据的结构，但我可以自由地将其组织成任何可以加快查找速度的数据结构。

键值的查找不仅应包括该确切键的值，还应包括预定阈值(例如 5)内编辑距离内的所有键的值。

例如，hello 的查找不仅应该返回在 hello 的键下索引的所有值，而且还应该返回 Hello 的值， hello!、yello、helo、hellooo 等

当然，天真的解决方案是遍历每个键，计算其编辑距离，如果它在某个阈值内则包括它的值。但是，此解决方案不能很好地扩展 O(n) 时间复杂度来迭代每个键，O(n-1) 来迭代每个键以将其与之比较，以及 O(n) 每次 levenshtein 计算，导致查找O(n * n * n-1) 的时间，这当然是 Not Acceptable 。

如何构造此数据以优化查找时间复杂度？空间复杂性、插入、删除和编辑运行时间都是无关紧要的(不过，我更愿意将插入操作保持在一秒以内，以避免出现瓶颈)。

关于数据的一些信息:

• 唯一键已准备好以 10 个/秒的相当恒定的速度添加
• 字符串已准备好以 10/秒的相当恒定的速率附加到值数组
• 每个键值的大小通常为 1-5 个元素，但一些异常值有数百个
• 值数组中的每个字符串的长度通常为 20-40 个字符

Answer 1

我不确定这里使用的数据结构，但最简单的选择可能是使用 ElasticSearch 的 fuzzy query或其亲属。嗯，从根本上说，它使用的是倒排索引，并且对执行模糊查询进行了良好的优化。