Эффективно находите совпадающую строку среди подстрок в больших списках

Проблема кажется несколько недоопределенной, но в то же время и переопределенной. Например, какое отношение к этому имеют кортежи?

Я позволю себе перефразировать это так: у вас есть список строк needles и еще один список строк haystacks. Вы хотите найти все стога сена, в которых есть (хотя бы одна) иголка.

Первое, что приходит на ум, — это предварительно обработать иглы, построить древовидную структуру, позволяющую более эффективно искать любую из них. Затем пройдите по стогам сена по одному, используя эту конструкцию для их проверки.

Вот простой код, который пришел мне в голову. Не похоже, что ОЗУ станет для вас проблемой, но если это так, то есть более интересные способы создания «сжатых» попыток. Кстати, если все ваши иглы содержат трехсимвольную подстроку " & ", то лучше всего предположить, что большинство стогов сена ее не содержат, поэтому в большинстве случаев вы можете дешево выйти из строя, сначала проверив именно это количество.

from collections import defaultdict

class Node:
    __slots__ = 'final', 'ch2node'

    def __init__(self):
        self.final = False
        self.ch2node = defaultdict(Node)

def add(trie, s):
    for ch in s:
        trie = trie.ch2node[ch]
    trie.final = True

# Does s[i:] start with a string in the trie?
def find(trie, s, i):
    for i in range(i, len(s)):
        if trie.final:
            return True
        ch = s[i]
        if ch in trie.ch2node:
            trie = trie.ch2node[ch]
        else:
            return False
    return trie.final

def search(trie, s):
    return any(find(trie, s, i) for i in range(len(s)))

needles = ["a & b", "kik", "c & as"]
haystacks = ["sldjkfa & b", "c&as", "akiko", "xc & asx", "kkc & a"]

root = Node()
for n in needles:
    add(root, n)
print(list(h for h in haystacks if search(root, h)))

Что печатает

['sldjkfa & b', 'akiko', 'xc & asx']

РЕДАКТИРОВАТЬ

В комментарии упоминается алгоритм Ахо-Корасика, который примерно похож на простой три-код, приведенный выше, но более удобен и эффективен (он эффективно выполняет поиск «по всему стогу сена одновременно»).

Я еще не использовал его, но, похоже, для этого есть подходящий пакет Python , доступный на PyPI .

РЕДАКТИРОВАТЬ2

Я пытаюсь вывести вас из тупика, а не дать вам теоретически оптимальное решение. Попробуйте что-нибудь! Вы можете быть удивлены тем, насколько хорошо может работать даже тот простой код, который я привел.

Я использовал вышеописанное, чтобы создать 5 миллионов «иголок», каждая из которых состоит из 2 словарных слов (каждое не менее 10 букв), разделенных одним пробелом. Построение дерева заняло менее 45 секунд (Python 3.12.4). Проверка 5_008_510 строк по ним заняла еще 55 секунд, то есть менее 2 минут от начала до конца. Сравните с «лучшей частью 1000 часов», с которой, как вы думаете, вам придется столкнуться сейчас.

И это без каких-либо попыток «оптимизировать» что-либо, кроме простого использования простой попытки.

Если бы я хотел заняться этим, я бы сначала посмотрел на использование памяти, а не на скорость. Это потребляло около 8,2 ГБ пиковой оперативной памяти. Один из способов сократить это — выполнить постобработку дерева, удалить пустой словарь на узлах final (или вообще не выделять словарь, если в этом нет необходимости). Но это несколько усложнит код. Другой вариант — рассмотреть возможность использования байтовых строк вместо строк Unicode. А еще есть чудовищные абсурды, например, вообще не использовать класс Node, вместо этого использовать необработанные 2-кортежи или 2-списки.

Но, учитывая все, что вы сказали о своей проблеме, это уже было бы «достаточно хорошо для меня».

КОМПРОМИССЫ

Большим преимуществом попытки является то, что она нечувствительна к количеству иголок: время проверки стога сена примерно одинаково, независимо от того, нужно искать одну или миллиард иголок.

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

Компромисс здесь заключается в том, что для стога сена длиной L может потребоваться выполнить L различных поисков. Соответствующему автомату Ахо-Корасика достаточно выполнить только один поиск, независимо от размера L. Но это более сложный вариант дерева, требующий больше памяти и более сложного кода.

При отсутствии какой-либо информации о распределении размеров вашего стога сена (или даже иголки) действует правило «сначала попробуйте самое простое, что может сработать». Потенциальная квадратичная (в L) временная природа поиска по принципу «просто-просто-три» убила бы его, если бы, например, L могло достигать миллиона, но это относительно незначительная вещь, если L не станет больше, чем, скажем, 100 (быть в 100 раз медленнее, чем теоретически необходимо, просто не имеет большого значения по сравнению с экономией в 5 миллионов раз).

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

