1. HOME
  2. ブログ
  3. IT技術
  4. 【後編】トリプルアレイで軽量で高速な辞書をつくる~実装~

【後編】トリプルアレイで軽量で高速な辞書をつくる~実装~

【後半】軽量で高速に検索できる辞書システムをつくる

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

今回は、トリプルアレイを用いて、軽量で高速に検索できる辞書システムを実装していきます。

前回の記事はこちら

トリプルアレイ実装(構築部分)

Trieクラスからトリプルアレイを構築する make_triple_array() を実装していきます。

このメソッドは、trieのノードに一つずつ以下の処理を適応することで、3つの配列を構築していきます。

  1. 要素がぶつからないずらし幅を見つける(find_offset)
  2. 見つかったずらし幅で、3つの配列に挿入する(update_arraies)
  3. NEXTの長さが足りない場合は、倍に増やす(resize_arraies)

コード

基本的には、1ノードずつずらし幅を見つけて(find_offset)挿入する(update_arraies)だけなので、トリプルアレイの仕組みが理解できていれば問題ないと思います。

コード中にかなり詳しくコメントを書いたので参考にしてください。

トリプルアレイ実装(検索部分)

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

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

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

トリプルアレイの実装(全体)

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

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

コード

トリプルアレイの構築、検索

最後に、トリプルアレイの構築、検索を行います。

結果

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

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

終わりに

お疲れさまでした。

トリプルアレイは、ダブルアレイに比べると簡単ですが、それでもきちんと理解するのは難しいかもしれません。

それでも、一度きちんと実装してみれば、必ず理解できるはずです。

また、トリプルアレイさえ理解できれば、ダブルアレイの理解も簡単になるので、ぜひチャレンジしてみてください。

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

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

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

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

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

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

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

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

採用情報はこちら

関連記事