3

私はスクラブルゲームを構築していて、wordDictionaryに対して単語を検証しています。

最初の試みでは、辞書を配列にロードし、検証するためにバイナリ検索を実行しました。

代わりにsqliteに切り替えたので、dict全体をメモリに保存する必要がなく、読み込み時間を短縮できます。

私には2つの課題があります。

  1. データベースにクエリを実行して、単語がそこにあるかどうかを確認する最も効率的な方法は何ですか？

  2. 一連の文字に対して可能なすべての単語を見つけるにはどうすればよいですか...wordDictionaryを配列に含めると、すべてをループして、すべての単語を検証できます。すべての行（〜700,000）をクエリし、sqliteで検証するのは非常に時間がかかります。

4

3 に答える 3

2

「明らかな」解決策は、インデックスを作成することです。ただし、メモリ内のバイナリ検索が機能しない場合、インデックスで問題が解決されるかどうかはわかりません。ほぼ同じ量のメモリを占有します。

一致する可能性のあるものを検索し、外部メモリから 1 回のフェッチでいくつかを取得し、比較をすばやく行うことができればいいと思いませんか?

これはデータベースで可能です。アイデアは、「ハッシュ」関数を作成することです。同じハッシュ値を持つものはすべて単語テーブルに格納されます。次に、検索のためにメモリにフェッチされます。

同じハッシュを持つ単語のセットを取得したら、自分で検索を行うことができます。または、これが機能する可能性があります。

select word
from (select word
      from words
      where hash(word) = hash(YOURWORD)
     ) t
where t.word = YOURWORD

ポイントは、最初にハッシュ インデックスを使用するように SQL コンパイラを「だまして」から、比較を行うことです。

非常に単純なハッシュ関数は最初の 5 文字かもしれません。したがって、「スパイ」のような単語には 1 つのエントリしかありません。しかし、「マルチ」という言葉には多くの意味があります。単語の表には、「単語」と「ハッシュ」の 2 つの列があります。次に、 hash にインデックスを作成します。. . 最適なパフォーマンスを得るには、words テーブルをハッシュで並べ替えます。単語リストを順序付けすると、一致するすべての単語が 1 ページまたは 2 ページに収まる可能性が高くなり、外部 I/O が最小限に抑えられます。

残念ながら、SQLite には組み込みのハッシュ関数がありません。文字列内の文字値をペアで合計するなどの操作を行うことで、自分で作成できます。

于 2013-01-15T19:23:45.093 に答える
1

私はすでにあなたの前の質問に答えていました。私はデータベースの専門家ではありませんが、レターアルゴリズムがどのように機能するかについていくつかのアイデアがあります。

  1. 検索を高速化するため、つまり結果の数を減らすためだけに DB を使用し、DB の結果をメモリで確認します。

  2. DB 内のすべての単語について、ハッシュも保存します。そのハッシュは数値または文字列になります。

  3. {a、b、b、c、x、t、u、v} などの一連の文字がある場合、文字から作成できる一連のハッシュを計算し、可能なすべてのハッシュについて、すべての結果のデータベース。

  4. セットの文字のみが含まれている場合は、結果をテストします (これについては、前の質問で既に説明しました)。

いくつかの可能なハッシュ関数:

  1. hash(transformers) = "aeo" など、繰り返しのない順序付けられた母音。上記のセットから、可能なハッシュ ""、"a"、"u"、"au"、"ua" を取得します。母音のない単語はほとんどないので、"" リクエストは問題にならないことに注意してください。

  2. hash(request) = "ee" など、繰り返される順序付けられた母音。セット {w, h, y, a, a, x, e} から、ハッシュ ""、"a"、"e"、"y"、"aa"、"ae"、"ay"、"ea "、"ey"、"ya"、"ye"、"aae"、"aay". 一般に、リクエストが多いほど、結果は少なくなります。

  3. hash(transformers) = "aefmnorst" など、繰り返しのない順序付けされた文字。Nが文字数であり、長さが 2 未満の単語を無視している場合、最大で (文字が繰り返されていない場合) が必要になり(N 3) + (N 4) + (N 5) + .... + (N N)ますN。

  4. ASCII 文字のビットマスク (非 ASCII アルファベットは無視されます)。位置 0 のビットは単語に「a」が含まれていることを意味し、位置 1 には「b」が含まれているなどです。文字に同じビットマスクを作成すると、次のような単語を選択できます。(wordMask & ~lettersMask) == 0

于 2013-01-15T20:08:31.557 に答える
0

2 番目の質問では、単語ごとに 2 番目の列を追加し、文字をアルファベット順に並べます。次に、使用可能なタイルを並べ替えて、その列を検索します。これにより、検索に使用されたすべてのタイルのすべての可能な単語が得られます。

残念ながら、一部のタイルではうまく機能しません。そのためには、一度に 1 つのタイルを削除して、検索をやり直す必要があります。

于 2013-01-17T01:56:34.210 に答える