status |
草稿 |
ZoomQuiet,xyb |
完成度~40% |
Contents
1. 文本处理实感
1.1. 读取google搜索信息
读取google搜索信息
互联网已经成为我们生活中必不可少的一部分，它提供的海量资料是我们在日常工作经常会接触和使用的。这里简单介绍有如何处理html格式数据。
1 import urllib2
2 from urllib import quote
3
4 def search(keyword):
5 request = urllib2.Request('http://www.google.com/custom?q=' + quote(keyword))
6 request.add_header('User-Agent', 'Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20061201 Firefox/2.0.0.6 (Ubuntu-feisty)')
7 opener = urllib2.build_opener()
8 html = opener.open(request).read()
9
10 html = html.replace('<div class=g', '\n<div class=g')
11 html = html.replace('</h2>', '</h2>\n')
12 results = [s for s in html.split('\n') if s.startswith('<div class=g')]
13 for s in results:
14 s = s[s.find('href="'):]
15 s = s.replace('href="', '')
16 link = s[:s.find('"')]
17 t = s[s.find('>')+1:]
18 t = t[:t.find('</a>')]
19 t = t.replace('<b>', '')
20 t = t.replace('</b>', '')
21 title = t[t.rfind('>')+1:]
22 yield link, title
程序首先从google上按照指定的关键字检索，并读取搜索结果，存入html变量。通过认真观察google的结果页面，可以找到一个规律，每个结果项都在一个class=g的div中；找到'<div class=g'，也就找到了一个搜索结果的起始位置。不过糟糕的是，所有搜索结果都挤在一行文本中，所以我们先找到'<div class=g'，在前面增加换行符，把它分成多行。每个搜索结果包括标题、链接，还有部分摘要。这个程序里，我们只取每个检索结果的标题和链接，所以在标题结束部分'</h2>'的后面，也增加一个换行符，把我们关心的这部分代码单独放到一行里。这时，每个检索结果就变成了这个样子：
<div class=g><link rel="prefetch" href="http://www.python.org/"><h2 class=r><a href="http://www.python.org/" target=_blank class=l onmousedown="return clk(0,'','','cres','1','')"><b>Python</b> Programming Language -- Official Website</a></h2>
准备好数据以后，按照换行符把html分割成字符串的列表，并且过滤出是以'<div class=g'开始的字符串，存入results列表。下面的处理就是我们不需要的字符去掉，并切分离出网址链接和标题。首先查找链接：s.find('href="')，并把它后面的字符串保留下来，然后就可以把网址分离出来，存入link变量。与此类似，我们可以得到标题部分的字符串。
if __name__ == '__main__':
import sys
for link, title in search(sys.argv[1]):
print link, title
程序的运行，传入的第一个参数作为检索的关键字。
大家看起来上面的代码，有没有觉得即繁琐，又不容易一眼看懂？也就是说，这种方法虽然简单，但可读性并不好。下面我介绍一种更简洁、同时也很易读懂的方法：使用正则表达式。
正则表达式是一种匹配及处理特定字符串的专门格式。如果用正则表达式来编写同样的功能，上面的函数就可以写成：
RE_LINK = r'<div class=g[^>]*>(?:<link [^>]*>)?<h2 class=r><a href="([^"]+)"[^>]*>(.+?)</a></h2>'
def search(keyword):
request = urllib2.Request('http://www.google.com/custom?q=' + quote(keyword))
request.add_header('User-Agent', 'Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20061201 Firefox/2.0.0.6 (Ubuntu-feisty)')
opener = urllib2.build_opener()
html = opener.open(request).read()
for link, title in re.findall(RE_LINK, html):
title = re.sub('</?b>', '', title)
yield link, title
RE_LINK是关键的正则表达式，它的含义为：
<div class=g[^>]*>：匹配以<div class=g开始，中间有零个或多个任意非'>'的字符，后跟一个>的字符串
(?:<link [^>]*>)?：匹配一组字符串：以'<link '开始，中间有零个或多个任意非'>'字符，后跟一个'>'字符。这组字符串可能出现一次或零次，其中问号后的冒号表示这个group表达式只匹配，但不计入group检索结果中。
<h2 class=r>：简单的匹配这个字符串
<a href="([^"]+)"[^>]*>(.+?)</a>：匹配以'<a href="'开始，中间是至少一个非双引号的字符（网址部分，group匹配），后面是零个或多个非'>'的字符；再后面是至少一个字符（标题部分，group匹配），最后是'</a></h2>'字符。(.+?)中的问号表示非贪婪匹配，也就是只要发现一个后面跟着'</a></h2>'的结果，就不再继续往下查找。
group匹配是我们从大量信息中挑出自己需要的数据的一种方法，也是用来组织复杂的、嵌套的正则表达式的有力工具。在这个正则表达式中，共出现三次group匹配，第一个(?:...)，是因为有多个表达式要绑定成一组，所以要用括号()把它们绑在一起之后，才能用后面带的问号?来修饰它，告知正则表达式处理引擎，它们或者一起出现一次，或者一起都不出现。由于这个匹配并不是我们需要的数据，不需要他出现在最终的结果中，所以我们用(?:...)类型，这样就可以把它从结果中忽略掉了。第二个和第三个(...)，是我们要命中匹配的链接地址和标题，这是两个普通类型的gorup匹配。
通过re.findall，就可以把文本中所有符合规则的信息一起全部提取出来。然后再稍作处理，用re.sub过滤掉标题中可能存在的'<b>'或者'</b>'，就得到最终的检索结果了。
1.1.1. search.py
1 #!/usr/bin/env python
2 # -*- coding: utf-8 -*-
3
4 import urllib2
5 from urllib import quote
6 import re
7
8 RE_LINK = r'<div class=g[^>]*>(?:<link [^>]*>)?<h2 class=r><a href="([^"]+)"[^>]*>(.+?)</a></h2>'
9
10 def search(keyword):
11 request = urllib2.Request('http://www.google.com/custom?q=' + quote(keyword))
12 request.add_header('User-Agent', 'Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20061201 Firefox/2.0.0.6 (Ubuntu-feisty)')
13 opener = urllib2.build_opener()
14 html = opener.open(request).read()
15
16 for link, title in re.findall(RE_LINK, html):
17 title = re.sub('</?b>', '', title)
18 yield link, title
19
20 def search2(keyword):
21 request = urllib2.Request('http://www.google.com/custom?q=' + quote(keyword))
22 request.add_header('User-Agent', 'Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20061201 Firefox/2.0.0.6 (Ubuntu-feisty)')
23 opener = urllib2.build_opener()
24 html = opener.open(request).read()
25
26 html = html.replace('<div class=g', '\n<div class=g')
27 html = html.replace('</h2>', '</h2>\n')
28 results = [s for s in html.split('\n') if s.startswith('<div class=g')]
29 for s in results:
30 s = s[s.find('href="'):]
31 s = s.replace('href="', '')
32 link = s[:s.find('"')]
33 t = s[s.find('>')+1:]
34 t = t[:t.find('</a>')]
35 t = t.replace('<b>', '')
36 t = t.replace('</b>', '')
37 title = t[t.rfind('>')+1:]
38 yield link, title
39
40 if __name__ == '__main__':
41 import sys
42 for link, title in search(sys.argv[1]):
43 print link, title
1.2. 从 whois 信息中提取网段信息
这段程序用于从 whois 信息中提取网段信息，并保存为 nc 格式的 tiny dns 配置文件。它可以针对来访者网段，为一个域名分配不同的ip。
我们先来看一段文本：
inetnum: 202.96.63.97 - 202.96.63.127 netname: CAIMARNET domain: 123.93.203.in-addr.arpa descr: Reverse zone for 203.93.123.0/24 domain: 140.4.221.in-addr.arpa descr: reverse delegation for 221.4.140/24 domain: 250.5.221.in-addr.arpa descr: China Network Communications Group Co. ChongQing
这是一段whois3程序生成的输出例子，其中保存的是中国网通使用的的部分IP网段信息。这里编写的这段程序将对他们进行处理，得到我们需要的结果。
whois3程序可以从
下载并编译生成。用
./whois3 -h whois.apnic.net -l -i mb MAINT-CNCGROUP > cnc.txt ./whois3 -h whois.apnic.net -l -i ml MAINT-CNCGROUP >> cnc.txt ./whois3 -h whois.apnic.net -l -i mu MAINT-CNCGROUP >> cnc.txt ./whois3 -h whois.apnic.net -l -i mb MAINT-CHINANET > chinanet.txt ./whois3 -h whois.apnic.net -l -i mb MAINT-CN-CRTC > crtc.txt
可以获得类似上面的结果文件。
_sample_whois = """ inetnum: 202.96.63.97 - 202.96.63.127 netname: CAIMARNET domain: 123.93.203.in-addr.arpa descr: Reverse zone for 203.93.123.0/24 domain: 140.4.221.in-addr.arpa descr: reverse delegation for 221.4.140/24 domain: 250.5.221.in-addr.arpa descr: China Network Communications Group Co. ChongQing """
从示例的数据中可以看出，数据的格式一共有4类，read_chunk从输入中分析出这四类格式，并读取相应的有用信息。 {{#!python def read_chunk(whois_file):
- """read one chunk from whois file once
>>> from StringIO import StringIO >>> list(read_chunk(StringIO(_sample_whois))) [('inetnum', ['202.96.63.97', '202.96.63.127']), ('descr', '203.93.123.0/24'), ('descr', '221.4.140/24'), ('domain', '250.5.221')] """ while True:
- line = whois_file.readline() if not line:
- break
- line = whois_file.readline() if line.startswith('inetnum:'):
- inetnum = line[len('inetnum:'):].strip()
inetnum = inetnum.replace(' ', ).split('-') yield ('inetnum', inetnum)
- domain = line[len('domain:'):].strip()
domain = domain.replace('.in-addr.arpa', ) line = whois_file.readline() if line.startswith('descr:'):
- descr = line[len('descr:'):].strip() segm = re.findall('[0-9.]+/[0-9]+', descr) if segm and len(segm) == 1:
- segm = segm[0] yield('descr', segm) continue
- descr = line[len('descr:'):].strip() segm = re.findall('[0-9.]+/[0-9]+', descr) if segm and len(segm) == 1:
- inetnum = line[len('inetnum:'):].strip()
- line = whois_file.readline() if not line:
}}} 用三个双引号括起来的，叫做doc，是python语言中函数等对象的特殊属性。其中，可以保存对该代码的描述等信息。关于doc的更多信息，请参考...。这段代码里，也包含doctest的测试代码，它看起来就像是我们在python中执行函数时的输入和输出，供 doctest 读取和验证函数的行为是否符合要求。随时编写测试代码是一个非常好的习惯，一旦养成，会终生受益。采用doctest书写的测试用例，在文件中添加如下语句，就可以作为一个单独的程序来执行：
if __name__ == '__main___':
import doctest
doctest.testmod()
如果文件的名字是 net_segm.py，则执行 python net_segm.py；如果没有看到任何输出，那么恭喜你，所有测试用例均已通过。作为UNIX哲学的一部分，像测试程序这样的一类程序的原则是：没有消息（输出）就是好消息。如果你想了解更多信息，可以输入：python net_segm.py -v，就可以看到每个测试用例执行的情况了。
这个函数首先以一个循环开始，从已经打开的文件中一行行读取数据，放到line变量中。从函数名可以知道，这个函数每次从文件中读取“一片”数据。只有一个换行符'\n'的空行就是标志，表示下面一个新的片断开始。根据四种数据格式的不同，程序判断逻辑为：
如果第一行以 'inetnum:' 开始：
（那么它是用两个ip标识一个网段）
把第一行的后面数据从'-'字符切开，返回 'inetnum' 和两个ip
如果第一行以 'domain:' 开始：
（那么是另外三种格式）
先把第一行中倒排的arp地址保存到domain变量中
读取第二行
如果第二行以'descr:'开始：
取 'descr:' 后面的数据中符合网段写法的部分
如果取得网段：
返回 'descr' 和网段
其他所有情况返回 'domain' 和 domain 变量内容
请对照以上伪代码描述阅读 read_chunk 函数。获取类似 '192.168.1/24' 的网段字符的代码，使用了正则表达式模块 re，关于这个模块的更详细介绍，请参考...。在该函数中，返回数据使用 yield 而不是 return，它使我们不须从函数退出即可返回数据给调用者，这个特性给我们的编程带来了极大的便利。包含yield的函数被称作生成器（generator），它是python在函数式编程方面引入的一个重要特性。这些名词看起来很深奥，但yield使用起来其实很简单：用yield返回数据，用for来遍历从函数返回的数据，这样立刻可以用起来了。关于yield的更多信息，请参考...。
下面是read_chunk的调用者network_segment函数，从中可以看到一行'for chunk in read_chunk(whois):'即可使用read_chunk读取信息，使用起来很是方便。
1 def network_segment(whois_file):
2 """read network segments from whois file
3
4 >>> from StringIO import StringIO
5 >>> list(network_segment(StringIO(_sample_whois)))
6 ['202.96.63.0/24', '203.93.123.0/24', '221.4.140.0/24', '221.5.250.0/24']
7 """
8 if isinstance(whois_file, str):
9 whois = file(whois_file)
10 else:
11 whois = whois_file
12 for chunk in read_chunk(whois):
13 name, segment = chunk
14 if name=='descr':
15 yield fix_segment(segment)
16 elif name=='domain':
17 inverted_network = segment
18 yield reverse_segment(inverted_network)
19 elif name=='inetnum':
20 ip1, ip2 = segment
21 yield max_mask24(get_network(ip1, ip2))
22 else:
23 yield chunk
这个函数根据每个片断的类型--变量"name"，分别使用不同的函数进行处理网段信息--变量segment，最后生成型如'202.96.63.0/24'这样我们需要的标准格式：后面的/24是这个网段的掩码的缩写方式，表示掩码中为1的比特共24位--这个例子是一个C类子网。函数开始部分是一段判断输入参数的代码，如果传入的参数是一个字符串，那么就把它作为一个文件名来打开；否则默认传入的是一个file类型的对象，从中读取每行数据。下面是不同类型数据的几个处理函数代码。
1 def fix_segment(segment):
2 """
3 >>> fix_segment('221.4.140/24')
4 '221.4.140.0/24'
5 >>> fix_segment('127/8')
6 '127.0.0.0/8'
7 """
8 list_segm = segment.split('/')[0].split('.')
9 if len(list_segm) < 4:
10 segment = "%s%s/%s" % (
11 segment.split('/')[0],
12 '.0' * (4-len(list_segm)),
13 segment.split('/')[1],
14 )
15 return segment
第一种格式，从descr中获得的信息，它的网段是缩写格式，例如： '221.4.140/24'。我们需要进行修复，扩展成 '221.4.140.0/24' 这样。首先，用split按照'/'字符把信息切开，前面的子网地址部分再用'.'字符切开；如果子网地址部分切开后少于4段，则说明这是个缩写格式，需要补全。把失掉的几段'.0'部分、缩写部分、'/'后的子网掩码部分统统合在一起，就可以得到完全格式的网段。
1 def reverse_segment(inverted_network):
2 """
3 >>> reverse_segment('250.5.221')
4 '221.5.250.0/24'
5 >>> reverse_segment('127')
6 '127.0.0.0/8'
7 """
8 segment = inverted_network.split('.')[::-1]
9 lr = len(segment)
10 segment = '.'.join(segment) + '.0'*(4-lr) + '/' + str(lr*8)
11 return segment
第二种格式，是arp的倒排的网段，例如：'250.5.221'。首先把地址用'.'字符切开，然后倒序排列。这里倒排是利用了列表类型的切片（slice）功能的第三个参数：如果该值为-1，则返回列表为倒序方式。这样修改并补全网段地址和子网掩码后，倒排格式就被修复为标准格式：'221.5.250.0/24'。
1 def get_network(ip1, ip2):
2 """
3 >>> get_network('218.106.0.0', '218.106.255.255')
4 '218.106.0.0/16'
5 >>> get_network('218.106.1.0', '218.106.1.255')
6 '218.106.1.0/24'
7 >>> get_network('219.158.32.0', '219.158.63.255')
8 '219.158.32.0/19'
9 >>> get_network('218.106.96.0', '218.106.99.255')
10 '218.106.96.0/22'
11 >>> get_network('218.106.208.0', '218.106.223.255')
12 '218.106.208.0/20'
13 >>> get_network('202.96.63.97', '202.96.63.127')
14 '202.96.63.96/28'
15 """
16
17 ip1 = [int(i) for i in ip1.split('.')]
18 ip2 = [int(i) for i in ip2.split('.')]
19
20 def same_bit_length(i1, i2):
21 return int(log((i2-i1+1), 2))
22
23 same = 0
24 for i1, i2 in zip(ip1, ip2):
25 if i1==i2:
26 same += 1
27 else:
28 break
29
30 same_bit = same_bit_length(ip1[same], ip2[same])
31 bit_mask_len = 2**same_bit
32 mask_len = 8*same+(8-same_bit)
33
34 ip = '.'.join([str(i) for i in ip1[:same]])
35 ip += '.' + str(ip1[same]/(bit_mask_len)*(bit_mask_len))
36 ip += '.0' * (4-same-1)
37 return ip + '/' + str(mask_len)
第三种格式，数据中只有该网段的起始和结束ip地址。这段转换代码稍微复杂一些，它的逻辑是以二进制方式比较两个ip数字，找到它们相同部分的最大比特长度，从而得到标准写法。首先，把每个ip地址都以'.'字符切分成四个整形数字；然后从前往后挨个比较对应的数字，把相同数字的个数存入变量same。用内嵌的函数same_bit_length来计算第一对不相等的两个数字中，相同部分的比特个数，存入same_bit变量。这样，通过这两个数字，就可以得到这个网段地址的子网掩码mask_len。在函数的最后，变量ip中保存网段地址，和子网掩码连接在一起就是我们需要的标准格式了。
1 def max_mask24(segment):
2 """
3 >>> max_mask24('202.96.63.96/28')
4 '202.96.63.0/24'
5 """
6 network, mask = segment.split('/')
7 if int(mask) > 24:
8 return '%s.0/24' % '.'.join(network.split('.')[:3])
9 else:
10 return segment
最后，我们希望网段最小的单位是C类。这个函数用来修正网段数据，如果不足一个C类的网段则补足。逻辑很简单，如果子网掩码小于24，则把网段第四部分置为零，并直接把掩码修改为24--也就是把它扩大到一个C类网段。
最后，下面的代码调用network_segment，从命令行输入的参数中读取一个文件，并把最终转换成的标准格式打印出来：
if __name__ == '__main__':
import sys
whois_filename = sys.argv[1]
for segm in network_segment(whois_filename):
print segm
1.2.1. netsegm.py
1 #!/usr/bin/env python
2 # -*- coding: utf-8 -*-
3
4 from math import log
5 import re
6 import sys
7
8 _sample_whois = """
9 inetnum: 202.96.63.97 - 202.96.63.127
10 netname: CAIMARNET
11
12 domain: 123.93.203.in-addr.arpa
13 descr: Reverse zone for 203.93.123.0/24
14
15 domain: 140.4.221.in-addr.arpa
16 descr: reverse delegation for 221.4.140/24
17
18 domain: 250.5.221.in-addr.arpa
19 descr: China Network Communications Group Co. ChongQing
20 """
21
22 def read_chunk(whois_file):
23 """read one chunk from whois file once
24
25 >>> from StringIO import StringIO
26 >>> list(read_chunk(StringIO(_sample_whois)))
27 [('inetnum', ['202.96.63.97', '202.96.63.127']), ('descr', '203.93.123.0/24'), ('descr', '221.4.140/24'), ('domain', '250.5.221')]
28 """
29 while True:
30 line = whois_file.readline()
31 if not line:
32 break
33 if line == '\n':
34 line = whois_file.readline()
35 if line.startswith('inetnum:'):
36 inetnum = line[len('inetnum:'):].strip()
37 inetnum = inetnum.replace(' ', '').split('-')
38 yield ('inetnum', inetnum)
39 elif line.startswith('domain:'):
40 domain = line[len('domain:'):].strip()
41 domain = domain.replace('.in-addr.arpa', '')
42 line = whois_file.readline()
43 if line.startswith('descr:'):
44 descr = line[len('descr:'):].strip()
45 segm = re.findall('[0-9.]+/[0-9]+', descr)
46 if segm and len(segm) == 1:
47 segm = segm[0]
48 yield('descr', segm)
49 continue
50 yield ('domain', domain)
51
52 def network_segment(whois_file):
53 """read network segments from whois file
54
55 >>> from StringIO import StringIO
56 >>> list(network_segment(StringIO(_sample_whois)))
57 ['202.96.63.0/24', '203.93.123.0/24', '221.4.140.0/24', '221.5.250.0/24']
58 """
59 if isinstance(whois_file, str):
60 whois = file(whois_file)
61 else:
62 whois = whois_file
63 for chunk in read_chunk(whois):
64 name, segment = chunk
65 if name=='descr':
66 yield fix_segment(segment)
67 elif name=='domain':
68 yield reverse_segment(segment)
69 elif name=='inetnum':
70 ip1, ip2 = segment
71 yield max_mask24(get_network(ip1, ip2))
72 else:
73 yield chunk
74
75 def fix_segment(segment):
76 """
77 >>> fix_segment('221.4.140/24')
78 '221.4.140.0/24'
79 >>> fix_segment('127/8')
80 '127.0.0.0/8'
81 """
82 list_segm = segment.split('/')[0].split('.')
83 if len(list_segm) < 4:
84 segment = "%s%s/%s" % (
85 segment.split('/')[0],
86 '.0' * (4-len(list_segm)),
87 segment.split('/')[1],
88 )
89 return segment
90
91 def reverse_segment(inverted_network):
92 """
93 >>> reverse_segment('250.5.221')
94 '221.5.250.0/24'
95 >>> reverse_segment('127')
96 '127.0.0.0/8'
97 """
98 segment = inverted_network.split('.')[::-1]
99 lr = len(segment)
100 segment = '.'.join(segment) + '.0'*(4-lr) + '/' + str(lr*8)
101 return segment
102
103 def get_network(ip1, ip2):
104 """
105 >>> get_network('218.106.0.0', '218.106.255.255')
106 '218.106.0.0/16'
107 >>> get_network('218.106.1.0', '218.106.1.255')
108 '218.106.1.0/24'
109 >>> get_network('219.158.32.0', '219.158.63.255')
110 '219.158.32.0/19'
111 >>> get_network('218.106.96.0', '218.106.99.255')
112 '218.106.96.0/22'
113 >>> get_network('218.106.208.0', '218.106.223.255')
114 '218.106.208.0/20'
115 >>> get_network('202.96.63.97', '202.96.63.127')
116 '202.96.63.96/28'
117 """
118
119 ip1 = [int(i) for i in ip1.split('.')]
120 ip2 = [int(i) for i in ip2.split('.')]
121
122 def same_bit_length(i1, i2):
123 return int(log((i2-i1+1), 2))
124
125 same = 0
126 for i1, i2 in zip(ip1, ip2):
127 if i1==i2:
128 same += 1
129 else:
130 break
131
132 same_bit = same_bit_length(ip1[same], ip2[same])
133 bit_mask_len = 2**same_bit
134 mask_len = 8*same+(8-same_bit)
135
136 ip = '.'.join([str(i) for i in ip1[:same]])
137 ip += '.' + str(ip1[same]/(bit_mask_len)*(bit_mask_len))
138 ip += '.0' * (4-same-1)
139 return ip + '/' + str(mask_len)
140
141 def max_mask24(segment):
142 """
143 >>> max_mask24('202.96.63.96/28')
144 '202.96.63.0/24'
145 """
146 network, mask = segment.split('/')
147 if int(mask) > 24:
148 return '%s.0/24' % '.'.join(network.split('.')[:3])
149 else:
150 return segment
151
152 def test():
153 import doctest
154 doctest.testmod()
155
156 if __name__ == '__main__':
157 import sys
158 if sys.argv[1] == 'test':
159 test()
160 sys.exit()
161 whois_filename = sys.argv[1]
162 for segm in network_segment(whois_filename):
163 print segm
1.3. 找出两个文件中不同部分
文件A和文件B是两组人名单，每行是一个人的名字。这里我们要完成一个任务，把在文件A中出现，但没有在文件B中的人都找出来。
首先读取文件内容：
>>> a = file('a.txt').readlines()
>>> b = file('b.txt').readlines()
>>> a
['a\n', 'b\n', 'd\n', 'f\n', 'g\n', 'h\n']
>>> b
['b\n', 'c\n', 'e\n', 'f\n']
然后是比较过程：
>>> for i in a:
... if i not in b:
... print i.rstrip('\n')
...
a
d
g
h
>>>
甚至连写程序都不用，我们就可以在python命令行里直接快速完成。file.readlines可以把文件中所有内容一次读取出来，放到内存中来处理。只有小文件才可以这样用，如果文件过大，内存就会被文件内容吃光，这样程序执行效率返回会下降。然后对文件a中的每一行内容，检查是否在文件b中存在，不存在就直接打印到屏幕上。
如果两个文件的数据量多起来的时候，用list的in操作来判断a里的一个名字在b里是否存在，效率就太差了；这时可以引进一个数据结构：集合(set)。读取文件内容的部分就变成了这样：
>>> a = set(file('a'))
>>> b = set(file('b'))
>>> a
set(['d\n', 'a\n', 'b\n', 'h\n', 'f\n', 'g\n'])
>>> b
set(['c\n', 'f\n', 'b\n', 'e\n'])
这样，比较的部分还是可以继续使用in操作符。读取文件的部分省略了readlines函数，set会自动从文件中读取所有数据。
数据多了，输出也可能会变得多起来，直接打印到屏幕已经不够用了，需要保存到文件中：
>>> f = file('output.txt', 'w')
>>> for i in a:
... if i not in b:
... print >>> f, i.rstrip('\n')
>>>
但是，当文件内容大到超出内存的大小时，上面的方法就无法使用了。这时怎么办呢？我们可以先排序，再比较。一旦两个文件被以相同的顺序排列好了，我们就可以“顺流而下”，逐行比较，而不用一次全部装载到内存来了。
1.3.1. 大文件排序
一般情况下，我们可以使用系统的sort命令对文件进行排序，但使用python排序文件也是很方便的：
>>> file('sorted.txt', 'w').writelines(sorted(file('filename.txt')))
这一行命令就可以按照升序对文件排序，并保存在一个新文件中。
但对于超大文件，受限于内存的大小，不论是系统提供的sort命令，还是上面使用的python函数，处理起来效率都非常差，甚至因为需要的内存超出系统内存大小无法完成任务。不过不用担心，我们还是有办法来解决的。通过化整为零，把大文件的排序降低难度为多个小文件的排序，然后通过合并算法就可把组合成一个完整的结果了。只要每个小文件足够放到内存中，再加上合并算法对内存的占用也很少，如此一来，大文件处理遇到的内存限制也就迎刃而解。
1 LINES = 10000
2 def split_sort(filename):
3 f = file(filename)
4 num = 0
5 while True:
6 lines = []
7 for i in range(LINES):
8 line = f.readline()
9 if not line:
10 break
11 lines.append(line)
12 if not lines:
13 break
14 lines.sort()
15 num += 1
16 file(filename + '.%d'%num, 'w').writelines(lines)
17 return num
这段代码把文件分割成多个排好序的小文件。返回值是文件的个数。首先打开文件，在while循环读取每行数据，直到再没有任何数据，退出循环。在循环中，每读取10000行，就把它们排序，并写入到一个新的文件中，文件名是原名后缀文件序号数字。
1 from heapq import heappop, heappush
2
3 def merge_sorted(filename, num):
4 lines = []
5 for i in range(num):
6 f = file(filename + '.%d'%(i+1))
7 line = f.readline()
8 if line:
9 heappush(lines, (line, f))
10 while lines:
11 line, f = heappop(lines)
12 yield line
13 line = f.readline()
14 if line:
15 heappush(lines, (line, f))
这段代码是把多个排好序的小文件合并成一个文件。首先，从每个文件中读取第一行，把数据和打开的文件一起存入列表lines。while循环把列表当成一个自动排序的队列，每次从里面取第一个元素（也是最小的一个元素），然后返回该值并从这个数据所在的文件中取下一个数据，重新放入队列中。这个过程保证了每次得到的都是当前几个文件中数据里最小的一个，当遍历完所有的已排序文件，这个函数返回的也就是所有数据按照顺序合后的结果。
这个过程使用到了一个特殊的模块：heapq。它是一个把列表当做特殊的队列使用，用heappush把新元素存入队列，用heappop从队列中取出第一个元素；通过这种方法操作，它就可以自动保持队列中的最小值始终排在队列的最前面，这样我们逐个取出的数据就可以保证是顺序排序的。实际上，把heappush的代码替换为：
lines.append((line, f)) lines.sort() 把heappop替换为： lines.pop(0)
也可以完成同样的功能，但列表排序的执行效率很一般，这在我们处理大数据量时会多花很多不必要的时间，所以我们采用heapq来优化代码、提高执行效率、节省运行时间。
if __name__ == '__main__':
import sys
num = split_sort(sys.argv[1])
output = file(sys.argv[2])
for line in merge_sorted(sys.argv[1], num):
outputu.write(line)
这段是把第一个参数的文件进行排序，并把结果保存到第二个参数的文件中。
上面的代码中还缺少一部分功能。看出来了吗？排序过程中生成了许多临时的小文件，但在程序里并没有及时删除。如果读者您有兴趣，不妨试试亲自修改一下这段程序，给它增加删除临时文件的功能。
1.3.2. 大文件比较
1 import sys
2
3 def notin(sorted_file_a, sorted_file_b):
4 r"""compare two file
5
6 >>> from StringIO import StringIO
7 >>>
8 >>> a = '\n'.join('abdfgh')
9 >>> b = '\n'.join('bcef')
10 >>> list(notin(StringIO(a), StringIO(b)))
11 ['a', 'd', 'g', 'h']
12 """
13 fa = sorted_file_a
14 fb = sorted_file_b
15 fa = isinstance(fa, str) and open(fa) or fa
16 fb = isinstance(fb, str) and open(fb) or fb
17
18 sa = fa.readline()
19 sb = fb.readline()
20 while True:
21 if not sa: break
22 if not sb: break
23 sa = sa.rstrip('\n')
24 sb = sb.rstrip('\n')
25
26 compare = cmp(sa, sb)
27 if (compare < 0):
28 # FILE A only
29 yield sa
30 sa = fa.readline()
31 elif (compare == 0):
32 # both
33 sa = fa.readline()
34 sb = fb.readline()
35 else:
36 # FILE B only
37 sb = fb.readline()
38
39 # print more FILEA
40 if sa:
41 yield sa.rstrip('\n')
42 for sa in fa:
43 yield sa
把大文件排好顺序以后，我们就可以按照顺序来逐行读取两个文件；这样，只需顺序读取一次，我们就可以找出A文件中哪些行在B文件中从来没有出现过。在函数的开头，打开两个文件，并读取第一行数据。在下面的while循环中，如果任何一个文件中没有更多数据了，就退出循环。然后用python自带的cmp函数比较两个文件中的当前数据。根据cmp的返回值，如果A的数据小于B的数据，则说明这行数据只在A中存在，它就是我们的目标，把它返回，并读取A中的下一个数据。如果A和B的数据相等，那么这个数据恰好在两个文件中都存在，那么跳过它们，并从A和B两个文件中读取下一个数据，用于下一轮比较。如果A的数据大于B，那么说明这个数据是只有B中存在的，则忽略它，并从B中读取下一个数据。经过这样的循环和比较，大部分的数据就被筛选了出来；但有可能当B中已经读完数据了，而A中还有多余的数据，那么我们就可以肯定，剩下的肯定全部都是A中所特有的，那么就需要把它们依次读取，全部返回。
if __name__ == '__main__':
notin(sys.argv[1], sys.argv[2])
1.3.3. notin.py
1 #!/usr/bin/env python
2 # -*- coding: GB2312 -*-
3
4 """Print the lines in FILEA and not in FILEB.
5
6 notin.py FILEA FILEB
7 FILEA and FILEB must be sorted
8 """
9
10 __revision__ = '1.0'
11
12 import sys
13
14 def notin(sorted_file_a, sorted_file_b):
15 r"""compare two file
16
17 >>> from StringIO import StringIO
18 >>>
19 >>> a = '\n'.join('abdfgh')
20 >>> b = '\n'.join('bcef')
21 >>> list(notin(StringIO(a), StringIO(b)))
22 ['a', 'd', 'g', 'h']
23 """
24 fa = sorted_file_a
25 fb = sorted_file_b
26 fa = isinstance(fa, str) and open(fa) or fa
27 fb = isinstance(fb, str) and open(fb) or fb
28
29 sa = fa.readline()
30 sb = fb.readline()
31 while True:
32 if not sa: break
33 if not sb: break
34 sa = sa.rstrip('\n')
35 sb = sb.rstrip('\n')
36
37 compare = cmp(sa, sb)
38 if (compare < 0):
39 # FILE A only
40 yield sa
41 sa = fa.readline()
42 elif (compare == 0):
43 # both
44 sa = fa.readline()
45 sb = fb.readline()
46 else:
47 # FILE B only
48 sb = fb.readline()
49
50 # print more FILEA
51 if sa:
52 yield sa.rstrip('\n')
53 for sa in fa:
54 yield sa
55
56 def test():
57 import doctest
58 doctest.testmod()
59
60 if __name__ == '__main__':
61 import sys
62 if sys.argv[1] == 'test':
63 test()
64 sys.exit()
65 for i in notin(sys.argv[1], sys.argv[2]):
66 print i
1.3.4. sortfile.py
1 #!/usr/bin/env python
2 # -*- coding: utf-8 -*-
3
4 from heapq import heappop, heappush
5 LINES = 2
6
7 def split_sort(filename):
8 f = file(filename)
9 num = 0
10 while True:
11 lines = []
12 for i in range(LINES):
13 line = f.readline()
14 if not line:
15 break
16 lines.append(line)
17 if not lines:
18 break
19 lines.sort()
20 num += 1
21 file(filename + '.%d'%num, 'w').writelines(lines)
22 return num
23
24 def merge_sorted(filename, num):
25 lines = []
26 for i in range(num):
27 f = file(filename + '.%d'%(i+1))
28 line = f.readline()
29 if line:
30 heappush(lines, (line, f))
31 while lines:
32 line, f = heappop(lines)
33 yield line
34 line = f.readline()
35 if line:
36 heappush(lines, (line, f))
37
38 if __name__ == '__main__':
39 import sys
40 num = split_sort(sys.argv[1])
41 for line in merge_sorted(sys.argv[1], num):
42 sys.stdout.write(line)
2. 小结
2.1. 练习
::-- ZoomQuiet [2007-09-01 04:13:30]