agrep は、アルゴリズム界隈では有名な研究者 Udi Manber と Sun Wu によって開発された、曖昧文字列マッチに対応した grep である。
ターゲットとなるテキストを走査して、クエリと近似マッチしたものを表示する。
類似文字列マッチならではのオプション:
（分かりやすさ優先で「エラー文字数」と表現しているが、実際はクエリ文字列とターゲット文字列を同じ文字列にするために行う挿入・削除・置換の合計回数）
クエリ abbc はファイル a.txt 内の ababacd の行と1文字エラーでマッチ（エラー文字数は "-s" オプションで表示される）。
詳しく見ると ababacd の 2-6 の箇所とマッチ、つまり、ab[abac]d で abac のところにマッチしている（マッチ位置は "--show-position" オプションで表示される）。
マッチした箇所 abac の2番目の a (ab[a]c) が b に置き換わってクエリ abbc と完全一致するということで、1エラーとなる。
最大3つのエラーまで許容した検索結果。
abbc と vwwaxxyzz は3エラー、つまり、abbc の a しか合ってない。
許容エラーを1ずつ変えてみた結果。
4の場合はクエリ無視で a.txt 内の行が全部出てくるので意味がない（クエリの文字数が4ゆえ）。
日本語文字 (utf-8) もいける。
position がバイト列ベースなので注意。
下の例では、クエリ「鈴木さん」に対応する箇所が「鈴木さま」なのだが、0-4 ではなく 0-12 になってる。
アルゴリズムの性質上、前後の塊が入れ替わっているパターンには弱い。
心情的には「山田さん、こんにちは」に対して「こんにちは、山田さん」がベストとして出てほしい。
まあ、これは文字列マッチではなく自然言語処理の範疇。
手軽になんとかしたい場合は ngram とかで（関連記事を参照）。
ターゲットとなるテキストを走査して、クエリと近似マッチしたものを表示する。
- インストール方法例
- "sudo yum install agrep"
- ウェブにある man page: agrep(1) - Linux man page
- 追記: github にあるやつ agrep は UTF-8 対応ではない模様（よくわからない）
類似文字列マッチならではのオプション:
- "-E NUM, --max-errors=NUM": エラー文字数の上限
- "-# (# = 0,1,2,3,4,5,6,7,8,9): エラー文字数の上限 ("-E #" と同じ)
- "-B, --best-match": ベストマッチな結果だけを表示する。
- "-s, --show-cost": コストの表示。何文字異なるかというエラー文字数を表示する。
- "--show-position": 何文字目から何文字目までマッチしたかを表示する。0始まり。
（分かりやすさ優先で「エラー文字数」と表現しているが、実際はクエリ文字列とターゲット文字列を同じ文字列にするために行う挿入・削除・置換の合計回数）
「やってみよう！」のコーナー
クエリ abbc はファイル a.txt 内の ababacd の行と1文字エラーでマッチ（エラー文字数は "-s" オプションで表示される）。
詳しく見ると ababacd の 2-6 の箇所とマッチ、つまり、ab[abac]d で abac のところにマッチしている（マッチ位置は "--show-position" オプションで表示される）。
マッチした箇所 abac の2番目の a (ab[a]c) が b に置き換わってクエリ abbc と完全一致するということで、1エラーとなる。
% cat a.txt ababacd vwwaxxyzz ydgjkdfjgkfd
% agrep -B abbc a.txt ababacd % agrep -B abbc a.txt -s 1:ababacd % agrep -B abbc a.txt -s --show-position 1:2-6:ababacd
最大3つのエラーまで許容した検索結果。
abbc と vwwaxxyzz は3エラー、つまり、abbc の a しか合ってない。
% agrep -E 3 abbc a.txt -s --show-position 1:2-6:ababacd 3:3-7:vwwaxxyzz
許容エラーを1ずつ変えてみた結果。
4の場合はクエリ無視で a.txt 内の行が全部出てくるので意味がない（クエリの文字数が4ゆえ）。
% agrep -1 abbc a.txt -s --show-position 1:2-6:ababacd % agrep -2 abbc a.txt -s --show-position 1:2-6:ababacd % agrep -3 abbc a.txt -s --show-position 1:2-6:ababacd 3:3-7:vwwaxxyzz % agrep -4 abbc a.txt -s --show-position 1:2-6:ababacd 3:3-7:vwwaxxyzz 4:0-4:ydgjkdfjgkfd
日本語文字 (utf-8) もいける。
position がバイト列ベースなので注意。
下の例では、クエリ「鈴木さん」に対応する箇所が「鈴木さま」なのだが、0-4 ではなく 0-12 になってる。
% cat aj.txt 鈴木さま、こんにちは こんにちは、山田さん おはよう、太田ちゃん
% agrep -B 鈴木さん aj.txt -s --show-position 1:0-12:鈴木さま、こんにちは
アルゴリズムの性質上、前後の塊が入れ替わっているパターンには弱い。
心情的には「山田さん、こんにちは」に対して「こんにちは、山田さん」がベストとして出てほしい。
% agrep -B 山田さん、こんにちは aj.txt -s --show-position 3:0-30:鈴木さま、こんにちは % agrep -5 山田さん、こんにちは aj.txt -s --show-position 3:0-30:鈴木さま、こんにちは 5:0-15:こんにちは、山田さん
まあ、これは文字列マッチではなく自然言語処理の範疇。
手軽になんとかしたい場合は ngram とかで（関連記事を参照）。
関連記事
- Perl の標準ライブラリ Search::Dict を使った転置インデックスによる類似テキスト検索スクリプト[2022-01-17-2]
- 前後の塊が入れ替わっている場合はこういう ngram 使ったやつが良い。
- Algorithm::Diff で類似文字列検索[2008-04-22-3]
- Perl のモジュール。
- Dynamic Programming による類似文字列マッチの実装例[2007-01-22-4]
- 基礎の基礎となるロジック。