スクラブルワードファインダー：トライの作成、トライの保存、トライの使用？

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

トライは、メモリ効率と検索効率の両方を兼ね備えているため、この問題を解決するために使用される古典的なデータ構造です。妥当な長さの約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」ノードを停止する必要はありません。前の質問で検索アルゴリズムをスケッチしました。

私は、しばらくの間ブログを書くつもりだった機能的なスタイルの永続的なトライの実装を持っていますが、それを回避することはありませんでした。最終的に投稿する場合は、この質問を更新します。