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

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

Я думаю, ваш путь довольно разумный.

Я могу представить разные стратегии - например, вы можете отсортировать оба файла перед сравнением (где эффективная реализация сортировки файлов, а утилита сортировки Unix может отсортировать несколько файлов Gbs за несколько минут), и, сортируя, вы можете сравнивать файлы последовательно читая построчно.

Но это довольно сложный путь - вам нужно запустить внешнюю программу (сортировку) или самостоятельно написать сопоставимую эффективную реализацию сортировки файлов в java - что само по себе является непростой задачей. Итак, ради простоты, я думаю, что вы читаете по частям очень многообещающе;

Что касается того, как найти разумный блок - во-первых, может быть не правильно, что «чем больше, тем лучше» - я думаю, время всей работы будет расти асимптотически, до некоторой постоянной линии. Так что, может быть, вы будете ближе к этой линии, чем вы думаете - вам нужен эталон для этого.

Далее - вы можете читать строки в буфер следующим образом:

final List<String> lines = new ArrayList<>();
try{
    final List<String> block = new ArrayList<>(BLOCK_SIZE);
    for(int i=0;i<BLOCK_SIZE;i++){
       final String line = ...;//read line from file
       block.add(line);
    }
    lines.addAll(block); 
}catch(OutOfMemory ooe){
    //break
}

Таким образом, вы читаете столько строк, сколько можете - оставляя последний BLOCK_SIZE свободной памяти. BLOCK_SIZE должен быть в восторге от остальной части вашей программы для запуска без OOM

Answer 2

В идеальном мире вы сможете читать каждую строку файла file_2 в память (возможно, используя объект быстрого поиска, такой как HashSet, в зависимости от ваших потребностей), а затем читать каждую строку из file_1 по одному время и сравните его с вашей структурой данных, содержащей строки из file_2.

Как вы уже сказали, у вас не хватает памяти, но я думаю, что стратегия типа «разделяй и властвуй» была бы лучшей. Вы можете использовать тот же метод, который я упоминал выше, но прочитать половину (или треть, четверть ... в зависимости от того, сколько памяти вы можете использовать) строк из file_2 и сохранить их, а затем сравнить все строки в файле_1. Затем прочитайте в следующую половину / третью / четверть / что угодно в памяти (заменяя старые строки) и снова пройдитесь по file_1. Это означает, что вам нужно пройти через file_1 больше, но вы должны работать с ограничениями памяти.

---

РЕДАКТИРОВАТЬ: В ответ на дополнительные детали в вашем вопросе, я бы частично изменил свой ответ. Вместо чтения всего файла file_2 (или кусками) и чтения в file_1 строки за раз, поменяйте местами, поскольку file_1 содержит данные для проверки.

Кроме того, что касается поиска соответствующих строк. Я думаю, что лучшим способом было бы выполнить некоторую обработку файла_1. Создайте HashMap<List<Range>>, который отображает String ("mat1" - "mat50") в список Range s (просто оболочка для startOfRange int и endOfRange int) и заполните его данными из file_1. Затем напишите функцию вроде (игнорируя проверку ошибок)

boolean isInRange(String material, int value)
{
    List<Range> ranges = hashMapName.get(material);
    for (Range range : ranges)
    {
        if (value >= range.getStart() && value <= range.getEnd())
        {
            return true;
        }
    }
    return false;
}

и вызывать его для каждой (проанализированной) строки файла_2.

Answer 3

Теперь, когда вы дали нам больше подробностей, подход, который я выбрал бы, основывается на предварительном разбиении и, возможно, сортировке перед поиском совпадений.

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

Разбиение: Прочитать file_1 и отправить все строки, начиная с mat1 до file_1_mat1, искоро.Сделайте то же самое для file_2.Это тривиально с небольшим grep, или, если вы хотите сделать это программно на Java, это упражнение для начинающих.

Это один проход через два файла для общего количества прочитанных 80 миллионов строк, что дает два набора по 50файлы по 800 000 строк в среднем.

Сортировка: Для каждого раздела сортируйте по числовому значению только во втором столбце (нижняя граница от file_1 и фактическое число отfile_2).Даже если 800 000 строк не умещаются в памяти, я полагаю, что мы можем адаптировать двустороннюю внешнюю сортировку слиянием и выполнять это быстрее (меньшее общее чтение), чем сортировка всего неразделенного пространства.

Сравнение: Теперь вам просто нужно итерировать один раз по обеим парам file_1_mat1 и file_2_mat1, без необходимости хранить что-либо в памяти, выводя совпадения в ваш выходной файл.Повторите для остальных разделов по очереди.Нет необходимости в последнем шаге «слияния» (если вы не обрабатываете разделы параллельно).

Даже без этапа сортировки уже выполняемое наивное сравнение должно работать быстрее для 50 пар файлов с 800 000 строккаждый, а не с двумя файлами по 40 миллионов строк в каждом.

