似てる、似てない？

知人が初めて海外旅行へ行くそうだ。行こうとしてた所は中国。でも、この所の騒ぎで人気が なくなり、（団体の）募集人数が集まらずに旅行中止になったらしい。それで別の行き先を 見つけたとか。東南アジアらしい。近場なら台湾とか韓国もあると思うんだけど、二の舞は いやよってんで、少々値が張るけど奮発したそうな。気持ち分かるなあ、いさんでパスポートを 手に入れ、スーツケースも買ったのに、それが役に立たないんじゃ意気消沈だもの。

観光、買い物？ どっちが主目的なんでしょうかね。日本じゃ手に入らない怪しい物を買ってきたりして。 何しろ、あちらはコピー天国ですからなあ。目抜き通りで白昼堂々と、偽物時計あるよ、偽物バック 彼女にお土産ね、って随分声を掛けられたものだ。気の弱い人だと、買わされちゃうかも？

Windows8の海賊版はもう出てるのだろうか？ マックのリテール版なら欲しいぞ。病気と言うか ウィルスが入ってる可能性があるから、止めとけ。それよりかの知人、やんちゃな人なので、 変な病気を貰ってこないか、心配だったりします。

コピー製品を水際で摘発して回収する、あの人達はどうやって見分けているのだろう？ おどおどした人は挙動で怪しいって分かるだろうけど、本物そっくりに作られている偽物は 見分ける点などを、周知徹底してるんだろうな？

似てる、似てないって言うと、アプルとサムスンの特許問題もあるな。こちらはその判定いかん によっては、死活問題になりかねないので大変だ。（はたで見てる分には面白いけど） 最終的には裁判官の判定で決まるけど、微妙な政治的圧力があったりして。

似てる、似てないは、まだまだあるぞ。よく指名手配の人が捕まるけど、これは一般市民の 感性と勇気の賜物だなあ。ああ、たまには賞金稼ぎもいるか。後は監視カメラですかねぇ。 膨大な人の中から特定な人を炙り出すって、とても人力では間に合わないだろう。監視 カメラの発売元が裏（でもないか）プログラムとして売ってるのかな。

まあ、こういう物騒な似てる、似てない話は置いておいて、生まれた赤ちゃんが、どっちに似てる ってのは、ほほえましいな。 眼はおとうさん似、鼻はおかあさん似って、どちらにも似てるよって言っておけば、問題ないからね。 間違っても、眼は隣の旦那さんにそっくりなんて（たとえ思っていても）言ってはいけません。 それが、大人の対応ってもんです。

似てる雰囲気

似てる、似てないがちょっと気になったので、どんな技術が使われるか調べてみたよ。 専門用語的には、類似とか類似度とか言うんですね。特許の類似性とかで、ぼろぼろと 出てきたよ。世の中、金にからんだ話には敏感なのね。

盗作とかが大問題になったりして。音楽なんかも、今度リリースされた曲、昔に流行った あの曲に似てない？ なんて、話題になるし。。。

類似楽曲検索システムを作ろうなんて 事をやってる方がいました。この方は音だけじゃなくて、画像関係でも同様な試みを されているんですね。

与えられたデータ（音、画像等）から、特徴を抽出して、それで類似度を判定してるんだ。 尼ゾンの余計なお節介（おいらは、尼嫌いなんでお節介を受けた事は無いけど）、こんな本を 買った人は、あんな本も刈っていますって、勝ってる戦略だな。根底を詳しく書いた本として 『集合知インアクション』なんてのが、リコメンドされてたよ。これぞ、金になる技術だな。

おいらも、似てる、似てないに手を出すか

金になる技術ったら、競馬の予想だけじゃないんだな。そなら、おいらも手出ししてみたい。 はて、対象領域は何にする。

うろうろしてたら、ツイターで、 こんな事をほざいている人がいた。 昔は、宿題を写させてもらって、写し間違いが先公にバレ、写すんならちゃんと写そうねって、 思いっきり嫌味を言われたなあ。今じゃ、それがコピペに進化してるから、写し間違いは無い。 敵は知的に対抗してきたって事か。

だったら、敵を欺けばいいんだな。それには敵の武器を良く知る事だ。Schemeを深く理解 するには、自分で実装してみるに限るってのがあるけど、それと同じ理屈。

