トライ木で高速な辞書を作ってみた！ – 株式会社ライトコードトライ木で高速な辞書を作りたい！ トライ木（英: trie）というデータ構造を知ってますか？ トライ木はテキストを扱う際に良く用いられているデータ構造で、文字列を非常に高速に検索することができるため、辞書の実装などに利用されています。 本記事では、トライ木の特徴の紹介と構築方法の解説・実装を行っていきます。 最終的に単語とその読み方を入力としたトライ木を構築し、単語を入力することでその読み方を出力する辞書システムを作成します。 トライ木とは トライ木とは、上の図のようなデータ構造で、順序付き木の一つです。 この図は、例として「a」「ab」「abc」「ac」「bc」という5単語が入ったトライ木です。 ノードの左上の数字は、ノードidを表します。 id0のノードの <s> というのは先頭文字を表していて、検索の際はここからスタートします。 丸が二重になっているノードは、そのノードが単語の終端文
