21 行の Python コードでスペルチェッカーを実装する方法

紹介

Google または Baidu で検索するとき、Google は検索コンテンツを入力するときに常に優れたスペルチェックを提供します。たとえば、スペルと入力すると、Google はすぐに スペル を返します。
以下は、21 行の Python コードで実装された、シンプルだが完全に機能するスペル チェッカーです。

Code

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):
   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 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=NWORDS.get)

correct 関数はプログラムのエントリ ポイントであり、渡されたスペルが間違っている単語は正しく返されます。例:

>>> correct("cpoy")
'copy'
>>> correct("engilsh")
'english'
>>> correct("sruprise")
'surprise'

このコードに加えて、機械学習の一環として必ず大量のサンプル データが必要になります。サンプル データとして big.txt が用意されています。

背後にある原理

上記のコードはベイジアンに基づいて実装されています。実際、Google Baidu によって実装されているスペル チェックもベイジアンによって実装されていますが、これよりも明らかに複雑です。
まず、その背後にある原理を簡単に紹介します。すでに理解している読者は、このセクションを読み飛ばしていただいても構いません。
単語が与えられると、最も正しいスペル候補を選択しようとします (入力された単語が候補になる場合もあります)。場合によっては、それが不明確である場合 (たとえば、遅刻を遅刻または遅刻に修正する必要があるか)、どちらを提案として使用するかを確率を使用して決定します。元の単語 w に関連するすべての可能な正しいスペルから最も可能性の高いスペル候補 c を見つけます:

argmaxc  P(c|w)

ベイズの定理により、上記の式は

argmaxc P(w|c) P(c) / P(w)

に変換できます。 以下は、上の式の意味を紹介します:

1. P(c|w) は、単語 w を入力するときに、もともと単語 c を入力したかった確率を表します。

2. P(w|c) は、ユーザーが単語 c を入力したいのに w を入力する確率を表します。これは所与であると考えることができます。

3. P(c) は単語 c がサンプルデータに出現する確率を表します

4. P(w) は単語 w がサンプル番号に出現する確率を表します
   P(w) はすべての可能な単語に対して決定できますc 確率 これらはすべて同じなので、上記の式は次のように変換できます

argmaxc P(w|c) P(c)

すべてのコードはこの式に基づいています

コード分析

words() 関数を使用して抽出します。 big.txt の単語

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

re.findall('[a-z]+' という単語は、Python 正規表現モジュールを使用して、'[a-z]+' 条件を満たすすべての単語、つまり文字で構成される単語を抽出します。 (正規表現についてはここでは詳しく紹介しません。式については、興味のある学生は正規表現の紹介を参照してください。 text. lower() はテキストを小文字に変換します。つまり、「the」と「The」は同じ単語として定義されます

train() 関数を使用して、各単語の出現回数を計算し、NWORDS[w] がサンプル内に単語 w が出現する回数を表すように、適切なモデル

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model
NWORDS = train(words(file('big.txt').read()))

をトレーニングします。このメソッドはデフォルトで時間を 1 に設定するもので、コレクション モジュールとラムダ式によって実装されます。 collections.defaultdict() はデフォルトの辞書を作成し、lambda: 1 はこの辞書の各値をデフォルトでは 1 (ラムダ式については、ラムダの概要を参照してください

式

の P(c) を処理したので、次は P(w|c)、つまり単語を入力する確率を処理します。 「編集距離」を介して単語 c を入力しようとしたとき、w が間違っている -- ある単語を別の単語に変更するのに必要な編集の数によって測定されます。編集には、削除、交換 (隣接する 2 つの文字)、挿入、および 1 つの単語が含まれます。次の関数は、c を返します。一度編集することで取得できるすべての単語 w のセットです。 argmaxc P(w|c) P(c)

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)

関連する論文によると、スペルミスの 80 ～ 95% は、スペルしたい単語からわずか 1 つの編集距離にあります。 1 回の編集では不十分だと感じたら、もう一度編集しましょう

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

同時に、編集距離が 0 回で正しく綴られているものもある可能性があります:

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

編集の確率は次のように仮定します。 1 回の距離は 2 回よりもはるかに大きく、0 回の確率は 1 回よりもはるかに大きくなります。まず、編集距離が最小の単語を選択します。それに対応する P(w|c) は次のようになります。候補単語としてより大きいものを選択し、スペル候補として最大の P(c) を持つ単語を選択します

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

以上が21 行の Python コードでスペルチェッカーを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。