抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
キーワード辞書とは文字列をキーとする連想配列であり,文字列集合を保管するためのデータ構造として古くから用いられている。一方で近年,このキーワード辞書を用いて大規模な文字列データを主記憶で管理するといった実例が数多く報告されており,メモリ効率の良い実装が求められている。現在のところ,静的用途に限定すれば数多くの実装が高いメモリ効率を達成している。しかし,それらに比べて既存の動的な実装は遥かに多くのメモリを消費する。そこで本稿では,Path Decompositionを用いたメモリ効率の良い動的キーワード辞書の実装法を提案する。Path Decompositionとは本来,キャッシュフレンドリーなTrie辞書を実装するために用いられる技法であるが,本提案では省メモリな動的辞書を実現するためにこの技法を用いる。大規模な現実のデータセットを用いた実験により,提案手法は既存の最もメモリ効率の良い実装と比べ,最大で2.8倍もコンパクトに動的辞書を実現できることを示す。(著者抄録)