2024-03-29T15:12:41Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001744862024-03-29T05:26:34Z01164:01165:08898:08899
動的ダブル配列辞書における実用的な再構成法Practical Rearrangement of Dynamic Double-array Dictionariesjpnデータ構造http://id.nii.ac.jp/1001/00174452/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=174486&item_no=1&attribute_id=1&file_no=1Copyright (c) 2016 by the Information Processing Society of Japan徳島大学大学院先端技術科学教育部徳島大学大学院先端技術科学教育部徳島大学大学院先端技術科学教育部徳島大学大学院先端技術科学教育部神田, 峻介藤田, 勇磨森田, 和宏泓田, 正雄ダブル配列とは,文字列をキーとする辞書を実現するために広く用いられるデータ構造である.動的辞書として利用する場合,キーの削除に伴う記憶効率の低下が問題とされてきたが,ダブル配列の再構成により,この問題が解決されることが先行研究により示されている.本稿では,従来の再構成法に関して,その実行時間が実用において問題となる点について述べ,それを改善するための新しい再構成法を提案する.1,000 万件以上のキーから構成される辞書を用いた実験により,従来手法では 2 分以上要した再構成を,提案手法では 1 秒未満でおこなえることを示す.加えて,提案手法による再構成は検索速度の向上にも繋がることを示す.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.AN10112482研究報告データベースシステム(DBS)2016-DBS-16312162016-09-062188-871x2016-09-05