给定一组非负整数元组，是否可以通过一些预处理快速判断该集合中的某个元组是否支配给定的查询元组？

Question

因此，这是由最近的一个问题所激发的，该问题询问如何快速确定查询单词是否可以被置换以匹配给定词典中的特定单词。快速查询解决方案的基本思想很简单:首先，对于预处理，对于每个字典单词，对字母表中每个字母出现的次数的元组进行散列，然后在预处理之后，对于查询单词，您所要做的就是对相同类型的元组进行散列，并查看是否在散列表中得到匹配。

所以基本上，这个问题归结为找出非负整数的元组(字母表中每个字母的计数)是否与哈希表中的元组完全匹配，与原始单词字典的大小相比，哈希表可以首先快速构建，并且不会占用太多内存。

所以现在我想扩展这个问题，就字符串而言，扩展后的问题是查询字符串是否可以被置换以匹配其中一个字典字符串的子序列(即，不一定是相邻子序列，尽管连续的情况也很有趣)。就字符计数的元组而言，这等同于确定在字典中是否存在主导查询元组的元组，即，字典单词的元组中的每个计数都大于或等于查询单词的元组中的对应计数。

为了获得快速解决方案，假设问题只是对查询的答案回答yes/no，如果是，则只返回满足查询的一个可能的字典单词(count tuple)。

就字典大小而言，是否有任何种类的预处理将花费合理数量的时间/存储器，使得这些子序列排列问题可以比仅仅通过对字典单词数据集的多个副本进行排序更快地得到回答，其中每个副本通过特定字符的出现来排序，然后线性地搜索给出满足该字符的查询字符串的最低数目的成员的排序列表以寻找匹配。

我有一种不好的感觉，我可能需要一个可能非常高维的范围树(维度是字母表中的字符数)，这样就可以执行范围查询了。然而，这个问题的范围查询有一种非常特殊的形式，所以我希望有更好的形式，特别是对于大小为d的字母表和n个单词的字典，范围树方法将需要O(n (log n)^(d-1))预处理时间和存储，查询将花费O((log n)^(d-1))时间。依赖于d，对于长度不超过w的n个单词的字典，范围树的经验查询时间很容易超过蛮力O(nw)，并且这种暴力方法甚至不需要任何预处理。

Answer 1

如果我们想要缩短搜索阶段，我们的预处理阶段可以为所有输入序列生成(和散列)所有允许的子序列。则搜索阶段被简化为检查从要发现的序列中获得的单个特定散列的存在/不存在。

下面的Python代码演示了这一思想。

itertools Python库帮助我们找到组合。

import itertools

考虑到我们有作为有序序列可用的输入数据：

# Keep the values ordered
DATA = (
    (1, 2, 2, 4),
    (1, 3, 5, 5),
    (2, 4),
    (2, 4, 6, 6, 6, 7, 8, 9, 10, 11, 12, 13, 15),
)

我们可以预先计算所有允许的子序列的集合：

ALLOWED = {c for d in DATA for l in range(len(d)) for c in itertools.combinations(d, l+1)}

我们可以测试它：

assert (1,) in ALLOWED
assert (1, 2) in ALLOWED
assert (1, 3) in ALLOWED
assert (1, 4) in ALLOWED
assert (1, 5) in ALLOWED
assert (1, 6) not in ALLOWED
assert (1, 2, 2, 4) in ALLOWED
assert (1, 2, 2, 5) not in ALLOWED