5

问题：提供了一个大的静态字符串列表。由数据和通配符元素（* 和 ?）组成的模式字符串。这个想法是返回所有匹配模式的字符串 - 很简单。

当前解决方案：我目前正在使用线性方法扫描大列表并将每个条目与模式进行匹配。

我的问题：是否有任何合适的数据结构可以存储大列表以使搜索的复杂性小于 O(n)？

也许类似于suffix-trie的东西？我也考虑过在哈希表中使用二元组和三元组，但是根据返回的单词列表和模式的合并来评估匹配所需的逻辑是一场噩梦，而且我不相信它是正确的方法。

4

6 回答 6

1

你可以建立一个常规的 trie 并添加通配符边缘。那么你的复杂性将是 O(n) 其中 n 是模式的长度。您必须首先替换模式中的运行**（*也是 O(n) 操作）。

如果单词列表是I am a ox，那么 trie 看起来有点像这样：

  （我（$ [我]）
   一个（米（$ [上午]）
      n ($ [一个])
      ? （$ [我]）
      * ($ [我]))
   o (x ($ [牛])
      ? （$ [牛]）
      * ($ [牛]))
   ? ($ [我]
      米（$ [上午]）
      n ($ [一个])
      x ($ [牛])
      ? （$ [我是一头牛]）
      * ($ [我是一头牛]
         米（$ [上午]）...）
   * ($ [我是一头牛]
      我 ...
    ...

这是一个示例 python 程序：

导入系统

def addWord（根，单词）：
    添加（根，单词，单词，''）

def add(root, word, tail, prev):
    如果尾巴 == ''：
        addLeaf（根，词）
    别的：
        头=尾[0]
        尾2 =尾[1:]
        add(addEdge(root, head), word, tail2, head)
        add(addEdge(root, '?'), word, tail2, head)
    如果上一个！='*'：
        对于范围内的 l(len(tail)+1)：
           add(addEdge(root, '*'), word, tail[l:], '*')

def addEdge（根，字符）：
    如果不是 root.has_key(char)：
        根[字符] = {}
    返回根[字符]

def addLeaf（根，字）：
    如果不是 root.has_key('$')：
        根['$'] = []
    叶=根['$']
    如果单词不在叶子中：
        叶.附加（字）

def findWord（根，模式）：
    上一页 = ''
    对于模式中的 p：
        如果 p == '*' 和 prev == '*'：
            继续
        上一页 = p
        如果不是 root.has_key(p)：
            返回 []
        根 = 根[p]
    如果不是 root.has_key('$')：
        返回 []
    返回根['$']

定义运行（）：
    print("输入单词，每行一个以 . 结尾")
    根 = {}
    而1：
        line = sys.stdin.readline()[:-1]
        如果行 == '.': 中断
        addWord（根，行）
    打印（代表（根））
    print("现在输入搜索模式。不要使用多个连续的 '*'s")
    而1：
        line = sys.stdin.readline()[:-1]
        如果行 == '.': 中断
        打印（查找字（根，行））

跑（）
于 2010-03-28T08:20:15.797 回答
1

我同意后缀 trie 是一个不错的尝试，但数据集的绝对大小可能会使其构建消耗的时间与其使用所节省的时间一样多。如果您必须多次查询它们以摊销建设成本，它们是最好的。可能有几百个查询。

另请注意，这是并行性的一个很好的借口。将列表一分为二并将其分配给两个不同的处理器，让您的工作以两倍的速度完成。

于 2010-03-28T08:20:44.370 回答
0

如果您不关心内存并且可以对列表进行预处理，请创建一个包含每个后缀的排序数组，指向原始单词，例如，对于 ['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构建候选集，并在最终线性 glob 之前找到它们的交集。ho

于 2010-03-28T08:19:11.070 回答
0

你说你目前正在做线性搜索。这是否为您提供了有关最常执行的查询模式的任何数据？eg在您当前的用户中比（我假设它是）blah*更常见？bl?h

有了这种先验知识，您可以将索引工作集中在常用案例上并将它们降低到 O(1)，而不是尝试解决更困难但更不值得的问题，即使每个可能的查询均等快速地。

于 2010-03-28T08:42:58.783 回答
0

您可以通过保留字符串中的字符数来实现简单的加速。b没有s 或单个的字符串b永远无法匹配 query abba*，因此测试它没有意义。如果您的字符串是由这些组成的，那么这对整个单词的效果要好得多，因为单词比字符多得多；另外，有很多库可以为您构建索引。另一方面，它与您提到的 n-gram 方法非常相似。

如果您不使用为您执行此操作的库，则可以通过首先在索引中查找全局最不常见的字符（或单词或 n-gram）来优化查询。这允许您预先丢弃更多不匹配的字符串。

一般来说，所有的加速都基于丢弃不可能匹配的东西的想法。要索引的内容和数量取决于您的数据。例如，如果典型的模式长度接近字符串长度，您可以简单地检查字符串是否足够长以容纳模式。

于 2010-03-30T00:09:15.620 回答
0

多字符串搜索有很多好的算法。谷歌“Navarro 字符串搜索”，您会看到对多字符串选项的良好分析。许多算法非常适合“正常”情况（搜索相当长的字符串：Wu-Manber；搜索具有在要搜索的文本中很少见的字符的字符串：并行 Horspool）。Aho-Corasick 是一种算法，它保证每个输入字符的（微小）有限工作量，无论输入文本如何调整以在搜索中创建最差行为。对于像 Snort 这样的程序，面对拒绝服务攻击，这一点非常重要。如果您对如何实现真正有效的 Aho-Corasick 搜索感兴趣，请查看ACISM - Aho-Corasick 交错状态矩阵。

于 2014-01-25T04:33:51.047 回答