77

string "Hello"とリストがあるとしましょう

words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo','question', 'Hallo', 'format']

n wordsリストに最も近く"Hello"、リストに存在するものを見つけるにはどうすればよいwordsですか？

この場合、['hello', 'hallo', 'Hallo', 'hi', 'format'...]

したがって、戦略は、リストの単語を最も近い単語から最も遠い単語に並べ替えることです。

こんなことを考えました

word = 'Hello'
for i, item in enumerate(words):
    if lower(item) > lower(word):
      ...

しかし、大きなリストでは非常に遅くなります。

UPDATE difflibは機能しますが、非常に遅いです。（words list内部に630000以上の単語があります（ソートされ、1行に1つ））。したがって、リストを確認するには、最も近い単語を検索するたびに5〜7秒かかります。

4

5 に答える 5

132

を使用しdifflib.get_close_matchesます。

>>> words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format']
>>> difflib.get_close_matches('Hello', words)
['hello', 'Hallo', 'hallo']

この関数はデフォルトで3つ以下の最も近い一致を返すため、ドキュメントを参照してください。

于 2012-04-04T20:27:09.537 に答える
29

Peter Norvigがスペル修正について提供した完全なソースコード（21行）を含む素晴らしい記事があります。

http://norvig.com/spell-correct.html

アイデアはあなたの言葉のすべての可能な編集を構築することです、

hello - helo   - deletes    
hello - helol  - transpose    
hello - hallo  - replaces    
hello - heallo - inserts    


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)

次に、リストでこれらの各編集を検索します。

ピーターの記事は素晴らしい読み物であり、読む価値があります。

于 2012-04-04T22:34:31.710 に答える
1

単語の並べ替えリストを作成し、bisectモジュールを使用して、並べ替え順序に従って単語が収まる並べ替えリスト内のポイントを特定します。その位置に基づいて、上下にk最近傍を与えて、2k最近傍の単語を見つけることができます。

于 2012-04-04T20:34:40.797 に答える
1

私は、リストまたは可能な代替案から最も近い一致を取得するためにこの答えを見ていました

difflib.get_close_matches

Peter Norwigの投稿に基づいてAmjithの答えを見つけ、それが良い代替品になるかもしれないと思いました。それが私のユースケースにはあまり適していないかもしれないことに気付く前に、私はそれからクラスを作りました。つまり、これはさまざまな単語のセットに使用できるバージョンのスペルです。おそらく、母集団の名前の照合に最適に使用できます。

import re
from collections import Counter

def words(text): return re.findall(r'\w+', text.lower())

# WORDS = Counter(words(open('big.txt').read()))


class WordMatcher:

    def __init__(self, big_text):
        self.WORDS=Counter(words(big_text))
        self.N = sum(self.WORDS.values())

    def P(self, word):
        "Probability of `word`."
        return self.WORDS[word] / self.N

    def correction(self, word):
        "Most probable spelling correction for word."
        return max(self.candidates(word), key=self.P)

    def candidates(self, word):
        "Generate possible spelling corrections for word."
        return (self.known([word]) or self.known(self.edits1(word)) or self.known(self.edits2(word)) or [word])

    def known(self, words):
        "The subset of `words` that appear in the dictionary of WORDS."
        return set(w for w in words if w in self.WORDS)

    def edits1(self, word):
        "All edits that are one edit away from `word`."
        letters    = 'abcdefghijklmnopqrstuvwxyz'
        splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
        deletes    = [L + R[1:]               for L, R in splits if R]
        transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
        replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
        inserts    = [L + c + R               for L, R in splits for c in letters]
        return set(deletes + transposes + replaces + inserts)

    def edits2(self, word):
        "All edits that are two edits away from `word`."
        return (e2 for e1 in self.edits1(word) for e2 in self.edits1(e1))
于 2020-09-18T20:27:53.317 に答える
-3

多分ヒープはあなたを助けることができます。

Heapサイズが、未満になるまで、 using関数nに単語を挿入するという名前のヒープがあります[この文字列が別の文字列よりも近いかどうかを示します]。Heapclose

nこの方法は小さいときに役立ちます:)

Heap = []
for word in words:
    if len(Heap)<n:
       Heap.insert(word)
    else
       if close(word,Heap[0]): # it means Heap[0] is the nth farthest word until now
             Heap.pop():
             Heap.insert(word)
于 2012-04-05T08:38:12.660 に答える