2. ダブル配列(Double Array)とは • トライ木の実装方法の一つ • トライ木とは? • 大語彙で前方一致検索を高速に行うことが可能なデータ構造 • 例えば形態素解析、かな漢字変換で利用される • どこが単語の始まりでどこが単語の終わりかわからない時に有用 ハッシュテーブルを使ってルックアップする方法の場合 単語境界がわからないので一文字づつ文字数を増やしてルックアップするしかない 最後までいったら開始点を1文字ずらして再度ルックアップ O(n^2) (入力文字数がn) わ た し の な ま え は な か の で す 。 ・・・ 3. ダブル配列(Double Array)とは • トライ木の実装方法の一つ • トライ木とは? • 大語彙で前方一致検索を高速に行うことが可能なデータ構造 • 例えば形態素解析、かな漢字変換で利用される • どこが単語の始
![ダブル配列の実装方法](https://cdn-ak-scissors.b.st-hatena.com/image/square/f6d66f4abb6700a0a08e2a014f9b416cbf9c24d7/height=288;version=1;width=512/https%3A%2F%2Fcdn.slidesharecdn.com%2Fss_thumbnails%2Frandom-110731112237-phpapp02-thumbnail.jpg%3Fwidth%3D640%26height%3D640%26fit%3Dbounds)