使用python制作单词拼写检查程序

我想大家在日常中使用英文单词拼写的时候都有过出错的情况,通过这篇文章向各位展示一个简单的拼写检查程序的思路。

首先需要的是一个字典,因为程序并不知道哪些单词是正确的哪些是错误的,所以字典是必须的。可以直接使用一个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个哈希函数。相比之前的两秒钟的停顿,用字典填充位图大约是一分钟,这不会慢一千倍。
如果各位还有问题,欢迎留下评论交流!

版权所属,如需转载,请注明出处:搜闲鱼

1,294 次浏览

发表评论

电子邮件地址不会被公开。 必填项已用*标注