おいらみたいな需要はきっとあるはず。すでにそういう武器は有るに違いないって方針で 探してみると、 リファクタリングのお供に。ソースコードの類似点を検索する なんてのが、見つかった。こういうのは、悪者に対抗する為の武器と言うより、平和的な利用 目的で作られてるんだな。世の中、棄てたもんじゃないな。

折角見つけたんだから試してみたいぞ。検体と言うかソースは何にする。３秒考えて、以前にやった jot.cのコードが良かろう。私の予想では、

NetBSD  ---> OpenBSD ---> FreeBSD
   +-------> Linux

のような関係があろうと思うからだ。jotの始まりはNetBSDで、そのコードがいろいろなOSに 移植されたって事を表してる。今現在、NwtBSD、FreeBSD、Linux上のjot.cは所有してるけど、 OpenBSDはまだだな。ちょっと遠回りして、OpenBSDを入れるか。（別に入れなくても、src.tar.gzを 落としてきて、そこから展開とかすればいいんだけど、物はついでって言葉も有るでしょ）

OpenBSD

入れてみた。面倒なので、全てデフォな設定。あれ？ NICの設定どうするんだっけな？ NICって事で、ifconfigのSee Also見たら、/etc/hostname.ifって書いてあったんで、 hostname.vic0ってファイルを作って、dhcp とだけ書いておいたよ。vicなんて面白い名前のNIC だな。

ついでにXも上げて、xfce4も動かすようにしとこう。X -configureで作ったファイルのドライバーを vesaに変更するだけで、1280x768の解像度になってくれたよ。

xfce4はメタパッケージになっていないので、関係者を入れてくのが面倒。カタログを作って 、そこから入れちゃえ。以前、カタログ作るのにちょと苦労したんで、今度は簡単に。

w3m -dump http://ftp.jaist.ac.jp/pub/OpenBSD/5.1/packages/i386/ | cut -c 6-40 >CATLOG
export PKG_PATH=http://ftp.jaist.ac.jp/pub/OpenBSD/5.1/packages/i386/
pkg_add `grep xfce4 CATLOG`

これであらかた入るので、後は手動で、xfdesktop、xfwm4、xfwm4-themes、gtk-xfce-engineあたりを入れて あげる。

$ cat .xinitrc
xfwm4 &
startxfce4

起動はこんなのを作ってからstartx。本当は、startxfce4だけで動くはずなんだけど、何故かxfwm4 が上がっていなかったんで、追加してる。都合よく、 最新のデスクトップ環境、スマホの普及で大幅刷新 なんてのが、参考になった。(本当は、archでxfce4が動いてる時のps結果とdiffしたんだけどね)

ready

これでPython製、リファクタリング支援ツールを使う準備が整った。舞台装置が豪華でないと 動かないみたいだ。wxpytonが必要なんですって！ wxpythonは幸いな事にWindows７に入って いたので、そこで動かしてみた。

コピペの疑いがある所が、赤くなったよ。類似度を表すスコアも出てきた。折角のツールなんだ けど、どうも落ち着かないな。ソースを読んでどうなってるか知りたいぞ。ソース一式を俯瞰 してみたけど、本質がGUIに隠れちゃってて、掻き分けてくのが面倒そう。

やっぱり、自分で作ってみるか。どうやって？ ヒントを貰いにぐぐる先生の所へ。

ソースコードの類似度

難しい式が出て来るのは、頭が痛くなりそうななので敬遠しましょ。groovy語で書かれた ソースコード同士の類似性評価ツールを作ってみた なんてのを見つけたよ。

groovy語、よう知らん。他に同様事例が無いかと探したら、 圧縮プログラムでテキスト間の類似性を測る なんてのを発見。これならスクリプトに落とせるな。やってみよう。

#!/bin/sh

list='N.c O.c F.c L.c'

runlength(){
  cat $a $a > aa$$
  cat $a $b > ab$$

  aaS=`wc -c aa$$ | cut -c 1-8`
  abS=`wc -c ab$$ | cut -c 1-8`

  aaZ=`gzip -c aa$$ | wc -c | cut -c 1-8`
  abZ=`gzip -c ab$$ | wc -c | cut -c 1-8`

  res=`echo "scale=4; ($abZ / $abS) / ($aaZ / $aaS)" | bc`
  rm -f aa$$ ab$$
}

