たつをの ChangeLog

72 件 見つかりました。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [ 次へ ]

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 とかで(関連記事を参照)。

関連記事


手元でのちょっとした用途で類似テキスト検索をやりたいのですが、
Linux環境であれこれインストールしなくても動かせて、
気ままにカスタマイズできる気が利いたやつがなかったので、
改めて作ってみました。
過去に何度も書いたことのあるプログラムなので目新しさはありませんが。
(「車輪の再発明を気にしない」が私の行動指針です!)

simpii


私の母プログラミング言語(母語)である Perl で書いています。
標準ライブラリしか使っていないので、
Perl さえインストールすればどこでも動くはずです。

転置インデックス(+リランキング)用のスクリプトと、リランキングだけするスクリプトがあります。
リランキング時のスコア計算方法は README.md を参照されたし。

関連記事


渋谷区の子供科学教育施設的な「ハチラボ」の企画展は「ときめく化石の展示会」。

ハチラボ ときめく化石の展示会 2017.11.5

  • 渋谷区/こども科学センター・ハチラボ
    ときめく化石の展示会

    9月1日(金)~11月12日(日)

    化石には夢や想像力を刺激する驚きがあります。本展示では、こどもたちの「え!」「なに?」という心の動きを大切にしながら、化石にまつわる探究を深めるために、さまざまなテーマで化石を扱います。

    協力:ふぉっしる・山と渓谷社

いろんな化石が置いてあって、さわれます。
キラキラしたアンモナイトや恐竜のうんちの化石など。
とらちゃん(小1息子)も面白がってさわっていましたよ。

ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5

これまでのハチラボ企画展


渋谷区の子供科学教育施設的な「ハチラボ」の企画展は秋山仁先生の「科学・数学ワンダーランドへようこそ」。
展示品が入れ替わりつつ常設展示されているのですが、それが今回は一堂に会する、的な。
明日までです。

ハチラボ

  • 渋谷区/こども科学センター・ハチラボ
    http://www.city.shibuya.tokyo.jp/edu/bunka/hachirabo.html
    企画展示 秋山仁先生の「科学・数学ワンダーランドへようこそ」~すべては感動から!~

    6月20日(火)~7月17日(月・祝)

    数学研究者の秋山仁先生が監修された"見て・さわって・かんがえる"体験型の作品を、どどーんとイッキに展示します。科学や数学の不思議な世界を体験して、考えて、学びましょう!
    協力:秋山数学研究所

ソートアルゴリズムの展示がありました。
見るの初めて(ここ半年以上ハチラボに行けてなかったので)。

ハチラボ

えっと、これなにソートだったけな。

これまでのハチラボ企画展


お金の流れ

元ネタはこちら。


プログラム書いて実験してみた。

