たつをの ChangeLog : 2009-10-20

iPhone とかケータイから使うことを念頭においたアマゾン検索サービスを作りました。

- aak50 search - アマゾン検索結果50件をコンパクト表示
http://aak50.ta2o.net/search.cgi


裏で Amazon API (PAAPI) を使ってキーワードでアマゾン検索しているだけですが、検索結果はタイトルのみ50件一気に表示されるというのが唯一の特徴なのです。
どうぞご利用ください。



Revilist (ttp://revilist.net/)もそうでしたが、最近はユーザに見せる情報・機能を最小にするというミニマム思想で物作りを行っています。

情報過多の今日この頃、どんなツールでも搭載機能は「必要最小限」が望まれていると思います。というか、リッチな機能やインターフェースにウンザリしているのは何を隠そうこの私なのです。自分で使いたいからミニマムなものを作ってるわけで。
aak50 search もまさにその流れなのです。

先週の土曜日、JR恵比寿駅の東口改札の内側にあるうどんやさんでランチ。



朝食を食べてなかったのであげものをついつい取っちゃいました。
「うどんであっさり」のつもりが結構ボリュームのある昼御飯になりました。まあ、いいか。



あと、うどんを食べるためにわざわざ入場券で入った人には「トッピング1品無料サービス」だそうです。
これは良いですね。

渋谷駅構内の連絡通路の壁に小さい新聞がいっぱい！
抜き取って持って行っちゃうことができます。



朝日新聞の広告ですね。
こういうのってついつい手に取っちゃいますよね。

よくあるトラブルなのでまとめておく。
suffix を文字列比較でソートするという単純な方法で Suffix Arrays を作るSUFARYでのトラブルについて。

- SUFARY 臨時復旧ページ
http://ta2o.net/tools/sufary/

ちなみに Suffix Array の作成ロジック（もっとも簡単なやつ）はこんな感じ(C言語です)：

#include <fcntl.h> 
#include <malloc.h> 
#include <stdio.h> 
#include <sys/mman.h> 
#include <sys/stat.h> 
#include <sys/types.h> 
/* usage: sufsort1 text > text.suf */ 
char *text; 
suffix_compare(int *a, int *b) 
{ 
  return strcmp(text + *a, text + *b); 
} 
main(int ac, char **av) 
{ 
  struct stat stat_buf; 
  int N, i, *suf; 
  FILE *fd = fopen(av[1], "r"); 
  fstat(fileno(fd), &stat_buf); 
  N = stat_buf.st_size; 
  text = (char *)malloc(N+1); 
  fread(text, sizeof(char), N, fd); 
  text[N] = 0; /* pad with null */ 
  suf = (int *)malloc(N * sizeof(int)); 
  for(i=0;i<N;i++) suf[i] = i; 
  qsort(suf, N, sizeof(int), suffix_compare); 
  fwrite(suf, N, sizeof(int), stdout); 
} 

(http://ta2o.net/doc/pub/dron-sa.pdf)

ここでは、原因と解決方法について述べる。

例えば000001-100000までの5桁IDを持つ10万件のデータ（10万行のテキスト）があるとする。

000001 六本木
000002 呼吸
...
099999 鰻
100000 札幌

改行文字も含めた各行の平均バイト数が15だとすると全体で150万バイト(1.5M)のテキストデータとなる。

もし何かの間違いでこのデータを二回コピペしたテキストファイルを作ってしまったとする。

000001 六本木
000002 呼吸
...
099999 鰻
100000 札幌
000001 六本木
000002 呼吸
...
099999 鰻
100000 札幌

このテキストに対してsuffix arrayを作るとなると、先頭からの suffix と、1,500,001バイト目からの suffix の文字列比較が行われる可能性が高い。
それはつまり、先頭から150万バイト同じで最後だけ異なる文字列の比較である。
常識的に考えて(JK)、これはやたらめったらと時間がかかる。
それがやっとこさ終わったとしても、先頭から2番目からの suffix と 1,500,002バイト目からの…（以下略）。
そして、先頭から3番目からの suffix と 1,500,003バイト目からの…（以下略）。
というわけで、これが「いつまでたっても終わらないよー！」の原因。

この場合の解決法は簡単で、事前にテキストファイルをソートするだけ。

sort original.txt > new.txt

または、ついでに重複除去して、

sort -u original.txt > new.txt

をコマンドラインで実行して、
new.txt に対して suffix array を作成する。

たまたまパンを持っていたので、駐車場にいたハトに餌としてあげました。
わらわらと寄って来ます。
てんやわんやの大パニックです。



しかし、この後、衝撃的なできごとが！
（続かない）

ref.
- [を] 鳩サブレーなクリップ[2009-10-02-5]