有效的大规模字符串搜索问题

我同意尝试使用后缀trie是一个好主意,只是数据集的巨大规模可能会使它的构造占用的时间与使用它节省的时间一样多。如果你要多次询问他们来分摊建筑成本,他们是最好的。可能有几百个问题。

您可以构建常规trie并添加通配符边。那么你的复杂度是O(n),其中n是模式的长度。你必须替换 ** 具有 *

如果单词表是 然后trie看起来有点像这样:

  (I ($ [I])
   a (m ($ [am])
      n ($ [an])
      ? ($ [am an])
      * ($ [am an]))
   o (x ($ [ox])
      ? ($ [ox])
      * ($ [ox]))
   ? ($ [I]
      m ($ [am])
      n ($ [an])
      x ($ [ox])
      ? ($ [am an ox])
      * ($ [I am an ox]
         m ($ [am]) ...)
   * ($ [I am an ox]
      I ...
    ...

下面是一个示例python程序:

import sys

def addWord(root, word):
    add(root, word, word, '')

def add(root, word, tail, prev):
    if tail == '':
        addLeaf(root, word)
    else:
        head = tail[0]
        tail2 = tail[1:]
        add(addEdge(root, head), word, tail2, head)
        add(addEdge(root, '?'), word, tail2, head)
    if prev != '*':
        for l in range(len(tail)+1):
           add(addEdge(root, '*'), word, tail[l:], '*')

def addEdge(root, char):
    if not root.has_key(char):
        root[char] = {}
    return root[char]

def addLeaf(root, word):
    if not root.has_key('$'):
        root['$'] = []
    leaf = root['$']
    if word not in leaf:
        leaf.append(word)

def findWord(root, pattern):
    prev = ''
    for p in pattern:
        if p == '*' and prev == '*':
            continue
        prev = p
        if not root.has_key(p):
            return []
        root = root[p]
    if not root.has_key('$'):
        return []
    return root['$']

def run():
    print("Enter words, one per line terminate with a . on a line")
    root = {}
    while 1:
        line = sys.stdin.readline()[:-1]
        if line == '.': break
        addWord(root, line)
    print(repr(root))
    print("Now enter search patterns. Do not use multiple sequential '*'s")
    while 1:
        line = sys.stdin.readline()[:-1]
        if line == '.': break
        print(findWord(root, line))

run()

如果您不关心内存,并且可以预先处理列表,请为每个后缀创建一个排序数组,指向原始单词,例如,['hello','world',],存储:

[('d'    , 'world'),
 ('ello' , 'hello'),
 ('hello', 'hello'),
 ('ld'   , 'world'),
 ('llo'  , 'hello'),
 ('lo'   , 'hello'),
 ('o'    , 'hello'),
 ('orld' , 'world'),
 ('rld'  , 'world'),
 ('world', 'world')]

使用此数组可以使用模式的片段构建候选匹配集。

例如,如果模式是 *or* ('orld' , 'world') 对子串使用二进制斩波 or ,然后使用正常的全局搜索方法确认匹配。

h*o ,为 h 和 o

你说你现在在做线性搜索。这是否为您提供了有关最频繁执行的查询模式的任何数据?e、 g.is公司 blah* 比 bl?h

有了这种先验知识,您可以将索引工作的重点放在常用的情况上,并将其降到O(1),而不是试图解决更困难、但更不值得做的问题 可能查询同样快。

通过保持字符串中字符的计数,可以实现简单的加速。没有的绳子 b 乙 无法匹配查询 abba* ,所以没有必要测试它。如果字符串是由这些字符串组成的,那么这对整个单词的效果要好得多,因为单词比字符多得多;另外,还有很多库可以为您构建索引。另一方面,它与您提到的n-gram方法非常相似。

如果不使用为您执行此操作的库,则可以首先在索引中查找最不常用的全局字符(或单词或n-grams),从而优化查询。这允许您在前面丢弃更多不匹配的字符串。

多字符串搜索有很多好的算法。谷歌“纳瓦罗字符串搜索”,你会看到一个很好的多字符串选项分析。许多算法对于“普通”情况非常好(搜索相当长的字符串:Wu Manber;使用在要搜索的文本中很少出现的字符的搜索字符串:parallel Horspool)。Aho Corasick是一种算法,它保证每个输入字符的工作量(很小)是有限制的,无论如何调整输入文本以在搜索中创建最坏的行为。对于Snort这样的程序,面对拒绝服务攻击,这一点非常重要。如果您对如何实现真正高效的Aho Corasick搜索感兴趣,请查看 ACISM - an Aho-Corasick Interleaved State Matrix