7

私がやろうとしていること:

  • ユーザーがスクラブルをプレイするときに再生する単語を見つけるのに役立つモバイル Web アプリケーションを構築する
  • ユーザーは、任意の数の文字と 0 個以上のワイルドカードを入力して、単語の候補を表示します

私がこれをやろうとしている方法：

  • 40 万語以上を含む辞書で MySQL データベースを使用する
  • ASP.NET と C# をサーバー側プログラミング言語として使用する
  • HTML5、CSS、Javascript の使用

私の現在の計画:

  • データベースのすべての単語を使用して Trie を作成し、ユーザーの文字/ワイルドカード入力に応じて単語をすばやく正確に検索できるようにします

計画を立てても、それを実行できなければ意味がありません。これは私が助けを必要としているものです。

  • データベースから Trie を構築するにはどうすればよいですか? (更新: 既にデータベースにある単語を使用して Trie を生成したいのですが、それが完了したら、単語の一致にデータベースを使用するつもりはもうありません)
  • 素早く簡単にアクセスできるように Trie を保管するにはどうすればよいですか? （更新：データベースを破棄できるように）
  • C# を使用して、文字とワイルドカードに応じてトライを使用して単語を検索するにはどうすればよいですか?

最後に:
どんな助けでも大歓迎です。私はまだ C# と MySQL の初心者なので、優しくしてください

本当にありがとうございました！

4

1 に答える 1

17

まず、問題の制約を見てみましょう。ゲームの単語リストを、「アナグラム」問題を効率的にサポートするデータ構造に格納したいと考えています。つまり、n文字の「ラック」が与えられた場合、そのラックから作成できる単語リスト内のn文字以下のすべての単語は何ですか. 単語リストは約 400K 語になり、非圧縮の文字列データはおそらく 1 ～ 10 MB になります。

トライは、メモリ効率と検索効率の両方を兼ね備えているため、この問題を解決するために使用される古典的なデータ構造です。妥当な長さの約 400K 語の単語リストを使用すると、トライをメモリに保持できるはずです。(ツリーが大きすぎて一度にメモリに収まらないため、ほとんどのツリーをディスク上に保持する、b ツリーのようなソリューションを使用するのとは対照的です。)

トライは基本的に 26 項ツリー (ローマ字を使用していると仮定) に過ぎず、すべてのノードには文字があり、各ノードにはそれが単語の終わりかどうかを示す 1 つの追加ビットがあります。

それでは、データ構造をスケッチしましょう。

class TrieNode
{
    char Letter;
    bool IsEndOfWord;
    List<TrieNode> children; 
}

もちろん、これは単なるスケッチです。おそらく、これらに適切なプロパティアクセサーとコンストラクターなどを持たせたいと思うでしょう。また、フラット リストは最適なデータ構造ではない可能性があります。たぶん、ある種の辞書の方が良いでしょう。私のアドバイスは、最初に動作させてからパフォーマンスを測定し、それが受け入れられない場合は、パフォーマンスを改善するために変更を加えてみることです。

空のトライから始めることができます:

TrieNode root = new TrieNode('^', false, new List<TrieNode>());

つまり、これは単語の始まりを表す「ルート」トライ ノードです。

スクラブル辞書の最初の単語「AA」をどのように追加しますか? まず、最初の文字のノードを作成します。

root.Children.Add('A', false, new List<TrieNode>());

OK、私たちの試みは今です

^
|
A

次に、2 番目の文字のノードを追加します。

root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));

私たちのトライは今

^
|
A
|
A$   -- we notate the end of word flag with $

偉大な。ここで、AB を追加するとします。「A」のノードがすでにあるので、それに「B$」ノードを追加します。

root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());

そして今、私たちは持っています

    ^
    |
    A
   / \
  A$   B$

そのように続けてください。もちろん、「root.Children[0]...」と書くのではなく、トライを検索して必要なノードが存在するかどうかを確認し、存在しない場合は作成するループを記述します。

トライをディスクに保存するには、率直に言って、単語リストをプレーン テキスト ファイルとして保存し、必要に応じてトライを再構築します。30 秒ほどかかることはありません。その後、メモリ内のトライを再利用できます。トライに近い形式でトライを保存したい場合は、シリアライゼーション形式を考え出すのは難しくありません。

トライを検索してラックを一致させるには、トライのすべての部分を探索しますが、ラックが一致しない可能性のある領域を除外します。ラックに「A」がない場合は、「A」ノードを停止する必要はありません。前回の質問で検索アルゴリズムをスケッチしました。

関数型の永続的なトライの実装を手に入れました。これについては、しばらくの間ブログに書きたいと思っていましたが、実現することはありませんでした。最終的に投稿する場合は、この質問を更新します。

于 2011-09-16T15:13:11.443 に答える