0

編集 :


私はあなたの良いアドバイスに従い、トライデータ構造を使用して辞書を含めました。私が選んだ構造は、関心のある人々のためのものです。

しかし、今のところ別の問題があります。アプリケーションを起動するたびにトライ データ構造を構築するのに時間がかかりすぎます。私の辞書が大きすぎるか、選択した trie の実装が単純な辞書には適していない可能性があります。

登録されたデータベースのようにアプリを閉じた後でもこの構造を保存する方法はありますか、または問題が実装によって引き起こされていると思われる場合は、別の方法をお勧めできますか?


Android のプロジェクトで重大な問題が発生しました。

ここでの目標は、一連の 6 文字で作成できるすべての単語を計算することです。

そのために、BDD に 2 つのテーブルがあります。

  • '_id' と 'mots' の 2 つの列を持つ 'words'
  • 「temp」は同じ列を持つ一時テーブルです。

「words」には語彙のすべての単語が含まれており (非常に大きい)、「temp」には 6 文字 (少なくとも 3 文字を使用) で作成できるすべての可能な文字の組み合わせが含まれています。

テーブル「一時」で実際の単語を選択しようとしているので、テーブル「単語」にある単語を選択しようとしています。これを行うための私のコードは次のとおりです。

良い文字を含む単語の最初の選択を行います (少なくとも 3 文字が使用されます)。

db.execSQL("CREATE TABLE temp2 (_id integer primary key autoincrement, mots text not null);");
db.execSQL("INSERT INTO temp2 (_id, mots) SELECT * FROM words WHERE mots like '%"+lettres.tab_char.get(0)+"%' OR mots like '%"+lettres.tab_char.get(1)+"%' "
                    + "OR mots like '%"+lettres.tab_char.get(2)+"%' OR mots like '%"+lettres.tab_char.get(3)+"%' OR mots like '%"+lettres.tab_char.get(4)+"%' "
                    + "OR mots like '%"+lettres.tab_char.get(5)+"%';");

(lettre.tab_char は、一時的に組み合わせを作成するために使用される文字を含む ArrayList(Character) です)

テーブル 'temp2' と 'temp' を結合します。

String MY_QUERY = "SELECT temp2._id, temp2.mots FROM temp2 INNER JOIN temp ON temp2.mots = temp.mots;";
Cursor test =  db.rawQuery(MY_QUERY, null);

その後、値をリストビューに入れました。

それは動作しますが、本当に遅いです: 助けてもらえますか?

4

2 に答える 2

1

一般に、使用しているアルゴリズムは非常に非効率的です。まず、ワイルドカード マッチを使用してすべてのエントリを 6 回検索し、次に、この巨大な結果をデータセット全体と再度結合します。

SQL はおそらくこれを行うのに適切な場所ではありません。SQL はクエリが得意です。これは計算に近いものです。コードでマッチングを行います。

これを実現する方法はたくさんありますが、適切なソリューションを見つける方法は要件によって異なります。文字は繰り返すことができますか?「巨大」とはどのくらいの語彙ですか?それでも数MBに収まりますか?このルックアップはほぼ瞬時に行う必要がありますか?

アップデート:

あなたの要求を考えると、私はジョーに同意しなければなりません。これは実際にはアルゴリズムというよりもデータ構造ですが、トライが最適です。アプリのロード中に一度トライを構築できるはずです。その後、各「一致」は、トライをたどるかなり単純なルックアップになります。

于 2011-06-20T23:58:30.387 に答える
1

探しているアルゴリズムは、実際には " trie " (re trie valの略) と呼ばれます。これらは、このタイプの計算に非常に適しています (Android では、実際に SMS やメール アプリでこれらを使用して、絵文字の置き換えなどを行っています)。適切に行うと、そこから得られるパフォーマンスに驚かれることでしょう。私はポールに同意します。現在のようにクエリを実行するべきではありません。実際、多くの実装では、ディクショナリ ファイル全体をメモリ内のトライにロードし、アプリケーションの存続期間中、単語の検索と検証にそのトライを使用します。スクラブル単語リスト (リンクは以下の質問にも含まれています: twl06.zip) はわずか 1.9MB で、178k ワードが含まれています。複数の単語が共通のプレフィックスを共有するため、メモリ内のトライは実際には 1.9MB よりもはるかに小さくする必要があります (たとえば、"stair" と "stare" は両方とも STA プレフィックスを共有し、2 つのリーフ ["I" と "I" に分岐します) "R"] など...)

ここから始めるのが良いでしょう:アナグラムを生成するアルゴリズム

于 2011-06-21T04:38:06.367 に答える