1. HOME
  2. ブログ
  3. IT技術
  4. 【後編】ダブルアレイで高速でコンパクトな辞書を実装する

【後編】ダブルアレイで高速でコンパクトな辞書を実装する

【後編】高速でコンパクトな辞書をつくる

【前編】の続きとなります。

今回は、ダブルアレイを用いて、高速でコンパクトな辞書システムを実装していきます。

前回の記事はこちら

ダブルアレイ実装(構築部分)

TripleArrayクラス から、ダブルアレイを構築する make_double_array() を実装していきます。

このメソッドは、TripleArray の NEXT、CHECK配列を書き換えることでダブルアレイを構築していきます。

トリプルアレイで、ずらす処理などは終わっているので、以下の2つの処理をすれば完了です。

1.  NEXT をノードidではなく、ずらし幅に変更して BASE を作成
2.  CHECK をノードidでなく、index に変更

コード

解説

1ループ目で TripleArray の OFFSETS から BASE を作成、また items も作成します。

さらに、後に CHECK を作成する際に、ノードid からそのノードを表す NEXT の index を得やすいように node_to_index という配列を作成しておきます。

2ループ目では、 node_to_index から新しい CHECK配列 を作成しています。

ダブルアレイ実装(検索部分)

続いて、検索を行う query()を実装していきます。

こちらは、検索文字列を一文字ずつループすることで、ダブルアレイを遷移していきます。

最後の index にたどり着いたら、items に格納されている、その index に対応する要素を返します。

コード

ダブルアレイの実装(全体)

ここまでで、ダブルアレイを用いた辞書の実装が完了です。

すべてのコードをまとめたものが以下になります。

全体のコード

構築、検索の実験

最後に、ダブルアレイの構築、検索の実験を行います。

結果

これを実行すると、以下のような結果になります。

辞書に insert した単語はきちんと読み方が「表示」され、そうでない単語は「None」となっていることがわかります。

終わりに

お疲れさまでした。

ダブルアレイを理解するのはかなり難しいかもしれませんが、非常に実用的なデータ構造です。

トリプルアレイから理解していけば、ダブルアレイも必ず理解できるようになるはずです。

ぜひチャレンジしてみてくださいね!

関連記事

ライトコードよりお知らせ

にゃんこ師匠にゃんこ師匠
システム開発のご相談やご依頼はこちら
ミツオカミツオカ
ライトコードの採用募集はこちら
にゃんこ師匠にゃんこ師匠
社長と一杯飲みながらお話してみたい方はこちら
ミツオカミツオカ
フリーランスエンジニア様の募集はこちら
にゃんこ師匠にゃんこ師匠
その他、お問い合わせはこちら
ミツオカミツオカ
   
お気軽にお問い合わせください!せっかくなので、別の記事もぜひ読んでいって下さいね!

一緒に働いてくれる仲間を募集しております!

ライトコードでは、仲間を募集しております!

当社のモットーは「好きなことを仕事にするエンジニア集団」「エンジニアによるエンジニアのための会社」。エンジニアであるあなたの「やってみたいこと」を全力で応援する会社です。

また、ライトコードは現在、急成長中!だからこそ、あなたにお任せしたいやりがいのあるお仕事は沢山あります。「コアメンバー」として活躍してくれる、あなたからのご応募をお待ちしております!

なお、ご応募の前に、「話しだけ聞いてみたい」「社内の雰囲気を知りたい」という方はこちらをご覧ください。

ライトコードでは一緒に働いていただける方を募集しております!

採用情報はこちら

書いた人はこんな人

ライトコードメディア編集部
ライトコードメディア編集部
「好きなことを仕事にするエンジニア集団」の(株)ライトコードのメディア編集部が書いている記事です。

関連記事