5

約 250.000 語の辞書があるとしましょう。アルゴリズムは 12 文字を配列または文字列として取り込み、辞書から最も長い単語に一致するバリエーションを見つける必要があります。

もちろん、いつでも総当たり攻撃を行うことができますが、これを行う最もエレガントな方法は何でしょうか?

主な問題のショートカットとして言語固有の関数を使用していない場合は、PHP 以外の言語を使用した回答も受け入れられます。

注: 単語はデータベースに保存されますが、高速化のためにメモリにプルすることができます。PHPのインデックス作成がMySQLデータベースのインデックス作成よりも優れているかどうかはわかりませんが?

4

5 に答える 5

4

すべての単語の署名を計算する必要があります。一度だけ実行し、単語とともにデータベースに保存します。

テーブルは次のようになります。

   word varchar(12), 
   a int,
   b int, 
   c int,
    ...
   w int,
   z int;

a から z までのフィールドには、単語に含まれる文字の数が含まれている必要があります。たとえば、アナグラムには次のようなレコードがあります。

word,    a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
anagram, 3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0

12 文字を取得したら、セットの署名を計算し、それを使用して次のような選択を作成する必要があります。

select word, length(word) as wordlen
from dictionary
where
a <= 4 and
b <= 0 and
c <= 1 and
d <= 2 and
e <= 0 and
f <= 0 and
 ....
z <= 0
order by wordlen desc;

あなたが持っている文字セットを使用して作成できるすべての単語を持つために。

順列も組み合わせもなしで、作業 (辞書のコンパイル) はオフラインで 1 回だけ実行されます。

もう 1 つのヒントとして、データベースから 12 文字を超えるすべての単語を取り除きます。

于 2009-09-28T12:37:14.360 に答える
3

ここでアナグラムの質問への回答を少し修正したバージョンを使用します

辞書の単語ごとに、文字をアルファベット順に並べ替えます。したがって、「foobar」は「abfoo」になります。

アルファベット順にソートされた完全な入力から始めます。見つからない場合は、1 文字削除して、もう一度検索してください。すべての文字に対してこれを行います。次に、2文字を削除します...など。

最悪の場合: 「アナグラム」がまったく見つかりません。可能なすべての入力の組み合わせをテストする必要があります。これにより、約 2^n 回のルックアップが得られます。n は入力文字数です (例では 12)。ただし、アルゴリズムの速度は辞書のサイズに依存しません。実行時に（もちろん、単語をアルファベット順にソートします）、これが私の意見ではここで最も重要なことです。

于 2009-09-28T12:17:25.263 に答える
1

Eric Lippert は、アナグラム検索に関する有益なブログ投稿を書いています。例はすべて c# を使用していますが、手法はどの言語でも使用できます。

辞書でアナグラムを効率的に検索する秘訣は、すべてのアナグラムが同じ文字であり、順序が異なるだけであることを理解することです。文字が大文字でアルファベット順になるように各単語を「正規化」すると、ある単語が別の単語のアナグラムであるかどうかを確認することは、それらの正規形を比較するのと同じくらい簡単です

この手法を使用すると、ハッシュ テーブルまたはバランス ツリーから簡単にアナグラムを検索できます。

于 2009-09-29T15:16:11.017 に答える
0

最長の一致する単語を見つけようとしている場合は、単語の長さで辞書を並べ替えることから始めます。これにより、最長の単語に最大限の努力を集中させることができます。

于 2009-09-28T10:22:13.467 に答える
-1

私の考え:

疑似コード:

int_32 letter_mask
int_32 permutation_match_mask
if(((letter_mask XOR permutation_match_mask) AND letter_mask)  == 0)
        YOU_HAVE_HIT;

これは、レターマスクに繰り返しのない文字がある場合に機能しますが、（おそらく持っているように）より多くの文字がある場合は、letter と permutationmatchmask を拡張できます

編集

別のアイデア

語彙内の単語をアルファベット順に並べ替えます。

12 個の文字があり、それらすべてが異なる場合、正確に 4095 通りの可能な組み合わせ ( i= 1->12 binomial(12 over i) の合計) (文字 ABCD の場合、(ABCD,ABC,ABD,ACD ,BCD,AB,AC,AD,BC,BD,CD,A,B,C,D) 先ほど言ったように、4095 には 12 の異なる文字があり、一部の文字が同じ場合はさらに少なくなります。

複雑さ 4095*Log2(250000) は約 75000 です。試してみる価値はあります。

各組み合わせで完全一致検索を行います。

于 2009-09-28T10:55:03.277 に答える