locate

Excelの自動書式により、遺伝子のリストを使用する論文の約20%に誤った遺伝子シンボルが掲載されているとの調査結果

誰もが悩まされる、WordとかExcelの余計なお節介、学業の世界にも有ったんですなあ。少なくともパソコンを使うスキルは、一般の人よりは高いと思うんだけど、それでも足を掬われるって事は、余計なお節介120%認定されました。

遺伝子がニュースになったので『ゲノム編集の衝撃』(NHK出版)こんな本を読んだ訳ではないんだけど、たまたま新刊の棚に有ったので、借りてきていた。

ゲノムって何よ？遺伝子でいいのかな？髪の毛が黒かったり、金髪だったり、瞳の色が黒だったり、青だったり、、これらは親からの遺伝で決まる。

ボイン度を上げようと思ったら、ボインの母を持つ娘と、ボインの母を持つ息子を掛け合わせて、子を産ませ、それを繰り返していけばよい。そうすれば、数百年先には、ボインの子の家系が出来るだろう。

この方法を頑張って適用したのが、乳牛種である、ホルスタイン。家畜とか競馬馬でお馴染みだ。長い年月がかかるのが欠点。

若し、ボインになるのを疎外、、いいかげんにボインはやめれって声が聞こえてきそうなので、筋肉に置き換えよう。

むきむきの筋肉になる遺伝子があるだろう。でも、そんなのだけじゃサイボーグになっちゃうので、筋肉の発達を阻害する遺伝子も有るだろう。そのバランス具合で結果が決まると思われる。

だったら、その疎外する遺伝子を壊してしまえ。そうすれば筋肉むくむくなのが出来る。近畿大学のマグロが有名だけど、肉量の多いマダイもここで、研究されているとか。

そう、ゲノムを編集してね。遺伝子は、卵子と精子が合体した時に決定される。そう受精した細胞の状態の時、狙った遺伝子が働かなくなるような操作をする。以後、細胞分裂していって成体になっても、疎外する遺伝子が無いから、むきむきなマダイになるって寸法。

この方法は、数年前にアメリカで開発され、急速に広まっているそうな。いろいろな応用が模索されてて夢の技術と言われているとか。

日頃お世話になってる物に、感謝を込めて

ってなタイトルで始めてみる。それは何？

毎日、オイラーのために飯を作ってくれる女房だな。彼女が居なかったら、こうして生き延びていられなかっただろう。

そして、日頃愛用してる、locateコマンドにも感謝だな。これが無かったら、広いDisk領域から手早くfileを探し出せなかっただろう。

よって、これがどう、実現されてるか調べてみる。ソース探検隊への新しい任務を申し付かりましたよ。

ソースを見るんで、コンパクトにまとまっている、OpenBSDにします。 OpenBSDも60回目のリリースという節目を迎えましたが、まだ、新しいのにはしてないから、5.9です。まあ、このあたりは枯れているんで、差は無いでしょうけど。

locateを使うには、検索用のDBを事前に作っておく必要がある。/etc/weeklyとかが cronで、週に１回実行されて、作成・更新が行われる。手動でやってみる。

[ob: ~]$ updatedb
/bin/ksh: updatedb: not found
[ob: ~]$ locate updatedb
/usr/libexec/locate.updatedb
/usr/share/man/man8/locate.updatedb.8
/usr/src/usr.bin/locate/locate/locate.updatedb.8
/usr/src/usr.bin/locate/locate/updatedb.sh

見つからなかったので、探してみた。どうやら、/usr/libexecの下にあるやつがそうみたい。見るとシェルスクリプトだった。眼で追うより、走らせろ。

[ob: libexec]$ ps a
  PID TT  STAT       TIME COMMAND
 7632 p2  Isp     0:00.24 -/bin/ksh
