第5回 演習問題 Trie
■ 共通
実行・測定環境
hardware: 貸与されたnotePC(3年生、任意のPC or WS、性能記載の必要がある)
OS: linux(時間的余裕があればwindowsXP)
測定時は、当該プログラム以外のプログラムはできるだけ削減する
5b 2分探索とTrie(26進)の探索効率の比較 難易度:B
キー: 文字列
使用ファイル: wordE100KS.dat
(0) 当該ファイルを読み込み、2つの配列(配列A2分探索対象、配列Bは総探索用)に格納する。
(1) 配列Bを探索キーとして配列Aに対して、2分探索法で総探索を行う。このとき、1万、2万、・・・と1万要素単位で、その時点での総照合回数、総探索時間を出力する。
(2) 配列AからTrie(26進)を生成し、配列Bを探索キーとして総探索を行い、(1)と同様の計測項目(探索時の巡回内部節総数、総探索時間)を出力する。
(1), (2)の計測結果を、表・グラフ(折れ線)にし、総合的に分析する。
作成済み5c Trie(26進) 削除関数 難易度: A
作成関数: 削除関数
キー: 文字列
使用ファイル: wordE100KR.dat
5d Trie(26進) 探索関数の拡張 難易度: B
作成関数: 部分一致文字列の探索関数
キー: 文字列
使用ファイル: wordE100KR.dat
前方一致(例: info?)、後方一致(例: ?tion)を実現できる関数を作成する。
作成済み5e Trie(26進)と分離連鎖法の比較(探索時間) 難易度: B
キー: 文字列
使用ファイル: wordE100KR.dat
上記ファイルを読み込み、通常の配列に格納する。この配列から要素を1万用語単位にで、分離連鎖法、およびTrie(26進)を生成する。格納された要素と同一の要素集合でそれぞれのデータ構造に対して、全探索を行い、探索時間を測定する。
------------------------------------------------------------
分離連鎖法 Trie(26進)
照合回数 探索時間 ノード数(辿った) 探索時間
1万要素 **** **** **** ****
2万要素 **** **** **** ****
3万要素 **** **** **** ****
・・・・・
・・・・・
9万要素 **** **** **** ****
10万要素 **** **** **** ****
------------------------------------------------------------
上記データをexcel(または互換ソフトウエア)に格納し、表、グラフを作成し、理論値と比較、分析する。
作成済み5f Trie(26進)とTrie(2進)の比較(記憶容量) 難易度: B
キー: 文字列
使用ファイル: wordE100KR.dat
上記ファイルを読み込み、Trie(26進)およびTrie(2進)を生成する。その際、1万レコード単位での格納された要素と同一の要素集合でそれぞれのデータ構造に対して、全探索を行い、探索時間を測定する。
------------------------------------------------------------
ノード数
Trie(26進) Trie(2進)
内部節 葉 内部節、葉
1万要素 **** **** **** ****
2万要素 **** **** **** ****
3万要素 **** **** **** ****
・・・・・
・・・・・
9万要素 **** **** **** ****
10万要素 **** **** **** ****
------------------------------------------------------------
上記データをexcel(または互換ソフトウエア)に格納表を作成する。1万要素単位でのでの記憶容量をも計算し、グラフを作成し、理論値と比較、分析する。
作成済み5g Trie(26進)とTrie(2進)の比較(探索時間) 難易度: B
キー: 文字列
使用ファイル: wordE100KR.dat
上記ファイルを読み込み、通常の配列に格納する。この配列から要素を1万用語単位にで、Trie(26進)およびTrie(2進)を生成する。格納された要素と同一の要素集合でそれぞれのデータ構造に対して、全探索を行い、探索時間を測定する。
------------------------------------------------------------
Trie(26進) Trie(2進)
node数 探索時間 node数 探索時間
1万要素 **** **** **** ****
2万要素 **** **** **** ****
3万要素 **** **** **** ****
・・・・・
・・・・・
9万要素 **** **** **** ****
10万要素 **** **** **** ****
------------------------------------------------------------
*node数 辿ったノード数
上記データをexcel(または互換ソフトウエア)に格納し、表、グラフを作成し、理論値と比較、分析する。
作成済み5i Trie(26進)での擬似正規表現探索関数の作成 難易度: A
作成関数: 格納、擬似正規表現探索関数、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
上記ファイルを読み込み、Trie(26進)を生成する。10個の異なった擬似正規表現文字列を文字列配列に格納し、擬似正規表現探索関数(巡回関数の拡張)を行い、個々の擬似正規表現パターン毎に、これを含む単語を出力する(1擬似正規表現文字列毎に、複数の単語が出力されるはずである)。1探索毎の時間を測定する(全てのパターンについて、それぞれ全ノードの巡回を行うので、ほとんど同じ探索時間になるはずである)、レポートとしては、作成した擬似正規表現探索関数のアルゴリズムと関数の説明、および実行結果の分析を含むようにする。
5j Trie(2進)での擬似正規表現探索関数の作成 難易度: A+
作成関数: 格納、擬似正規表現探索関数、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
上記ファイルを読み込み、Trie(26進)を生成する。10個の異なった擬似正規表現文字列を文字列配列に格納し、擬似正規表現探索関数(巡回関数の拡張)を行い、個々の擬似正規表現パターン毎に、これを含む単語を出力する(1擬似正規表現文字列毎に、複数の単語が出力されるはずである)。1探索毎の時間を測定する(全てのパターンについて、それぞれ全ノードの巡回を行うので、ほとんど同じ探索時間になるはずである)、レポートとしては、作成した擬似正規表現探索関数のアルゴリズムと関数の説明、および実行結果の分析を含むようにする。
作成済み5K 部分一致文字列の探索関数の比較(配列‐二分探索とTrie(26進)) 難易度: B
作成関数: 追加、探索
キー: 文字列
使用ファイル: wordE100KR.dat
・二分探索法を改良し、前方一致(例: info?)を実現する関数を作成する。
・多分探索木の巡回関数に基づき、部分木出力関数をTrie(26進)に適用し、前方一致(例: info?)を実現する関数(部分木巡回‐出力関数)を作成する。
・特定の部分文字集合(100)に対し、比較(照合)回数、および出力時間を測定し、これらの結果を、表、グラフに表し、分析する。
作成済み>5x Trie(2進)操作関数の作成 難易度: A
作成関数: 格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat