- 30 名前：デフォルトの名無しさん mailto:sage [2015/11/28(土) 10:32:03.28 ID:tW/rjk30.net]
- >>27
部分一致検索をするには大きく分けて
・検索される側の文字列を変換して検索に特化させる
・検索する側の文字列を変換して検索に特化させる
・検索される側・する側どちらも何ら変換しない
の3通りの方法がある。
最初のはは例えば接尾辞配列を作ってそれを保持するって方法で、
これは検索される側の文字列長をnとした時にO(n log n)償却時間で変換する方法や
O(n log^2 n)最悪時間で変換する方法なんかが知られている。
検索時間は検索する側の文字列の長さに依らずO(log n)平均時間
次のは例えば正規表現を有限状態オートマトンに変換する方法で、
その正規表現の長さをm、検索される側の文字列の長さをnとする時にO(m^3)平均時間、
O(m^2 * 2^m)最悪時間で構築してO(n)時間で検索できる方法が知られている。
データベースに何でもかんでもぶち込むだけが方法じゃない。
データの総量が増えないなら前者の方法で準線形時間掛けて初期化しておけば対数時間で検索できるし、
データが追加されうるならとりあえず何らかのファイルに1行につき1エントリの形式で書き込んでおいて
後者の方法を使えば線形時間で検索できる。
特に、後者の場合は(1行につき1エントリという形式にしておけば)Unixのgrepコマンドが使える。
|
 |
