Быстрый поиск подстроки в большой текстовой базе данных?

Question

У меня есть коробка с дисководами, в которой хранятся резервные копии рабочих и личных файлов на протяжении многих лет.Большинство файлов и каталогов являются дубликатами других резервных копий на других дисках или даже на том же диске.

Чтобы объединить этот беспорядок, я создал CSV-файл, содержащий контрольную сумму, размер и полный путь каждого файла.,Затем я написал простую программу на Python, используя библиотеку pandas для вычисления контрольной суммы и размера для каждого каталога, который представляет собой просто сумму контрольных сумм и размеров всех файлов, содержащихся в каталоге.Идея состоит в том, чтобы найти все каталоги с одинаковым содержимым и удалить все из них, кроме одного.

К сожалению (но я ожидал этого раньше), код выполняется несколько часов даже для моего набора тестовых данных, который содержит около 1 миллиона строк,Фактический набор данных имеет около 10 миллионов строк.

Вот фрагмент кода Python:

# for all directories, compute their checksum and total content size

df = pd.DataFrame(columns=['cksum', 'len', 'path'])
i = 0

for path in directories:

    # create new dataframe having all files in this directory
    items = data[data['path'].str.startswith(path)]

    # sum all checksums
    cksum = pd.to_numeric(items['cksum']).sum()

    # sum all file sizes
    len = pd.to_numeric(items['len']).sum()

    # store result 
    df.loc[i] = [cksum, len, path]

    i += 1

Очевидно, проблема в том, что для каждого каталога, который я должен найти, содержались каталоги и файлы,и для идентификации тех, которые я делаю, сравнение строк с использованием starts (path), которое является медленным, и мне нужно выполнить это 1 (или 10) миллион раз для каждого каталога.Итак, у нас есть проблема типа O (n ^ 2).

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

• Стоит ли использовать здесь базу данных SQL?Подумайте об утверждении, похожем на SELECT cksum, len, path FROM files,directories WHERE leftstr(files.path,n) == directories.path;.Но, может быть, это утверждение так же дорого, как и его эквивалент в Python?
• Подходит ли другая база данных или инструмент для такого типа текстового поиска?Я думал об Apache Lucene, ElasticSearch, MongoDB, NOSQL, но у меня нет опыта работы с ними, чтобы решить, какой продукт попробовать.
• Может быть, кто-то другой уже решил эту проблему дедупликации?Я нашел несколько коммерческих программных продуктов для ПК, но я не уверен, что они могут обрабатывать 10 миллионов файлов.

Пожалуйста, сообщите.