アルゴリズムとデータ構造連載の4日目です。

データ構造とアルゴリズムはどちらかというと独立した存在（どちらも大事）っぽく語られることが多いと思いますが、一方で、特定のアルゴリズムと組み合わせるスペシャルなデータ構造というものがあります。例えば、次の二分探索に特化して、配列の並び替えをすることで、２分探索を早くする（CPUのキャッシュに乗せやすくする）、というものとかがあります。

キャッシュフレンドリーな二分探索ーデータ構造を再考する

そのような、探索やカウントなどの特定アルゴリズムに特化しつつ、なおかつ情報理論的下限まで使用メモリを抑え、圧縮したまま利用できるようにしたデータ構造を簡潔データ構造（succinct data structure)と呼びます。新しめの研究分野かつ、日本での研究が活発らしいです。本も何冊も出ています（といっても、僕は論文をあまり読まないので詳しくはないですが）。

基本のデータ構造のビットベクトル、ウェーブレット木などの木構造などがあり、それを使った例もいろいろです。圧縮したまま検索できるということで、巨大なゲノムデータをコンピュータで扱ったり、日本語入力の大量の辞書を組み込みながらも使用メモリを減らす、といった応用例があります。全文データを定数時間で直接スキャンする（FM-index）こともでき、それを使ったブラウザで動く検索エンジンを作ったりしました。

今回は木構造のLOUDSを扱ってみようと思います。本当は自分で実装するところからやりたかったのですが、今回は次のライブラリを使ってみます。理論的なところは抜いて、まずは使ってみます。

https://github.com/hideo55/go-loudstrie

LOUDS

LOUDSというのを調べると出てくるのはこんな図です。正確にはTRIEという木構造がこれで、これの簡潔データ構造的表現がLOUDS、みたいな関係です。格納するのは単語のリストです。この木にはto、tea、ted、ten、A、in、innの６個の単語が登録されています。

図はWikipediaのTrieから引用

探索した単語を調べると、ノードのIDの数値が出てきます。単語のリストをmap（Goでは、他の言語では辞書と呼んだりhashと呼んだり)でキーを単語に、ノードIDを値に持つのと似ています。ちょびっと違うのは以下の3点

共通部分をまとめて、差分だけを子供に持つ、みたいな感じでデータ量を減らしています。
単語のノードの親を見つけることができる（mapだと全捜査が必要）
ノードの子供をまとめて取って来れる

共通部分が多いツリーであれば効果が高いということですね。

実際に試してみる

GoではLOUDSを実装しているライブラリはGitHubでは3つだけありました。そのうち、mainパッケージに全部入れているようなやつではなく、ライセンスが明記されているものは次のライブラリだけでした。

github.com/hideo55/go-loudstrie

文字列の共通部分が比較的多く出てくるものといえば住所データかな、ということで、政府CIOポータルを探して、総務省の標準地域コードが良さそうなのでこのCSVを落としてきました。コードをシンプルにするためにShiftJISはあらかじめUTF-8にして、先頭のヘッダー行は抜いておきます。

統計に用いる標準地域コード

データはこんな感じになっています。

ken-code,sityouson-code,tiiki-code,ken-name,sityouson-name1,sityouson-name2,sityouson-name3,yomigana
21,505,21505,岐阜県,加茂郡,,八百津町,やおつちょう
21,506,21506,岐阜県,加茂郡,,白川町,しらかわちょう
21,507,21507,岐阜県,加茂郡,,東白川村,ひがししらかわむら
21,520,21520,岐阜県,可児郡,,,かにぐん
21,521,21521,岐阜県,可児郡,,御嵩町,みたけちょう
21,600,21600,岐阜県,大野郡,,,おおのぐん
21,604,21604,岐阜県,大野郡,,白川村,しらかわむら
22,0,22000,静岡県,,,,しずおかけん
22,100,22100,静岡県,静岡市,,,しずおかし
22,101,22101,静岡県,静岡市,,葵区,あおいく
22,102,22102,静岡県,静岡市,,駿河区,するがく
22,103,22103,静岡県,静岡市,,清水区,しみずく
22,130,22130,静岡県,浜松市,,,はままつし
22,131,22131,静岡県,浜松市,,中区,なかく
22,132,22132,静岡県,浜松市,,東区,ひがしく
22,133,22133,静岡県,浜松市,,西区,にしく

LOUDS木を作って探索する

LOUDS木を作るコードは次の通りです。文字列のスライスを作り、それをNewTrie()に渡すだけです。

f, err := os.Open("code.csv")
if err != nil {
	log.Fatalln(err)
}
defer f.Close()
r := csv.NewReader(f)
var names []string
for {
	row, err := r.Read()
	if err != nil {
		break
	}
	names = append(names, strings.Join(row[3:7], ""))
}
t, err := loudstrie.NewTrie(names, false)

NewTrie()で作ったインスタンスにいろいろなメソッドがあります。

MarshalBinary()で[]byteに書き出せますし、NewTrieFromBinary()で[]byteから再構築ができます。高速ロードができますね。なお、130KBほどの元データでしたが、漢字の自治体名部分だけ取り出し（体感でデータ量の半数超）てLOUDSを作ったところ、32KBでした。NewTrieの2番目のデータ圧縮オプションを有効にすると25KBまで減りますが、キーを復元できなくなるので用途に応じてオンにするといいでしょう。

基本的に、探索するとIDが出てくるので、必要に応じてIDからキーを復元する、といった使い方になります。なお、IDは最初に投入したスライスのインデックスとは異なります。

探索メソッドは3つありました。

// 正確に一致
i, _ := t.ExactMatchSearch("広島県広島市")
key, _ := t.DecodeKey(i)
fmt.Println(i, key)
// 940 広島県広島市

