How to Write a Spelling Corrector in Python

最近忙著比賽的事項~ 所以有點久沒有來po文了~ XDD~

How to Write a Spelling Corrector．這是今天Lab所發出來的訊息~ 重點就在於「Spelling Corrector」拼字檢查器，就類似像Google所提供的功能~ 當我們拼字錯誤時，它能提供建議修正~ 詳細的演算法請參考上述網頁資源~

底下我加上一些小程式方便測試：

import re, collections

def words(text):
	return re.findall('[a-z]+', text.lower()) 

def train(features):
	model = collections.defaultdict(lambda: 1)

	for f in features:
		model[f] += 1

	return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'
def edits1(word):
	n = len(word)
	return set([word[0:i]+word[i+1:] for i in range(n)] +                     # deletion
	           [word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition
	           [word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration
	           [word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet])  # insertion

def known_edits2(word):    
	return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): 
	return set(w for w in words if w in NWORDS)

def correct(word):    
	candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
	return max(candidates, key=lambda w: NWORDS[w])

if __name__ == "__main__":
	running = True
	while running:
		str = raw_input('Please input a word: ')
		if str == 'q':
			running = False
		else:
			print correct(str)
	else:
		print 'Done'

執行結果：(按Q離開程式)

C:\>corrector.py
Please input a word: speling
spelling
Please input a word: korrecter
corrected
Please input a word: q
Done

執行效率似乎還蠻快的~ 有空再來深入看看~ 不過我想是沒空了...... XD

．原始檔下載(含索引檔)