こんにちは。白ヤギコーポレーション、エンジニアの乗松です。

この度、Go言語で実装されたダブル配列ライブラリを公開しましたのでお知らせします。

https://github.com/shiroyagicorp/double_array

何に使うもの？

ある文字列があらかじめ定義した集合に含まれているかどうか判定するときに使います。

ダブル配列って何？

Trieの効率的な実装方法です。
詳細は https://www.slideshare.net/s5yata/dsirnlp-04s5yata によくまとめられています。

特徴

• 文字ベース (runeベース) のtrieです。byteベースのtrieに比べてメモリ使用量が小さくなります。ただし構築に時間がかかります。
• データ構造をシリアライズできます。フォーマットはMessagePackです。

なぜ作ったのか

私の趣味です。

…というのは半分冗談ですが、本当の所はGoで書かれたtrie実装でプロダクションで使えそうなものを見つけられませんでした。
(「ここにあるよ！」というのをご存知の方がいらっしゃいましたら教えて下さい。)

いくつかのリポジトリを拝見しましたがリポジトリによっては数年放置されていたり、
起動しなかったり、実装の基礎(だと私が思っているもの)が押さえられていなかったりしていました。

今回の実装は「静的なTrieをGoで扱いたいんだけど…(でも自前実装したくない)」という需要に応えるものです。

中身はごくごく普通のダブル配列実装です。特に凝ったことや難しいこと、新しい手法の開発などはしていません。

他の実装との比較

とはいえ他の実装とどう違うのか確認しておきましょう。
比較対象は godarts です。
(https://github.com/awsong/go-darts の方が実装の筋は良いような気がしましたが使い方を間違えているのか起動しませんでした)

実験には全国に存在する法人のうち、5文字以上の法人名の集合を使いました。
このデータセットには 2,109,909種類の法人名が含まれています。

このデータセットでビルドすると、ダブル配列の配列長は以下のようになります。

go-darts: 12,516,574
弊社実装: 6,803,126

約半分です。

ただし構築時間はgo-dartsの方が速いです。

go-darts: 19秒
弊社実装: 24秒

使い方

exampleディレクトリに解説つきの例を入れていますのでご覧ください。

ありそうなQ&A

Key-Value store的な使い方はできない？

弊社のユースケースでは不要だったため未実装です。ごめんなさい。

もっと効率のいいダブル配列のビルド法、沢山あると思うんだけど

多くの高速なビルド法は256分岐trieを想定しており文字ベースtrieでの実装は結構大変です。
また、業務上、数十秒でビルドできるならそれで十分でした。

動的な更新は？

未対応です。

バグを見つけました

PRお待ちしております。