// 前方一致
result := t.PredictiveSearch("広島県広島市", 0)
for _, item := range result {
key, _ := t.DecodeKey(item)
	fmt.Printf("ID:%d, key:%s\n", item, key)
}
// ID:940, key:広島県広島市
// ID:1535, key:広島県広島市中区
// ID:1536, key:広島県広島市佐伯区
// ID:1537, key:広島県広島市南区
// ID:2147, key:広島県広島市安佐北区
// ID:2148, key:広島県広島市安佐南区
// ID:1833, key:広島県広島市安芸区
// ID:1219, key:広島県広島市東区
// ID:1220, key:広島県広島市西区

// 親を探索
result2 := t.CommonPrefixSearch("広島県広島市中区", 10)
for _, item := range result2 {
	key, _ := t.DecodeKey(item.ID)
	fmt.Printf("ID:%d, key:%s\n", item.ID, key)
}
// ID:20, key:広島県
// ID:940, key:広島県広島市
// ID:1535, key:広島県広島市中区

漢字名をキーに、読みを検索できるようにする

内部的なノードIDがわかってもうれしくないでしょう。読みを検索できるようにします。やり方は単純で、ノードのIDを配列のインデックスと見立てて、読みが入ったスライスから取り出してくるだけです。漢字を見てノードIDを調べたら、そのIDのインデックスに、読みデータの文字列を入れます。

var names []string
tmpyomi := make(map[string]string)
var name2yomi []string

for {
	row, err := r.Read()
	if err != nil {
		break
	}
	name := strings.Join(row[3:7], "")
	names = append(names, name)
	tmpyomi[name] = row[7]
}
t, err := loudstrie.NewTrie(names, false)

if err != nil {
	log.Fatalln(err)
}
// NodeIDをキーに、読みが入っているスライス
name2yomi = make([]string, int(t.GetNumOfKeys()))

// インデックスを取り出して、それを使ってスライスに読みを入れる
for i := uint64(0); i < t.GetNumOfKeys(); i++ {
	name, _ := t.DecodeKey(i)
	name2yomi[i] = tmpyomi[name]
}

LOUDS情報を作るときはmapも駆使して優雅にメモリを使いますが、実行環境ではスライスのインデックスアクセスのみ、というストイックな実装になっています。

検索は２段階で行います。

// 読みを調べる
i, _ := t.ExactMatchSearch("広島県広島市")
log.Println(i, name2yomi[int(i)])

読み側もLOUDSにしてみる

せっかくなので読み側のデータもLOUDSにしてみます。2つのLOUDSのインデックスの対応表をスライスにします。ちなみに、データ量は３０KBでした。

var names []string
tmpyomi := make(map[string]string)
var yomis []string
var name2yomi []uint64

for {
	row, err := r.Read()
	if err != nil {
		break
	}
	name := strings.Join(row[3:7], "")
	names = append(names, name)
	tmpyomi[name] = row[7]
	yomis = append(yomis, row[7])
}
n, err := loudstrie.NewTrie(names, false) // 名前用のLOUDS
y, err := loudstrie.NewTrie(yomis, false) // 読み用のLOUDS

if err != nil {
	log.Fatalln(err)
}
// NodeIDをキーに、読みのNodeIDが入っているスライス
name2yomi = make([]uint64, int(n.GetNumOfKeys()))

// インデックスを取り出して、それを使って読みのノードIDを調べてスライスに入れる
for i := uint64(0); i < n.GetNumOfKeys(); i++ {
	name, _ := n.DecodeKey(i)
	yi, _ := y.ExactMatchSearch(tmpyomi[name])
	name2yomi[i] = yi
}

今回は調べるのは3ステップです。

// 読みを調べる
i, _ := n.ExactMatchSearch("広島県広島市")
yi := name2yomi[int(i)]
yomi, _ := y.DecodeKey(yi)
fmt.Println(yomi)
// ひろしまし

無事出ましたね。ノードのIDをキーとするスライスを用意して有効なデータをそこから取り出せるようにすれば、メタデータやその他の有用なデータをたくさん格納できますね。

まとめ

LOUDSとか簡潔データ構造は調べると数式とかが多くてどうやって使うのか、みたいな情報があまりなさそうなので、あえて深入りせずにライブラリの利用方法に限定して調べました。

メモリ効率よくデータを格納できてそのまま取り出せるというのが簡潔データ構造の魅力です。個人的には値の変更がないマスタデータなんかは、RedisやRDBや共通サービスに持たせるのではなく、こういうデータにして各サービスに配ってしまう、というのも面白いんじゃないかなと思っています。マイクロサービスを真面目に正規化して設計すると依存関係が深くなって大変になったりしますが、それを適度に非正規化するための道具として使えそうかなって。

Goの場合（Go以外でも）なかなかライブラリ数が少なく、POPCNTという、インテルやARMのSIMD命令を使った効率の良いビットベクター実装とかもあまりないのが実情。まだまだみなさんの目の前のPCのポテンシャルが眠らされている、という感じがします。僕が簡潔データ構造に夢を持つのはそのあたりです。

まあ、自力で実装しても元が取れるぐらい業務利用用途があるかというと、まだ見つけられていないのが実情です。定年したら、盆栽をいじるみたいな感じで簡潔データ構造のコードをぽちぽち実装する、みたいなのが将来の夢です。

参考

GoとSuffixArray

LOUDSをGoで試してみる

LOUDS

実際に試してみる

LOUDS木を作って探索する

漢字名をキーに、読みを検索できるようにする

読み側もLOUDSにしてみる

まとめ

参考