python: поиск в файле

Question

У меня есть два текстовых файла, которые являются примерно 1M строк. Назовем их f1 и f2.

Для каждой строки в f1 мне нужно найти индекс строки в f2, где строка в f1 является подстрокой строки в f2. Так как мне нужно сделать это для всех строк f1, использование вложенного цикла слишком дорогостоящее, и мне было интересно, есть ли обходной путь, который может значительно сократить время.

Заранее благодарю за помощь.

Answer 1

Конечно, есть лучшие способы, чем использование двух циклов: D Это даст вам O (n^2) время исполнения. Что-то очень полезное для поиска подстрок называется rolling hash. Это способ использовать предыдущую информацию, чтобы ускорить поиск подстрок. Это выглядит примерно так:

Скажем, у меня есть строка, f1 = "cat" и длинная строка f2 = "There once was a cat named felix". То, что вы делаете, - это определение «хэш» на основе букв вашей строки f1. Специфика этого может быть найдена в Интернете в разных источниках, но в этом примере позволяет упростить вещи и сказать, что буквы присваиваются числам, начинающимся с 0, до 25, и мы умножим значение каждой буквы, чтобы сформировать десятичное число с числом цифры, равные длине строки:

hash("cat") = 10^2 * 2 + 10^1 * 0 + 10^0 * 19 
      = some value (in python the "hash" values of letters 
       are not 0 through 25 but given by using the ord cast: 
       ord("a") will give you 97) 

Теперь эта следующая часть супер крутая. Мы обозначаем окна размера нашей строки f1, поэтому размер 3 и хэш строку f2 так же, как и с f1. Вы начинаете с первых трех букв. Хэш не соответствует, поэтому мы движемся дальше. Если хэш согласован, мы убеждаемся, что это одна и та же строка (иногда хэши одинаковы, но не являются одной и той же строкой из-за того, как мы назначаем хэши, но это нормально).

COOL PART ** Вместо того, чтобы просто сдвигать окно и переписывать буквы от 2 до 4 букв f2, мы «свертываем» окно и не пересчитываем весь хеш (который, если f1 действительно длинный, будет пустой тратой время), так как единственные буквы меняются первыми и последними! Трюк состоит в том, чтобы вычесть первое значение хэша (в нашем примере будет ord ("t") * 10^2), затем умножьте все число, оставшееся на десять (потому что мы переместили все влево) и добавим новый хеш буква, ord («r») * 10^0. Проверьте снова матч и перейдите. Если мы сопоставим, вернем индекс.

Почему мы это делаем: если у вас достаточно длинная строка f1, вы сокращаете время выполнения до O (n * len (n)), так что асимптотически линейны!

Теперь фактическая реализация требует времени и может стать беспорядочной, но для такого ответа есть много источников в Интернете. My algorithms class имеет отличные примечания к курсу в Интернете, которые помогают понять теорию немного лучше, и есть тонны ссылок с реализациями python. Надеюсь это поможет!