Эффективная задача поиска массовой строки

Question

Проблема: Предоставлен большой статический список строк. Строка шаблона, состоящая из данных и подстановочных элементов (* и?). Идея состоит в том, чтобы вернуть все строки, которые соответствуют шаблону - достаточно просто.

Текущее решение: В настоящее время я использую линейный подход сканирования большого списка и привязывания каждой записи к шаблону.

Мой вопрос: Существуют ли какие-либо подходящие структуры данных, в которые я могу сохранить большой список так, чтобы сложность поиска была меньше, чем O (n)?

Возможно, что-то похожее на суффикс-три ? Я также подумал об использовании би- и триграмм в хеш-таблице, но логика, необходимая для оценки соответствия на основе слияния возвращенного списка слов и шаблона, является кошмаром, более того, я не уверен, что это правильно подход.

Answer 1

Я согласен, что суффикс-три это хорошая идея, за исключением того, что из-за большого размера вашего набора данных его конструкция может использовать столько же времени, сколько его использование сэкономит. Лучше всего, если вам придется запрашивать их несколько раз, чтобы амортизировать стоимость строительства. Возможно несколько сотен запросов.

Также обратите внимание, что это хороший повод для параллелизма. Разрежьте список пополам, раздайте его двум разным процессорам и сделайте свою работу в два раза быстрее.

Answer 2

вы можете построить обычный три и добавить подстановочные ребра. тогда ваша сложность будет O (n), где n - длина шаблона. Сначала вам придется заменить прогоны ** на * в шаблоне (также операция O (n)).

Если бы список слов был Я бык , тогда дерево будет выглядеть примерно так:

  (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()

Answer 3

Существует множество хороших алгоритмов многострочного поиска. Google "поиск строки Navarro", и вы увидите хороший анализ многострочных опций. Ряд алгоритмов очень хороши для «нормальных» случаев (строки поиска довольно длинные: Wu-Manber; строки поиска с символами, которые скромно редки в искомом тексте: параллельный Horspool). Aho-Corasick - это алгоритм, который гарантирует (крошечный) ограниченный объем работы для каждого входного символа, независимо от того, как настроен входной текст для создания худшего поведения в поиске. Для таких программ, как Snort, это действительно важно перед лицом атак типа «отказ в обслуживании». Если вас интересует, как можно реализовать действительно эффективный поиск Aho-Corasick, взгляните на ACISM - матрица состояний с чередованием Aho-Corasick .

Answer 4

Вы можете добиться простого ускорения, сохраняя количество символов в ваших строках. Строка без b s или с одним b никогда не может соответствовать запросу abba*, поэтому нет смысла ее проверять. Это работает намного лучше для целых слов, если ваши строки сделаны из них, так как слов намного больше, чем символов; Кроме того, существует множество библиотек, которые могут создавать индексы для вас. С другой стороны, он очень похож на упомянутый вами подход с использованием n-граммы.

Если вы не используете библиотеку, которая делает это за вас, вы можете оптимизировать запросы, посмотрев сначала самые редкие в мире символы (или слова, или n-граммы) в ваших индексах. Это позволяет вам отбрасывать больше несоответствующих строк заранее.

В общем, все ускорения будут основаны на идее отбрасывать вещи, которые не могут быть сопоставлены. Что и сколько нужно индексировать, зависит от ваших данных. Например, если типичная длина шаблона близка к длине строки, вы можете просто проверить, достаточно ли строки для размещения шаблона.

Answer 5

Вы говорите, что в настоящее время делаете линейный поиск. Это дает вам какие-либо данные о наиболее часто выполняемых шаблонах запросов? например blah* гораздо чаще встречается среди ваших нынешних пользователей, чем bl?h (что, я бы предположил)?

Имея такие предварительные знания, вы можете сосредоточить свои усилия по индексированию на наиболее часто используемых случаях и довести их до O (1), вместо того, чтобы пытаться решить гораздо более сложную, но гораздо менее стоящую проблему создания каждый одинаково быстрый запрос.

Answer 6

Если вас не волнует память и вы можете позволить себе предварительно обработать список, создайте отсортированный массив каждого суффикса, указывающего на оригинальное слово, например, для ['hello', 'world'], store это:

[('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 и найдите их пересечение перед последним линейным шаром.