特殊格式的大文本文件处理

lifeistrue

有一个大文本文件log，格式如下：
IP:1.1.1.1
DNS:2.2.2.2
PAGE:http://a.com/q?pl=xxx
{
........
不同内容，行数不定，各个记录互不相同
........
}
IP:1.1.1.1
DNS:2.2.2.2
PAGE:http://ab.com/q?pl=xxx
{
........
不同内容，行数不定，各个记录互不相同
........
}
对此，我们称从IP到}截止为一个记录，该文件有多个这样的记录组成（可能达到百万级），其中xxx为数字。
现在需要将所有形如PAGE：http://a.com/q?pl=XXX且xxx出现重复(2次或者多次)的记录提取出来（例如，PAGE:http://a.com/q?pl=123这样的记录出现了2次，则将这两条记录提取出来）。如何高效的完成？

琢磨了一天也没有得到结果，将自己的做的描述一下，当作抛砖。
grep 'PAGE:http://a.com/q?pl=' log>tmp#此步得到所有形如PAGE:http://a.com/q?pl=xxx的url
uniq -D tmp>tmp2#此步得到所有xxx出现重复的url（大概有2K个左右）
设置$/="}"，然后一个记录一个记录的去匹配出现重复的url。但是这样实在是太慢了，每个url要扫描整个文件，2K个就要扫描2K次。。。。

求助各位大虾，如何高效的完成该工作？谢谢啦！

[ 本帖最后由 lifeistrue 于 2009-2-5 01:36 编辑 ]

Lonki

估算了下, 一条记录50字节, 百万级别的记录, 此文件可能高达50G?

你都得到了重复的url的话, 就算一个一个匹配用琢磨一天的时间应该运行完了吧(一条估个很坏情况10秒不得了了, 2K也就5个小时), 脚本就是这样用的嘛:>

PS: 在大文件中去除那些非重复的url, 但是估计在几十K个...
分段读入内存处理不知道会不会好点.

要不然就用C写, 也不复杂的.

ynchnluiti

用PAGE:http:......做hash的键。
新读入的记录，即键不存在的记录可能需要先保存起来。

[ 本帖最后由 ynchnluiti 于 2009-2-5 01:42 编辑 ]

MMMIX

也可以把 log 导到数据库中，然后查询。

记得以前就有人这么搞过。

wxlfh

1. open FH,"<","log.txt" or die "Cannot open the file: log.txt\n";
   
2. 
   
3. # 把形如 PAGE:[url]http://ab.com/q?pl=xxx[/url] 的行，作为散列 %url 的键
   
4. while (<FH>) {
   
5.         if (m!(PAGE:http://[a-zA-Z]+\.com/q\?pl=\d{3})!) {
   
6.                 if (exists $url{$1}) {
   
7.                         $url{$1}->{'time'} = 2;
   
8.                 }else{
   
9.                         $url{$1}->{'time'} = 0;
   
10.                 }
    
11.         }
    
12. }
    
13. close FH;
    
14. 
    
15. # 剔除不重复的键
    
16. while (($key,$value) = each %url) {
    
17.         delete $url{$key} unless ${$value}{'time'};
    
18.         $url{$key}->{'list'} = [];
    
19. }
    
20. 
    
21. open FH,"<","log.txt" or die "Cannot open the file: log.txt\n";
    
22. 
    
23. $/ = '}';
    
24. 
    
25. # 把重复的记录加进散列
    
26. while (<FH>) {
    
27.         if (m!(PAGE:http://[a-zA-Z]+\.com/q\?pl=\d{3})!) {
    
28.                 if (exists $url{$1}) {
    
29.                         push @{$url{$1}->{'list'}},$_;
    
30.                 }
    
31.         }
    
32. }
    
33. close FH;
    
34. 
    
35. # 好了，现在重复的记录都在数组 @{$url{$key}->{'list'}} 中了，你爱怎么处理就怎么处理了

复制代码

我这个方法的优点是扫描文件2次（我的能力到此为止了），缺点是散列 %url 刚开始时会非常大。

[ 本帖最后由 wxlfh 于 2009-2-5 13:08 编辑 ]

ynchnluiti

原帖由 MMMIX 于 2009-2-5 09:49 发表
也可以把 log 导到数据库中，然后查询。

记得以前就有人这么搞过。

嗯。这样方法也不错

ynchnluiti

原帖由 wxlfh 于 2009-2-5 09:56 发表
我这个方法的优点是扫描文件2次（我的能力到此为止了），缺点是散列 %url 刚开始时会非常大。

如果重复的记录不多的话，hash是会很大

wxlfh

原帖由 ynchnluiti 于 2009-2-5 10:00 发表

如果重复的记录不多的话，hash是会很大

是啊，不知道计算机的虚拟内存吃不吃得消？

MMMIX

原帖由 wxlfh 于 2009-2-5 09:56 发表
我这个方法的优点是扫描文件2次（我的能力到此为止了），缺点是散列 %url 刚开始时会非常大。

扫描文件两次应该是缺点，咋还成优点了？优点应该是比起直接保存记录，这种先找重复记录的方法消耗内存较少，但缺点是需要扫描文件两次。

wxlfh

原帖由 MMMIX 于 2009-2-5 10:08 发表

扫描文件两次应该是缺点，咋还成优点了？优点应该是比起直接保存记录，这种先找重复记录的方法消耗内存较少，但缺点是需要扫描文件两次。

我的意思是比起楼主扫描文件n次，我少一点。汗......