Как сравнить большие текстовые файлы?

Question

У меня есть общий вопрос о вашем мнении о моей "технике".

Есть 2 текстовых файла (file_1 и file_2), которые необходимо сравнить друг с другом.Оба очень большие (3-4 гигабайта, от 30 000 000 до 45 000 000 строк каждая).Моя идея - прочитать несколько строк (как можно больше) file_1 в память, а затем сравнить их с всеми строками file_2.Если есть совпадение, строки из обоих файлов должны быть записаны в новый файл.Затем перейдите к следующим 1000 строкам file_1, а также сравните их с всеми строками file_2, пока я полностью не пройду file_1.

Но на самом деле это звучит действительнодействительно трудоемкий и сложный для меня.Можете ли вы придумать какой-нибудь другой метод для сравнения этих двух файлов?

Как вы думаете, сколько времени может занять сравнение?Для моей программы время не имеет большого значения.У меня нет опыта работы с такими огромными файлами, поэтому я понятия не имею, сколько времени это может занять.Это не должно занять больше дня, хотя.;-) Но я боюсь, что моя техника может занять вечность ...

Другой вопрос, который мне только что пришёл в голову: сколько строк вы бы прочитали в памяти?Как можно больше?Есть ли способ определить количество возможных строк, прежде чем пытаться это сделать?Я хочу прочитать как можно больше (потому что я думаю, что это быстрее), но у меня часто кончается память.

Заранее спасибо.

РЕДАКТИРОВАТЬ IЯ думаю, что мне нужно объяснить мою проблему немного подробнее.

Цель состоит не в том, чтобы увидеть, идентичны ли эти два файла вообще (они не являются).В каждом файле есть несколько строк, которые имеют одинаковую «характеристику».Вот пример: file_1 выглядит примерно так:

mat1 1000 2000 TEXT      //this means the range is from 1000 - 2000
mat1 2040 2050 TEXT
mat3 10000 10010 TEXT
mat2 20 500 TEXT

file_2 выглядит так:

mat3 10009 TEXT
mat3 200 TEXT
mat1 999 TEXT

TEXT относится к символам и цифрам, которые не представляют интересадля меня mat может идти от mat1 - mat50 и не в порядке;также может быть 1000x mat2 (но цифры в следующем столбце отличаются).Мне нужно найти подходящие линии таким образом, чтобы: matX был одинаковым в обеих сравниваемых линиях, а число, указанное в file_2, соответствует диапазону, указанному в file_1.Так что в моем примере я нашел бы одно совпадение: строка 3 из file_1 и строка 1 из file_2 (потому что оба - mat3 и 10009 между 10000 и 10010).Надеюсь, это прояснит вам!

Итак, мой вопрос: как бы вы искали соответствующие строки?

Да, я использую Java в качестве языка программирования.

РЕДАКТИРОВАТЬ Теперь я сначала разделил огромные файлы, чтобы у меня не было проблем с нехваткой памяти.Я также думаю, что быстрее сравнивать (много) меньшие файлы друг с другом, чем эти два огромных файла.После этого я могу сравнить их так, как я упоминал выше.Возможно, это не идеальный способ, но я все еще учусь ;-) Тем не менее, все ваши подходы были очень полезны для меня, спасибо за ваши ответы!

Answer 1

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

Вероятно, вам следует провести несколько экспериментов [тестов] с изменяющимся размером фрагмента, чтобы выяснить, какой блок оптимален для чтения в среднем случае.

Answer 2

Я бы попробовал следующее: для каждого файла, который вы сравниваете, создайте временные файлы (я называю это частичным файлом позже) на диске, представляющем каждую буквенную букву, и дополнительный файл для всех других символов. затем прочитайте весь файл построчно. при этом вставьте строку в соответствующий файл, который соответствует букве, с которой он начинается. так как вы сделали это для обоих файлов, теперь вы можете ограничить сравнение для загрузки двух меньших файлов одновременно. строка, начинающаяся с A, например, может появляться только в одном частичном файле, и не будет необходимости сравнивать каждый частичный файл более одного раза. Если получающиеся файлы все еще очень велики, вы можете применить ту же методологию к результирующим частичным файлам (буквенным файлам), которые сравниваются, создавая файлы в соответствии со второй буквой в них. обменом здесь будет временное использование большого дискового пространства до завершения процесса. в этом процессе подходы, упомянутые в других постах, могут помочь более эффективно работать с частичными файлами.

Answer 3

Как насчет использования управления исходным кодом, например Mercurial ? Я не знаю, может быть, это не совсем то, что вы хотите, но это инструмент, который предназначен для отслеживания изменений между ревизиями. Вы можете создать репозиторий, зафиксировать первый файл, затем перезаписать его другим, а затем зафиксировать второй:

hg init some_repo
cd some_repo
cp ~/huge_file1.txt .
hg ci -Am "Committing first huge file."
cp ~/huge_file2.txt huge_file1.txt
hg ci -m "Committing second huge file."

Отсюда вы можете получить различие, сообщающее вам, какие линии отличаются. Если бы вы могли каким-то образом использовать эту разность, чтобы определить, какие строки были одинаковыми, у вас все было бы в порядке.

Это просто идея, кто-то поправит меня, если я ошибаюсь.

Answer 4

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