古い記事
ランダムジャンプ
新しい記事
よくあるトラブルなのでまとめておく。
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 を作成する。