Agrep
From Wikipedia, the free encyclopedia
agrep (approximate grep)[訳注 1]は文字列のあいまい検索を行うプログラムである。コンピュータ科学者のUdi ManberとSun Wuにより開発された。最初の実装はUnix向けに開発され、後にOS/2やDOS、Windowsに移植された。
agrepは与えられたクエリに応じて、組み込まれた高速な文字列探索アルゴリズムから最適なアルゴリズムを選択する。特に、開発者のManberとWuが提案した、あいまい検索に適したBitapアルゴリズム（レーベンシュタイン距離に基づいて検索対象から一定の距離内にあるパターンを、ビット並列的な手法により大きなコスト増なく発見できる）を実装していることが特徴である。
agrepはGLIMPSEというインデクサの検索エンジンにも用いられている。agrepの権利はアリゾナ大学に帰属するが、ISCライセンスで利用できる。
類似な実装
多くのagrepは正規表現ライブラリであるTREを利用したコマンドラインツールとして提供されている。パターン内部の独立したグループに重みと総コストを割り当てることができるため、TRE agrepはWu-Manber agrepよりも強力である。また、Unicodeにも対応している[1]。Wu-Manber agrepとは違いTRE agrepは二条項BSDライセンスのもとで利用できる。
オープンソースなコマンドラインインターフェイスライブラリであるFREJ (Fuzzy Regular Expressions for Java)はagrepと同様に利用することができる。これはagrepやTREとは違って、マッチ後の文字列に複雑な構造の置換を適用することができる[2]。しかしながらその文法と探索能力は普通の正規表現とは明確に違う。