for a in $list
do
  for b in $list
  do
    runlength
    echo $res $a $b
  done
done

gzipがstdinを受け付けてくれないので、一度ファイルに落とす必要が有り、ちょいと気分が 悪い。まあ、ファイルの圧縮ソフトだからしょうがないのか。ああ、N.cとかは、各OSから持って きたjot.cのファイルを、OS名の一文字目に改名したものです。各ファイルの属性は 次の通り

[sakae@secd ~/z]$ wc *c
     493    1887   11975 F.c
     421    1475    9340 L.c
     399    1526    9434 N.c
     446    1642   10274 O.c

NetBSDが一番小さいオリジナル。FreeBSDが一番肥大化してる。で、折角作ったスクリプトの 一発芸です。

[sakae@secd ~/z]$ ./dif.sh | sort -nr
1.5416 F.c N.c
1.5393 O.c N.c
1.5212 L.c N.c
1.4959 F.c L.c
1.4250 L.c F.c
1.4242 O.c L.c
1.4240 N.c L.c
1.3790 N.c O.c
1.3766 N.c F.c
1.3687 L.c O.c
1.2590 F.c O.c
1.2589 O.c F.c
1.0000 O.c O.c
1.0000 N.c N.c
1.0000 L.c L.c
1.0000 F.c F.c

結果の見方は、オリジナルのHPにも書いてあるけど、数字の大きい方が差異が強烈って事です。 FreeBSDとOpenBSDは良く似てるって事で、進化の近縁にいると認めてあげましょう。

一番離れていると思われるのは、FreeBSDとNetBSDなんですが、どちらからどちらを見るかに よって、大きく差が出ています。退化する事には大きな抵抗があるんでしょうか？ いまだに 人間は猿から進化したって事を頑として認めようとしない、あの派の人達みたいに。。。

diff方式

上のrunlength方式は、アイデアに感心しましたよ。おいらみたいな凡人は、違ってる所が 多いのは似てない証拠と思っちゃうぞ。ストレートにね。違ってる所ったら、そりゃdiffでしょ。 みんなgitとかでお世話になってるね。

dif(){
  abS=`cat $a $b | wc -l | cut -c 1-8`
  abD=`diff -bBiw $a $b | wc -l | cut -c 1-8`
  res=` echo "scale=1; 100 * $abD / $abS" | bc`
}

違いを分かる評価関数だけを示す。変更が多いと、diffの出力行数も多くなるでしょって理論。 diffのごちゃごちゃしたオプションは、空行とかの余分な違いをなるべく無視する為に入れた。 本当は、if-elseとかのスタイルを統一（以前にやった、indentを使う）してから、比較するのが 好いと思う。得られた差分の行数を、比較したファイル２つのファイルの行数を足したもので割って、一応、正規化してる。 上に出てきた、母艦のdif.shに組み込んで使う。

[sakae@secd ~/z]$ ./dif.sh | sort -nr
76.8 L.c N.c
76.6 L.c F.c
76.5 N.c L.c
76.4 O.c N.c
76.4 F.c L.c
76.3 N.c O.c
75.7 N.c F.c
75.5 F.c N.c
63.6 O.c L.c
63.6 L.c O.c
48.2 F.c O.c
48.0 O.c F.c
0.0 O.c O.c
0.0 N.c N.c
0.0 L.c L.c
0.0 F.c F.c

今度は、どちらから、どちらのファイルを見てもほぼ一緒な結果だな。良く似てるのは、FreeBSDとOpenBSDか。 先祖(のNetBSD)と各世代の差が大きいのが特徴かな。

小さな差

上の結果で、同じファイルをdiffしたにも関わらず、小さな差があるのは何故だろう？ 75セントのコンピュータ利用料金の差からとんでもない事を炙りだした実録小説 カッコウはコンピュータに卵を産む の主人公の気分になっちゃうじゃないですか。

調べるなら、diffの差をもう一度diffしてみるってのが上等手段だと思うけど、それを手がかりに diffの深い森に立ち入るのは必須だろう。おいらには荷が重い。期待した人、ごめんなさい。 代わりといっちゃ何だけど、おいら流のdiffを思い付いたんで、披露しよう。

まずは、基礎実験だな。いきなり実装ってのは疲労するからな。

