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

Я думаю, ваш способ довольно разумен.

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

Но это довольно сложный путь - вам нужно запустить внешнюю программу (сортировку) или написать сопоставимую эффективную реализацию filesort в 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 должен быть большим enouth для остальной части программы, чтобы работать без OOM

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

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

---

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

Также, Что касается поиска совпадающих строк. Я думаю, что лучшим способом было бы сделать некоторую обработку на file_1. Создайте HashMap<List<Range>>, который сопоставляет строку ("mat1" - "mat50") со списком Ranges (просто оболочка для 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;
}

И назовем это для каждой (проанализированной) строки file_2.

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

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

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

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

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

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

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

И все эти ответы о хэшах, контрольных суммах и т. д.: Они не быстрее. Вы должны прочитать весь файл в обоих случаях. С хэшами / контрольными суммами вам даже придется что-то вычислять...

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

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

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

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

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

После того, как ваш текстовый файл etc был загружен, сделайте его цикл через каждую строку и в конце распечатайте хэш. Ссылки на примеры ниже будут более подробными.

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, фокусирующийся на текстовом файле

Поэтому вопрос о вычислении SHA в JAVA (возможно полезно)

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

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

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

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

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

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

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

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

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

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

Таким образом, в полном объеме алгоритм будет выглядеть примерно так:

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

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

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

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

Как насчет использования системы управления версиями, такой как 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."

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

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

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