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

#python #grep #perl #awk #linux

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

Файл2:
Трубадур
Тест корова
телефон

Должно получиться:
Трубадур 1
Тест корова 2
телефон 1

Файл 1 много больше файл2.    

Ответы

Ответ 1

Эффективным методом поиска нескольких подстрок одновременно в большом тексте является
алгоритм Ахо-Корасика. Оригинальный 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'\n')

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'\n')

main()


Работает на Windows, *nix. Код для Питон 3, но его можно легко адаптировать для Питон
2, если необходимо.


Ответ 2

Решение "в лоб" (сомневаюсь, что будет быстро)))
grep -o -f file2 file1 | sort | uniq -c

5 строк в file2 и 2.7Г в file1 где-то за 4 минуты обработало.
Если не требуется для каждой отдельной строки количество считать (т.е. достаточно
общего количества), тогда можно еще проще (и немного быстрее):
grep -co -f file2 file1


Ответ 3

Ну, как вариант, можно попробовать вот так в лоб:
somelist1 = []  
somelist2 = []  
f1 = open('file1.txt')  # файл на 2mb
f2 = open('file2.txt')  # файл на 2gb

for line in f1:
    a1 = line.replace('\n', '')
    somevar = a1.split()
    for i in somevar:
        somelist1.append(i)

for line in f2:
    a2 = line.replace('\n', '')
    somevar = a2.split()
    for i in somevar:
        somelist2.append(i)

for i in somelist1:
    index = 0
    for j in somelist2:
        if i == j:
            index += 1
    print(i + " - " + str(index))

Вывод в виде:
Трубадур - 481779
Тест - 963549
корова - 1445337
телефон - 481779

Попробовал на файле в 150 мб, сделался за 5-7 секунд, время не замерял. Может, кто-то
предложит более оптимизированное решение.
UPDATE
Попробовал на файле побольше, 2gb скорее всего точно не прогрузить, этот вариант
применим только к небольшим файлам.