連載モノ 5ﾚﾝｼﾞｬｰ - c⌒っ_д

なんかノリ気に書いてた割には勢いあまってソースコードなんて書いた瞬間にやる気が減退した＝ｗ＝;
少しヒートダウンしつつ、しかしながらTrieを実装しないと･･･んーむｗ

Trie(トライ)

Trieと書いてトライと読む。Tryではないのだ。
木構造の一種だが、一つのノードか幾つも枝があるのが特徴だ。
フォルダ構造なんかがこれにあたるんじゃないかと。

そう、フォルダと例えると非常にわかりやすいかもしれない。
たとえば私の論文のデータは

/home/noya/paper/zogojuacg/

に入っている。
これは初期状態(ルート)から→home→noya→paper→zogojuacgと移動したことを示すわけだ。

これを捨て牌に当てはめればよいではないか。
おお、別にソースコードなんて書かなくてもきれいに説明できた。
これでモチベーションも保てるというわけだ

とはいえこんなに身近にあるデータ構造なのにTrieなんて誰も使いやしない。
大抵木構造といえば2分木で、なんかかっこいい名前がついてるやつと言えばB木*1とかそんなやつだ
Trieで有名なのって言ったらPatricia Trie位だろう。
なんで誰も使わないんだろう?

まぁ使用メモリ量が多いからでしょう。
ちょうどPatricia Trieが出てきたから英単語の出現頻度をカウントすることを考えてみよう。
たとえばnoyaという単語をn→o→y→aとMapして、そこの数字を+1すればいい。
さて、あくまでHashを知らないという初心者さんならこれを実装しろと言われたらどんな感じに実装してくれるだろう
ちょっと気分でCで書いてみるか･･･久しぶりだからスーパー間違いそうだけどｗ

typedef struct TriePointer{
	int counter;
	struct Trie* nodeA;
	...
	struct Trie* nodeZ;
}Trie;

void putTrie(Trie* trie, char* term){
	len = strlen(term); //get length of term
	if (len==0){
		trie.count++;
	}
	else {
		switch (*term){	//*term means term[0]
		case a:
			putTrie(trie.nodeA, term+1);
			break;
			...
		}
	}
}
		
int main (int argc, char** argv){
	/**
	* mallocしねーから即死すっぞ、こんなコード書くんじゃない
	*/
	
	int cnt;
	Trie root;
	for (cnt = 1; cnt < argc; cnt++){
		putTrie(root, *(argv + cnt));
	}
}

んー、書いては見たもののmallocしねーから速攻でセグフォして死ぬと思います。
どうせ誰もこんな実装しねーと思っていい加減に書きました。だが反省はしていない。

さて、何が言いたいか。この実装でnoyaをMAPすると4層の木ができます。
そのノード数はアルファベットが26種類なのでこの４乗
26の4乗･･･26×26が難問な私が考えていい数字ではありませんね(・ω・`

実際はHash使えばかなりメモリ量を少なくできます。
*2
どうせqで始まる単語は大抵次はuなんだ。
そうじゃない単語なんてQMAくらいしか思いつかないさ(＝ｗ＝

なんて感じで鼻で笑うのは簡単。
でも、私の考えだとむしろHashを使うほうが損になります。
でもこれはまた明日。

次回予告

さぁ迫りくる16の21乗!この恐怖にどうnoyaは立ち向かうのか

どうでもいいけど

えらく趣向が変わってきたなぁ･･･

*1:N根とかそーいう隠語ではない

*2:他にも少ないメモリでがんばろうとしたのがPatriciaTrie LISPで実装したところがあったのでそっちも見てください http://www.geocities.jp/m_hiroi/clisp/clisp08.html