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

Ответ 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: Добавлен вариант alogrithm, предложенный ninjagecko для таймингов. Вы можете видеть, что это намного лучше, чем все подходы грубой силы.

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

Ответ 2

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

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

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

edit: fooobar.com/questions/400190/... на самом деле является теоретически лучшим ответом. Я смотрел на связанную страницу Википедии, прежде чем этот ответ был отправлен, и думал, что "линейный размер строки не то, что вы хотите", а только позже понял, что именно вы хотите. Ваша интуиция для создания регулярного выражения (Aword1|Aword2|Aword3|...) верна, так как конечный автомат, который генерируется за кулисами, будет быстро выполнять согласование, если он поддерживает совпадающие совпадения совпадений, которые могут быть не все двигатели регулярных выражений. В конечном итоге то, что вы должны использовать, зависит от того, планируете ли вы повторно использовать As или B, или если это всего лишь одноразовая вещь. Вышеупомянутый метод намного проще реализовать, но работает только в том случае, если ваши слова ограничены (и вводит уязвимость DoS, если вы не отклоняете слова выше определенного ограничения по размеру), но может быть то, что вы ищете, если вы не хотите строка Aho-Corasick, соответствующая конечному автомату или аналогичная, или она недоступна в качестве библиотеки.

Ответ 3

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

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

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

Есть реализации шаблона шаблона aho corasick в 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 script, она дала несколько меньшие результаты, чем другие методы, и я не уверен, почему. Я написал письмо создателю, возможно, он это выяснит.

Ответ 4

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

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