(Quiz/2年次) アルゴリズムとデータ構造: Spotlightでの例
火曜日, 8月 4th, 2009（出典: Wikipedia:データ構造）
データ構造（データこうぞう、英 en:data structure）とは、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。
ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。
Mac OS X の Spotlight では，OSが標準で処理可能なテキスト文章であれば，Word 等のバイナリファイルの中身も含めて検索対象とすることが可能である．
Spotlight が対象とする検索対象とは，一つのファイル内には複数の単語が記述されており，さらにそのような文書が大量にある．このような膨大な文書を検索対象としつつ，ユーザーの入力した検索キーワードが含まれる文書を適切に列挙する必要がある．
上記を踏まえて，以下のクイズに答えよ．
- 文書内のキーワードをリストで表現するとし，文書毎に異なるリストでデータを格納すると仮定する．すなわち，文書1にキーワードA,Bがある場合，そのデータを格納しているリスト1には「A->B」，文書2にキーワードA,C,Dがある場合，そのデータを格納しているリスト2には「A->C->D」と格納されているとする．この場合のメリット・デメリットを検討せよ．
- 同様に，文書内のキーワードを木構造で表現しているとする．この場合のメリット・デメリットを検討せよ．
- それ以外の適当なデータ構造は無いだろうか？