ユビキタス環境におけるダブル配列を用いた検索データベースの圧縮法に関する研究

普适环境下双数组搜索数据库压缩方法研究

基本信息

批准号：
17700116
负责人：
泓田正雄
金额：
$ 0.9万
依托单位：
The University of Tokushima
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2006
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17700116/
关键词：
キー検索辞書データベースダブル配列トライ圧縮

项目摘要

ダブル配列をトライの深さごとに分割し,その分割したブロックの開始位置からの距離をBASE値とすることにより圧縮する手法のデータ構造とアルゴリズムを提案した.本手法を用いて,現在までに研究されている圧縮手法をさらに圧縮できることを確認した.1.トライの深さごとにブロックに分割を行った.各ブロックのBASE値を,次のブロックの開始位置からの距離とすることにより,各BASE値を小さくすることができ,BASE配列を圧縮することができた.2.分割したブロックのサイズが異なることに着目し,ダブル配列の2式を次のブロックとの大きさの割合をBASE値にかける次の式に変更することにより.さらにBASE値を小さく出来た.t=s*r[d] + BASE[d][s] + CODE[c]t - s*r[d] = CHECK[d+1][t]ここでrは次のブロックとの大きさの割合.dは,トライの深さを表す.3.1,2の手法を実現したまま,CHECK値に遷移した文字を格納し,CHECK配列を圧縮できることを確認した.4.上記のアルゴリズムをコンピュータ上で実現し,できるだけBASEの値が小さくなるように,試行錯誤を繰り返し,キーの追加アルゴリズムを改善した.5.特許記事から抽出した数百万件に及ぶキー集合を登録し圧縮率を求めた.また,従来のダブル配列,17年度の手法との圧縮率,速度の比較実験を行った.

我们提出了一种通过将双数组划分为特里结构深度并使用距每个划分块的起始位置的距离作为BASE值来压缩双数组的数据结构和算法，我们证实正在研究的压缩方法可以进一步压缩1。我们将试验分为每个深度的块，每个块的 BASE 值为。通过设置距块起始位置的距离，可以使每个BASE值变小，从而可以压缩BASE数组。 2． 2代入下面的公式，将BASE值乘以下一个块的大小比例，我们可以进一步减小BASE值。t=s*r[d] + 基址[d][s] + 代码[c]t - s*r[d] = CHECK[d+1][t]这里，r是大小与下一个块的比例。d代表try的深度。在实现3.1和2的方法时，过渡到CHECK值的字符是确认CHECK数组可以被压缩。4.上述算法在计算机上执行。为了尽可能降低BASE值，我们通过反复试错改进了密钥添加算法。 5.我们注册了一组从专利文章中提取的数百万个密钥并计算了压缩率。与传统双阵列方法和2017方法的压缩比和速度进行比较。