Agrep

agrep（approximate grep）は、与えられた文字列に対して、あいまい検索を行うためのプログラムです。コンピュータ科学者のUdi ManberとSun Wuによって開発されました。当初はUnix向けに実装されましたが、後にOS/2、DOS、Windowsといった環境にも移植されています。

agrepの主な特徴は、組み込まれた複数の文字列探索アルゴリズムの中から、与えられたクエリに応じて最適なアルゴリズムを自動的に選択する点です。特に、開発者であるManberとWuが考案したBitapアルゴリズムは、レーベンシュタイン距離に基づいて、検索対象から一定の距離内にあるパターンを効率的に検出できます。このBitapアルゴリズムは、ビット並列的な手法を用いることで、大きなコスト増を抑えつつ高速なあいまい検索を可能にします。

agrepは、GLIMPSEというインデクサの検索エンジンにも採用されています。このことから、その検索能力の高さが伺えます。agrepの権利はアリゾナ大学に帰属していますが、ISCライセンスの下で自由に利用することができます。

類似の実装

agrepと類似の機能を提供する実装も存在します。その一つが、正規表現ライブラリであるTREを利用したコマンドラインツールです。TRE版のagrepは、パターン内の独立したグループに重みやコストを割り当てることができ、より複雑な検索条件を扱うことが可能です。また、Unicodeにも対応しているため、多様な文字コードのテキストを検索できます。TRE版agrepは、Wu-Manber版agrepとは異なり、二条項BSDライセンスに基づいて利用できます。

さらに、オープンソースのコマンドラインインターフェイスライブラリであるFREJ（Fuzzy Regular Expressions for Java）もagrepと同様の目的で使用できます。FREJは、agrepやTREとは異なり、マッチした文字列に対してより複雑な構造の置換を適用できるという特徴があります。ただし、FREJの文法や検索能力は、一般的な正規表現とは大きく異なるため、注意が必要です。

まとめ

agrepは、あいまい検索を行うための強力なツールであり、その高速性と柔軟性から様々な場面で利用されています。複数の実装が存在し、それぞれに特徴があるため、用途に応じて最適なものを選択することが重要です。

外部リンク

Wu-Manberによるagrep
For Unix
For DOS, Windows and OS/2 home page
Christoph's Personal Wiki（英語）

もう一度検索