タグ

性能に関するdhrnameのブックマーク (1)

  • Trie TreeならびにDouble Array Trie Treeを用いたパフォーマンスの検証

    2. 1 はじめに ブログなどの大量のテキストデータが蓄積される CGM サイトでは、必然的にシステムや プログラムの中でも文字列処理の回数が多くなる。そのため効率的なアルゴリズムの採用 は、サイトのプログラム処理速度、ひいては対ユーザのページレスポンスタイムに関わる 重要な事案となる。 今回は、文字列の全文一致検索や前方一致検索処理において効率的なアルゴリズムとして 知られる「トライ木」についてそのパフォーマンスの検証を行った。 2 TrieTree について 2.1 アルゴリズムの内容 以下、トライ木についての解説を wikipedia より引用する。 トライ木(Trie)とは、順序付き木構造 (データ構造)の一種。プレフィックス木 (Prefix Tree)とも呼ばれる。キーが文字列である連想配列の実装構造として使 われる。2 分探索木と異なり、各ノードに個々のキーが格納されるのでは

    Trie TreeならびにDouble Array Trie Treeを用いたパフォーマンスの検証
  • 1