Эффективные строки, содержащие друг друга

Question

У меня есть два набора строк (A и B), и я хочу знать все пары строк a in A и b in B, где a является подстрокой b.

Первым шагом кодирования этого было следующее:

for a in A:
    for b in B:
        if a in b:
            print (a,b)

Однако я хотел бы знать - есть ли более эффективный способ сделать это с помощью регулярных выражений (например, вместо проверки if a in b:, проверьте, совпадает ли регулярное выражение '.*' + a + '.*': с буквой B. Я подумал, что, возможно, использование чего-то подобного позволило бы мне кэшировать функцию отказа Кнут-Моррис-Пратт для всех a. Также, используя списокпонимание внутреннего цикла for b in B:, вероятно, даст довольно большое ускорение (и понимание вложенного списка может быть даже лучше).

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

Знаете ли вы какие-либо хитрости или у вас есть общие советы, чтобы сделать это быстрее? Большое спасибо за любые идеи, которыми вы можете поделиться!

---

Редактировать:

Используя советы @ninjagecko и @Sven Marnach, я построил таблицу быстрых префиксов из 10 элементов:

    import collections
    prefix_table = collections.defaultdict(set)
    for k, b in enumerate(B):
        for i in xrange(len(prot_seq)-10):
            j = i+10+1
            prefix_table[b[i:j]].add(k)

    for a in A:
        if len(a) >= 10:
            for k in prefix_table[a[:10]]:
                # check if a is in b
                # (missing_edges is necessary, but not sufficient)
                if a in B[k]:
                    print (a,b)
        else:
            for k in xrange(len(prots_and_seqs)):
                # a is too small to use the table; check if
                # a is in any b
                if a in B[k]:
                    print (a, b)

Answer 1

Конечно, вы можете легко написать это как понимание списка:

[(a, b) for a in A for b in B if a in b]

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

Редактировать : Вот некоторые моменты:

import itertools
import timeit
import re
import collections

with open("/usr/share/dict/british-english") as f:
    A = [s.strip() for s in itertools.islice(f, 28000, 30000)]
    B = [s.strip() for s in itertools.islice(f, 23000, 25000)]

def f():
    result = []
    for a in A:
        for b in B:
            if a in b:
                result.append((a, b))
    return result

def g():
    return [(a, b) for a in A for b in B if a in b]

def h():
    res = [re.compile(re.escape(a)) for a in A]
    return [(a, b) for a in res for b in B if a.search(b)]

def ninjagecko():
    d = collections.defaultdict(set)
    for k, b in enumerate(B):
        for i, j in itertools.combinations(range(len(b) + 1), 2):
            d[b[i:j]].add(k)
    return [(a, B[k]) for a in A for k in d[a]]

print "Nested loop", timeit.repeat(f, number=1)
print "List comprehension", timeit.repeat(g, number=1)
print "Regular expressions", timeit.repeat(h, number=1)
print "ninjagecko", timeit.repeat(ninjagecko, number=1)

Результаты:

Nested loop [0.3641810417175293, 0.36279606819152832, 0.36295199394226074]
List comprehension [0.362030029296875, 0.36148500442504883, 0.36158299446105957]
Regular expressions [1.6498990058898926, 1.6494300365447998, 1.6480278968811035]
ninjagecko [0.06402897834777832, 0.063711881637573242, 0.06389307975769043]

Редактировать 2: Добавлен вариант алогрита, предложенного ninjagecko к таймингу.Вы можете видеть, что это намного лучше, чем все методы грубой силы.

Редактировать 3: Использовать наборы вместо списков для устранения дубликатов.(Я не обновлял сроки - они остались практически без изменений.)

Answer 2

Давайте предположим, что ваши слова ограничены разумным размером (скажем, 10 букв).Чтобы добиться линейной (!) Временной сложности, выполните следующие действия: O(A+B):

• Инициализируйте хеш-таблицу или три *
• Для каждой строки b в B:
  • Для каждой подстроки этой строки
    • Добавить подстроку в хеш-таблицу / trie (это не хуже, чем 55*O(B) = O(B)), с метаданными той строки, которой она принадлежит
• Для каждой строки a в A:
  • Сделайте O(1) запрос к вашей хеш-таблице / trie, чтобы найти все B-строки, в которых он находится, и получите те

(На момент написания этого ответа ответа пока нет, если «слова» ОП ограничены. Если они не ограничены, это решение по-прежнему применимо, но существует зависимость O(maxwordsize^2), хотя на практике это лучше, так как не все слова имеют одинаковый размер, поэтому он может быть таким же хорошим, как O(averagewordsize^2) с правильным распределением. Например, если бы все слова были размером 20, размер проблемы увеличился бы нав 4 раза больше, чем если бы они были размером 10. Но если бы достаточно мало слов, яЕсли увеличить размер 10-> 20, то сложность не сильно изменится.)

edit: https://stackoverflow.com/q/8289199/711085 - теоретически лучший ответ.Я просматривал связанную страницу Википедии до того, как был опубликован этот ответ, и думал, что «линейный размер строки - это не то, что вам нужно», и только позже понял, что это именно то, что вы хотите.Ваша интуиция для построения регулярного выражения (Aword1|Aword2|Aword3|...) верна, поскольку конечный автомат, сгенерированный за сценой, быстро выполнит сопоставление, ЕСЛИ он поддерживает одновременные совпадения совпадений, что не все механизмы регулярного выражения могут.В конечном счете, то, что вы должны использовать, зависит от того, планируете ли вы повторно использовать As или B, или это просто одноразовая вещь.Описанный выше метод гораздо проще реализовать, но он работает только в том случае, если ваши слова ограничены (и вводит уязвимость DoS, если вы не отклоняете слова выше определенного предела размера), но может быть тем, что вы ищете, если вы не хотите конечный автомат совпадения строк Aho-Corasick или аналогичный, или он недоступен как библиотека.

Answer 3

Очень быстрый способ поиска множества строк - это использование конечного автомата (так что вы не так уж далеки от предположения регулярного выражения), а именно строка Aho Corasickсоответствующий компьютер, который используется в таких инструментах, как grep , антивирусные сканеры и т. п.

Сначала он компилирует строки, которые вы хотите найти (вВ вашем случае слова в А) превращаются в конечный автомат с функцией отказа (см. документ от '75, если вас интересуют подробности).Затем этот автомат читает входную строку (и) и выводит все найденные строки поиска (возможно, вы захотите немного изменить его, чтобы он выводил строку, в которой была найдена строка поиска).

Этот методимеет преимущество в том, что он ищет все строки поиска одновременно и, следовательно, должен просматривать каждый символ входной строки (строк) только один раз ( линейная сложность )!

Есть реализаций aho corasick pattern matcher в pypi , но я не проверял их, поэтому не могу ничего сказать о производительности, удобстве использования или правильности этих реализаций.

---

EDIT : я попробовал эту реализацию автомата Aho-Corasick, и это действительно самый быстрый из предложенных методов на данный момент, а также простой в использовании:

import pyahocorasick

def aho(A, B):
    t = pyahocorasick.Trie();
    for a in A:
        t.add_word(a, a)
    t.make_automaton()
    return [(s,b) for b in B for (i,res) in t.iter(b) for s in res]

Однако я заметил, что при тестировании этой реализации с помощью сценария @SvenMarnachs она дала чуть меньше результатов , чем другие методы, и я неконечно почему.Я написал письмо создателю, может, он это выяснит.

Answer 4

Для этого существуют специализированные индексные структуры, см., Например, http://en.wikipedia.org/wiki/Suffix_tree

Вы должны построить дерево суффиксов или что-то подобное для B, а затем использовать A для запроса.