[sakae@secd ~]$ irb
irb(main):001:0> a = %w(aa bb cc dd ee ff)
=> ["aa", "bb", "cc", "dd", "ee", "ff"]
irb(main):002:0> b = %w(bb cc dd ee ff gg)
=> ["bb", "cc", "dd", "ee", "ff", "gg"]
irb(main):003:0> a & b
=> ["bb", "cc", "dd", "ee", "ff"]
irb(main):004:0> a - b
=> ["aa"]
irb(main):005:0> b - a
=> ["gg"]

まあ、matzさん一家に頑張ってもらおうって訳。そして、おいらも頑張ってrubyのコードを shellスクリプトの中に埋め込んでみたんだが、旨く結果がshell側に戻ってこない。 しょうがないので、埋め込みは諦めた。（悪足掻きの内容も載せておきますね。）

mydifX(){   ## Don't work this code, env at FreeBSD + ruby 1.9.3
  res=`ruby -e '<<EORUBY
    a=[]; b=[]
    open(ARGV[0]){|f| a = f.readlines }
    open(ARGV[1]){|f| b = f.readlines }
    abS = a.size + b.size
    abD = (a - b).size
    baD = (b - a).size
    printf("%.2f\n", (100.0 * (abD + baD) / abS))
EORUBY' $a $b `
}

mydif(){
  res=` ruby mydif.rb $a $b`
}

結果はどうなったかと言うと

[sakae@secd ~/z]$ ./dif.sh | sort -nr
56.95 N.c L.c
56.95 L.c N.c
54.08 O.c N.c
54.08 N.c O.c
53.06 L.c F.c
53.06 F.c L.c
52.13 N.c F.c
52.13 F.c N.c
45.67 O.c L.c
45.67 L.c O.c
29.39 O.c F.c
29.39 F.c O.c
0.00 O.c O.c
0.00 N.c N.c
0.00 L.c L.c
0.00 F.c F.c

うん、これで微妙な差は無くなったな。でも、本物のdiffを使った方式とは大きな差が出てる。 本方式の方がdiff式より小さめに出てるのは、余計な(diffからの)制御情報をカウントしていないからだな。

騙されないで

上記３種の比較方式、コピペする時とかに、エディターで、変数名とか関数名を書き換える。 無用なコメントを追加して、行数を水増しするとかの、悪徳SEがいたりすると、もう無力に なってしまう。厚化粧にコロッと騙されてしまう訳だ。こういうのを見破る方法は無いもの だろうか？

今、ふと思ったね。どんなブスでも美人でも、食べて、消化して糞をする。プログラムだって、 データを入力して、計算して、出力する。うんと細かい部分はライブラリーを呼び出して行う。 このライブラリーの呼び出しをしないプログラムって、超変態じゃない限り無いよね。

だったら、このライブラリーの呼び出し状況から、プログラムが似てる、似てないの判定は 出来ないものだろうか？ これなら、関数名の付け替えとか、コメントの水増しとかは 関係なくなるな。

ライブラリーの呼び出しをトレースするなら、ltraceが有るけど、これを動かすには、ソースから コンパイルして実行ファイルになっていなければならない。基本的には、そのソースがコンパイル 出来る環境が入るって事で、あちこちから集めてきたものには不適だ。

変数名より、関数に注目すれば、ctags -x とかが使えそうだけど、はて、出て くるかな？

[sakae@secd ~/z]$ ctags -x F.c
BEGIN_DEF         63 F.c              #define   BEGIN_DEF
ENDER_DEF         64 F.c              #define   ENDER_DEF
 :
format            82 F.c              static char       format[
getformat        390 F.c              getformat(
getprec          369 F.c              getprec(
intdata           78 F.c              static bool       intdata;
is_default        73 F.c              #define   is_default(
longdata          77 F.c              static bool       longdata;
main              90 F.c              main(
nosign            80 F.c              static bool       nosign;
prec              76 F.c              static int        prec
putdata          321 F.c              putdata(
sccsid            38 F.c              static char sccsid[
sepstring         81 F.c              static const      char *sepstring
usage            356 F.c              usage(

残念、潜って行ってくれないよ。うろうろしてたら、やはり同じ考えの人が居た。 プログラムの類似度計算 なんて事をやっている。

はて、どうすべ？ ずっと考えていたら、うまい方法を思いついた。でも、この余白はそれを 書くには狭すぎる。

一度、言ってみたかったんだ。 フェルマーさん みたいに。