Поиск подстрок в строках списков на Python

Question

Существует ли более быстрый способ поиска подстрок в строках списков загружаемых из файлов.

Для конкретики, приведу пример моего кода на Python.

# -*- coding: utf-8 -*-
import os
dirFiles = 'd:/data/'
files = os.listdir(dirFiles) # Файлов в каталоге около 3'000
files.sort()
fileA = open('d:/ListA.txt')
linesA = fileA.readlines() # В файле порядка 50'000 уникальных искомых подстрок
fileA.close()
for fileName in files:
    fileB = open(dirFiles + fileName)
    linesB = fileB.readlines() # В каждом файле порядка 700'000 уникальных строк
    fileB.close()
    for lineA in linesA:
        res = [y for y in linesB if lineA.replace('\n','') in y] # Поиск каждой строки lineA в качестве подстроки в каждой строке списка linesB
        if len(res) > 0:
            print res

Код работает очень медленно, и хотелось бы найти способы ускорить поиск.

Пример искомых подстрок списка linesA:
sjfrhfereirevb
fvbdjvejeirerer
wiuewuewifwwcb
bvdfkbdvbevkbeee

Пример строк списка listB, в которых производится поиск:
djcwjbcbcwiebcwebcerbuevitbbtvietbvndwnecwoewrnen
ewwfsjfrhfereirevbewdownwonewrnoenrviernveonvoenrveornveor
weacewewijernceirvetvnenrvernvernveoitnvetnvenrvoenrverv
euccdwiuewuewifwwcbewcwcwwirbeiwrorjoeroehroverivheiveveeverv

Answer 1

Мне кажется, вместо внутреннего цикла нужно сделать так:

# ещё до цикла по файлам
setA = set(linesA)
# ...
for lineB in linesB:
    setB = set(lineB.split())
    if setA & setB:
        print(lineB)

P.S. Это для поиска отдельных слов. Если речь всё же о подстроках, как вы указали в последнем изменении вопроса, то, думаю, простого решения тут нет. Хотя можно попробовать в 2 этапа - сначала искать пересечение с множеством слов и если оно есть, тогда искать подстроку, возможно это даст ускорение. Но нужно проверять.

Answer 2

Trie или префиксное дерево хорошо подходит для решения задачи. Это дерево для набора строк. В корне хранится dict со всеми возможными первыми символами строк. В узлах внутри тоже хранятся словари с буквами, которыми можно продолжить строку. Признак конца строки - пустой ключ в словаре. Пример:

import pprint

def make_trie(iterable):
    root = {}
    for s in iterable:
        node = root
        for c in s:
            node = node.setdefault(c, {})
        node[''] = None
    return root

pprint.pprint(make_trie(('then', 'than', 'thing', 'those')))

{'t': {'h': {'a': {'n': {'': None}},
             'e': {'n': {'': None}},
             'i': {'n': {'g': {'': None}}},
             'o': {'s': {'e': {'': None}}}}}}

С помощью префиксного дерева можно проверить, что данный текст содержит какое-нибудь слово из дерева.

Например, чтобы проверить что строка есть в дереве, будем брать из неё символы по одному и спускаться по дереву:

s = ...              # строка которую ищем в дереве
node = root          # корень префиксного дерева
for c in s:          # символ за символом ...
    node = node[c]   # ... спускаемся по дереву

Если очередного символа в узле не оказалось, то строки в дереве нет. Если последний узел содержит ключ '', то строка в дереве есть.

Так как нам надо проверять не только начало текста, но и любое место внутри, то будем поддерживать список узлов, которые действительны на данном символе. С каждым новым символом текста список пополняется новым элементом - корнем дерева. Все узлы, которые не соответствуют очередному символу из списка удаляются. Чтобы эти операции были быстрыми приходится работать с индексами, что не привычно для Питона:

def contains(text, trie):
    if '' in trie:
        return True

    nodes = []
    for c in text:
        nodes.append(trie)  # анализируем строку, которая начинается на этом символе
        i = 0
        while i < len(nodes):
            node = nodes[i]
            if c in node:
                # спуск по дереву
                node = node[c]
                nodes[i] = node
                if '' in node:  # признак конца строки в trie
                    return True
                i += 1
            else:
                # удаляем узел из списка
                nodes[i] = nodes[-1]
                nodes.pop()
    return False

Для проверки эффективности trie были изготовлены тестовые данные. Скрипт generate_sample.py готовит файл со строками для поиска (50'000 строк от 10 до 20 символов) ...

...
uctufrxhfomiuwrhvkyy
hbzkmicgsw
gupmuoeiehxrrix
nsmlheqpcybdeufzvnt
mmtoqiravxd
...

... и текст в котором они ищутся (20'000 строк длиной от 20 до 100 символов) ...

...
oeosbugxnbfvqgfonutgbzrmmuzumrglpphrqritsiwavmwfvdamrlvulfjswnuzsrhikfybbzxajlfxwhtt
qizjtyarlbiwnstvtmrqqomblafkhmvwtiocelcyczobausadcudkzykcgyzwajxzkbdwytlnxdqxxycgsdwsyqtn
xtwlvjyxcisvvbvacljxzmdjrhsueyjffdd
wyctzgitvbzroiiquohbfostrsvvrorslfevbyhrxqadpytrswk
fwxeyfmkqavccxgjrtjsikpazaajpknqiizbpbweublcowani
...

В текст с некоторой вероятностью вставлены слова из словаря, чтобы иногда что-то находилось.

Оригинальный поиск на этих данных выполняется 112 секунд. baseline.py:

with open('patterns.txt') as f:
    patterns = tuple(line.replace('\n','') for line in f)

with open('corpus.txt') as f:
    for line in f:
        for p in patterns:
            if p in line:
                print(line, end='')
                break

Поиск с помощью trie около двух секунд. trie.py:

def make_trie(iterable):
    ...

def contains(text, trie):
    ...

with open('patterns.txt') as f:
    trie = make_trie(line.replace('\n', '') for line in f)

with open('corpus.txt') as f:
    for line in f:
        line = line.replace('\n','')
        if contains(line, trie):
            print(line)

Так как обработка посимвольная, то Питон не лучший кандидат для быстрого решения. Решение на C или C++ должно работать быстрее раз в 10-20 если не больше.

БЛОГ НА HUSL

Поиск подстрок в строках списков на Python

Ответы (2 шт):