A compression method of double Array by deleting BASE array

一种删除BASE数组的double数组压缩方法

• 批准号: 22700101
• 负责人: FUKETA Masao
• 金额: $ 1.33万
• 依托单位: The University of Tokushima
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22700101/
• 关键词: キー検索; トライ; ダブル配列; 辞書圧縮; 可変長文字列; 固定長文字列

Double-array is a data structure to implement a trie and can retrieves keywords very fast. But the size of LOUDS is smaller than that of double-array. Double array uses two one-dimensional arrays, named BASE and CHECK. This research proposed a compression data structure of the double array by dividing trie into each depth and removing the BASE array from that double array. From experimental results, the retrieval speed was almost the same as double array, and the size of the presented method was more compact than LOUDS for a large set of keywords with fixed length.

双数组是一种实现trie的数据结构，可以非常快地检索关键字。但是LOUDS的尺寸比双阵列的尺寸小。Double array使用两个一维数组，分别命名为BASE和BASE。本研究提出一种双数组的压缩数据结构，将trie树分成不同深度，并移除双数组中的BASE数组。实验结果表明，该方法在检索速度上与双数组方法相当，而在固定长度的大量关键词集上，该方法比LOUDS方法更紧凑。

项目成果

Compression of double array structures for fixed length keywords

• DOI: 10.1016/j.ipm.2014.04.004
• 发表时间: 2014-09
• 期刊: Inf. Process. Manag.
• 作者: M. Fuketa;Hiroya Kitagawa;T. Ogawa;K. Morita;J. Aoe

New methods for compression of MP double array by compact management of suffixes

通过后缀紧凑管理MP双数组压缩的新方法

• 发表时间: 2010
• 期刊: Information Processing & Management
• 影响因子: 8.6
• 作者: 青戸了;清水敏之;吉川正俊;Tshering C.Dorji
• 通讯作者: Tshering C.Dorji