2

私はここでこのような単語デスクランブラーをコーディングしようとしていますが、これを実装するためにどのアルゴリズムを使用すべきか疑問に思っていました。また、誰かがこれのための既存のコードを見つけることができれば、それも素晴らしいでしょう。基本的に、機能はボグルソルバーのようになりますが、マトリックスではなく、文字列からすべての単語の可能性を検索するだけです。私はすでに十分な辞書を持っています。

私はこれをPythonまたはRubyのいずれかで行うことを計画していました。よろしくお願いします！

4

5 に答える 5

3

Trieを使用します。Pythonでの実装は次のとおりです。http：//jtauber.com/2005/02/trie.py（James Tauberのクレジット）

于 2009-10-15T04:17:00.703 に答える
2

ゲームの理解が足りないかもしれませんが、「ジョーカー」（ワイルドカード）文字の導入、欠落または追加の文字、複数の単語など、ルールの複雑さを除けば...次のアイデアが役立つと思いますやや比較的興味のないことの問題。:-(

文字の順序による主なアイデアのインデックス ワード。
たとえば、「computer」は「cemoprtu」とキー付けされます。ランダムな描画が提供するものは何でも、種類ごとに並べ替えられ、一致する可能性のあるものを見つけるためのキーとして使用されます。perimosocordiae によって提案されたトライ構造を使用して、これらのソートされたキーと関連する単語/wordIds の基になるストレージとして、「リーフ」ノードで、単語の検索を O(n) 時間で実行できます。ここで、n は文字数です。 （または、存在しない単語のために平均してより良い）。

インデックス作成をさらに支援するために、文字数ごとに 1 つずつ、複数のテーブル/辞書を作成できます。また、統計によっては、母音と子音を別々に処理することもできます。もう 1 つのトリックは、最も選択的な文字を最初に配置して、カスタムの並べ替え順序を設定することです。

ゲームへの追加のひねり (文字のサブセットから作成された単語を見つけるなど) は、ほとんどの場合、これらの文字の累乗セットを反復し、 組み合わせごとに辞書をチェックすることです。

いくつかの組み合わせを削減するのに役立ついくつかのヒューリスティックを導入できます(たとえば、母音のない組み合わせ [および特定の長さ] は可能な解決策ではありません。ルックアップ コストが比較的小さいため、これらのヒューリスティックを慎重に管理する必要があります。

于 2009-10-15T05:08:19.377 に答える
2

ディクショナリ インデックスのマップを作成します (Map[Bag[Char], List[String]])。O(1) ワード ルックアップを取得できるように、ハッシュ マップにする必要があります。Bag[Char] は、文字順まで一意な単語の識別子です。これは基本的に、Char から Int へのハッシュ マップです。Char は単語内の特定の文字であり、Int はその文字が単語内に出現する回数です。

例：

{'a'=>3, 'n'=>1, 'g'=>1, 'r'=>1, 'm'=>1} => ["anagram"]
{'s'=>3, 't'=>1, 'r'=>1, 'e'=>2, 'd'=>1} => ["stressed", "desserts"]

単語を見つけるには、入力文字列からすべての文字の組み合わせを取得し、このマップで検索します。このアルゴリズムの複雑さは、入力文字列の長さが O(2^n) です。特に、複雑さは辞書の長さに依存しません。

于 2009-10-15T05:43:39.093 に答える
1

これは、Rabin-Karp 文字列検索が適しているように思えます。ローリング ハッシュ関数を使用する場合、各位置で 1 つのハッシュ値の更新と 1 つの辞書検索が必要です。また、すべての単語をセット内の最も短い単語に切り詰めたり、可能な一致を再チェックしたりするなど、さまざまな単語の長さに対処するための適切な方法を作成する必要もあります。単語セットを別々の長さの範囲に分割すると、ハッシング作業が増加しますが、偽陽性の量が減少します。

于 2009-10-15T11:58:10.903 に答える
1

これには 2 つの方法があります。1 つは、単語内の文字のすべての候補順列をチェックして、その候補が単語の辞書にあるかどうかを確認することです。単語の長さに応じて、これは O(N!) 操作です。

もう 1 つの方法は、辞書内のすべての候補単語をチェックして、その単語が単語内に含まれているかどうかを確認することです。これは、辞書を集約することで高速化できます。すべての候補単語の代わりに、相互のアナグラムであるすべての単語を一度にチェックします。それらのいずれかが単語に含まれている場合、それらはすべて含まれているためです。

したがって、キーがソートされた文字列であり、値がキーのアナグラムである単語のリストである辞書を作成することから始めます。

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> with open(r"c:\temp\words.txt", "r") as f:
        for line in f.readlines():
            if line[0].isupper(): continue
            word = line.strip()
            key = "".join(sorted(word.lower()))
            d[key].append(word)

次に、単語に候補が含まれているかどうかを確認する関数が必要です。この関数は、単語と候補の両方が並べ替えられていることを前提としているため、文字ごとに両方を調べて、一致しないことがわかったときにすぐにあきらめることができます。

>>> def contains(sorted_word, sorted_candidate):
        wchars = (c for c in sorted_word)
        for cc in sorted_candidate:
            while(True):
                try:
                    wc = wchars.next()
                except StopIteration:
                    return False
                if wc < cc: continue
                if wc == cc: break
                return False
        return True

次に、単語に含まれる辞書内のすべての候補キーを見つけ、それらのすべての値を 1 つのリストに集約します。

>>> w = sorted("mythopoetic")
>>> result = []
>>> for k in d.keys():
        if contains(w, k): result.extend(d[k])
>>> len(result)
429
>>> sorted(result)[:20]
['c', 'ce', 'cep', 'ceti', 'che', 'chetty', 'chi', 'chime', 'chip', 'chit', 'chitty', 'cho', 'chomp', 'choop', 'chop', 'chott', 'chyme', 'cipo', 'cit', 'cite']

この最後のステップは、私のラップトップでは約 4 分の 1 秒かかります。私の辞書には 195,000 個のキーがあります (BSD Unix の単語ファイルを使用しています)。

于 2009-10-15T20:52:16.610 に答える