25129 p2  I+p     0:00.02 /bin/sh /usr/libexec/locate.updatedb
25625 p2  R+p     0:45.19 find / ! ( -fstype ffs -or -fstype ufs -or -fstype ex
 1077 p2  I+p     0:00.03 /bin/sh /usr/libexec/locate.mklocatedb

走っている時のプロセス状況

[ob: ~]$ /usr/libexec/locate.updatedb
/usr/libexec/locate.updatedb[113]: cannot create /var/db/locate.database: Permission denied

そして、その結果。/var/dbにDBを作ろうとして、権限無しでエラー。よって、スクリプトをちょい読みする。そして追跡。

[ob: ~]$ sh -x /usr/libexec/locate.updatedb --fcodes=MYDB
+ LOCATE_CONFIG=/etc/locate.rc
+ [ -f /etc/locate.rc -a -r /etc/locate.rc ]
+ . /etc/locate.rc
+ TMPDIR=/tmp
   :
+ mktemp /tmp/_updatedb.XXXXXXXXXX
+ tmp=/tmp/_updatedb.8011VlYxYR
+ trap rm -rf $tmp 0 1 2 3 5 10 15
+ find / ! ( -fstype ffs -or -fstype ufs -or -fstype ext2fs ) -prune -or -path /tmp -prune -or -path /var/tmp -prune -or -print
+ 2> /dev/null
+ locate.mklocatedb
+ > /tmp/_updatedb.8011VlYxYR
+ find /tmp/_updatedb.8011VlYxYR -size -257c -print
+ [ MYDB = - ]
+ cat /tmp/_updatedb.8011VlYxYR
+ > MYDB
+ rm -rf /tmp/_updatedb.8011VlYxYR

追跡結果とソースを比べてみると動きがよく分かるな。findでダンプしたファイルパスは、パイプを使って、mklocatedbっていうスクリプトに渡されて、そこで、最終系の/tmp/_updatedb.8011VlYxYRになり、それを指定したMYDBにしてるんだ。

話が前後するけど、/usr/libexecの中に関係者が居た。

[ob: libexec]$ file locate.*
locate.bigram:     ELF 32-bit LSB shared object, Intel 80386, version 1
locate.code:       ELF 32-bit LSB shared object, Intel 80386, version 1
locate.concatdb:   Bourne shell script text executable
locate.mklocatedb: Bourne shell script text executable
locate.updatedb:   Bourne shell script text executable

updatedbの初期値は

: ${mklocatedb=locate.mklocatedb}        # make locate database program
: ${FCODES=/var/db/locate.database}      # the database
: ${SEARCHPATHS="/"}                     # directories to be put in the database
: ${PRUNEPATHS="/tmp /var/tmp"}          # unwanted directories
: ${FILESYSTEMS="ffs ufs"}               # allowed filesystems

locate.mklocatedb

どうやらこれが肝になりそう。スクリプトなんで軽く見ておくと

    # Locate database bootstrapping
    # 1. first build a temp database without bigram compression
    # 2. create the bigram from the temp database
    # 3. create the real locate database with bigram compression.
    #
    # This scheme avoid large temporary files in /tmp

これ、FreeBSDの同ファイルに書かれていた指標。OpenBSDのそれには無かった。そして、コードもちょっと違ってた。

if $sortcmd $sortopt > $filelist; then
        $bigram < $filelist | $sort -nr |
                awk -Ft 'BEGIN { ORS = "" } NR <= 128 { print $2 }' > $bigrams\
&&
        $code $bigrams < $filelist

    if $sortcmd $sortopt > $filelist; then
        $bigram < $filelist | $sort -nr |
        awk '{if (/^[   ]*[0-9]+[       ]+..$/) {printf("%s",$2)} else {exit 1}
}' > $bigrams || exit 1
        $code $bigrams < $filelist || exit 1

上がOpenBSDで下がFreeBSDのコードだ。ソースが読めるなら、色々なコードを読むと丁寧に解説されてたりして、理解が深まるかな。

コメントを読むと、findで取得したのを元にbigramを作る。bigramの圧縮を効かせて最終的な本番用DBを作るとな。

bigramって何よ？どうやら、全文検索 - Wikipediaに関係するらしい。

bigramってプログラムが、どんなデータを生成するか観察してみるかな。

[ob: tmp]$ find /tmp
/tmp
/tmp/.X11-unix
/tmp/.ICE-unix
/tmp/vi.recover
/tmp/uscreens
/tmp/uscreens/S-sakae
/tmp/uscreens/S-sakae/10616.ttyp0.ob
/tmp/emacs1000
/tmp/emacs1000/server
[ob: tmp]$ find /tmp | /usr/libexec/locate.bigram | sort -nr
   2    un
   2    ix
   2    er
   1    vi
   1    ve
   1    us
     :
   1    .o
   1    -s

よく変換の仕組みが分からないので、人工データを与えてみる。

[ob: tmp]$ cat aa.txt | /usr/libexec/locate.bigram
   1    -m
   1    ci
   1    ix
   1    ri
   2    sc
[ob: tmp]$ cat aa.txt
risc
cisc
cisc-mix

どうやら、２文字づつ区切った時の発現頻度っぽい。scが３になってもよさそうだけど、他にルールが有るのかな？元テキストの１行目を消すと、結果は、

