Дублированные строки в TXT-файле 3 ТБ

Question

Скажем, есть TXT-файл объемом 3 ТБ, в котором каждая строка является строкой. Как найти в них эти дублированные строки? Это вопрос интервью от моего друга. Нам лучше прояснить эти вопросы после собеседования, в случае следующего.

PS: Если я интервьюирую, я скажу интервьюеру: Как вы, ребята, можете хранить так много строк в файле TXT? Это действительно плохая идея!

Answer 1

Одной из возможностей является использование фильтра Блума.

Фильтр Блума работает быстро (например, с использованием хэш-кода) и не содержит ложных негативов. Это также очень экономно. Различные параметры (размер (м) и количество функций (к)) можно настроить для достижения лучшего ложноположительного показателя за счет размера и времени.

Вы добавляете все строки одну за другой к набору, представленному фильтром. Во время вставки вы можете определить, существует ли дубликат. Поскольку он не имеет ложных отрицаний, вам нужно только дважды проверить строки, которые появляются как «дубликаты» фильтра.

Если вам нужна дополнительная информация о фильтрах Блума, перейдите по ссылке wikipedia

Это, безусловно, лучший подход к решению этой проблемы. Фильтры Блума используются прокси-серверами, чтобы определить, находится ли URL в их кэше. Прокси-сервер видит миллиарды URL-адресов и должен быть в состоянии очень быстро определить, является ли URL-адрес новым или был «просмотрен» им ранее. Если URL-адрес «новый», прокси-сервер немедленно выбирает веб-сайт с исходного URL-адреса, а не ищет его в своем кэше.

Все остальные ответы здесь, которые даже отдаленно используют «сортировку», явно неверны.

Answer 2

sort bigfile.txt | uniq -d

Answer 3

если в строке только одно слово, почему бы вам просто не записать текстовый файл в таблицу базы данных со следующими столбцами id, text и сделать несколько

select text, count(text) 
from table 
group by text
having count(text)>1

тогда вы должны получить правильные ответы очень простым способом.

Answer 4

SELECT String
FROM TextFile
GROUP BY String
HAVING COUNT(*) > 1
ORDER BY String

Answer 5

Если у вас достаточно свободного места на диске, что-то вроде этого должно быть работоспособным:

for every line in the file:
    calculate a hash function for that line.
    append to a file named based on that hash (create if new).
for every file created:
    sort it.
    for every line in sorted file:
        if first line in file:
            set count to 0.
            set lastline to line.
        else
            if line identical to lastline:
                add 1 to count.
                if count is 1:
                    Output line.
            else:
                set count to 0.
        set lastline to line.

Если ваша хеш-функция относительно сбалансирована, сортировки не должны быть слишком обременительными.

Answer 6

Достаточно простой способ отразить все мои мысли:

Вы можете объединить текстовый файл (с хорошей производительностью для данных, слишком больших для размещения в основной памяти).Затем вы можете идентифицировать дубликаты за один проход через файл.O(nlogn).Конечно, это либо изменит исходный текстовый файл, либо вы можете сделать копию.

Answer 7

Полагаю, лучше использовать Perl, так как он полезен для обработки текста.Напишите следующее в программе Perl:

my% dataHash = (); # создайте ваш хэшwhile (@ARGV) {#argv - аргумент командной строки, который будет файлом chomp размером 3 ТБ ($ _);# удалить новую строку

если (! существует ($ dataHash {$ _})) {$ dataHash {$ _} = $ currentLine;# увеличить счетчик значения ключа, если ключ существует ... для устранения дубликатов ....};$ CurrentLine ++;};# конец

Теперь мы можем делать все, что захотим ... например, мы хотим дублироватьИтак, что мы можем сделать, это запустить цикл for и проверить, что все ключи, для которых значение больше 0, являются дубликатами ... вот и все

Я думаю, что следует сделать ... извините за не добавление цвета в программу для лучшей читаемости

Answer 8

Вероятностное решение

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

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

Эта техника не гарантирует избавления от всех дубликатов (только большинство из них).

Пусть

1. s [1], s [2], ..., s [n] - входные строки.
2. h [1], h [2], ..., h [m] - различные хеш-функции размера k.
3. a [1, ... n] будет массивом битов со значениями 0, 1.
4. b [1, ..., m] [1, ..., k] будет массивом флагов, имеющих значения 0, 1, 2.

Тогда

1. Для i = 1 до k:
   1. Для j = 1 до n:
      1. если a [j] == 0 // эта строка может / не может быть уникальной
         1. Пусть x будет h [i] (s [j]).
         2. если b [i] [x] == 0, то b [i] [x] == 1
         3. иначе, если b [i] [x] == 1, то b [i] [x] = 2
      2. иначе, если a [j] == 1, эта строка доказала свою уникальность, пропустите ее.
   2. Для j = 1 до n:
      1. если a [j] == 0 // эта строка может / не может быть уникальной
         1. Пусть x будет h [i] (s [j])
         2. если b [i] [x] == 1, то установить a [j] = 1 // мы доказали, что строка уникальна
         3. иначе, если b [i] [x] == 2 эта строка может / не может быть уникальной
         4. иначе, если b [i] [x] == 0, есть проблема реализации
      2. иначе, если a [j] == 1, эта строка доказала свою уникальность, пропустите ее

Answer 9

Я бы предложил 2 решения.

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

Вторым было бы отсортировать текстовый файл, как предлагали другие.

Answer 10

Сортируйте этот файл, дубликаты будут отсортированы вместе.В качестве альтернативы, создайте второй файл и хеш (md5?) Каждой строки в нем, а затем отсортируйте его.