たつをの ChangeLog : 2022-01-19

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

• インストール方法例
  • "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]
  • 基礎の基礎となるロジック。

Kindleセール情報サイト「キンセリ」の公式ブログとして2016年3月から「キセブ」を運営してきたのですが、一昨年2020年12月31日を最後に更新停止しています。本家キンセリの更新だけでもいろいろと大変で手が回らないのです。

そこで、2021年は人気ブログ「ネタフル」のコグレさん (@kogure) に、キセブの記事を書くときに使っていたHTML生成ツールを提供し、キンドル本セール記事作成時に使ってもらいました（Kindleセール アーカイブ - ネタフル）。



ということで、ネタフルの「Kindleセール」カテゴリが実質的な「キセブ」の後継となります。「キンセリ認定ブログ」ということで、キンセリともども今後ともよろしくお願いいたします。

ちなみに、「キセブの記事を書くときに使っていたHTML生成ツール」はこんな感じです。やっつけデザインの実用本位なやつです。



キャッチ画像やHTMLテキストがコピペできます。一般公開予定はありません。

過去記事・関連記事

• Kindleセール情報に特化したブログを始めました[2016-03-03-1]
• キンセリ公式ブログ「キセブ」の後継ブログとして「ネタフル」が認定されました！ - ネタフル