我想大家在日常中使用英文单词拼写的时候都有过出错的情况,通过这篇文章向各位展示一个简单的拼写检查程序的思路。
首先需要的是一个字典,因为程序并不知道哪些单词是正确的哪些是错误的,所以字典是必须的。可以直接使用一个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个哈希函数。相比之前的两秒钟的停顿,用字典填充位图大约是一分钟,这不会慢一千倍。
如果各位还有问题,欢迎留下评论交流!
版权所属,如需转载,请注明出处:搜闲鱼