用于处理大量数据的节省空间的算法-猫眼课题宝

用于处理大量数据的节省空间的算法

批准号：

16092222

负责人：

定兼邦彦

金额：

$8.32万

依托单位：

Kyushu University

依托单位国家：

日本

项目类别：

Grant-in-Aid for Scientific Research on Priority Areas

财政年份：

2004

资助国家：

日本

项目状态：

已结题

起止时间：

2004 至 2007

来源：

https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16092222/

关键词：

領域計算量グラフ探索簡潔データ構造データ圧縮エントロピースケールフリーグラフ逆探索情報検索データ構造接尾辞配列圧縮接尾辞配列文字列検索文字列圧縮省スペースオンラインアルゴリズム Web検索並列化

项目摘要

项目成果

定兼邦彦的其他基金

相似基金

相关文献

中文摘要

翻译

点击翻译按钮获取中文摘要

英文摘要

本研究では大量データ処理のための領域効率の良いアルゴリズムの開発を行った.大量データ処理を行う際の問題点としては,処理時間だけではなく,データの格納やアルゴリズムの動作に必要な記憶領域の大きさがある.よって本研究では領域効率の良いアルゴリズムの開発に重点を置き,以下のアブローチを行った.(1)データを圧縮する:データ自身やデータ構造を圧縮して保存する簡潔データ構造を開発し,少ないメモリで大量のデータを扱えるようにした.(2)データの一部分のみをメモリに格納するアルゴリズム:全体のデータ量は多いが,同時にはその限られた部分のデータのみを使用するようなアルゴリズムならば限られたメモリでも動作する.本研究では特に,グラフの探索を行う省スペースアルゴリズムを開発した.その結果,大量データ処理のための基礎となるアルゴリズムとデータ構造を開発できた.全てのデータは文字列とみなす事ができる.その文字列の長さをn,文字のアルファベットサイズをσとすると,データの圧縮前のサイズはnlog_2 σビットとなる.通常のデータ圧縮法ではこの文字列をnH_k+o(n log σ)ビットに圧縮するが,その一部分のみアクセスしたい場合でも圧縮されたデータ全体を復元する必要がある.本研究の圧縮法では,圧縮された文字列の任意の部分を高速に復元できる.具体的には,文字列中の位置が指定されたとき,その位置から始まる部分文字列で長さがlog nビットのものを定数時間で復元することができる.圧縮サイズはnH_k+o(n log σ)ビットであり従来法と漸近的に等しい.

期刊论文(44)

专著(0)

科研奖励(0)

会议论文