子序列查询的数据结构

Question

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

给定一组字符串A和查询字符串q返回所有s ? A这样q是一个序列的s

例如,给定A = {"abcdef", "aaaaaa", "ddca"}并且q = "acd"确切地"abcdef"应该返回.

---

以下是我到目前为止所考虑的内容:

1. 对于每个可能的字符,请为其显示的所有字符串/位置创建排序列表.对于查询交错所涉及字符的列表,并扫描它以查找字符串边界内的匹配.

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

2. 对于每个n前缀q可能具有的,存储所有匹配字符串的列表.n实际上可能接近于3.对于长于此的查询字符串,我们强制执行初始列表.

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

---

您是否知道任何数据结构,算法或预处理技巧可能有助于大型As 有效执行上述任务？(我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猜想.这可能是我们遭受苦难的原因.然后,唯一的选择是反驳猜想,使用近似或利用数据集.我想象四胞胎和尝试会在不同的设置中做最后一次.

Answer 1

它可以通过建立一个automaton.你可以从NFA(非确定性有限自动机,就像一个不确定的有向图)开始,它允许用epsilon字符标记的边,这意味着在处理过程中你可以从一个节点跳到另一个节点而不消耗任何字符.我会尽力减少你的A.让我们说你A是:

A = {'ab, 'bc'}

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

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

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

1. Sstate是起始状态,F是结束状态.
2. 如果您处于F状态,则表示您的字符串符合子序列.
3. 在自动机内传播的规则是你可以消耗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.

编辑

NFA的子序列abc将是a?b?c?,因此您可以将您的NFA构建为:

现在,考虑输入acd.要查询if是否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

你是对的!如果你有10,000个独特的字符A.通过唯一我的意思是A是这样的:{'abc', 'def'}即A的每个元素的交集是空集.那么你的DFA在状态方面就是最糟糕的情况2^10000.但是我不确定什么时候会有可能,因为永远不会有10,000独特的角色.即使你在A中有10,000个字符仍然会有重复,这可能会减少很多状态,因为e-closure最终可能会合并.我无法估计它可能会减少多少.但即使拥有1000万个州,你也只能消耗不到10mb的空间来构建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国家要小.

Answer 2

测试

这个帖子中有四个主要提议:

1. Shivam Kalra建议根据所有字符串创建一个自动机A.在文献中已经尝试了这种方法,通常名称为"有向无环子序列图"(DASG).

2. J Random Hacker建议将我的'前缀列表'思想扩展到查询字符串中的所有'n选择3'三元组,并使用堆将它们全部合并.

3. 在"数据库中的高效子序列搜索"中,Rohit Jain,Mukesh K. Mohania和Sunil Prabhakar建议使用Trie结构进行一些优化,并递归搜索树以进行查询.他们也有类似于三联想法的建议.

4. 最后还有'天真'的方法,wanghq建议通过存储每个元素的索引进行优化A.

为了更好地了解值得继续努力的内容,我已经在Python中实现了上述四种方法,并在两组数据上对它们进行了基准测试.通过在C或Java中完善的实现,可以更快地实现几个实现; 我还没有包含针对'trie'和'naive'版本建议的优化.

测试1

A由我的文件系统中的随机路径组成.q是100个[a-z]平均长度为7的随机字符串.由于字母表很大(Python很慢),我只能使用方法3的duplet.

以秒为单位的施工时间与A尺寸的关系:

以秒为单位的查询时间与A大小的关系:

测试2

A由随机抽样[a-b]的长度为20的字符串组成.q是100个[a-b]平均长度为7的随机字符串.由于字母表很小,我们可以使用方法3的quadlet.

以秒为单位的施工时间与A尺寸的关系:

以秒为单位的查询时间与A大小的关系:

结论

双对数图有点难以阅读,但从数据我们可以得出以下结论:

• 自动机在查询时非常快(恒定时间),但它们无法创建和存储|A| >= 256.有可能进行更密切的分析可以产生更好的时间/内存平衡,或者适用于其余方法的一些技巧.

• dup-/trip-/quadlet方法的速度大约是我的trie实现速度的两倍,是'naive'实现速度的四倍.我只使用了线性数量的列表进行合并,而不是n^3j_random_hacker所建议的.有可能更好地调整方法,但总的来说它是令人失望的.

• 我的trie实现始终比天真的方法做得好一两倍左右.通过结合更多预处理(如"这个子树中下一个'c'在哪里")或者可能将它与三元组方法合并,这似乎是今天的赢家.

• 如果你的性能可以降低,那么天真的方法相对来说只需很少的成本就可以了.