前の行との差分を見てるっぽいな。findの検索結果って、dir部分が同じ事が多いから(並び替えが行われているしね）、前との差分ってのは、大いに圧縮効果が出てくるだろうね。そういう観点で、/usr/src/usr.bin/locate/ 以下のコードを見ると、

                /* skip longest common prefix */
                for (cp = path; *cp == *oldpath; cp++, oldpath++)
                        if (*cp == '\0')
                                break;

                while (*cp != '\0' && *(cp + 1) != '\0') {
                        bigram[(u_char)*cp][(u_char)*(cp + 1)]++;
                        cp += 2;
                }

前の行のバッファーと現在の行のバッファーを比較して、同一な部分は飛ばす。差が出てきたら、２文字のコードでインデックスされる配列をインクリメント。

次は、バッファの役割をひっくり返して、現在のバッファーに行を読み込んで同じ事を繰り返す。

最後に、インデックスがASCIIの印字文字だけで構成されるデータを出力するとな。

locate.code.c

次は、bigramで得られたデータとfindの元データから、最終DBを作り出すんだな。コメントが助けになるな。

 * EXAMPLE:     For simple front compression with no bigram encoding,
 *              if the input is...              then the output is...
 *
 *              /usr/src                         0 /usr/src
 *              /usr/src/cmd/aardvark.c          8 /cmd/aardvark.c
 *              /usr/src/cmd/armadillo.c        14 armadillo.c
 *              /usr/tmp/zoo                     5 tmp/zoo
 *
 *      The codes are:
 *
 *      0-28    likeliest differential counts + offset to make nonnegative
 *      30      switch code for out-of-range count to follow in next word
 *      31      an 8 bit char followed
 *      128-255 bigram codes (128 most common, as determined by 'updatedb')
 *      32-127  single character (printable) ascii residue (ie, literal)

[ob: tmp]$ cat aa.txt | /usr/libexec/locate.mklocatedb
locate.code: bigram array too small to build db, index more files

出来上がったものを観察したくて、小さいデータでやってみたけど、そんなの受け付けてくれなかった。大きいデータサイズ専用なのね。

locate.code.cの先頭でbigramのデータを読み込むんだな。その個数はlocate.hに NBGと言う名前で128と定義されてた。頻出する128個か。その他重要そうなのも定義が有った。

#define NBG             128             /* number of bigrams considered */
#define OFFSET          14              /* abs value of max likely diff */
#define PARITY          0200            /* parity bit */
#define SWITCH          30              /* switch code */
#define UMLAUT          31              /* an 8 bit char followed */

で、ちらちらとコードを見て行ったんだけど、追いきれない。こういう時は、ライブで観察するのがよかろう。-gのオプションを付けてコンパイル。それを自分の領域へ持ってきた。

bigramが小さいと拒否されるので、すでに作ってあるやつから、拝借してくる。冒頭の256バイトが欲しいので、cutで切り出す。

[ob: z]$ cut -c1-256 MYDB | head -1 > bi.txt

cutは最後に勝手に行末文字を付けてくれるので、ファイルサイズとしては257文字になる。次は、学習用のデータだな。

[ob: z]$ find / | head -4 > fl.txt

余り多くても、持て余しちゃうので、こんなもんにした。

[ob: z]$ cat fl.txt
/
/bsd
/bsd.rd
/usr

そして、自前のDBを作成。動作確認をしておこう。ちゃんと動く事を確認して足場を固めておかなと、折角の作業が無駄になるからね。EXCELの余計なお世話を思い出して、気を引き締めて行こう。

[ob: z]$ ./locate.code bi.txt < fl.txt  > OUT
[ob: z]$ locate -d OUT rd
/bsd.rd
[ob: z]$ locate -d OUT r
/bsd.rd
/usr

どうやら、動いているっぽい。記念にダンプしておくかな。

[ob: z]$ hexdump -C OUT
00000000  6e 74 65 73 72 69 74 6f  70 6f 73 69 72 79 52 65  |ntesritoposiryRe|
00000010  2f 45 2f 43 56 53 6c 65  69 6e 66 69 6b 65 4d 61  |/E/CVSleinfikeMa|
00000020  73 74 64 69 2e 70 66 6f  70 61 2e 63 49 53 44 45  |stdi.pfopa.cISDE|
00000030  53 43 50 4c 74 63 2e 68  6e 67 72 65 66 2e 65 72  |SCPLtc.hngref.er|
00000040  74 65 2e 33 67 7a 68 65  70 6b 70 63 73 2e 6f 6e  |te.3gzhepkpcs.on|
00000050  6c 69 5f 63 63 6f 74 2e  65 2e 6d 61 68 2d 64 65  |li_ccot.e.mah-de|
00000060  6b 67 72 2e 65 6e 73 65  70 6e 6f 72 70 79 69 6c  |kgr.ensepnorpyil|
00000070  6c 2e 61 74 74 69 32 2e  65 5f 6d 65 31 2e 61 72  |l.atti2.e_me1.ar|
00000080  6c 6f 72 61 6d 6c 70 6c  34 2e 74 61 6e 66 5f 69  |loramlpl4.tanf_i|
00000090  65 6c 74 5f 61 6c 73 5f  75 74 69 74 67 2e 6f 62  |elt_als_utitg.ob|
000000a0  74 72 73 68 64 2e 72 6f  6e 65 33 2e 70 65 69 6f  |trshd.rone3.peio|
000000b0  65 78 6e 2e 6e 64 69 67  61 73 76 65 6f 75 63 61  |exn.ndigasveouca|
000000c0  6d 70 69 73 63 5f 70 2e  69 63 2e 74 6c 61 6d 6f  |mpisc_p.ic.tlamo|
000000d0  67 65 63 68 68 74 6f 70  61 63 74 68 70 72 70 70  |gechhtopacthprpp|
000000e0  6f 6f 63 2e 72 74 72 73  61 6e 2e 67 63 74 75 72  |ooc.rtrsan.gctur|
000000f0  76 61 61 6b 75 6e 61 64  30 2e 73 63 65 74 6f 63  |vaakunad0.scetoc|
00000100  0e 2f 0f 62 73 64 11 2e  72 64 0b 75 73 72        |./.bsd..rd.usr|
0000010e

ファイルオフセット100からが、追加したfl.txtだな。どうも頭にコントロールバイトが付いているようなので、整理してみる。

0e    /      /          0
0f    bsd    /bsd       1
11    .rd    /bsd.rd    3
0b    usr    /usr       -3

３つの列。一番左がコントロールバイト（とおぼしきもの）、真ん中がそれに続く文字列、一番右が、オリジナル。こう整理してみても、ピンとこないな。

上の方で、大事な定数としてOFFSETが14になってたな。これを16進にすると、0e。オフセットだから、その数を引いたものを、更に右に追加するか。面倒なので、上に追加した。

所で、14がオフセットって意味深。昔のunixは、ファイル名の長さが14だったような。探してみた。 Comparison of file systems

unix v6がそうだな。util.cに興味深いコメントが有った。

/*
 * Read integer from stream.
 *
 * Convert network byte order to host byte order if necessary.
 * So we can read on FreeBSD/i386 (little endian) a locate database
 * which was built on SunOS/sparc (big endian).
 */

SunOSの元は、v7あたりに行き着くのかな。

HISTORY
     The locate command appeared in 4.4BSD.

こういうのが、manに有ったぞ。昔の名残がそのまま残ってるっぽい。

余談に走っちゃったけど、code.cってのは、bigram.cに似てるね。今度は、少し骨のあるやつ。最初は、出来上がったBDの可変部分

00000100  0e 2f 76 bf 2f 63 ec a3  2f 66 a7 9a a7 8d 67 2f  |./v./c../f....g/|
00000110  66 32 32 33 30 39 62 32  33 38 31 33 34 64 33 63  |f22309b238134d3c|
00000120  df 36 33 34 33 35 66 35  32 38 39 37 36 63 64 2d  |.63435f528976cd-|
00000130  6c 65 33 32 64 38 2e df  e9 65 2d 34 19 73 61 6d  |le32d8...e-4.sam|
00000140  62 61 08 73 61 73 6c 32  10 6d 62 61 11 2f 70 82  |ba.sasl2.mba./p.|
00000150  f8 a0 05 95 d1 72 63 0f  ee 6f 66 b7 65 0d 73 79  |.....rc..of.e.sy|
00000160  73 0e 62 6f 6f 74 0e 77  69 6e                    |s.boot.win|
0000016a

こちらは、その元データ。

[ob: z]$ tail MYDB.txt
/var/cache/fontconfig/f22309b238134d3cca63435f528976cd-le32d8.cache-4
/var/cache/samba
/var/sasl2
/var/samba
/var/samba/private
/.cshrc
/.profile
/sys
/boot
/win

よく考えたら、謎のOFFSETが14ってのをファイル名の最大長に結びつけたのは、こじつけっぽく思えてきた。

最後にDBに纏め上げるプログラムが、locate.codeって名前。codeって暗号とも取れる。そう解釈すると、ASCIIの表示可能文字(32-127)はそのまま扱いましょう。それ以外の数値は、(人を惑わず)追加文字として扱いましょう。

よく表れる2文字の組(bigramと言うんだった)を原文から128組取り出して、それをインデックス番号で呼ぶ事にすれば、2文字を1文字(byte)に圧縮出来る。その１文字は、数値として128-255で表す事にしよう。

そうすると、残りの範囲は、0-31になる。30と31に特別な意味を持たせたんで、残りは0-28。前の行との差分位置って事で、時としてマイナスもあろう。 1バイトの範囲でマイナス表現を導入しちゃうと、先のインデックスの使用が破綻する。よって、28の半分の14だけ、下駄を履かせる事にした。これで、プラス・マイナス14の範囲を表せるようになった。

こういう暗号方式なんだね。危なく、誤解する所だったよ。

DBの統計データ

locateで使うDBは、工夫して圧縮してる。どれぐらい寄与してるか統計情報を出して、どーだ、凄いだろうって悦に入るオプションが用意されてた。最初は、シンプルなやつ。後のものは、骨のありそうなDBである。

[ob: z]$ locate -S -d OUT

Database: OUT
Compression: Front: 70.00%, Bigram: 100.00%, Total: 70.00%
Filenames: 4, Characters: 20, Database size: 270
Bigram characters: 0, Integers: 0, 8-Bit characters: 0

[ob: z]$ locate -S -d z

Database: z
Compression: Front: 75.93%, Bigram: 95.30%, Total: 65.43%
Filenames: 10, Characters: 162, Database size: 362
Bigram characters: 17, Integers: 0, 8-Bit characters: 0

Linuxでは、どうよ？

Fedoraで確認してみた。updatedbは何処？

[sakae@fedora ~]$ locate updatedb
/etc/updatedb.conf
/etc/systemd/system/timers.target.wants/mlocate-updatedb.timer
/usr/bin/updatedb
/usr/lib/systemd/system/mlocate-updatedb.service
/usr/lib/systemd/system/mlocate-updatedb.timer
/usr/libexec/mlocate-run-updatedb
/usr/share/augeas/lenses/dist/updatedb.aug
/usr/share/man/man5/updatedb.conf.5.gz
/usr/share/man/man8/updatedb.8.gz
/usr/share/vim/vim74/ftplugin/updatedb.vim
/usr/share/vim/vim74/syntax/updatedb.vim
/var/lib/systemd/timers/stamp-mlocate-updatedb.timer

BSD系と違って、普通の場所にありますなあ。confファイルが有ったので確認。

[sakae@fedora ~]$ cat /etc/updatedb.conf
PRUNE_BIND_MOUNTS = "yes"
PRUNEFS = "9p afs anon_inodefs auto autofs bdev binfmt_misc cgroup cifs coda configfs cpuset debugfs devpts ecryptfs exofs fuse fuse.sshfs fusectl gfs gfs2 gpfs hugetlbfs inotifyfs iso9660 jffs2 lustre mqueue ncpfs nfs nfs4 nfsd pipefs proc ramfs rootfs rpc_pipefs securityfs selinuxfs sfs sockfs sysfs tmpfs ubifs udf usbfs ceph fuse.ceph"
PRUNENAMES = ".git .hg .svn .bzr .arch-ids {arch} CVS"
PRUNEPATHS = "/afs /media /mnt /net /sfs /tmp /udev /var/cache/ccache /var/lib/yum/yumdb /var/lib/dnf/yumdb /var/spool/cups /var/spool/squid /var/tmp /var/lib/ceph"

DBに載せないものを、色々な形で指定出来るんだな。9pなんてファイルシステムが、除外リストに入ってるよ。その他、ゴミが溜まる所も無視の方向なのね。

スナップショットをバンバン取る運用をしてる某サイトで、locate.dbが2Gにも肥大する事例が報告されてたけど、除外リストに追加したそうな。

[sakae@fedora ~]$ locate * | wc
  71187   71187 4818594
[sakae@fedora ~]$ locate '*' | wc
 261698  261708 15453224
[sakae@fedora ~]$ locate / | wc
 261698  261708 15453224

shellのワイルドカードの使い方には、注意！（って、オイラーだけ？）

ねたばらし

ググル様を見てたら、 C言語系/「デーモン君のソース探検」読書メモ/05, locate(1)なんてのを見つけた。先にこれを見ておけば、苦労しなかったのに、後の祭りである。

永らく続いてきた、短期間のEMITも目的が達成したので、これで終了。これからは、通常の週一回ベースのアップデートに戻る予定