Suffix Arrays の構築がいつまでたっても終わらない問題
2009-10-20-4
[Algorithm]
よくあるトラブルなのでまとめておく。
suffix を文字列比較でソートするという単純な方法で Suffix Arrays を作るSUFARYでのトラブルについて。
- SUFARY 臨時復旧ページ
http://ta2o.net/tools/sufary/
ちなみに Suffix Array の作成ロジック(もっとも簡単なやつ)はこんな感じ(C言語です):
ここでは、原因と解決方法について述べる。
例えば000001-100000までの5桁IDを持つ10万件のデータ(10万行のテキスト)があるとする。
もし何かの間違いでこのデータを二回コピペしたテキストファイルを作ってしまったとする。
このテキストに対してsuffix arrayを作るとなると、先頭からの suffix と、1,500,001バイト目からの suffix の文字列比較が行われる可能性が高い。
それはつまり、先頭から150万バイト同じで最後だけ異なる文字列の比較である。
常識的に考えて(JK)、これはやたらめったらと時間がかかる。
それがやっとこさ終わったとしても、先頭から2番目からの suffix と 1,500,002バイト目からの…(以下略)。
そして、先頭から3番目からの suffix と 1,500,003バイト目からの…(以下略)。
というわけで、これが「いつまでたっても終わらないよー!」の原因。
この場合の解決法は簡単で、事前にテキストファイルをソートするだけ。
new.txt に対して suffix array を作成する。
suffix を文字列比較でソートするという単純な方法で Suffix Arrays を作るSUFARYでのトラブルについて。
- SUFARY 臨時復旧ページ
http://ta2o.net/tools/sufary/
ちなみに Suffix Array の作成ロジック(もっとも簡単なやつ)はこんな感じ(C言語です):
(http://ta2o.net/doc/pub/dron-sa.pdf)#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); }
ここでは、原因と解決方法について述べる。
例えば000001-100000までの5桁IDを持つ10万件のデータ(10万行のテキスト)があるとする。
改行文字も含めた各行の平均バイト数が15だとすると全体で150万バイト(1.5M)のテキストデータとなる。000001 六本木 000002 呼吸 ... 099999 鰻 100000 札幌
もし何かの間違いでこのデータを二回コピペしたテキストファイルを作ってしまったとする。
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 を作成する。