3

私は言葉を受け取り、手紙のいくつかが行方不明になっています。一致する可能性のあるすべての単語をこのパターンに戻す必要がありました。たとえば、私は__erf_ow返す必要があると受け取りましたoverflow

パターンを取得した場合は_a_、返す必要があります: cat bag... 長さが 3 で、2 番目の文字が a であるすべての単語

すべての単語の辞書が与えられた場合、それを保存する最良の方法は何ですか、または関連するすべての単語をすばやく見つけるために使用するアルゴリズムはどれですか?

編集：せいぜい実行時間を意味します。データを保存するのにどれだけの時間がかかるかは気にしませんが（終了している限り）、迅速に回答したいと思います。明らかな答えはハッシュ テーブルですが、このテーブルは大きすぎます。

4

4 に答える 4

1

「最高」は、持っているリソースによって異なります。

これが私がすることです：

  1. 単語の長さごとに個別の辞書を保存します。
  2. 検索では大文字と小文字が区別されないと思います。文字が単語内に出現する場合、ビット 0 ～ 25 が設定される 32 ビット値を単語ごとに格納しますa..z。単語を a に格納しますMap<Integer, List<String>>(キーは 32 ビット値、値はこのキーのすべての単語のリストです)

検索方法:

  1. 必要な長さの単語で辞書を取る
  2. パターンの 32 ビット値を作成します。

  3. のすべてのキーを反復しMap、キーがビット単位でパターンの 32 ビット値がパターンの 32 ビット値と等しいかどうかを確認します。そうでない場合、これは一致しません。このチェックに合格した場合、文字の順序が処理されないか、文字が複数発生するかどうかが処理されないため、一致しているとは言えません。ただし、チェックは非常に高速で、単語の各文字を確認する必要はありません。

  4. のリストを反復し、リスト内Mapの各単語の文字をパターンと比較して、パターンに実際に一致するものを確認します。

例: 3 文字の単語の辞書: the、cat、bag、nor、ega、atc、ron;

-> Hashvalues
     00000000000010000000000010010000   the
     00000000000010000000000000000101   cat, atc
     00000000000000000000000001000011   bag
     00000000000000100110000000000000   nor, ron
     00000000000000000000000001010001   age, ega

 Value for pattern _a_ is 00000000000000000000000000000001

Step 3 returns that the keys 
      00000000000010000000000000000101,  
      00000000000000000000000001000011 and 
      00000000000000000000000001010001 are candidates for matches.



Step 4 returns: 'cat' and 'bag'
于 2013-05-26T19:42:22.067 に答える
0

メモリ効率が非常に悪いことを気にしない場合は、単語のセットをハッシュ テーブルに格納できます。キーはパターンです (これは、データを取得するための最速のアルゴリズムの 1 つになるはずです)。

trees = {}


def init(filename):
    with open(filename) as f:
        for word in f:
            word = word.strip()
            s = trees.get((len(word),0,''), set())
            s.add(word)
            trees[(len(word),0,'')] = s
            for i,c in enumerate(word):
                s = trees.get((len(word),i,c), set())
                s.add(word)
                trees[(len(word),i,c)] = s


def words_for_pattern(pattern):
    pattern = pattern.lower()
    words = trees[(len(pattern),0,'')]
    for i, c in enumerate(pattern):
        if c in "abcddefghijklmnopqrstuvwxyz":
            words = words.intersection(trees[(len(pattern),i,c)])

    return words

if __name__ == '__main__':
    init('english-words.20')
    while (True):
        pattern = raw_input("Enter pattern: ")
        print words_for_pattern(pattern)


 Enter pattern: **ll*
>>> set(['balls', 'rolls', 'hills', 'cells', 'polls', 'jelly', 'bills', 'pills', 'jolly', 'halls', 'bells'])

treesキーが 3 タプルであるマップを次に示します。各(word-length, character index, character)キーの値は、長さがword-lengthおよびcharacterがそのcharacter index場所にあるすべての単語のセットです。さらに、特定の長さのすべての単語を含む特別なキーがあります。

パターンの単語を取得するとき、パターン内の空白以外の各文字の単語のセットを交差させます。

于 2013-05-26T20:38:23.773 に答える
0

レーベンシュタイン距離が役に立ちます。他にも文字列類似関数があります。制約があれば、独自の距離関数に取り組むことができます。また、トランスデューサは良い考えです。これは、このアイデアに取り組むための良いスタートです。繰り返しますが、これを自分の問題に合わせる作業を行う必要があります。

Dukeling が以下で述べているように、ランタイムを削減する必要がある場合は、ウェーブレット ツリーのようなコンパクトなデータ構造を使用してこれを実行し、ノードに対してアクセス/範囲/ランク クエリを実行できる可能性があります (サイズが log2 の場合が最適です)。アルファベットの）、しかし、繰り返しますが、あなたはそれをあなた自身の問題に合わせる必要があります.

于 2013-05-26T19:59:25.707 に答える
0

文字でソートする HashMap を使用すると、小さく見えますか?

 ArrayList<HashMap<Character, ArrayList<String>>> dictionary;

HashMap の最初の文字は、どの文字が単語の一部であるかを示す指標です。

最初の ArrayList はすべての単語を格納でき、リストのインデックスは、どの文字がどこに格納されているかを示すことができます。したがって、-a-: dictionary.get(2).get(a) で単語を取得できます。結果: 2 位のすべての単語。

2 番目の ArrayList には単語が格納されます。

于 2013-05-26T19:30:12.323 に答える