Поиск повторяющихся строк

Привет. Возник вопрос: Есть файл 1 ~ 2GB и есть файл 2 ~ 1MB Вопрос - как наиболее быстро подсчитать кол-во вхождений строк из файла2 в файле1? К примеру файл1: Тест корова большая Флагман большая корова Трубадур золотистый Флагманский телефон N90 Логическое оформление Тест корова Бла бла стар Файл2: Трубадур Тест корова телефон Должно получиться: Трубадур 1 Тест корова 2 телефон 1 Файл 1 много больше файл2.

Ответ

Эффективным методом поиска нескольких подстрок одновременно в большом тексте является алгоритм Ахо-Корасика. Оригинальный fgrep (grep -F) использует этот алгоритм. GNU grep в этом случае использует Commentz-Walter алгоритм (объединение Ахо-Корасика и алгоритма поиска строки Бойера—Мура). ripgrep (rg) иногда работает быстрее GNU grep, используя SIMD алгоритм, называемый Teddy -- см. ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}
Чтобы подсчитать найденные строки, можно использовать sort | uniq -c команду, предложенную @BOPOH в комментарии к вопросу. Ещё можно использовать словарь вместо сортировки:
#!/bin/sh grep -Fof file2 file1 | perl -lne '$seen{$_}++ }{ while (my ($k,$v)=each %seen){print "$k $v"}'
Измерения могут показать, какая из команд (sort+uniq или perl) быстрее в данном случае.
Для сравнения можно посмотреть, сколько займёт Питон-скрипт без использования дополнительных пакетов (например, esm), которые реализуют Ахо-Корасик-подобные алгоритмы:
#!/usr/bin/env python import re import sys from collections import Counter
def main(): # load substrings from file2 with open('file2', 'rb') as file2: substrings = {line.strip() for line in file2} # unique lines substrings = filter(None, substrings) # filter blank lines substrings = sorted(substrings, key=len, reverse=True) # longest first pattern = b"|".join(map(re.escape, substrings)) find_substrings = re.compile(pattern).findall
# count substrings in file1 counter = Counter() counter_update = counter.update # cache the lookup (for CPython) with open('file1', 'rb') as file1: for line in file1: counter_update(find_substrings(line))
# write substrings frequencies write = getattr(sys.stdout, 'buffer', sys.stdout).write for substring, count in counter.most_common(): # most common first write(substring) write(b' ') write(str(count).encode()) write(b'
')
main()
Результат
Тест корова 2 телефон 1 Трубадур 1
Вот ещё вариант для сравнения, где строки в файле ищутся с помощью регулярного выражения и mmap
#!/usr/bin/env python3 import re import sys from collections import Counter from mmap import ACCESS_READ, mmap from operator import methodcaller
def generate_tokens(filename, pattern): with open(filename) as f, mmap(f.fileno(), 0, access=ACCESS_READ) as mm: yield from re.finditer(pattern, mm)
def main(): # load substrings from file2 with open('file2', 'rb') as file2: substrings = {line.strip() for line in file2} # unique lines substrings = filter(None, substrings) # filter blank lines substrings = sorted(substrings, key=len, reverse=True) # longest first pattern = b"|".join(map(re.escape, substrings))
# count substrings in file1 file1_substrings = generate_tokens('file1', pattern) counter = Counter(map(methodcaller('group'), file1_substrings))
# write substrings frequencies write = getattr(sys.stdout, 'buffer', sys.stdout).write for substring, count in counter.most_common(): # most common first write(substring) write(b' ') write(str(count).encode()) write(b'
')
main()
Работает на Windows, *nix. Код для Питон 3, но его можно легко адаптировать для Питон 2, если необходимо.