具有融合拼写错误纠正算法的拼写检查器

Question

最近，我研究了几种拼写检查算法，包括简单的算法（例如 Peter Norvig 的）等等复杂的（如布里尔和摩尔的）。但有一类错误是它们都无法处理的。例如，如果我输入 stackoverflow 而不是 stackoverflow，这些拼写检查程序将无法纠正错误类型（除非术语词典中的 stackoverflow） 。存储所有单词对的成本太高（如果错误是 3 个单词之间没有空格，这将无济于事）。 是否有一种算法可以纠正（尽管通常会出现错误）此类错误？

我需要的一些示例：
拼写检查器 -> 拼写检查器
拼写检查器 -> 拼写检查器
spelcheker -> 拼写检查器

Answer 1

我有时在 kate 中进行拼写检查时会得到这样的建议，所以肯定有一种算法可以纠正一些此类错误。我确信可以做得更好，但一个想法是将候选者拆分到可能的位置，并检查组件是否存在紧密匹配。困难的部分是确定可能的位置。在我熟悉的语言中，有些字母组合在单词中很少出现。例如，据我所知，组合 dk 或 lh 在英语单词中很少见。其他组合通常出现在单词的开头（例如 un、ch），因此这些组合也是分割的好猜测。在 spelcheker 示例中，lc 组合并不太普遍，而 ch 是常见的单词开头，因此拆分 spel 和 cheker 是主要候选者，任何像样的算法都会找到 spell 和 checker （但它也可能会找到 < code>spiel，所以不要自动更正，只是提出建议）。

Answer 2

我破解了 Norvig 的拼写校正器来做到这一点。我不得不作一些作弊，将“检查器”一词添加到 Norvig 的数据文件中，因为它从未出现。如果没有这种作弊，这个问题真的很难。

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

Answer 3

这个问题与应用于德语或荷兰语的复合分裂问题非常相似，但也与嘈杂的英语数据有关。请参阅Monz 和De Rijke 提出了一个非常简单的算法（我认为可以将其实现为有限状态转换器以提高效率），而 Google 则提出“复合分裂”和“分解”。