古い記事
ランダムジャンプ
新しい記事
agrep は、アルゴリズム界隈では有名な研究者 Udi Manber と Sun Wu によって開発された、曖昧文字列マッチに対応した grep である。
ターゲットとなるテキストを走査して、クエリと近似マッチしたものを表示する。

agrep


類似文字列マッチならではのオプション:
  • "-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 とかで(関連記事を参照)。

関連記事