加入超过 6 亿行的文本文件

Question

我有两个文件，huge.txt和small.txt. huge.txt有大约 600M 行，它是 14 GB。每行有四个空格分隔的单词（标记），最后是另一个带有数字的空格分隔列。small.txt有 150K 行，大小为 ~3M，一个空格分隔的单词和一个数字。

这两个文件都使用 sort 命令进行排序，没有额外的选项。两个文件中的单词都可能包含撇号 (') 和破折号 (-)。

所需的输出将包含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. 如何以 join 命令认为文件正确排序的方式对文件进行排序？

2. 我正在考虑计算MD5或字符串的其他一些哈希值以去除撇号和破折号，但在行尾保留数字。使用散列而不是字符串本身进行排序和连接，最后将散列“翻译”回字符串。由于只有 150K 哈希值，所以还不错。为每个字符串计算单个散列的好方法是什么？一些AWK魔法？

请参阅最后的文件示例。

巨大的样本.txt

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. 逐行处理huge.txt，添加从散列中查找的列并将结果写入输出文件
3. 缓冲输入和输出，使其以至少 4K 的块发生

Answer 2

以 Michael Borgwardt 的回答为基础：只要对两个文件进行排序，您就可以通过基本上执行合并排序的一个步骤将它们放在一起。它与标准归并排序略有不同，因为您只想保留其中一个文件。当然，这必须用您最喜欢的编程语言来实现。

这是算法的草图：

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

我知道这很简单，但很有效。
基于我的原始文件只包含小写字符的假设，我简单地将有问题的撇号和破折号替换为两个大写字母，重新排序并加入文件，最后将字母改回符号。就是这样。

再次感谢大家提供答案或富有洞察力的评论。

giga.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