■コード(rand-ageru.pl)
#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw(min max);
my ($num, $loop_max) = @ARGV;
my @money = ($num) x $num;
for (my $loop = 1; $loop <= $loop_max; $loop++) {
    for (my $from = 0; $from < $num; $from++) {
        next if $money[$from] == 0;
        my $to = int(rand($num - 1));
        $to++ if $from <= $to;
        $money[$from]--;
        $money[$to]++;
    }
    next if $loop !~ /^10*$/;
    print "LOOP:$loop MIN:".min(@money)."-MAX:".max(@money)."\n";
    print join(",", map {"$_:$money[$_]"} 0..$#money)."\n\n";
}

■実行例(実験)
% ./rand-ageru.pl 45 1000000
LOOP:1 MIN:44-MAX:48
0:44,1:44,2:44,3:47,4:44,5:45,6:47,7:44,8:45,9:46,10:45,11:46,12:46,13:44,14:45,15:46,16:46,17:46,18:46,19:44,20:44,21:44,22:45,23:48,24:47,25:44,26:46,27:45,28:45,29:44,30:44,31:44,32:45,33:44,34:44,35:45,36:44,37:45,38:44,39:46,40:44,41:45,42:46,43:45,44:44

LOOP:10 MIN:39-MAX:51
0:43,1:47,2:40,3:49,4:42,5:47,6:46,7:39,8:43,9:42,10:41,11:48,12:45,13:42,14:44,15:45,16:45,17:47,18:46,19:49,20:47,21:48,22:47,23:50,24:48,25:48,26:44,27:48,28:44,29:43,30:45,31:48,32:46,33:45,34:45,35:45,36:44,37:42,38:42,39:45,40:40,41:43,42:43,43:44,44:51

LOOP:100 MIN:24-MAX:68
0:33,1:37,2:36,3:39,4:41,5:68,6:58,7:54,8:52,9:27,10:28,11:53,12:38,13:34,14:64,15:39,16:57,17:51,18:43,19:55,20:43,21:47,22:44,23:54,24:46,25:50,26:48,27:59,28:43,29:35,30:38,31:45,32:26,33:55,34:62,35:43,36:33,37:45,38:52,39:55,40:42,41:24,42:35,43:35,44:59

LOOP:1000 MIN:3-MAX:116
0:68,1:11,2:41,3:33,4:23,5:41,6:71,7:66,8:38,9:48,10:73,11:34,12:61,13:32,14:99,15:77,16:34,17:53,18:35,19:111,20:20,21:84,22:49,23:27,24:8,25:65,26:61,27:116,28:58,29:3,30:61,31:50,32:6,33:40,34:12,35:14,36:5,37:34,38:77,39:21,40:67,41:6,42:31,43:3,44:58

LOOP:10000 MIN:0-MAX:136
0:85,1:93,2:22,3:71,4:10,5:23,6:31,7:37,8:101,9:87,10:17,11:49,12:89,13:44,14:62,15:16,16:12,17:133,18:59,19:99,20:96,21:4,22:25,23:27,24:35,25:24,26:68,27:39,28:45,29:0,30:19,31:136,32:24,33:51,34:9,35:22,36:37,37:22,38:7,39:5,40:32,41:0,42:9,43:99,44:50

LOOP:100000 MIN:0-MAX:241
0:56,1:152,2:202,3:10,4:49,5:241,6:70,7:1,8:7,9:47,10:31,11:13,12:42,13:17,14:11,15:9,16:29,17:15,18:19,19:4,20:17,21:39,22:30,23:6,24:27,25:43,26:27,27:52,28:16,29:40,30:31,31:76,32:0,33:86,34:36,35:18,36:74,37:73,38:19,39:6,40:51,41:0,42:80,43:152,44:1

LOOP:1000000 MIN:0-MAX:154
0:21,1:62,2:1,3:0,4:17,5:108,6:112,7:38,8:15,9:1,10:64,11:22,12:25,13:22,14:91,15:6,16:133,17:154,18:74,19:43,20:31,21:47,22:84,23:38,24:82,25:58,26:32,27:36,28:59,29:1,30:144,31:22,32:27,33:8,34:26,35:29,36:59,37:50,38:36,39:12,40:59,41:22,42:29,43:13,44:12

rand ageru chart 1 rand ageru chart 3 rand ageru chart 4
(グラフ作成には Google スプレッドシートを使用)

感想:
  • 貧富の差には限度がある
  • 総取り(一極集中)はない
  • 現在の所有金額の大小は次のステップの増減に一切無関係
  • 富めるものがますます富む、とかない
  • 貧富の差が偏ったまま固定されることはない
  • 流動的であり平等と言える
  • 結局「だからなに?」的な話である

追記170712:
別の実験として各回の所持金の平均値を出してみました。

1,000,000回での結果。
だいたい元の金額(45)に集まってますが、意外と幅がありますね。
47.109276,39.766891,44.485117,42.094945,48.880024,34.869301,33.526229,44.400548,44.321862,57.116979,43.650657,44.855215,52.352078,55.901575,41.772016,36.231049,39.193968,41.251579,54.798544,40.119214,44.436059,53.725595,42.635439,62.990679,34.254802,53.590373,47.450794,44.125513,47.254422,44.515322,55.606053,46.902899,45.656174,49.379549,38.403945,44.062136,44.67439,35.194652,41.732219,52.976818,52.299069,39.047405,37.888052,36.47502,43.025554
rand ageru chart ave

10,000,000回での結果。
かなりなだらかになりました。
46.5702488,43.8328284,45.8270906,44.6686343,43.2340561,45.0662266,45.7241905,47.0050791,47.4551543,44.0662231,41.7885695,45.7371473,46.1179543,46.6515994,44.7205374,43.8517445,44.2021394,49.440519,44.1752983,43.5311201,44.9863164,52.5071599,44.9063098,43.2437545,44.5055422,44.0465947,45.8916589,44.88514,44.8972846,47.300969,43.6881715,41.2315118,43.479499,41.9327546,45.7992128,44.1887204,42.8419904,45.5845929,44.5653823,46.8827679,41.478226,46.4430494,43.0199561,45.6001414,47.4269325
rand ageru chart ave 10M steps

100,000,000回での結果。
平等ですね。
45.35740571,45.85611521,44.63398068,45.00681025,44.56915261,45.02652108,46.17506567,46.9452281,45.18124463,44.55733916,44.65472928,45.56778022,46.38509387,44.44781417,45.95134651,44.89093438,44.44047169,44.945177,44.90714924,45.29232582,45.53773343,45.12128488,45.01620548,43.9533694,44.48471894,45.40748693,44.76070381,43.82386026,45.01944748,45.71821635,45.32716238,44.68688319,45.23233019,44.41700684,44.69463016,44.50295805,45.11377298,44.41073274,44.02743855,45.21732131,44.11600142,44.9320687,44.30679792,45.37499137,45.00519196
rand ageru chart ave 100M steps


追記170712:
SNSにて Perl プログラムの下記の意味について質問をいただいたのでここにも書いておきます。
$to++ if $from <= $to;
これは自分に渡さないようにするための仕掛けです。
rand($num - 1) で自分を除いた数の配列のインデックスを決め、その後、本来の自分の位置を挿入してずらしてる、といったイメージです。
同じような方法としては、下記の方が分かりやすいかもしれません。
$to = $num - 1 if $from == $to;
ランダムで自分の位置が選ばれてしまったら配列の末尾が選ばれたことにします。
(配列の末尾はランダムで選ばれないことに留意)
もともとは下記のような「やり直しループ」を書いていたのですが、貧乏性なので少しでもコードを短くしようとああなってしまいました。
my $to = int(rand($num));
while ($to == $from) {
    $to = int(rand($num));
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [ 次へ ]

たつをの ChangeLog
Powered by chalow