Присоединение текстовых файлов с 600M+ строк

Question

У меня есть два файла, huge.txt и small.txt . Текст . huge.txt имеет около 600 миллионов строк и 14 ГБ. В каждой строке есть четыре слова (токены), разделенные пробелами, и, наконец, еще один столбец с цифрами, разделенный пробелами. small.txt имеет 150K строк размером ~ 3M, разделенное пробелами слово и число.

Оба файла отсортированы с помощью команды сортировки без дополнительных опций. Слова в обоих файлах могут включать апострофы (') и тире (-).

Требуемый вывод будет содержать все столбцы из файла huge.txt и второй столбец (число) из small.txt где первое слово huge.txt и первое слово small.txt совпадают.

Мои попытки ниже потерпели неудачу со следующей ошибкой:

cat huge.txt|join -o 1.1 1.2 1.3 1.4 2.2 - small.txt > output.txt

join: memory exhausted  

Я подозреваю, что порядок сортировки как-то неправильный, хотя файлы предварительно отсортированы с использованием:

sort -k1 huge.unsorted.txt > huge.txt
sort -k1 small.unsorted.txt > small.txt

Проблемы, кажется, появляются вокруг слов, которые имеют апострофы (') или тире (-). Я также пробовал сортировку по словарю, используя опцию -d в конце которой встречалась та же ошибка.

Я попытался загрузить файлы в MySQL, создать индексы и присоединиться к ним, но, похоже, на моем ноутбуке это заняло несколько недель. (У меня нет компьютера с большим объемом памяти или быстрым диском /SSD для этой задачи)

Я вижу два выхода из этого, но не знаю, как реализовать любой из них.

1. Как отсортировать файлы так, чтобы команда соединения считала их правильно отсортированными?

2. Я думал о том, чтобы вычислить MD5 или некоторые другие хеши строк, чтобы избавиться от апострофов и тире, но оставить числа нетронутыми в конце строк. Выполняйте сортировку и объединение хешей вместо самих строк и, наконец, "переводите" хеши в строки. Поскольку хэшей будет всего 150K, это не так уж плохо. Что будет хорошим способом для вычисления отдельных хешей для каждой из строк? Немного волшебства AWK?

Смотрите образцы файлов в конце.

Образец огромный. Текст

had stirred me to 46 
had stirred my corruption 57 
had stirred old emotions 55 
had stirred something in 69 
had stirred something within 40 

Образец small.txt

caley 114881 
calf 2757974 
calfed 137861 
calfee 71143 
calflora 154624 
calfskin 148347 
calgary 9416465 
calgon's 94846 
had 987654

Желаемый результат:

had stirred me to 46 987654
had stirred my corruption 57 987654
had stirred old emotions 55 987654
had stirred something in 69 987654
had stirred something within 40 987654

Answer 1

IMO лучший способ сделать это - использовать язык программирования / сценариев, который вы знаете лучше всего:

1. загрузите small.txt в хэш / карту / ассоциативный массив в памяти, содержащий слова
2. Обрабатывайте огромный файл .txt построчно, добавляя столбец, ищущий из хеша, и записывая результат в выходной файл.
3. Буфер ввода и вывода так, чтобы это происходило порциями по крайней мере 4K

Answer 2

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

Вот эскиз алгоритма:

line1 = read a line from file 1
line2 = read a line from file 2
start of loop:
if (first word of line1 == first word of line2) {
    write all fields of line1
      and second field of line2 to output
    line1 = read a line from file 1
    go to start of loop
}
else if (first word of line1 < first word of line2) {
    write line1 to output
    line1 = read a line from file 1
    go to start of loop
}
else (first word of line1 > first word of line2) {
    line2 = read a line from file 2
    go to start of loop
}

Вот версия Python (так как Python - это то, что я знаю лучше всего, не обязательно лучший язык для работы):

file1 = open('file1', 'r')
file2 = open('file2', 'r')
w2, n2 = file2.readline().split()
for line1 in file1:
  w11, w12, w13, w14, n15 = line1.split()
  if w11 == w2:
    print w11, w12, w13, w14, n15, n2
    continue
  elif w11 < w2:
    print w11, w12, w13, w14, n15
    continue
  else:
    while w11 > w2:
      w2, n2 = file2.readline().split()
    if w11 == w2:
      print w11, w12, w13, w14, n15, n2
    elif w11 < w2:
      print w11, w12, w13, w14, n15

и для полноты после некоторого копания вот что я придумал для Awk:

BEGIN {
  getline line2 <"file2";
  split(line2, a);
}
{
  if (a[1] == $1) print $0,a[2];
  else if (a[1] < $1) print $0;
  else { getline line2 <"file2"; split(line2, a); }
}

Вызвать как awk -f program.awk <file1 .

Answer 3

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

Answer 4

Хорошо, этот подход использует http://cr.yp.to/cdb.html как более быстрый способ поиска содержимого файла small.txt:

• Перейдите и установите cdbmake (часть пакета 'freecdb' в Ubuntu, но есть много реализаций).

• Используйте awk для передачи small.txt в cdbmake .

  % awk '    { printf "+%d,%d:%s->%s\n", \
                  length($1),length($2),$1,$2 } \
         END { print "" }' | cdbmake small.cdb small.cdbtmp
  

(Это преобразует строку small.txt из чего-то вроде "значения ключа" в «+ks, vs:key-> value».)

• Теперь вы переходите строка за строкой над «принцпом» и распечатываете его, ища первое слово в «канале»:

  #!/bin/python
  import cdb
  import fileinput
  
  c = cdb.init("small.cdb")
  for l in fileinput.input(['huge.txt']):
      print l.strip(),
      v = c.get(l.split()[0])
      print "" if v == None else v
  

Конечно, вам придется установить python-cdb, чтобы этот крошечный фрагмент работал (и он работает только для Python 2.5 из-за « условного выражения »). В любом случае, есть много привязок для любого языка, который вам нравится. Вы также можете использовать cdbget (инструмент командной строки) и вызывать его снова и снова, но порождение нового процесса для миллионов строк немного неэффективно.

Во всяком случае, имейте это в виду:

• Каждый файл .cdb не может быть больше 4 ГБ. Поэтому, если вам нужно обработать файл small.txt размером 10 ГБ, вам, очевидно, придется разделить его на несколько файлов и создать файлы small1.cdb, small2.cdb, small3.cbd и т.д. Это должно быть легкой задачей.
• Вам не нужно сортировать 'small.txt', поиск в файле cdb довольно быстрый.
• Я не рассчитал свой маленький тестовый пример, он основан на том, что вы предоставили. :)

Answer 5

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

Еще раз спасибо за каждый вклад в ответ или проницательный комментарий.

Для огромного .txt (14Gig) сортировка заняла около 2 часов, соединение заняло менее часа.

cat small.txt | tr "\'-" "AD" | sort -k1 > small.AD
cat huge.txt | tr "\'-" "AD" | sort -k1 | cat huge.txt | join -o 1.1 1.2 1.3 1.4 2.2 - small.AD | tr "AD" "\'-" > output.txt

Answer 6

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