☰

合并超过 6 亿行的文本文件

tag-icon • tag-icon command-line sed sorting awk join
合并超过 6 亿行的文本文件

我有两个文件，huge.txt其中small.txt.huge.txt有大约 6 亿行，大小为 14 GB。每行有四个空格分隔的单词（标记），最后还有一个空格分隔的列和一个数字。 .small.txt有 15 万行，大小约为 3M，一个空格分隔的单词和一个数字。

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

所需的输出将包含文件中的所有列以及的第一个单词和 的第一个单词匹配的huge.txt第二列（数字）。small.txthuge.txtsmall.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 魔法？

请参阅最后的文件示例。

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

答案1

我认为最好的方法是使用你最了解的编程/脚本语言：

  1. 将 small.txt 加载到以单词为键的内存哈希/映射/关联数组中
  2. 逐行处理 huge.txt，添加从哈希中查找的列并将结果写入输出文件
  3. 缓冲输入和输出，使其至少以 4K 的块进行

答案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。

答案3

我的回答与 Michael Borgwardt 的类似，但您不必将两个文件全部加载到内存中。如果两个文件都已排序，则您一次一行地浏览第一个文件，然后对第二个文件进行二分搜索以找到目标行。这需要大量高清访问，但内存消耗很低。

答案4

好的，这种方法使用http://cr.yp.to/cdb.html作为一种更快捷的方式来查找“small.txt”的内容：

  • 去安装cdbmake（Ubuntu 中“freecdb”包的一部分，但有很多可用的实现。

  • 使用 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”中的一行从“key value”之类的内容转换为“+ks,vs:key->value”。）

  • 现在逐行浏览“huge.txt”并将其打印出来，查找“small.cdb”中的第一个单词：

    #!/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 GB。因此，如果您必须处理大小为 10 GB 的“small.txt”，则显然必须将其拆分为多个文件并创建“small1.cdb”、“small2.cdb”、“small3.cbd”等。这应该是一项简单的任务。
  • 您不需要对“small.txt”进行排序，因为在 cdb 文件中查找速度非常快。
  • 我没有在这里对我的小测试用例进行计时，它是基于您提供的内容。:)

相关内容