Как найти общие строки среди двух очень больших файлов?

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

sort file1 | uniq > output
sort file2 | uniq >> output
sort file3 | uniq >> output
...
sort output | uniq -d

В зависимости от того, насколько подобный записи в одном файле, могло бы быть возможно создать Trie (не дерево) от него. Используя этот trie можно выполнить итерации другого файла и проверить каждую запись, если это в trie.

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

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

Я сделал бы это следующим образом (для любого количества файлов):

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

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

Основанное на хеше решение могло бы быть похожим на это (в псевдокоде Python):

hashes = dict()
for file in files:
    for line in lines:
        h = md5(line)
        hashes[h] += 1

Затем цикл снова, печатая согласующие отрезки длинной линии:

for file in files:
    for line in lines:
        h = md5(line)
        if hashes[h] == nfiles:
            print line
            del hashes[h]  # since we only want each once.

Существует две потенциальных проблемы.

1. потенциальные хэш-коллизии (который может быть смягчен некоторые, но является риском.)
2. потребности смочь обработать dict (ассоциативный массив) размера: строки |uniq во всех файлах |

Это - O (строки * стоят (md5)).

(если люди более полная реализация Python, довольно легко записать, я не знаю Java хотя!).

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

Сделать это в Windows довольно просто .. Допустим, у вас есть два файла A и B. Файлы «A» содержат строки, которые вы хотите искать в файле B. просто откройте командную строку и используйте следующую команду

FINDSTR /G:A B > OUTPUT

. Эта команда довольно быстрая и может очень эффективно сравнивать два файла. . Файл OUTPUT будет содержать строки, общие для A и B.

, если вы хотите выполнить операции OR (строки в B, кроме A), используйте

FINDSTR /V /G:A B > OUTPUT