gperf
静的検索構造は、初期化、挿入、取得などの基本操作を持つ抽象データ型です。概念的には、すべての挿入が、どの取得よりも先に行われます。実際には、gperfは、検索集合のキーワードと、利用者が指定した関連属性を含む静的配列を生成します。そのため、挿入には実質的に実行時のコストがかかりません。これは静的検索集合を表すのに役立つデータ構造です。静的検索集合は、ソフトウェアシステムの応用で頻繁に現れます。典型的な例には、コンパイラの予約語、アセンブラ命令のオペコード、シェルインタプリタの組み込みコマンドがあります。キーワードと呼ぶ検索集合の要素は、通常はプログラムの初期化時に一度だけ構造に挿入され、一般に実行時には変更されません。
静的検索構造には、配列、連結リスト、二分探索木、デジタル探索トライ、ハッシュテーブルなど、多数の実装があります。各方式には、空間の利用効率と検索時間の効率とのトレードオフがあります。たとえば、n個の要素からなる整列済み配列は空間効率がよいものの、二分探索による取得操作の平均時間計算量はlog nに比例します。一方、ハッシュテーブルの実装は、しばしば定数時間でテーブル項目を見つけられますが、通常は追加のメモリを必要とし、最悪の場合の性能がよくありません。
最小完全ハッシュ関数は、ある種類の静的検索集合に対して最適な解を提供します。最小完全ハッシュ関数は、次の2つの性質で定義されます。
ほとんどの用途では、完全ハッシュ関数を生成する方が、最小完全ハッシュ関数を生成するよりはるかに容易です。さらに、実際には、最小ではない完全ハッシュ関数の方が最小完全ハッシュ関数より速く実行されることがよくあります。疎なキーワードテーブルを検索すると「null」の項目が見つかる確率が高まり、文字列比較が減るためです。gperfは、デフォルトではキーワード集合に対してほぼ最小の完全ハッシュ関数を生成します。ただし、gperfには、最小性や完全性の程度を利用者が制御できる多数のオプションがあります。
静的検索集合は、時間が経過しても比較的安定していることがよくあります。たとえば、Adaの63個の予約語は、ほぼ10年間変わっていませんでした。そのため、後で何度も頻繁に使うのであれば、最適な検索構造を一度構築するために集中的に労力をかける価値があることがよくあります。gperfは、時間と空間の効率がよい検索構造を手作業で作る煩雑さを取り除きます。本格的なプログラミングプロジェクトで、有用かつ実用的なツールであることが実証されています。gperfの出力は現在、GNU C、GNU C++、GNU Java、GNU Pascal、GNU Modula 3を含む、実用および研究用の複数のコンパイラで使われています。最後の2つのコンパイラは、まだ公式のGNU配布物には含まれていません。各コンパイラはgperfを使い、それぞれの予約語を効率よく識別する静的検索構造を自動生成します。