Если это не очевидно, вот прагматичная вещь: если оперативная память для попытки иглы «слишком велика», вы можете сократить ее примерно в K раз, выполнив K прогонов, используя только len(needles)/K игл за прогон. В этом случае сначала следует отсортировать иглы (общие префиксы физически являются общими в дереве, и сортировка объединит иглы с общими префиксами).

Или вы можете проделать гораздо больше работы по созданию дискового дерева.

Возможное пространство решений велико.

БЫСТРОЕ СРАВНЕНИЕ

Как и выше, 5 миллионов игл, но я сократил их средний размер примерно вдвое, примерно с 21 символа до примерно 10,5 - в противном случае с другим пакетом будет нехватка оперативной памяти. Чуть более 5 миллионов стогов сена. Большинству из них было меньше 70 лет, но некоторые исчислялись сотнями. В нескольких стогах сена была иголка (всего 910 штук).

Для другого кода я использовал ahocorapy, полноценную реализацию Aho-Corasick на чистом Python.

Использование памяти для другого пакета было значительно выше. Ожидал. Если мой класс Node содержит только 2 члена, то аналогичный ему класс State содержит 7. Ему необходимо сохранить гораздо больше информации, чтобы гарантировать производительность в линейном времени в наихудшем случае.

По той же причине строительство игольной машины шло медленнее. Около 24 секунд для моего кода, около 60 для ахокотерапии.

Но вы получаете то, за что платите ;-) Поиск по более чем 5 миллионам стогов сена занял около 55 секунд для моего кода и всего около 22 для ахокопии. Поскольку иголки обнаруживались редко, для моего кода это почти худший случай (он должен попробовать len(haystack) отдельные поиски, чтобы прийти к выводу, что иголок нет).

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

В реализации Python PyPy весь этот код выполняется как минимум в два раза быстрее.

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

ЕЩЕ ОДИН УДАР

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

x
ax
aax
aaax
aaaax
aaaaax
...
aaaaa.....aaax

и стог сена типа aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaay. Совпадений нет, но поиск по одному займет много времени. Полный Ахо-Корасик гораздо быстрее.

from collections import defaultdict

class Node:
    __slots__ = 'final', 'ch2node'

    def __init__(self):
        self.final = ""
        self.ch2node = None

class Trie:
    def __init__(self):
        self.root = Node()
        self.leaders = set()

    # Add a needle.
    def add(self, s):
        if not s:
            raise ValueError("empty string not allowed")
        trie = self.root
        for ch in s:
            if (ch2node := trie.ch2node) is None:
                ch2node = trie.ch2node = defaultdict(Node)
            trie = ch2node[ch]
        trie.final = s
        self.leaders.add(s[0])

    # Search a haystack `s`. Generates a 2-tuple, (needle, i), for each needle the
    # haystack contains. The needle starts at s[i].
    def search(self, s):
        leaders = self.leaders
        root = self.root
        for i, ch in enumerate(s):
            if ch not in leaders:
                continue
            trie = root
            for i in range(i, len(s)):
                if ((ch2node := trie.ch2node)
                      and (ch := s[i]) in ch2node):
                    trie = ch2node[ch]
                    if trie.final:
                        yield trie.final, i - len(trie.final) + 1
                else:
                    break

Тогда, например,

t = Trie()
for n in 'eat', 'tea', 'car', 'care', 'cares', 'arc':
    t.add(n)

for m in t.search('eateacarcares'):
    print(m)

отображает:

('eat', 0)
('tea', 2)
('car', 5)
('arc', 6)
('car', 8)
('care', 8)
('cares', 8)

РАБИН-КАРП

Другой подход — использовать алгоритм Рабина-Карпа (RK) для сопоставления нескольких игл. Конкретный хеш-код предварительно вычисляется для каждой иглы, и все необходимое хранилище — это словарь, сопоставляющий хеш-код со списком игл с этим хеш-кодом.

Для поиска в стоге сена достаточно один раз просмотреть его слева направо и вычислить «скользящий хэш» RK для каждого окна. Хэш-функция спроектирована таким образом, что хэш следующего окна можно вычислить с использованием небольшого и фиксированного числа (независимо от размера окна) арифметических операций. Если хеш есть в словаре, напрямую сравните каждую иголку с этим хешем с окном стога сена.

Это просто, быстро и очень экономно по памяти. НО. Увы, это просто, если все иглы имеют одинаковую длину и размер окна фиксирован. Если есть K игл разной длины, получается путаница. Вы можете, например, использовать K различных скользящих хешей, но это замедлит его в K раз. Или вы можете использовать размер окна, равный длине самой короткой иглы, но тогда количество ложных срабатываний может увеличиться.

