带拼写纠错算法的拼写检查器

最近我浏览了几种拼写检查算法，包括简单的算法（如Peter Norvig's）和更复杂的算法（如Brill and Moore's）。但是有一种错误，他们都不能处理。例如，如果我输入stackoverflow而不是stack overflow，这些拼写检查程序将无法更正错误类型（除非字词术语中的stack overflow）。存储所有的单词对是非常昂贵的（并且如果错误是3个单词之间没有空格，它将无济于事）。是否有一种算法可以纠正（尽管通常是错误类型）这种类型的错误？带拼写纠错算法的拼写检查器

的什么，我需要一些例子：
spel checker - >spell checker
spellchecker - >spell checker
spelcheker - >spell checker

来源

2012-02-13 StuffHappens

我篡改了Norvig的拼写修正器来做到这一点。我不得不作弊，并在Norvig的数据文件中加入'checker'这个词，因为它永远不会出现。没有这种欺骗，这个问题真的很难。

expertsexchange expert exchange 
spel checker spell checker 
spellchecker spell checker 
spelchecker she checker # can't win them all 
baseball base all # baseball isn't in the dictionary either :(
hewent he went

基本上你需要使更改代码：

您添加空间字母自动探索断字。
您首先检查构成短语的所有单词是否在字典中以考虑该短语有效，而不是直接字典成员资格（该字典不包含短语）。
你需要一种方式来对普通单词进行评分。

后者是最棘手的，我用词组组成的新空房禁地独立性假设，即两个相邻字的概率是他们个人的概率（这里用日志的概率空间和完成）的产品，用小罚款。我相信在实践中，你会想保留一些bigram统计数据来做好分裂。

import re, collections, math 

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

def train(features): 
    counts = collections.defaultdict(lambda: 1.0) 
    for f in features: 
    counts[f] += 1.0 
    tot = float(sum(counts.values())) 
    model = collections.defaultdict(lambda: math.log(.1/tot)) 
    for f in counts: 
    model[f] = math.log(counts[f]/tot) 
    return model 

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

alphabet = 'abcdefghijklmnopqrstuvwxyz ' 

def valid(w): 
    return all(s in NWORDS for s in w.split()) 

def score(w): 
    return sum(NWORDS[s] for s in w.split()) - w.count(' ') 

def edits1(word): 
    splits  = [(word[:i], word[i:]) for i in range(len(word) + 1)] 
    deletes = [a + b[1:] for a, b in splits if b] 
    transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1] 
    replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b] 
    inserts = [a + c + b  for a, b in splits for c in alphabet] 
    return set(deletes + transposes + replaces + inserts) 

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

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

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

def t(w): 
    print w, correct(w) 

t('expertsexchange') 
t('spel checker') 
t('spellchecker') 
t('spelchecker') 
t('baseball') 
t('hewent')

来源

2012-02-13 20:16:42

我有时会得到这样的建议时，拼写检查凯特，所以有一定是一种算法，可以纠正一些这样的错误。我确信一个人可以做得更好，但有一个想法是在可能的地方将候选人分开，并检查组件是否存在近似匹配。困难的部分是决定可能的地方。在我熟悉的语言中，字母组合很少出现在文字中。例如，据我所知，英文单词中罕见的组合dk或lh。其他组合通常出现在单词的开头（例如un,ch），所以这些也是分裂的好猜测。在这个例子中spelcheker，该lc组合是不是太普遍，ch是的话，公共启动，所以分割spel和cheker是总理候选人，然后任何像样的算法会发现spell和checker（但它或许能找到spiel，所以不要自动更正，只是给出建议）。

来源

2012-02-13 12:16:19

此问题与应用于德语或荷兰语的复合拆分问题非常相似，但也适用于嘈杂的英语数据。请参阅Monz & De Rijke了解一种非常简单的算法（我认为它可以作为有效状态转换器来实现）和Google进行“复合分裂”和“分解”。

来源

2012-02-13 20:57:53

带拼写纠错算法的拼写检查器

回答

相关问题