3

次のように、Pythonでスペルチェックのような操作を実行する必要があります。

私は単語の膨大なリストを持っています（それをレキシコンと呼びましょう）。これでテキストが表示されます（サンプルと呼びましょう）。レキシコンで各サンプル単語を検索する必要があります。見つからない場合は、そのサンプル単語はエラーです。

つまり、ブルートフォースのスペルチェッカーです。ただし、各サンプル単語のレキシコンを直線的に検索するのは遅くなります。これを行うためのより良い方法は何ですか？

複雑な要因は、サンプルもレキシコンも英語ではないということです。これは、26文字ではなく、300文字を超えることができる言語であり、Unicodeに格納されています。

任意のアルゴリズム/データ構造/並列化方法の提案が役立ちます。100％の精度は必要ないので、100％未満の精度で高速なアルゴリズムが最適です。Norvigのこのアルゴリズムについては知っていますが、英語固有のようです。

4

8 に答える 8

6

Unicode文字列のセットを使用できます。

s = set(u"rabbit", u"lamb", u"calf")

演算子を使用してin、単語が出現するかどうかを確認します。

>>> u"rabbit" in s
True
>>> u"wolf" in s
False

このルックアップは基本的にO（1）であるため、辞書のサイズは重要ではありません。

編集:(大文字と小文字を区別する）スペルチェッカー（2.6以降）の完全なコードは次のとおりです。

from io import open
import re
with open("dictionary", encoding="utf-8") as f:
    words = set(line.strip() for line in f)
with open("document", encoding="utf-8") as f:
    for w in re.findall(r"\w+", f.read()):
        if w not in words:
            print "Misspelled:", w.encode("utf-8")

（print端末がUTF-8を使用していることを前提としています。）

于 2012-04-09T12:39:34.700 に答える
1

ツリー構造を使用して単語を格納し、ルートからリーフまでの各パスが1つの単語を表すようにします。トラバーサルがリーフに到達できない場合、または単語の終わりより前にリーフに到達する場合は、レキシコンに単語がありません。

Emilがコメントで言及している利点とは別に、これにより、別のスペルを見つけるためにバックトラッキングなどを行うことができることにも注意してください。

于 2012-04-09T12:46:06.050 に答える
1

ここでセットが配置されます。辞書にあるすべての単語のセットを作成し、メンバーシップ演算子を使用して、その単語が辞書にあるかどうかを確認します。

これは簡単な例です

>>> dictionary = {'Python','check-like', 'will', 'perform','follows:', 'spelling', 'operation'}
>>> for word in "I will have to perform a spelling check-like operation in Python as follows:".split():
    if word in dictionary:
        print "Found {0} in the dictionary".format(word)
    else:
        print "{0} not present in the dictionary".format(word)


I not present in the dictionary
Found will in the dictionary
have not present in the dictionary
to not present in the dictionary
Found perform in the dictionary
a not present in the dictionary
Found spelling in the dictionary
Found check-like in the dictionary
Found operation in the dictionary
in not present in the dictionary
Found Python in the dictionary
as not present in the dictionary
Found follows: in the dictionary
>>>
于 2012-04-09T12:39:56.143 に答える
1

みんなが言っているように、セットで試してみてください。セットルックアップは、経験豊富なプログラマーによってPythonのCコードで最適化されているため、小さなアプリケーションでこれ以上のことを行う方法はありません。

Unicodeは問題ではありません。セットキーと辞書キーはUnicodeまたは英語のテキストにすることができます。問題はありません。異なる次数の発音区別符号は等しく比較されないため、唯一の考慮事項はユニコードの正規化です。これがあなたの言語の問題である場合、私は最初にレキシコンが正規化された形式で保存されていることを確認し、次にそれをチェックする前に各単語を正規化します。例えば、unicodedata.normalize('NFC', word)

于 2012-04-09T12:49:25.830 に答える
0

Python辞書でのハッシュ検索の平均時間計算量はO（1）です。したがって、「値のない辞書」（別名セット）を使用できます。

于 2012-04-09T12:40:10.853 に答える
0

それがPythonの辞書とセットの目的です！:)各単語に何らかの値（頻度など）がある場合は辞書に辞書を保存するか、存在を確認する必要がある場合はセットを保存します。それらを検索するのはO（1）なので、非常に高速になります。

lex = set(('word1', 'word2', .....))

for w in words:
    if w not in lex:
        print "Error: %s" % w
于 2012-04-09T12:40:30.440 に答える
0

最初に、レキシコンのインデックスを作成する必要があります。たとえば、独自のインデックスシステムを作成することもできますが、より良い方法は全文検索エンジンを使用 することです。全文検索エンジン 私はあなたにapacheluceneまたはsphinxをお勧めします。高速でオープンソースです。Pythonから検索エンジンにsearcheクエリを送信し、応答をキャッチした後。

于 2012-04-09T13:14:24.547 に答える
0

これは私がそのようなことをチェックすることについて書いた投稿です。グーグルの提案/スペルチェッカーが機能するのと同じです。

http://blog.mattalcock.com/2012/12/5/python-spell-checker/

それが役に立てば幸い。

于 2013-01-26T18:00:47.450 に答える