子序列查询的数据结构
在一个程序中，我需要高效地回答以下表单的查询：
给定一组字符串A和一个查询字符串q返回所有s ∈ A使得q是s的子序列
例如，给定A = {"abcdef", "aaaaaa", "ddca"}和q = "acd"恰好"abcdef"应该被返回。
以下是我迄今为止考虑过的内容：
对于每个可能的字符，请对其出现的所有字符串/位置进行排序。 用于查询交错涉及字符的列表，并扫描它以查找字符串边界内的匹配项。
这可能会更有效，而不是字符，因为有限数量的不同字符将使返回列表非常密集。
对于q可能有的每个n前缀，存储所有匹配字符串的列表。 n可能实际上接近于3.对于比这更长的查询字符串，我们强制初始列表。
这可能会加速一些事情，但我们可以很容易地想象出一些n-子序列存在于A所有的字符串附近，这意味着最坏的情况就像只是强制整个集合一样。
你知道有哪些数据结构，算法或预处理技巧可能有助于为大型A s有效执行上述任务吗？ （我s约100个字符）
更新：有人建议使用LCS来检查q是否是s的子序列。 我只想提醒一下，这可以使用一个简单的函数来完成，例如：
def isSub(q,s):
i, j = 0, 0
while i != len(q) and j != len(s):
if q[i] == s[j]:
i += 1
j += 1
else:
j += 1
return i == len(q)
更新2：我被要求详细说明q ， A及其元素的性质。 尽管我更喜欢一些尽可能通用的东西，但我认为A长度大概在10 ^ 6左右，并且需要支持插入。 元素s会更短，平均长度为64.查询q只有1到20个字符并且用于实时搜索，所以查询“ab”将在查询“abc”之前发送。 再次，我更喜欢解决方案尽可能少地使用上述内容。
更新3：我想到，一个具有O(n^{1-epsilon})查找的数据结构可以让你解决OVP /推翻SETH猜想。 这可能是我们遭受苦难的原因。 唯一的选择是反驳猜想，使用近似或利用数据集。 我想象一下四分体和尝试会在不同的设置中做最后一个。
它可以通过构建一个automaton来完成。 您可以从NFA （非确定性有限自动机，它就像一个不确定的有向图）开始，它允许使用epsilon字符标记边，这意味着在处理过程中可以从一个节点跳到另一个节点而不消耗任何字符。 我会尽量减少你的A 比方说，你A是：
A = {'ab, 'bc'}
如果你为ab字符串构建NFA ，你应该得到像这样的东西：
+--(1)--+
e | a| |e
(S)--+--(2)--+--(F)
| b| |
+--(3)--+
上图不是最好看的自动机。 但有几点需要考虑：
S状态是起始状态， F是结束状态。 F状态，这意味着你的字符串被认定为子序列。 e （epsilon）向前跳跃，因此在每个时间点你可以处于多于一个状态。 这被称为e闭包。 现在，如果给定b ，从状态S开始，我可以跳一个epsilon ，达到2 ，消耗b并达到3 。 现在给出end字符串，我消耗epsilon并达到F ，因此b有资格作为ab一个sub-sequence 。 所以，做a或ab你可以使用上面自动尝试自己。
NFA的好处是他们有一个开始状态和一个最终状态。 两个NFA可以使用epsilons轻松连接。 有各种算法可以帮助您将NFA转换为DFA 。 DFA是一个有向图，它可以遵循给定角色的精确路径 - 特别是，在任何时间点，它总是处于一种状态。 （对于任何NFA，都有一个对应的DFA，其状态对应于NFA中的状态集合。）
因此，对于A = {'ab, 'bc'}我们就需要建立NFA为ab那么NFA对bc再加入两个NFAs和构建DFA整个大的NFA 。
编辑
abc的子序列的NFA将是a?b?c? ，所以你可以建立你的NFA：
现在，考虑输入acd 。 要查询ab是否为{'abc', 'acd'}序列，可以使用此NFA： (a?b?c?)|(a?c?d) 。 一旦拥有NFA，您可以将其转换为DFA，其中每个州将包含它是abc或acd的子序列还是两者。
我使用下面的链接从正则表达式创建NFA图形：
http://hackingoff.com/images/re2nfa/2013-08-04_21-56-03_-0700-nfa.svg
编辑2
你是对的！ 如果你在A有10,000个唯一字符。 通过独特的我的意思是A是这样的： {'abc', 'def'}即A的每个元素的交集是空集。 那么你的DFA在状态方面是最差的，即2^10000 。 但我不确定什么时候可以做到这一点，因为永远不会有10,000独特的角色。 即使你在A中有10000个字符，仍然会有重复，并且这可能会减少状态，因为电子关闭最终可能会合并。 我无法估计它会减少多少。 但即使拥有1000万个州，您也只会消耗不到10 MB的空间来构建DFA。 您甚至可以在运行时使用NFA并查找e-closures，但这会增加运行时复杂性。 您可以搜索不同的论文，了解正则表达式如何转换为DFA。
编辑3
对于正则表达式(a?b?c?)|(e?d?a?)|(a?b?m?)
如果您将以上NFA转换为DFA，则会得到：
它实际上比NFA少很多。
参考：http://hackingoff.com/compilers/regular-expression-to-nfa-dfa
编辑4
在更多地摆弄那个网站之后。 我发现最坏的情况会是这样的A = {'aaaa'，'bbbbb'，'cccc'....}。 但即使在这种情况下，国家也比NFA国家要少。
测试
本主题有四个主要提案：
Shivam Kalra建议创建一个基于A所有字符串的自动机。 这种方法已经在文献中稍微尝试过，通常以“定向无环次序图”（DASG）的名称。
J Random Hacker建议将我的'前缀列表'想法扩展到查询字符串中的所有'n选择3'三元组，并且使用堆将它们合并。
在注释“数据库中的有效子序列搜索”中，Rohit Jain，Mukesh K. Mohania和Sunil Prabhakar建议使用Trie结构进行一些优化并递归搜索树中的查询。 他们也有类似于三重想法的建议。
最后是“朴素”的方法，wanghq建议通过存储A每个元素的索引来进行优化。
为了更好地了解什么是值得继续努力的，我已经在Python中实现了上述四种方法并基于两组数据进行了基准测试。 这些实现可以通过在C或Java中完成的很好的实现来提高几个数量级; 并且我没有包含针对'trie'和'naive'版本所提出的优化。
测试1
A由我的文件系统中的随机路径组成。 q是100个平均长度为7的随机[az]字符串。由于字母表很大（而且Python很慢），我只能在方法3中使用duplets。
以秒为单位的施工时间与A尺寸的函数关系： 
以秒为单位的查询时间与A尺寸的函数关系： 
测试2
A由长度为20的随机抽样的[ab]字符串组成q是平均长度为100的随机[ab]字符串。由于字母表很小，我们可以在方法3中使用四字节。
以秒为单位的施工时间与A尺寸的函数关系： 
以秒为单位的查询时间与A尺寸的函数关系： 
结论
双对数图有点难以阅读，但从数据中我们可以得出以下结论：
自动机查询速度非常快（恒定时间），但无法为|A| >= 256创建和存储 |A| >= 256 。 进一步分析可能会产生更好的时间/记忆平衡，或者可能适用于其余方法。
dup- / trip- / quadlet方法的速度是我的实施方案的两倍，而“天真”实施的速度是其四倍。 我只使用线性数量的合并列表，而不是j_random_hacker建议的n^3 。 有可能更好地调整方法，但总的来说令人失望。
我的执行情况总是比天真方式好两倍左右。 通过结合更多的预处理（比如“这个子树中的下一个c在哪里”）或者可能将其与三元组方法合并，这看起来像今天的赢家。
如果你可以做到性能低下，那么天真的方法相对而言只需很少的成本即可。
正如你指出的那样，可能A中的所有字符串都包含q作为子序列，在这种情况下，你不可能希望比O（| A |）做得更好。 （也就是说，对于A中的每个字符串我都可以比在（q，A [i]）上运行LCS所花费的时间做得更好，但我不会在这里专注于此。）
TTBOMK没有什么神奇的，快速的方式来回答这个问题（以后缀树是魔法的方式，快速回答涉及子字符串而不是子序列的相应问题）。 尽管如此，如果你期望大多数查询的答案平均很小，那么值得寻找加快这些查询的方法（那些产生小尺寸答案的答案）。
我建议基于启发式（2）的泛化来进行过滤：如果某个数据库序列A [i]包含q作为子序列，则它还必须包含q的每个子序列。 （不幸的是，反向不是真的！）因此，对于一些小的k，例如你建议的3，你可以通过建立一个列表数组来预处理，告诉你，对于每个长度为k的字符串s，包含s的数据库序列列表为一个子序列。 即c [s]将包含包含s的数据库序列的ID号列表作为子序列。 按数字顺序保存每个列表以便稍后启用快速交叉。
现在，每个查询q的基本思想（我们将立即改进）是： 查找 q的所有k个大小的子序列，在列表c []中查找每个子序列，然后交叉这些列表以找到A中可能包含q作为子序列的序列。 然后对于这个（希望是小的）交点中的每个可能的序列A [i]，用q执行O（n ^ 2）LCS计算以确定它是否确实包含q。
几点意见：