algorithm - 针对多个目标的快速不完全匹配算法

Question

假设我有一组 S ，元素是 N 元组，即 (xi1, xi2, ... , xin) .

给定元素 x = (x1, x2, ..., xn)和 y = (y1, y2, ..., yn) , matches(x,y,M)当且仅当至少 M x 的元素和 y是平等的。

现在给定一个集合S , matchSet(x,S,M)返回 S 的元素哪个matches(x,y,M)是真的。

假设S有这样的数据 matchSet平均只会匹配 0 或 1 个元素(它偶尔会匹配更多，但很少)，有没有办法写 matchSet与结构S以便它的运行时间与 S 的大小呈次线性关系，并且它的空间是合理的(即不在 2^L 上放置 S 索引，其中 L 是元素的长度)？

或者，快速运行 matchManySet(S', S, M)也可以接受，它运行 matchSet对于 S' 的每个元素，只要它花费的时间明显少于 S 的大小S' 的倍数.

Answer 1

这个任务对我来说听起来很有趣。我有一些想法，不幸的是有人应该测试它(我没有时间实现)。存储这种元组的数据结构让我想起后缀树。 (有关更多信息，请参阅 https://en.wikipedia.org/wiki/Suffix_tree)。

例如，您可以将集合 Sx 存储在一个后缀树中，将 Sy 存储在另一棵后缀树中。在这种情况下，您的任务归结为通过合并给定的两棵树来创建结果后缀树(当然，在合并期间您应该使用特定的谓词，例如元组是否有 K 出现)。总体算法复杂度为 O(N + M)，其中 N、M 是输入后缀树的大小。

希望这样的想法对你有所帮助。

编辑:这个想法有很强的限制——元组的字典顺序