動的ダブル配列辞書における実用的な再構成法

• Item type: SIG Technical Reports(1)
• 公開日: 2016-09-06
• タイトル: 動的ダブル配列辞書における実用的な再構成法
• タイトル / 言語: en
• タイトル: Practical Rearrangement of Dynamic Double-array Dictionaries
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: データ構造
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者名: 神田, 峻介; 藤田, 勇磨; 森田, 和宏; 泓田, 正雄
• 著者名(英): Shunsuke, Kanda; Yuma, Fujita; Kazuhiro, Morita; Masao, Fuketa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ダブル配列とは，文字列をキーとする辞書を実現するために広く用いられるデータ構造である．動的辞書として利用する場合，キーの削除に伴う記憶効率の低下が問題とされてきたが，ダブル配列の再構成により，この問題が解決されることが先行研究により示されている．本稿では，従来の再構成法に関して，その実行時間が実用において問題となる点について述べ，それを改善するための新しい再構成法を提案する．1,000 万件以上のキーから構成される辞書を用いた実験により，従来手法では 2 分以上要した再構成を，提案手法では 1 秒未満でおこなえることを示す．加えて，提案手法による再構成は検索速度の向上にも繋がることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The double-array is a data structure widely used to implement dictionaries with string keys. While a previous dynamic double-array dictionary had a problem that its memory efficiency decreases with key deletion, earlier studies have solved it by rearranging the double-array. This paper describes that conventional rearrangement time becomes problematic in practice, and proposes new rearrangement methods. From experiments using a dictionary with over ten million keys, we show that our methods use less than one second for rearrangement while the conventional ones use over two minutes. In addition, we show that our rearrangement can improve search speed.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10114171
• 書誌情報: 研究報告情報基礎とアクセス技術（IFAT）; 巻 2016-IFAT-123, 号 12, p. 1-6, 発行日 2016-09-06
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8884
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会