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

Question

У меня два очень больших файла (и ни один из них не помещается в память ). В каждом файле есть одна строка (в которой нет пробелов и длина 99/100/101 символов) в каждой строке.

Обновление: Строки расположены не в любом порядке.
Обновление2: Я работаю с Java в Windows.

Теперь я хочу выяснить, как лучше всего выяснить все строки, встречающиеся в обоих файлах.

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

Когда вы предлагаете решение, укажите также, будет ли решение работать, если бы было более 2 файлов, и во всех них нужно было найти строки.

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

FINDSTR /G:A B > OUTPUT

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

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

FINDSTR /V /G:A B > OUTPUT

Answer 5

Решение на основе хеш-функции может выглядеть следующим образом (в псевдокоде 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!).

Answer 6

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

Answer 7

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

Answer 8

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