ScalazのBKTreeを触ってみる

Scala

Scalaz Advent Calendarの7日目の記事になります。遅刻しましたごめんなさい＞＜

論文を読んだわけでもScalaがバリバリ書けるわけでもないので、間違っていたら突っ込みいれてください。

Scalazで木構造といえば

scalaz.coreの中には少なくとも3つの木構造が存在します（(自分が確認できていないだけでもっとあるかもしれません)）。

  1. Tree(いわゆるRose Tree)
  2. FingerTree(おそらく2-3 finger tree)
  3. BKTree

今回はこのうちBKTreeを触ってみます。残りの2つは某カレンダーの2周目3周目が回ってきたら核かもしれません。

BK-treeってなーに？

BK-treeはmetric treeの一種です。metric treeとは、indexを距離空間を使って構成する木構造です。距離空間は…数学の話に突入するので割愛しますが、何かしらのデータ間の距離に関する理論です、たぶん。
【12/10追記】コメント欄にcocoatomoさんのわかりやすい簡潔な説明があります
BK-treeは距離が定義されているデータであれば要素として扱えます。一つ目に追加した要素がrootになり、それ以降の要素は、既にTreeに登録された各要素との距離を計算しながら登録されます。BK-tree内に既に距離が同じ要素が登録されている場合は、実装に使われている内部のデータ構造に依存します。ただ、Haskell、Scalaz、FSharpxの実装ではIntMapを利用しているので、たぶん重複登録できません。

簡単にメソッドを眺める

ScalazのBKTreeには、以下のpublicメソッドが存在します。

  • BKTreeに要素を追加する+
  • 他のBKTreeを合成する++
  • BKTreeから要素を削除する-
  • 他のBKTreeに存在する要素を一括削除する--
  • 要素数を返すsize
  • BKTree空かどうかを判定するisEmpty
  • 各要素に関数fを適用するmap
  • BKTreeの全要素をListとして返すvalues
  • BKTree内に指定した要素が含まれるか調べるcontainsとそのaliasの-?-
  • 指定した要素もしくは指定した要素との距離がn以内の要素が存在するか調べるcontainsApproximateとそのaliasの=?=
  • 指定した要素もしくは指定した要素との距離がn以内の要素をListとして取得するvaluesApproximateとそのaliasの|=|

使ってみる

簡単にですが、ScalazのBKTreeを使ってみましょう。
ちなみに、IntとStringの距離空間(MetricSpace)はScalaz内で実装されているので、scalazをimportすればすぐ使えます。


要素の登録は空のBKTreeに+で追加するか、初期データを一括で渡して生成するかです。

// 以下の最終結果は等価
BKTree[String] + "a" + "b" + "c"
BKTree[String]("a","b","c")
BKTree[String](List("a","b","c"): _*)

次に、距離が2以内の要素一覧を取得してみましょう。

BKTree[String]("kitten", "setting", "getting") |=| ("sitting", 2) // must_== List("setting", "getting")
BKTree[String]("スカラちゃん", "スカラたん", "スカラ", "すから") |=| ("スカラ", 2) // must_== List("スカラたん", "スカラ")

ちゃんと日本語も解釈できます。

最後に、距離が2以内の要素が存在するかどうかと、一致するものが存在するかの違いを見てみましょう。

BKTree[String]("kitten", "setting", "getting") -?- "sitting" // must beFalse
BKTree[String]("kitten", "setting", "getting") =?= ("sitting", 2) // must beTrue

このように、-?-の場合はfalseですが、=?=の場合はtrueが返るのがわかると思います。

余談

先月まで-と--メソッドが存在しませんでした。えー、と思いつつScala基礎勉強会でそのことを愚痴っていたら「ならpull request送ればいいと思いますよ」という至極真っ当な助言をいただいたので、送って取り込んでもらいました。

Add remove method to BKTree by pocketberserker · Pull Request #189 · scalaz/scalaz · GitHub

コメント欄の会話が地味に面白いです。


というわけで、Scalaz初心者でもテスト書いて実装して真っ当な変更だと認識されれば取り込んでもらえます。