Я использовал последнюю стратегию и не смог сделать ее конкурентоспособной под управлением CPython. Тем не менее, PyPy превосходно ускоряет код Python, выполняющий арифметические операции с целыми числами машинного размера, и при этом скорость была сопоставима. Использование памяти стало в 10 раз меньше, что является огромным выигрышем. РК также хорошо умеет избегать патологических случаев, хотя это вероятностно, а не гарантировано.

ДЛЯ КОРОТКИХ, НО НЕ СЛИШКОМ КОРОТКИХ ИГЛ

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

Обновлено: добавлен leaders, что значительно ускоряет обработку моих данных.

Обновлено: при поиске .startswith() позволяет избежать необходимости создавать новый строковый объект.

class RK: # not Rabin-Karp, but inspired by it
    def __init__(self):
        from collections import defaultdict
        self.needles = []
        self.h2ns = defaultdict(list)
        self.leaders = set()

    def add(self, s):
        if not s:
            raise ValueError("empty string not allowed")
        if self.h2ns:
            raise ValueError("cannot add() after finalize() called")
        self.needles.append(s)
        self.leaders.add(s[0])

    def finalize(self):
        h2ns = self.h2ns
        if h2ns:
            return # already finalized
        w = self.w = min(map(len, self.needles))
        for n in self.needles:
            h2ns[hash(n[:w])].append(n)
        del self.needles

    def search(self, s):
        if not self.h2ns:
            raise ValueError("must call finalize() before search()")
        h2nsget = self.h2ns.get
        w = self.w
        leaders = self.leaders
        for i in range(len(s) - w + 1):
            if (s[i] in leaders
                  and (ns := h2nsget(hash(s[i : i + w])))):
                for n in ns:
                    if s.startswith(n, i):
                        yield n, i

Тогда, например,

t = RK()
for n in 'eat', 'tea', 'car', 'care', 'cares', 'arc', 's':
    t.add(n)
t.finalize()

for m in t.search('eateacarcares'):
    print(m)

принты

('eat', 0)
('tea', 2)
('car', 5)
('arc', 6)
('car', 8)
('care', 8)
('cares', 8)
('s', 12)

Поисковая часть на самом деле не быстрее, но finalize() намного быстрее, чем построение дерева. Длина самой короткой иглы имеет решающее значение: чем она короче, тем больше вероятность того, что при поиске придется отсеивать «ложные срабатывания».

По моим же тестовым данным общее время от начала до конца составляет около 15 секунд.

Вариант: зачем вообще хеш? Вместо этого h2ns мог бы сопоставить строку w-символов с иглами, начинающимися с этой строки. Конечно, хеширование все равно будет происходить, но скрыто, как часть Python, выполняющего поиск по диктовке. Это не имеет большого значения для скорости, но увеличивает использование памяти (клавиши w-символов dict требуют больше места, чем машинные ключи int). Это, в свою очередь, можно уменьшить, сохранив needle[w:] в списках, для возможного уменьшения общего объема необходимого хранилища символов. Но это делает finalize() медленнее — нарезка не бесплатна. Все такие варианты кажутся мне «достаточно хорошими».

Для эффективной работы потребуются некоторые сложные структуры данных, выполненные должным образом - таким образом, чтобы термин из второго списка можно было найти по поисковому запросу в более удобной, чем линейная, форме.

Например, если поисковый запрос фиксирован (всегда обе строки объединяются с помощью & и всегда находятся в начале строки в целевом списке (список2), то это будет вопрос сортировки этого второго списка и создания двоичного списка. выполните поиск по нему - это позволит вам получить элементы, пропорциональные LOG(N) (где N - количество элементов в списке2).

Как я могу использовать расширение FTS5 с модулем Python sqlite3 с Python 3.7?

Однако если поисковый запрос не всегда будет находиться в начале строк в списке list2, вам понадобится другая структура данных, например Trie. Хорошая реализация trie, вероятно, сможет справиться с таким объемом данных. У меня есть программа, написанная на чистом Python, которая использует некоторые высокоуровневые структуры данных под капотом и не сможет обрабатывать что-либо близкое к 5 миллионам фраз.

Но затем вы можете просто перенести свои фразы в базу данных, добавить индекс полнотекстового поиска в таблицу «list2» и просто выполнить запрос.

Даже в базе данных sqlite3, поставляемой с Python, включен полнотекстовый поиск — проверьте этот вопрос — ответы включают фрагменты того, как его использовать. Записывая 5 миллионов фраз на диск, что может сделать sqlite, у вас не должно быть ограничений по памяти:

Как я могу использовать расширение FTS5 с модулем Python sqlite3 с Python 3.7?