BK-tree を golang で実装した
先日はてぶに 興味深いデータ構造：BK木 | プログラミング | POSTD という翻訳記事 ( 元記事 http://signal-to-noise.xyz/post/bk-tree/) があがっているのをみて初めて BK-tree というものを知ったので，golang で実装してみました．
BK-tree とは
先程の記事に全部書いてあるのですが… BK-tree は，ある距離空間内で近傍点探索を効率的に行えるデータ構造です．利用例としてはスペルチェックや類似画像検索などがあります．
距離空間とは，なにかしらの距離を計算することができる空間のことで，距離としてハミング距離やマンハッタン距離，レーベンシュタイン距離，ユークリッド距離などなどが挙げられます． 例えば，いわゆる普通の 3 次元の空間は，ユークリッド距離を距離関数に持つ距離空間と考えられます．
近傍点探索は，要するにある点に対して，近くにある点を探すことです．
ものすごく単純に近傍点探索をやろうと思うと，全要素を線形に探索して距離を計算していく必要があります． そこで BK-tree を使うともっと計算量が減らせるというわけなのです．(ちなみに僕は BK-tree を使った場合の計算量がよくわかっていません．実験的に速いことを確認しただけです．正確な計算量は考えてもよくわかりませんでした…)
構造や仕組みは元記事などをご参照ください．
golang での bk-tree 実装は実はいくつかあったのですが，単純にアルゴリズムを理解するために実装したかったのと，レーベンシュタイン距離を距離関数として使うことを前提にしていたりとちょっと自分の用途に合っていない気がしたので，別で作ってみました．
このパッケージでは，スペルチェックそのものや距離関数を提供していません．BK-tree というデータ構造だけを提供しています．
使用例
16 bit 整数を要素，ハミング距離を距離関数とした例です．
要素となる型は bktree.Entry interface を満たす必要があります．これは Distance(Entry) int を要求する interface です．
本当は distance<T: Entry>(x: T) -> int みたいな形にしたいのですが，golang だと出来ないので，実装側で e.(hashValue) のように型アサーションする必要があります．
ここでは uint16 に戻してハミング距離を計算しています．
要素の追加は Add(e Entry) です．
ここでは 0 ~ 0xffff までを突っ込んでいます．
探索は Search(e Entry, tolerance int) []*Result です．
第一引数がキー，第二引数が許容する距離の最大値です．
package main import ( "fmt" "github.com/agatan/bktree" ) type hashValue uint16 // Distance calculates hamming distance. func (h hashValue) Distance(e bktree.Entry) int { a := uint16(h) b := uint16(e.(hashValue)) d := 0 var k uint16 = 1 for i := 0; i < 16; i++ { if a&k != b&k { d++ } k <<= 1 } return d } func main() { var tree bktree.BKTree // add 0x0000 to 0xffff to the tree. for i := 0; i < 0xffff; i++ { tree.Add(hashValue(i)) } // search neighbors of 0x0000 whose distances are less than or equal to 1. results := tree.Search(hashValue(0), 1) for _, result := range results { fmt.Printf("%016b (distance: %d)\n", result.Entry.(hashValue), result.Distance) } }
これを実行すると，
0000000000000000 (distance: 0) 0000000000000001 (distance: 1) 0000000000000010 (distance: 1) 0000000000000100 (distance: 1) 0000000000001000 (distance: 1) 0000000000010000 (distance: 1) 0000000000100000 (distance: 1) 0000000001000000 (distance: 1) 0000000010000000 (distance: 1) 0000000100000000 (distance: 1) 0000001000000000 (distance: 1) 0000010000000000 (distance: 1) 0000100000000000 (distance: 1) 0001000000000000 (distance: 1) 0010000000000000 (distance: 1) 0100000000000000 (distance: 1) 1000000000000000 (distance: 1)
という感じで 0x0000 とのハミング距離が 0 ~ 1 である要素がとれます．
パフォーマンス
単純な線形探索との比較をするベンチマークをおいてあります．
64 bit 整数，距離関数はハミング距離，データ量 1,000,000 件での結果が以下のようになりました．
| ベンチマーク | 実行時間 |
|---|---|
| BK-tree (完全一致) | 1108 ns/op |
| BK-tree (fuzziness 1) | 29468 ns/op |
| BK-tree (fuzziness 2) | 328753 ns/op |
| BK-tree (fuzziness 4) | 5490888 ns/op |
| BK-tree (fuzziness 8) | 68182122 ns/op |
| BK-tree (fuzziness 32) | 353715305 ns/op |
| Linear Search | 4132926 ns/op |
fuzziness が小さければ小さいほど ( = tolerance が小さければ小さいほど ) 高速に探索できることが分かります．
また，データ量が増えるほど Linear Search より有利になるので，距離に対してデータが十分に大量にある場合はかなり有効といえそうです．
おまけ
tree の構築にかかるコストがそこそこ大きかったので pprof で見つつチューニングする必要がありました． 学びとして，「map が重い」「interface が重い」というのがありました．
各ノードの部分木は，そのノードからの距離 d を key として，map[int]*Node としていました．
tree を構築する際には，allocate + read + write をかなりの回数行うのですが，これがまぁ遅い．
最終的にこの部分はスライスでもっておいて，d を key として部分木をとりたい時は線形探索をするようにしました．
next, ok := n.children[d] としていた部分が
type elem struct distance int node *node } for _, c := range n.children { if c.distance == d { return c.node } } return nil
という感じになります．あんまりきれいではないんですが，こっちの方がほとんどのケース倍以上速かったので，こちらを採用しました．
部分木の数が増えてくると，map のほうが速いと思われるのですが，ハミング距離の場合最大でも bit 数までしか部分木が増えないので．
レーベンシュタイン距離を用いたスペルチェックの場合でも，単語の最大文字数以上の距離にはなりません．
2 次元 / 3 次元程度の距離空間なら kd-tree などもっと他に良い方法があるきがするので，レーベンシュタイン距離やハミング距離を使うケースをメインに考えました．
その結果，実行時間のかなりの割合が Entry interface を介した関数呼び出しのオーバヘッドとか，inteface の allocation になってしまいました．
データ構造を golang で提供する以上このオーバヘッドは避けられないです．( もちろん BK-tree そのものを，自分の利用形態に特化して作れば回避できますが… )
ちょっと Rust や C++ で書きたくなりました．十分速いし書きやすいので良いんですが…
Rust でグラフ構造や木構造を作る
プログラムを書いていると何かしら木構造っぽいものやグラフっぽいものを作りたい場面が多々あると思います．
Rust は所有権や Size の都合で，これらを作ろうと思うと地味にハマるのでまとめておきます．
Rust で木構造
最も単純な木構造は Rust だと
enum Tree<T> { Leaf(T), Node(Box<Tree<T>>, Box<Tree<T>>), }
といった形で表せます． Rust では明示的に boxing してあげないと再帰的なデータ構造は作れないのでちょっと複雑に見えるかもしれませんが，まぁ単純です．
この木構造を書き換えたい場合は，ownership をとって書き換えた値を返すこともできますし，&mut Tree<T> をとって in-place に書き換えることもできます．
fn inc(&mut self) { match *self { Tree::Leaf(ref mut i) => *i = *i + 1, Tree::Node(ref mut left, ref mut right) => { left.inc(); right.inc(); } } } fn inc2(self) -> Tree<i32> { match self { Tree::Leaf(i) => Tree::Leaf(i + 1), Tree::Node(left, right) => Tree::Node(Box::new(left.inc2()), Box::new(right.inc2())), } }
Rust で有向非巡回グラフ
有向非巡回グラフ構造は，グラフのエッジに向きがあり，かつ循環がない構造で，これは割りと単純に表現できます．
struct Node<T>(T, Vec<Rc<Node<T>>>);
Node は自身の値 T と，つながっているノードの Vec を持ちます．(対象問題によっては Vec ではなくて HashMap とか HashSet とか)
Rc は参照カウント方式のスマートポインタです．
グラフでは，Node は複数の Node から参照される可能性があるので， Box は使えません．
これを変更可能にしたい場合はちょっと面倒ですが RefCell を使う必要があります．
Rust では基本的に mutable borrow は常にひとつしか存在できず，mutable borrow が生きている間は immutable borrow もつくることができません．
Rc から mutable な参照を取り出すこともできません．
そこで RefCell を使うことで borrow check をランタイムに行うようにします．
RefCell は immutable な参照から mutable な参照を取り出せるようにする働きをしますが，
mutable な参照を取っている間に，さらに mutable な参照を作ろうとしたり immutable な参照を作ろうとすると，ランタイムに panic します．
コンパイル時検査ではなくランタイム検査になるので，プログラマの責任できちんと管理しないと死にます．
RefCell 版がこちら
struct Node<T>(T, Vec<Rc<RefCell<Node<T>>>>); impl Node<i32> { fn inc(&mut self) { self.0 += 1; for n in &self.1 { n.borrow_mut().inc(); } } }
Rust で巡回有向グラフ
循環がある場合は厄介です．
Rust で参照を共有するための Rc は参照カウントなので，循環参照があるとリークします．
したがって循環のある構造を表すために Rc は使えません．
木構造で親を参照するポインタを子に持たせておきたいといったケースでは，親は子を Rc で持ち，子は親を Weak で持つという形で対応できますが，
グラフだとそういうわけにもいきません．
そこで出て来るのが Arena という方法です．
オブジェクトの実体は Arena の中に作り，グラフにはその ID を持たせて管理します．
type NodeId = usize; struct NodeArena<T> { arena: Vec<Node<T>>, } impl<T> NodeArena { fn alloc(&mut self, value: T) -> NodeId { let id = self.arena.len(); let node = Node(id, value, Vec::new()); self.arena.push(node); id } fn get(&self, id: NodeId) -> &Node<T> { &self.arena[id] } fn get_mut(&mut self, id: NodeId) -> &mut Node<T> { &mut self.arena[id] } } struct Node<T>(NodeId, T, Vec<NodeId>);
こんな感じです．
こうすることでコンパイル時の borrow check を諦めることなくグラフ構造を作ることができます．
(i と i+1 番目のノードを同時に mutable に参照したいとかは苦しいですが)
欠点としては単純に間接的な表現でめんどくさいというのもありますが，GC がないので参照されなくなったオブジェクトも Arena 上で生き続けてしまうことです．
そのため，動的に要素が生きたり死んだりするケースには使いにくいです．
ノードグラフの構築が終わったら Arena をリフレッシュするみたいなことをすると良いのかもしれません．
(構築中は Vec で Arena を表現して，構造が固まったら HashMap を使った Arena に切り替えて参照されているidだけを残すみたいな)
それでも構築中はオブジェクトがあまりまくるので辛いですね...
mio で echo サーバメモ
Rust の非同期 IO ライブラリのなかでももっとも低レベルなレイヤーを担っている mio を使ってecho サーバを書いた。 echo サーバばっかり書いているような気がするけど，echo サーバやっておくと簡単な割にライブラリの使い方とかがちゃんと分かる気がするので好きです。
コード
extern crate mio; use std::io::prelude::*; use std::collections::HashMap; use mio::*; use mio::tcp::{TcpListener, TcpStream}; #[derive(Debug)] struct ClientsHolder { table: HashMap<Token, TcpStream>, free_token: Vec<Token>, next_max_token: Token, } impl ClientsHolder { fn new_from(start_token: Token) -> Self { ClientsHolder { table: HashMap::new(), free_token: Vec::new(), next_max_token: start_token, } } fn next_token(&mut self) -> Token { if let Some(tok) = self.free_token.pop() { return tok; } let tok = self.next_max_token; self.next_max_token = Token(tok.0 + 1); tok } fn register(&mut self, tok: Token, client: TcpStream) { self.table.insert(tok, client); } fn get_mut(&mut self, tok: Token) -> Option<&mut TcpStream> { self.table.get_mut(&tok) } fn remove(&mut self, tok: Token) -> Option<TcpStream> { let result = self.table.remove(&tok); if result.is_some() { self.free_token.push(tok); } result } } // Setup some tokens to allow us to identify which event is // for which socket. const SERVER: Token = Token(0); fn main() { let addr = "127.0.0.1:13265".parse().unwrap(); // Setup the server socket let server = TcpListener::bind(&addr).unwrap(); // Create an poll instance let poll = Poll::new().unwrap(); // Start listening for incoming connections poll.register(&server, SERVER, Ready::readable(), PollOpt::edge()) .unwrap(); // Create storage for events let mut events = Events::with_capacity(1024); let mut clients = ClientsHolder::new_from(Token(1)); loop { poll.poll(&mut events, None).unwrap(); for event in events.iter() { match event.token() { SERVER => { // Accept and drop the socket immediately, this will close // the socket and notify the client of the EOF. let (stream, _) = server.accept().unwrap(); let tok = clients.next_token(); poll.register(&stream, tok, Ready::readable(), PollOpt::edge()).unwrap(); clients.register(tok, stream); } tok => { let mut close = false; if let Some(mut stream) = clients.get_mut(tok) { let mut buf = [0; 1024]; let n = stream.read(&mut buf).unwrap(); if n == 0 { poll.deregister(stream).unwrap(); close = true; } else { stream.write(&buf[0..n]).unwrap(); } } if close { clients.remove(tok); } } } } } }
面倒だったので unwrap まみれですが。
やったこと
mio の全体の流れとしては，Poll 型の値がイベントを監視する役割を担います．
Poll に監視対象を登録していき，Poll::poll でイベントの発火を待ちます．
発火したイベント一覧が Events 型の Events::iter で取れるので，対応していけばよいです．
mio では Token という型の値を使って監視対象を識別しています．
監視対象には TcpListener ，TcpStream，Sender，などなどいろんなものがあるので，統一的に扱うために Poll は Token だけを保持します．
Token と監視対象の紐付けはユーザ側の責任でやってくれという感じみたいです．
echo サーバではクライアントの数は不特定なので，「空いている Token を探す」と「Token に対応するクライアント (TcpStream) を探す」がうまくできる必要があります．
そこで，ClientsHolder を定義しました．
こいつが，空いている Token を返すのと Token をキーに TcpStream を返す仕事をします．
remove されたらその Token は再利用します．
気になるところ
mio はファイルに対する抽象化は提供しない方針のようです．
STDIN / STDOUT も同様です．
ファイル IO もノンブロッキングにしたい場合はどうしたらいいんでしょう？よくわかっていない．
mio::unix 以下に UNIX 限定の拡張がおいてあって，EventedFd という file descriptor を扱う実装はあるので，UNIX 限定なら力技でなんとかなるのかもしれない．
あと mio は関係ないんですが，実装の部分で，
let mut close = false; if let Some(mut stream) = clients.get_mut(tok) { let mut buf = [0; 1024]; let n = stream.read(&mut buf).unwrap(); if n == 0 { poll.deregister(stream).unwrap(); close = true; } else { stream.write(&buf[0..n]).unwrap(); } } if close { clients.remove(tok); }
というのがあるんですが，これどうやったらスマートなんでしょう．
close = true としている部分で clients.remove(tok); をやるのが普通だと思うんですが，if let Some(mut stream) = clients.get_mut(tok) { のところで clients は borrow されているから mutable borrow はこれ以上作れないのです．
NCurses の Crystal binding を作った
この記事は、 Crystal Advent Calendar 2016 の８日目の記事です。 qiita.com
ncurses という CUI を作るためにスクリーンやキー入力を扱う有名なライブラリの Crystal binding を作りました。
ほとんど C の ncurses と同じ感じで使えるようになっていると思います． Ruby や Python の curses ライブラリを参考にしつつ，なるべく使用感がかわらないようにしています．
examples
require “ncurses” NCurses.open do NCurses.cbreak NCurses.noecho NCurses.move(x: 30, y: 20) NCurses.addstr(“Hello, world!”) NCurses.refresh NCurses.notimeout(true) NCurses.getch end
NCurses.addstr とか NCurses.move とかは ncurses で言う addstr や move に当たる関数で，stdscr に対して waddstr とか wmove するやつです．
w = NCurses::Window.new(height: height, width: width) とすることで subwindow が作れます．
w.addstr や w.move という形で w prefix な関数たちが呼べるようになっています．
pad や attron / attroff などなども使えます．
詳細な例は example/ 以下のにおいてあります
なぜ作ったのか
実は ncurses bindings for Crystal はすでにあります．(https://github.com/jreinert/ncurses-crystal)
curses が Crystal の標準ライブラリから外されることが決まったときの CHANGELOG を見ると，今後はそっちを使ってねと書いてあったりします．
じゃあなんでわざわざ別で作ったのかという話ですが，API が足りない & 提供する API の形を変えたいと思ったからです．
単純に bind されている API が少なくてやりたいことができなかったので，最初は追加して PR を出そうと思っていたのですが，すでに提供されている API が割と高級になっていて 1 : 1 で C API と対応していない感じでした． 個人的には C library の wrapper にはなるべく薄くなっていてもらって基本的な API は覚え直さないでも使えるようになっていてほしいというふうに思ったので，C API と 1 : 1 で対応した形の API を提供する wrapper を作ってみようという経緯で新しく作ることにしました．
おまけ
C bindings を書くときに，wrapper API として LibC::Int が登場しちゃうのがなんとなく嫌で，LibC::Int を C が要求してくる関数を呼ぶ wrapper 関数には型指定をあえてしないという選択をしたんですがどうなんでしょう．
lib LibNCurses fun wmove(w : Window, y : LibC::Int, x : LibC::Int) : Result end
class Window def move(y, x) LibNCurses.wmove(@win, y, x) end end
みたいな感じです．（多少簡略化しています）
これどうなんですかね．なるべく外に見せる API には型を明記するようにしたかったのですが，LibC:Int 系は環境によって異なるのでそういうわけにも行かず…
y : LibC::Int, x : LibC::Int とかは別に良いんですが，ncurses は文字と属性をくっつけた chtype なる型を持っていてこれが結構厄介というか混乱を招くのではと思っています．
chtype は char ではなく unsigned int で，文字と属性を bitor でくっつけたものになっています．addch のように char をとることを連想させる関数の引数が実は chtype = unsigned int でしかも Crystal の文字型 Char は 32bit なのでものすごく混乱します…
C は型変換を勝手にやってくれるので，unsigned int を返す関数から受け取った値を short を受け取る関数に渡すみたいなことをよくやっていて，Crystal のような型変換を暗黙にやらない言語から使おうとすると難しいんだなぁと思いました．
なにか良い方法があればぜひ知りたいです．
Rust で Box に包まれた構造体の所有権分解
ちょっとはまったのでメモ
struct A { foo: Vec<i32>, bar: Vec<bool>, }
こんな構造体があったとする。
普通、A の所有権を分解して foo と bar にしたいときは
fn xxx(x: A) -> (Vec<i32>, Vec<bool>) { let A { foo, bar } = x; (foo, bar) }
とやれば良い（この例だともっと簡単に書ける気もするけど）
一方、Box<A> から foo と bar に分解したい場合は話が変わってくる。
fn error1(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
(x.foo, x.bar)
}
fn error2(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
let A { foo, bar } = *x;
(foo, bar)
}
これらは両方共コンパイルできない。
人間から見ると，Box<A> は A の所有権を持っているのだから、A -> foo/bar に分解できるなら Box<A> も同様にできる気がする。
実際にはこのようにするとコンパイルが通る。
fn success(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
let x = *x;
let A { foo, bar } = x;
(foo, bar)
}
うーん、エラーになるケースだと Deref トレイトの機能を経由している感じになるのかな？
Deref 経由で foo の所有権をとるとその時点で Box<A> の所有権は奪われちゃうから bar の所有権が取れないということなのだと想像した。
success のようなコードが突然出てきたら混乱しそうだ。
日本語の改行を適当にいい感じにするツールを作りました
必要に迫られて、HTML ページ内の改行位置をいい感じにするツールを作ってみました。
HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。
しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。
最も有名な問題として、今すぐダウンロー
ド問題が挙げられます。
japawrap を使うと、それっぽく日本語を解釈して <span> でくくるみたいなことができます。inline-block を適用すれば改行がそれっぽく入るようにできます。
Install
go get github.com/agatan/japawrap/...
で japawrap コマンドが使えるようになります。
Usage
CLI
ファイル名を指定するか標準入力から流し込みます。
$ echo "今日も元気です" | japawrap <span class="wordwrap">今日も</span><span class="wordwrap">元気です</span>
このように適宜いい感じに wrap してくれます。
オプションとして -open string と -close string をサポートしているので、
$ echo "今日も元気です" | japawrap -open '<span style="display: inline-block;">' -close "</span>" <span style="display: inline-block;">今日も</span><span style="display: inline-block;">元気です</span>
みたいなことができます。
Library
一応 japawrap はライブラリとしても使用できるようになっています。
w := japawrap.New(open, close) s := "今日も元気です" fmt.Println("%s => %s", s, w.Do(s))
これだけです。
Example
では実際に使った結果を下に記したいと思います。 文章は、上の方に自分で書いた文章をそのまま使います。
before
HTMLに長文を書くと、親DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。
after
HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。
こんな感じになります。猛烈に効果がわかりにくくて驚いていますが、一応効果はちゃんと出ているのではないでしょうか？ HTMLを直接見ていただければどうなっているかはわかると思います。
次に青空文庫から夏目漱石「こころ」の序文を抜粋してみたのが下の画像たちです。
レスポンシブ！それなりになっている気がします。
あとがき
この問題へのアプローチとして、https://github.com/google/budou が有名だと思います。
budou は Cloud Natural Language API を内部で使っていて、しっかり日本語の文章を構文解析しているようです。
なので非常に精度は高いと思うのですが、今僕の GCP アカウントがごにょごにょしていてぱぱっと試せる状況ではなかったので自作しました。
budou と違ってしっかり構文解析などはしていなくて、形態素解析した後、それっぽく分割しているだけです。なので精度は落ちると思います。
一方、budou は GCP の credentails が必要だったりと準備が必要になるので、お手軽に試せるというのは悪くないかなと思っています。
Rust の Result と Iterator
Rust には失敗するかもしれない値を表す Result<T, E> という型があります。
std::result::Result
そして iterate できることを表す Iterator という trait があります。
std::iter::Iterator
また、Iterator trait は要素型を表す関連型を持ちます。例えば
ここ間違っていました。String は Iterator<Item=char> を impl しています。これは char 型を要素にもつ Iterator であることを意味します。String が直接 Iterator を impl しているのではありませんでした。
たまに Iterator<Item=Result<T, E>> のようになっている型を見かけます（T, E にはなにかしら具体的な型が入っていると思ってください）。
例えば、std::io::stdin().bytes() の返り値である std::io::Bytes は Iterator<Item=Result<u8>> を impl しています。
（ちょっとわかりにくいのですがここでの Result は std::result::Result ではなくて std::io::Result です。std::io::Result は std::result::Result<T, std::io::Error> のエイリアスです。）
さて、このような Iterator からすべての要素が Ok(_) であれば Ok<Vec_>> を、Err(_) があれば Err<_> を返すような処理を書きたいということは割りとよくあります。
で、これを一生懸命実装しようとしていたのですが、標準ライブラリの範囲内ですでに実装されていました。べんり。
let result = std::io::stdin().bytes().collect::<Result<Vec<_>, _>>();
これだけです。これで要件を満たす Result<Vec<_>, _> が返って来ます。すばらしい。
タネは簡単な話で Result が FromIterator trait を impl しているので collect で変換が可能であるというお話でした。
std::iter::FromIterator
