我想大家在日常中使用英文单词拼写的时候都有过出错的情况，通过这篇文章向各位展示一个简单的拼写检查程序的思路。
首先需要的是一个字典，因为程序并不知道哪些单词是正确的哪些是错误的，所以字典是必须的。可以直接使用一个txt文件即可，内容大致如下：
a abc apple bad cent dog egg food good ...
一般来说按照字母排序下来就行了。我们将这个文件命名为MyWords.txt。
首先将这个文件读入内存,再根据换行符分割存入list：
words = open("MyWords.txt").readlines()
words = map(lambda x: x.strip(), words)
可以试试能否找到单词：
>>> 'food' in words True
假如现在有一千个单词需要查找，可以使用一个循环来将上面的代码执行1000次。
可以想象，这样做效率是很低很低的。
所以我们不能使用这种数据形式，看下看来的代码：
hash = {}
for word in words : present = hash.has_key('food')
看名字就可以知道，这事哈希表。其中的哈希函数为字典中的所有字符串生成随机地址，这在很短的时间内就可以完成，因为我只用到了布尔值。
假如有一个百万级的bmp(位图)，我们给词典的每53751个单词来生成0到999999之间的 散列，我们可以将为徒的对应位置设为1，然后在检查词汇表中是否有某个单词，这时候只用生成它的哈希值就可以了，如果有值代表正确，不然就错误。
如果没有设置布尔值，那么这个单词显然不在我们的词典中。但是，一个拼写错误的单词可能仍然会产生一个哈希表，这个哈希表已经由字典中的一个(甚至更多)单词设置。但它可以最小化。
一种改进方法可能是将位图的大小增加一倍。然后只有大约1/40被设置，我们的误报率会下降一半。当然，我们的哈希函数需要扩展新的大小。
使用不同的哈希函数创建第二个位图。一个折衷方法是只使用一个位图，但仍然要从两个独立的哈希函数中设置位。然后将设置大约10位中的1位，错误率约为1/100(10*10)。还是比1/40好。
理论看完了，下面开始实现,首先新建一个名为Bmap的类：
class Bmap : def _position(self, which) : whichBit = which % self.nBits self.whichWord = whichBit / self.wLength self.mask = self.masks[whichBit % self.wLength] def getBit(self, which) : self._position(which) return (self.map[self.whichWord] & self.mask) != 0 def setBit(self, which) : self._position(which) mask = self.mask if not self.map[self.whichWord] & mask : self.nSet += 1 self.map[self.whichWord] |= mask def __init__(self, nBits, wLength=16) : self.nBits = nBits self.wLength = wLength self.masks = [] self.nSet = 0 self.sWords = (nBits+self.wLength-1)/self.wLength bit = 1 for i in range(self.wLength) : self.masks.append(bit) bit <<= 1 self.map = [0]*self.sWords
模拟位图是一个整数列表，每个都有16位。4个整数给出了64位的位图。我们可以这样设置位：
import bmap b = bmap.Bmap(64) b.setBit(0) b.map >>>[1, 0, 0, 0] b.setBit(1) b.map >>>[3, 0, 0, 0] b.setBit(63) b.map >>>[3, 0, 0, 32768] b.getBit(63) >>>True b.getBit(62) >>>False
我们已经相当仔细地研究了可能的哈希函数，以确保每个哈希函数都能在位图中给出均匀的结果，并且这些函数相互独立。接下来给大家看下使用hashlib模块的md5函数从任何输入字符串生成一个32位hexidecimal：
import hashlib
hashlib.md5('good').hexdigest()
最后将前面的方法综合起来，首先使用首先所有的单词创建和填充位图。然后从MyWords.txt中读取文本。文本首先是标点符号的去除，并设置为小写。然后检查每个单词的拼写，并将结果输出。
from bmap import Bmap
from hashlib import md5
def main() :
import sys, re
bmap = loadBmap(sys.argv[1])
text = sys.stdin.read()
words = re.sub("[^a-zA-Z'-]"," ",text).lower().split()
for word in words :
print " %-6s %s" % (checkWord(bmap,word),word)
if __name__ == "__main__" : main()
def makeHash(word) :
hex32 = md5(word).hexdigest()
hashes = []
for i in range(0,30,5) :
hashes.append(int(hex32[i:i+5],16))
return hashes
def loadBmap(file) :
words = open(file).readlines()
words = map(lambda x: x.strip(), words)
bmap = Bitmap(2**20)
for word in words :
hashes = makeHash(word)
for hash in hashes :
bmap.setBit(hash)
return bmap
def checkWord(bmap, word) :
hashes = makeHash(word)
for hash in hashes :
if not bmap.getBit(hash): return False
return True
在最初的方法中，使用了4个哈希函数。相比之前的两秒钟的停顿，用字典填充位图大约是一分钟，这不会慢一千倍。
如果各位还有问题，欢迎留下评论交流！
版权所属，如需转载，请注明出处：搜闲鱼