文字列圧縮と組合せ論による大規模データ管理・処理技法の開発
使用字符串压缩和组合学开发大规模数据管理和处理技术
基本信息
- 批准号:18F18120
- 负责人:
- 金额:$ 0.9万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for JSPS Fellows
- 财政年份:2018
- 资助国家:日本
- 起止时间:2018-10-12 至 2021-03-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
The focus of this research was set on (a) practical and dynamic trie data structures, (b) the computation of the grammar compression Re-Pair in small space, and (c) advancements for the bijective Burrows-Wheeler transform (BBWT), a variant of the Burrows-Wheeler transform (BWT) well received in theory as well as in practice for indexing string data.(a) We have devised a novel approach for compact hashing, which is the most memory-efficient approach in practice when working with a huge number of integer keys of a bounded domain. Based on this approach, we have proposed dynamic trie data structures working with path-decomposition or with trie compaction.(b) Re-Pair, a grammar with high compression ratios, is difficult to compute within limited amount of memory. Here, we could find a quadratic time algorithm computing Re-Pair with almost no additional space. We also devised an index data structure build upon a grammar representing the Lyndon tree. This index exploits several properties of the Lyndon words to improve the running time of the currently fastest grammar index from a quadratic factor on the pattern length to a linear one.(c) Finally, we could build an indexing data structure on top of the BBWT, compute the BBWT in-place or transform the BWT into the BBWT, and finally build the BBWT in linear time.Asides from that, we could find space-efficient factorization algorithms for the non-overlapping LZ77 factorization and the LZ78 substring compression problem. These algorithms work in near-linear time with space asymptotic to the input text length in bits.
这项研究的重点是(a)实用和动态的 trie 数据结构,(b)小空间中语法压缩 Re-Pair 的计算,以及(c)双射 Burrows-Wheeler 变换(BBWT)的进展, Burrows-Wheeler 变换 (BWT) 的一种变体,在理论上和实践中都广受好评,用于索引字符串数据。(a) 我们设计了一种新颖的紧凑散列方法,这是实践中内存效率最高的方法当处理有界域的大量整数键时。基于这种方法,我们提出了与路径分解或trie压缩一起使用的动态trie数据结构。(b)Re-Pair是一种具有高压缩比的语法,很难在有限的内存量内进行计算。在这里,我们可以找到一种几乎不需要额外空间即可计算 Re-Pair 的二次时间算法。我们还设计了一种基于表示 Lyndon 树的语法的索引数据结构。该索引利用 Lyndon 词的几个属性来改进当前最快语法索引的运行时间,从模式长度的二次因子变为线性因子。(c) 最后,我们可以在 BBWT 之上构建索引数据结构,就地计算 BBWT 或将 BWT 转换为 BBWT,最后在线性时间内构建 BBWT。除此之外,我们还可以找到用于非重叠 LZ77 分解的空间高效分解算法以及LZ78子串压缩问题。这些算法在近线性时间内工作,空间渐近于输入文本长度(以位为单位)。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Re-Pair in Small Space
小空间重新配对
- DOI:10.3390/a14010005
- 发表时间:2020
- 期刊:
- 影响因子:2.3
- 作者:Dominik Koeppl;Tomohiro I;Isamu Furuya;Yoshimasa Takabatake;Kensuke Sakai;Keisuke Goto,
- 通讯作者:Keisuke Goto,
Dynamic Path-Decomposed Tries
动态路径分解尝试
- DOI:10.1145/3418033
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Tsuruta Kazuya;Koppl Dominik;Kanda Shunsuke;Nakashima Yuto;Inenaga Shunsuke;Bannai Hideo;Takeda Masayuki;Shunsuke Kanda and Dominik Koeppl and Yasuo Tabei and Kazuhiro Morita and Masao Fuketa
- 通讯作者:Shunsuke Kanda and Dominik Koeppl and Yasuo Tabei and Kazuhiro Morita and Masao Fuketa
Bidirectional Text Compression in External Memory
外部存储器中的双向文本压缩
- DOI:
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:Patrick Dinklage;Jonas Ellert;Johannes Fischer;Dominik Koeppl;Manuel Penschuck
- 通讯作者:Manuel Penschuck
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
稲永 俊介其他文献
負電荷脂質を含有する油滴小球への脂溶性薬物担持と物性評価
含负电荷脂质油滴上的脂溶性药物负载及物理性质评价
- DOI:
- 发表时间:
2006 - 期刊:
- 影响因子:0
- 作者:
稲永 俊介;宗 慶太郎;武岡 真司;土田 英俊 - 通讯作者:
土田 英俊
Serpentine minerals from Irikura, Oita Prefecture, Japan
产自日本大分县入仓的蛇纹石矿物
- DOI:
- 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
中島 祐人;稲永 俊介;坂内 英夫;竹田 正幸;加藤隆文;長谷川亮太・山口飛鳥・福地里菜・石川剛志・北村有迅;延寿 里美 - 通讯作者:
延寿 里美
日向沖南海トラフ前弧域の浅部活構造
日向附近南海海槽弧前区的浅层活动构造
- DOI:
- 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
中島 祐人;稲永 俊介;坂内 英夫;竹田 正幸;加藤隆文;長谷川亮太・山口飛鳥・福地里菜・石川剛志・北村有迅;延寿 里美;加藤隆文;加藤隆文;山口飛鳥・新井和乃・池原研・金松敏也・福地里菜・中村恭之・宇佐美和子・奥津なつみ・清家弘治・芦寿一郎;加藤隆文;山口飛鳥・福地里菜・濱橋真理・清水真由子・江口大賀・金川久一;Takafumi Kato;加藤隆文;芦寿一郎・山口飛鳥・福地里菜・大出晃弘・奥津なつみ・田淵優・池原研 - 通讯作者:
芦寿一郎・山口飛鳥・福地里菜・大出晃弘・奥津なつみ・田淵優・池原研
An Authentication Protocol with Anonymity against Service Providers and the Central Manager
针对服务提供商和中央管理器的匿名身份验证协议
- DOI:
- 发表时间:
2010 - 期刊:
- 影响因子:0
- 作者:
中村 徹;稲永 俊介;馬場 謙介;池田 大輔;安浦 寛人;Toru Nakamura;Shunsuke Inenaga;K. Baba;Daisuke Ikeda;H. Yasuura - 通讯作者:
H. Yasuura
延岡衝上断層ボーリングコア中の断層帯の化学組成分布
延冈逆冲断层钻孔核心断层带化学成分分布
- DOI:
- 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
中島 祐人;稲永 俊介;坂内 英夫;竹田 正幸;加藤隆文;長谷川亮太・山口飛鳥・福地里菜・石川剛志・北村有迅 - 通讯作者:
長谷川亮太・山口飛鳥・福地里菜・石川剛志・北村有迅
稲永 俊介的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('稲永 俊介', 18)}}的其他基金
広義文字列のアルゴリズムと組合せ論
宽字符串算法和组合数学
- 批准号:
23K24808 - 财政年份:2024
- 资助金额:
$ 0.9万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
感度と圧縮率を両立するデータ圧縮法の創出とその限界解明
创建同时实现灵敏度和压缩率的数据压缩方法,并阐明其局限性
- 批准号:
23K18466 - 财政年份:2023
- 资助金额:
$ 0.9万 - 项目类别:
Grant-in-Aid for Challenging Research (Exploratory)
広義文字列のアルゴリズムと組合せ論
宽字符串算法和组合数学
- 批准号:
22H03551 - 财政年份:2022
- 资助金额:
$ 0.9万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
相似国自然基金
地表与大气层顶短波辐射多分量一体化遥感反演算法研究
- 批准号:42371342
- 批准年份:2023
- 资助金额:52 万元
- 项目类别:面上项目
高速铁路柔性列车运行图集成优化模型及对偶分解算法
- 批准号:72361020
- 批准年份:2023
- 资助金额:27 万元
- 项目类别:地区科学基金项目
随机密度泛函理论的算法设计和分析
- 批准号:12371431
- 批准年份:2023
- 资助金额:43.5 万元
- 项目类别:面上项目
基于全息交通数据的高速公路大型货车运行风险识别算法及主动干预方法研究
- 批准号:52372329
- 批准年份:2023
- 资助金额:49 万元
- 项目类别:面上项目
高效非完全信息对抗性团队博弈求解算法研究
- 批准号:62376073
- 批准年份:2023
- 资助金额:51 万元
- 项目类别:面上项目
相似海外基金
Elements: Advanced Lossless and Lossy Compression Algorithms for netCDF Datasets in Earth and Engineering Sciences (CANDEE)
元素:地球与工程科学中 netCDF 数据集的高级无损和有损压缩算法 (CANDEE)
- 批准号:
2004993 - 财政年份:2020
- 资助金额:
$ 0.9万 - 项目类别:
Standard Grant
New Trends in Transform-based Lossless Compression Algorithms
基于变换的无损压缩算法的新趋势
- 批准号:
17K00004 - 财政年份:2017
- 资助金额:
$ 0.9万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Research on Adaptive Lossless Data Compression -The Context Tree Weighting Method with a Finite Window-
自适应无损数据压缩研究-有限窗口上下文树加权方法-
- 批准号:
13650400 - 财政年份:2001
- 资助金额:
$ 0.9万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Efficient Algorithms for Lossless Data and Image Compression
无损数据和图像压缩的高效算法
- 批准号:
0122293 - 财政年份:2001
- 资助金额:
$ 0.9万 - 项目类别:
Standard Grant
Study of Sort-Based Data Compression Algorithms
基于排序的数据压缩算法研究
- 批准号:
11680339 - 财政年份:1999
- 资助金额:
$ 0.9万 - 项目类别:
Grant-in-Aid for Scientific Research (C)