How to Write a Spelling Corrector in Python

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
			print correct(str)
		print 'Done'


Please input a word: speling
Please input a word: korrecter
Please input a word: q

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


2008-07-22 01:00:34

2 comments on "How to Write a Spelling Corrector in Python"

  1. 1. Sophie 說:

    I'm a PhD student of reading education who is trying to establish a spelling error coding system (in English). I don't have any background knowledge about Python. Would u have time to explain a little to me?
    Is there any literature or logic behind mention about the reason why using splits, deletes, transposes, replaces, and inserts to categorize the errors made by human?
    Thanks a lot!


    2011-05-10 04:28:50

  2. 2. Shen 說:

    Dear Sophie,
    I think you have to dive into the edit distance algorithm, or refer to the Levenshtein Distance website(, it's helpful for you.

    2011-05-10 09:12:52

Leave a Comment

Copyright (C) Ching-Shen Chen. All rights reserved.

::: 搜尋 :::

::: 分類 :::

::: Ads :::

::: 最新文章 :::

::: 最新回應 :::

::: 訂閱 :::

Atom feed
Atom Comment