string - 子序列查询的数据结构

Question

在一个程序中，我需要有效地回答以下形式的查询:

Given a set of strings A and a query string q return all s ∈ A such that q is a subsequence of s

例如，给定 A = {"abcdef", "aaaaaa", "ddca"}和 q = "acd"正是 "abcdef"应该退回。

以下是我迄今为止考虑过的:

对于每个可能的字符，制作一个排序列表，列出它出现的所有字符串/位置。查询交错涉及的字符列表，并扫描它以查找字符串边界内的匹配项。

这对于单词而不是字符可能会更有效，因为有限数量的不同字符会使返回列表非常密集。

对于每个 n 前缀 q可能有，存储所有匹配字符串的列表。 n实际上可能接近 3。对于长于该长度的查询字符串，我们会强制使用初始列表。

这可能会加快速度，但可以很容易地想象在 A 中的所有字符串附近存在一些 n 子序列。 ，这意味着最坏的情况与暴力破解整个集合相同。

您是否知道任何数据结构、算法或预处理技巧可能有助于有效地为大型 A 执行上述任务？年代？ (我的 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 猜想。这大概就是我们受苦的原因。唯一的选择是反驳猜想、使用近似值或利用数据集。我想 quadlets 和尝试会在不同的设置中做最后一个。

Answer 1

可以通过构建 automaton 来完成.您可以从 NFA 开始(非确定性有限自动机，类似于不确定性有向图)，允许用 epsilon 标记的边字符，这意味着在处理过程中，您可以从一个节点跳转到另一个节点，而不会消耗任何字符。我会尽量减少你的A .比方说你A是:

A = {'ab, 'bc'}

如果您构建 NFA对于 ab字符串你应该得到这样的东西:

     +--(1)--+ 
  e  |  a|   |e
(S)--+--(2)--+--(F)
     |  b|   |
     +--(3)--+

上图不是最好看的自动机。但有几点需要考虑:

S state 是起始状态，F是结束状态。

如果您在 F声明这意味着您的字符串有资格作为子序列。

在 autmaton 内传播的规则是您可以使用 e (epsilon) 向前跳跃，因此您可以在每个时间点处于多个状态。这称为 e关闭。

现在如果给出 b ，从状态 S 开始我可以跳一个 epsilon , 到达 2 ，并消耗 b并联系 3 .现在给出 end我消费的字符串 epsilon并联系 F ，因此 b有资格作为 sub-sequence的 ab . 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 中有 10,000 个字符，仍然会有重复，这可能会大大减少状态，因为 e-closure 最终可能会合并。我无法真正估计它可能会减少多少。但是即使有 1000 万个状态，您也只会消耗不到 10 mb 的空间来构建 DFA。您甚至可以使用 NFA 并在运行时查找电子闭包，但这会增加运行时的复杂性。您可以搜索有关如何将大的正则表达式转换为 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 州少。