Agrepの技法を巨大なファイルシステムに適用したものらしい。 インデクスを併用する。

最近はWebGlimpseとして頑張っているらしい。 (2000/1 増井)

ftp://dcc.ufmg.br/pub/research/~nivio/cgrep Cgrepというプログラムになっているらしい。

'Bloom Filter'を使用したスペルチェッカの経験。Bloom Filterとは、判定したい文字列に対して複数のハッシュ関 数を計算し、その結果をテーブル上で捜すことによりその 文字列が正しいスペルかどうかをチェックするというもの である。ハッシュ関数をたくさん使用することにより間違 いの率を低くすることができる。スペル訂正については Peterson_spellcorrectと同じ方法(侯補を生成して それぞれが正しいかどうかチェックする方法)をとっている。

Bibファイルがこわれていたため、以下のもの (Peterson:spellcorrect)と混同しているかもしれない。 Address: Berlin/Heidelberg/New York Month: oct Booktitle: Proceedings of the 10th ACM Symposium on the Theory of Computing Editor: G. Goos J. Hartmanis Pages: 59-65

BM法より速い文字列検索アルゴリズム。BM法がパタン文字 列の最後からマッチを捜すのに対し、まだ調べていないテ キスト文字列の最初の文字からパタン比較を行なう。 BM法に対し、パタンが短い場合数10%、長い場合10%程度高 速化される。

Windowsのアプリケーションにどんな検索機能が用意 されているか、などを解説している エディタの中でgrepを動かすものとか、 find的にディレクトリを捜してgrepするものなどがある。 「なめらか」なものはあまり無さそうだが...?

BM,KMP等の比較

Waterloo大学のパターンマッチシステム。長さnのパターン のマッチングを計算するとき、マッチ状態をnビットで表現 し、ビットkがk文字マッチしていることを示すようにする。 例えば"11101"は2文字マッチしていることを示す。次の文 字がcであるとき、この状態変数を1ビット左にシフトし、 T[c]とのORを計算することにより新しい状態を計算する。 T[c]はあらかじめ計算しておく値で、パタン文字==cの位置 だけ0になっている。(例えば、パタン"abac"に対し T['a']="0101"となる。) k個のミスマッチを許すときはOR のかわりに加算を使ってミスマッチ個数を計算する。

Shifter Algorithmと呼ぶらしい。条件によってはBMより実 行が速いといっているがどのようなものであろうか。状態 の表現方法が違うだけのような気がするが。Univ. of Waterlooのシステムを使ったと称するIRシステムが商用に なっているが、これのことなのだろうか？ ミスマッチには いろいろなタイプがあるが、どのタイプに対しても計算可 能なのだろうか？

スペルチェッカの概説(TYPO,DEC20のSPELL)及び自分で作っ たチェッカの解説。プログラムリストが附属している。 \begin{itemize} \item{スペルチェッカの歴史} \\ 初期のもの(TYPOなど)は2語または2語の組合せの起こる確立によって スペルエラーをチェックしていたが、その後は実際の辞書を参照する方式が 主流となっている。 \item{辞書構成方法} \\ 数千語程度の辞書が適当なので辞書の大きさは100KBぐらいとなる。 もっとも頻繁に出現するものを静的なメモリ上においておき、 個人や文書に依存する特殊なものを動的なメモリ上に置き、 頻繁にあらわれないものをディスク上に置いておくという3段方式がよい。 DEC SPELLでは最初の2文字及び文字長による 6000エントリのハッシュ表を作っている。 \item{誤りの訂正方法} \\ 1文字欠けているもの、余分にはいっているもの、転置しているものに ついてそれぞれ調べる。間違っている語は普通少ないので、訂正に多少時間が かかっても大きな問題ではない。 \item{バッチ方式とインタラクティブ方式} \\ バッチ式の場合辞書をソートしておけばスキャンが一度だけですむという 特徴があるが、使いやすさを考えるとインタラクティブ方式が望ましい 。 \item{サフィックスの扱い} \\ 辞書を小さくするため、サフィックスの可否という属性を辞書に 書いているものがある。属性は20種類ぐらい必要である。 \end{itemize}

Shift-addアルゴリズムの紹介。ちょっと古い。