algorithm - 具有融合拼写纠错算法的拼写检查器

Question

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

我需要的一些例子:
拼写检查器 -> 拼写检查器
拼写检查器 -> 拼写检查器
拼写检查器 -> 拼写检查器

Answer 1

我破解了 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

基本上您需要更改代码以便:

• 您在字母表中添加空格以自动探索单词中断。
• 您首先要检查构成一个短语的所有单词是否都在字典中以认为该短语有效，而不是直接检查字典成员(字典不包含短语)。
• 您需要一种方法来根据普通单词对短语进行评分。

后者是最棘手的，我对短语组合使用脑死亡独立性假设，即两个相邻单词的概率是它们各自概率的乘积(这里用对数概率空间中的总和)，并有一个小的惩罚。我敢肯定，在实践中，您会希望保留一些二元统计数据来很好地进行拆分。

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')