Проверьте, содержит ли строка хотя бы одну из строк в списке

Я пытаюсь выполнить сопоставление с помощью python.

У меня есть список строк (len ~ 3000) и файл, и я хочу проверить, есть ли для каждой строки в файле, по крайней мере, одна из строк в списке.

Самый простой способ – проверить один за другим, но для этого требуется время (не так долго).

Есть ли способ ускорить поиск?

Например:

list = ["aq", "bs", "ce"] if the line is "aqwerqwerqwer" -> true (since has "aq" in it) if the line is "qweqweqwe" -> false (has none of "aq", "bs" or "ce") 

4 Solutions collect form web for “Проверьте, содержит ли строка хотя бы одну из строк в списке”

Вы можете использовать any выражение и генератор :

 # Please do not name a list "list" -- it overrides the built-in lst = ["a", "b", "c"] if any(s in line for s in lst): # Do stuff 

Вышеприведенный код проверяет, можно ли найти line в lst . Если это так, # Do stuff Будет запущен материал.

См. Демонстрацию ниже:

 >>> lst = ["aq", "bs", "ce"] >>> if any(s in "aqwerqwerqwer" for s in lst): ... print(True) ... True >>> if any(s in "qweqweqwe" for s in lst): ... print(True) ... >>> 

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

Пытаться:

 def re_match(strings_to_match, my_file): # building regular expression to match expression = re.compile( '(' + '|'.join(re.escape(item) for item in strings_to_match) + ')') # perform matching for line in my_file: if not expression.search(line): return False return True 

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

См. Сравнение в ноутбуке IPython: http://nbviewer.ipython.org/gist/liori/10170227 . Тестовые данные состоят из 3000 строк, которые соответствуют списку из 1 миллиона строк. Наивный подход занял 1 минуту 46 секунд на моей машине, тогда как это решение было всего 9,97 с.

Вы можете использовать itertools.groupby:

 from itertools import groupby pats = ['pat', 'pat2', …] matches = groupby(lines, keyfunc=lambda line:any(pat in line for pat in pats)) 

Если ваши шаблоны являются одиночными символьными строками, вы можете оптимизировать это с помощью набора:

 pats = set('abcd') matches = groupby(lines, keyfunc=pats.intersection) 

Это приведет к повторению, аналогичному

 [(matched patterns, lines matched), (empty list, lines not matched), (matched patterns, lines matched), …] 

(Кроме того, это будет генератор, а не список.) Это основная логика этого. Ниже следует один из способов повторения этого предварительно обработанного генератора для вывода продукта.

 for linegrp in matches: for line in matched_pats, linegrp: if matched_pats: print('"{}" matched because of "{}"'.format(line, matched_pats)) else: print('"{}" did not match') 

Более активное участие, но гораздо быстрее: предварительно обработайте список строк в префикс trie.

Затем, для каждой строки файла, начиная с каждой позиции символа, смотрите, как далеко вы можете пройти в trie.

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


Простым шагом будет сокращение вашего большого списка строк до списка списков строк, индексированных по трем первым символам каждой строки, которую вы ищете.

 from itertools import count, tee, izip def triwise(iterable): # base on pairwise, from the itertools documentation "s -> (s0,s1,s2), (s1,s2,s3), (s2,s3,s4), ..." a, b, c = tee(iterable, 3) next(b, None) next(c, None) next(c, None) return izip(a, b, c) class Searcher: def __init__(self): self.index = {} def add_seek_strings(self, strings): for s in strings: pre = s[:3] if pre in self.index: self.index[pre].append(s) else: self.index[pre] = [s] def find_matches(self, target): offset = -1 for a,b,c in triwise(target): offset += 1 pre = a+b+c if pre in self.index: from_here = target[offset:] for seek in self.index[pre]: if from_here.startswith(seek): yield seek def is_match(self, target): for match in self.find_matches(target): return True return False def main(): srch = Searcher() srch.add_seek_strings(["the", "words", "you", "want"]) with open("myfile.txt") as inf: matched_lines = [line for line in inf if srch.is_match(line)] if __name__=="__main__": main() 
  • Удаление нескольких словарей в списке
  • Python: эффективный подсчет количества уникальных значений ключа в списке словарей
  • Как преобразовать строку с разделителями-запятыми в список в Python?
  • нахождение суммы чисел X в списке (Python)
  • Перечисление через список функций в функции в Python динамически
  • Индекс отрицательного списка?
  • Итерации по всем парам последовательных элементов из данного списка
  • Индексирование списка с уникальным индексом
  • Python - лучший язык программирования в мире.