Answer 4

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

Вы упомянули, что число строк достигает примерно 45 миллионов.Это означает, что вы можете (потенциально) хранить индекс, который использует 16 байтов на запись (128 бит), и он будет использовать около 45 000 000 * 16 = ~ 685 МБ ОЗУ, что не является необоснованным в современной системе.Использование решения, которое я описываю ниже, сопряжено с дополнительными затратами, поэтому вам все же может понадобиться использовать другие методы, такие как файлы с отображением памяти или таблицы на дисках, для создания индекса.См. Hypertable или HBase для примера того, как сохранить индекс в быстрой хэш-таблице на основе диска.

Таким образом, в целом алгоритм будет чем-тонапример:

1. Создание хэш-карты, которая отображает Long в список Long (HashMap)
2. Получить хэш каждой строки в первом файле (достаточно Object.hashCode)
3. Получить смещение в файле строки, чтобы вы могли найти его позже
4. Добавить смещение в список строк с совпадающими хэш-кодами в хэш-карте
5. Сравнить каждую строку второго файла с набором смещений строк в индексе
6. Сохранить все строки, которыеесть соответствующие записи

РЕДАКТИРОВАТЬ: В ответ на ваш отредактированный вопрос, это не очень поможет само по себе.Вы можете просто хэшировать первую часть строки, но при этом будет создано только 50 разных записей.Затем вы можете создать еще один уровень в структуре данных, который сопоставит начало каждого диапазона со смещением линии, из которой он получен.

Так что что-то вроде index.get("mat32") вернет TreeMap диапазонов.Вы можете найти диапазон, предшествующий искомому значению lowerEntry () .В совокупности это даст вам достаточно быструю проверку, чтобы определить, была ли данная комбинация matX / number в одном из диапазонов, которые вы проверяете.

Answer 5

Если вы хотите точно знать, отличаются ли файлы или нет, то нет лучшего решения, чем у вас, - последовательное сравнение.

Однако вы можете сделать некоторую эвристику, которая скажет вам что-товероятности, если файлы идентичны.1) Проверьте размер файла;это самое простое.2) Возьмите случайную позицию файла и сравните блок байтов, начиная с этой позиции в двух файлах.3) Повторите шаг 2) для достижения необходимой вероятности.

Вы должны вычислить и проверить, сколько операций чтения (и размера блока) полезно для вашей программы.

Answer 6

Что вы можете сделать, это отсортировать каждый отдельный файл. например UNIX sort или аналогичный в Java. Вы можете прочитать отсортированные файлы по одной строке за раз, чтобы выполнить сортировку слиянием.

Answer 7

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

Answer 8

Действительно, это может занять некоторое время. Вы должны сделать 1 200 000 000 сравнений строк. Есть несколько возможностей ускорить это на порядок:

Можно отсортировать файл2 и выполнить бинарный поиск на уровне файлов. Другой подход: вычислить контрольную сумму каждой строки и найти ее. В зависимости от средней длины строки, рассматриваемый файл может быть намного меньше, и вы действительно можете выполнить бинарный поиск, если сохраните контрольные суммы в фиксированном формате (то есть длинном)

Количество строк, которые вы прочитали сразу из file_1, однако, не имеет значение. Это микрооптимизация перед лицом большой сложности.

Answer 9

Не уверен, насколько хорошим был бы ответ - но взгляните на эту страницу: http://c2.com/cgi/wiki?DiffAlgorithm - он обобщает несколько алгоритмов различий.Алгоритм Ханта-Макилроя, вероятно, является лучшей реализацией.С этой страницы также есть ссылка на Java-реализацию GNU diff.Тем не менее, я думаю, что реализация на C / C ++ и скомпилированная в нативный код будет намного быстрее.Если вы застряли с Java, вы можете рассмотреть JNI.

Answer 10

Я никогда не работал с такими огромными файлами, но это моя идея, и она должна работать.

Вы можете посмотреть в хэш. Использование SHA-1 Хеширования.

Импорт следующего

import java.io.FileInputStream;
import java.security.MessageDigest;

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

StringBuffer myBuffer = new StringBuffer("");
//For each line loop through
    for (int i = 0; i < mdbytes.length; i++) {
        myBuffer.append(Integer.toString((mdbytes[i] & 0xff) + 0x100, 16).substring(1));
    }
System.out.println("Computed Hash = " + sb.toString());

Пример кода SHA с упором на текстовый файл

SO Вопрос о вычислении SHA в JAVA (возможно, полезен)

Еще один пример кода хеширования.

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

Тогда, если вы получите другое значение, вы можете выполнить супер-трудоемкую проверку построчно.

В целом, кажется, что чтение строка за строкой и т. Д. Будет длиться вечно. Я бы сделал это, если вы пытаетесь найти каждую индивидуальную разницу. Но я думаю, что хэширование будет быстрее, если они будут одинаковыми.

контрольная сумма SHA