接尾辞木（Suffix Tree）を作って高速に文字列照合する自作Javaプログラム。
再帰使いまくり。
再帰は情報科学の真髄だと思う。
情報科学ってナンデスカって聞かれたら、僕の場合「データ」と「情報」と「知識」の違いを説明して、それから再帰とか帰納とか分割統治とかの方法の威力を熱く語る。
再帰の記述能力は凄まじく、それでいてシンプルで美しい。
でも、ループで書けるところをわざわざ凝って何でも再帰で書くようになったらそれは病気だと思う。
再帰使いまくり。
import java.util.*;
public class SuffixTreeGenerator {
//すべての接尾辞
static Vector<String> all_suffixes = new Vector<String>();
//接尾辞木オートマトンのルート
static State root = new State(State.ROOT);
public static void main(String[] args) {
try {
//全ての接尾辞を取得
next_suffix(args[0]);
//接尾辞木を構成
prefix_grouping(all_suffixes, root, null, "");
//接尾辞木を表示
System.out.println("nSuffix Tree for string "" + args[0] + ""n");
root.scan(0);
System.out.println("nPattern Matching...");
//文字列照合
for(int i = 1; i <args.length; i++)<br>
System.out.println(args[i] + " : " + (root.is_subsequence(args[i]) ? "yes" : "no"));
}catch(ArrayIndexOutOfBoundsException e) {
System.out.println("使い方：java SuffxTreeGenerator text pattern0 pattern1 pattern2 ... ");
System.exit(1);
}
}
//接尾辞を得る再帰関数
static void next_suffix(String org) {
if(org.equals(""))
return;
//頭文字を取り除いた文字列で再帰
next_suffix(org.substring(1));
all_suffixes.addElement(org);
}
//接尾辞木を構成する再帰関数
static void prefix_grouping(Vector<String> suffixes, State current_state, State pre_state, String pre_key) {
Hashtable<Character, Vector<String>> prefix_map = new Hashtable<Character, Vector<String>>();
//頭文字が共通の文字列ごとに分ける
initial_letter_grouping(suffixes, prefix_map);
//木を構成（この中で再帰呼び出し）
construct_tree(prefix_map, current_state);
//枝分かれしていない枝をまとめる
if(current_state.func.size() == 1)
compress(current_state, pre_key, pre_state);
}
//枝分かれしていない枝をまとめる
static void compress(State current_state, String pre_key, State pre_state) {
String key = current_state.func.keys().nextElement();
pre_state.add_func(pre_key + key, current_state.func.get(key));
pre_state.func.remove(pre_key);
current_state.func.clear();
}
//接尾辞木を構成
static void construct_tree(Hashtable<Character, Vector<String>> prefix_map, State current_state) {
Enumeration<Character> e = prefix_map.keys();
while(e.hasMoreElements()) {
Character common_char = e.nextElement();
//共通の頭文字がなかった場合はそこから先を全部まとめる
if(prefix_map.get(common_char).size() == 1)
current_state.add_func(common_char.toString() + prefix_map.get(common_char).firstElement(), new State(State.LEAF));
//あった場合は頭文字を束ねて先を再帰
else {
State next_state = new State(State.NODE);
current_state.add_func(common_char.toString(), next_state);
prefix_map.get(common_char).removeElement("");
prefix_grouping(prefix_map.get(common_char), next_state, current_state, common_char.toString());
}
}
}
//頭文字が共通の文字列ごとに分ける
static void initial_letter_grouping(Vector<String> suffixes, Hashtable<Character, Vector<String>> prefix_map) {
Enumeration<String> e = suffixes.elements();
while(e.hasMoreElements()) {
String sequence = e.nextElement();
//頭文字をキーとして文字列のマップを作成
if(prefix_map.containsKey(sequence.charAt(0)))
prefix_map.get(sequence.charAt(0)).addElement(sequence.substring(1));
else {
Vector<String> group = new Vector<String>();
group.addElement(sequence.substring(1));
prefix_map.put(sequence.charAt(0), group);
}
}
}
}
//オートマトンの一状態
class State {
static final int ROOT = 0;
static final int NODE = 1;
static final int LEAF = 2;
//(入力系列、行き先)の組み合わせのテーブル
Hashtable<String, State> func = null;
//この状態の種類
int status;
State(int status) {
this.status = status;
if(status != State.LEAF)
this.func = new Hashtable<String, State>();
}
//行き先を追加
void add_func(String input, State destination) {
this.func.put(input, destination);
}
//構造を深さ優先でスキャン、表示
void scan(int depth) {
if(this.status == State.LEAF) {
return;
}
Enumeration<String> e = this.func.keys();
while(e.hasMoreElements()) {
String key = e.nextElement();
System.out.print(" - " + key + "t");
this.func.get(key).scan(depth + 1);
System.out.println();
for(int i = 0; i <depth; i++)<br>
System.out.print("t");
}
}
//索引構造をたどって文字列照合をする再帰関数
boolean is_subsequence(String pattern) {
boolean subseq = false;
Enumeration<String> e = this.func.keys();
while(e.hasMoreElements()) {
String key = e.nextElement();
int min_length = Math.min(key.length(), pattern.length());
if(pattern.substring(0, min_length).equals(key.substring(0, min_length))) {
if(key.length() >= pattern.length())
return true;
else if(this.func.get(key).status == State.LEAF)
return false;
else
subseq = this.func.get(key).is_subsequence(pattern.substring(min_length));
}
}
return subseq;
}
}
再帰は情報科学の真髄だと思う。
情報科学ってナンデスカって聞かれたら、僕の場合「データ」と「情報」と「知識」の違いを説明して、それから再帰とか帰納とか分割統治とかの方法の威力を熱く語る。
再帰の記述能力は凄まじく、それでいてシンプルで美しい。
でも、ループで書けるところをわざわざ凝って何でも再帰で書くようになったらそれは病気だと思う。
