解決

　よくよくみると、DoubleArrayというのは非常に密なデータ構造だ。実際に計測してみると、普通に辞書として単語を登録していくと、99.95%ぐらいの要素にはデータが詰まっている。ということは、ひとつ前を探索する際にも空き要素を先頭から手繰っていく方が速い、という事じゃないか。
　というわけで、そのように変更すると、約9万語の登録に200秒近くかかっていたのが45秒程度にまで圧縮された。4倍以上の高速化である。