如何过滤非常非常大的文件

Question

我有一个非常大的未分类文件,1000GB的ID对

1. ID:ABC123 ID:ABC124
2. ID:ABC123 ID:ABC124
3. ID:ABC123 ID:ABA122
4. ID:ABC124 ID:ABC123
5. ID:ABC124 ID:ABC126

我想过滤该文件

1)重复

example
ABC123 ABC124
ABC123 ABC124

2)反向对(丢弃第二次出现)

example
ABC123 ABC124
ABC124 ABC123

过滤后,上面的示例文件看起来像

1. ID:ABC123 ID:ABC124
2. ID:ABC123 ID:ABA122
3. ID:ABC124 ID:ABC126

目前,我的解决方案就是这样

my %hash;

while(my $line = <FH>){
     chomp $line; #remove \n
     my ($id1,$id2) = split / /, $line;
     if(exists $hash{$id1$1d2} || exists $hash{$id2$id1}){
            next;
     }
     else{
         $hash{$id1$id2} = undef ; ## store it in a hash
         print "$line\n";
      }
}

这给了我较小列表的预期结果,但是对于较大的列表占用了太多内存,因为我将哈希存储在内存中.

我正在寻找一种可以减少内存实施的解决方案.我有一些想法

1)将哈希值保存到文件中,而不是内存中

2)多次传递文件

3)使用unix对文件进行排序和统一 sort -u -k1,2

在堆栈交换cs上发布后,他们建议使用外部排序算法

Answer 1

您可以使用映射减少来完成任务。

Map-Reduce 是一个批处理框架，可让您轻松地将工作分布在多台机器之间，并使用并行处理，而无需考虑同步和容错。

map(id1,id2):
    if id1<id2:
        yield(id1,id2)
   else:
        yield(id2,id1)

reduce(id1,list<ids>):
   ids = hashset(ids) //fairly small per id
   for each id2 in ids:
       yield(id1,id2)

Map-Reduce 实现将允许您将工作分布在多台机器上，几乎不需要额外的编程工作。
该算法还需要对数据进行线性（且相当少量）的遍历，并且需要相当少量的额外内存（假设每个 ID 与少量其他 ID 相关联）。

请注意，这会改变对的顺序（在某些情况下将第一个 id 放在第二个）
如果原始 id 的顺序很重要，您可以使用额外的字段轻松解决它。
另请注意，数据的顺序会改变，并且在使用 Map-Reduce 时无法克服它。

为了提高效率，您可能需要添加一个组合器，在本例中它将完成与减速器相同的工作，但它是否真的有帮助很大程度上取决于数据。

Hadoop是一个实现Map-Reduce的开源库，在社区中得到广泛应用。