前编码字符串字典：快速紧凑的索引字符串集

这是一个 Rust 库，用于存储索引字符串集并支持快速查询。该数据结构是一个平面前编码字符串字典，由 Martínez-Prieto 等人，实用压缩字符串字典，INFOSYS 2016 中描述。

日语描述

功能

• 索引集。 Fcsd 以压缩格式实现字符串的索引集。集中的 n 个字符串按字典顺序用整数 [0..n-1] 索引并分配。
• 简单快速的压缩/解压缩。 Fcsd 通过 前编码，一种针对字符串的差分压缩技术，在压缩空间中维护字符串集，允许快速解压缩操作。
• 随机访问。 Fcsd 通过桶化技术维护字符串，可以直接解压缩任意字符串并对字符串执行二分搜索。

示例

use fcsd::Set;

// Input string keys should be sorted and unique.
let keys = ["ICDM", "ICML", "SIGIR", "SIGKDD", "SIGMOD"];

// Builds an indexed set.
let set = Set::new(keys).unwrap();
assert_eq!(set.len(), keys.len());

// Gets indexes associated with given keys.
let mut locator = set.locator();
assert_eq!(locator.run(b"ICML"), Some(1));
assert_eq!(locator.run(b"SIGMOD"), Some(4));
assert_eq!(locator.run(b"SIGSPATIAL"), None);

// Decodes string keys from given indexes.
let mut decoder = set.decoder();
assert_eq!(decoder.run(0), b"ICDM".to_vec());
assert_eq!(decoder.run(3), b"SIGKDD".to_vec());

// Enumerates indexes and keys stored in the set.
let mut iter = set.iter();
assert_eq!(iter.next(), Some((0, b"ICDM".to_vec())));
assert_eq!(iter.next(), Some((1, b"ICML".to_vec())));
assert_eq!(iter.next(), Some((2, b"SIGIR".to_vec())));
assert_eq!(iter.next(), Some((3, b"SIGKDD".to_vec())));
assert_eq!(iter.next(), Some((4, b"SIGMOD".to_vec())));
assert_eq!(iter.next(), None);

// Enumerates indexes and keys starting with a prefix.
let mut iter = set.predictive_iter(b"SIG");
assert_eq!(iter.next(), Some((2, b"SIGIR".to_vec())));
assert_eq!(iter.next(), Some((3, b"SIGKDD".to_vec())));
assert_eq!(iter.next(), Some((4, b"SIGMOD".to_vec())));
assert_eq!(iter.next(), None);

// Serialization / Deserialization
let mut data = Vec::<u8>::new();
set.serialize_into(&mut data).unwrap();
assert_eq!(data.len(), set.size_in_bytes());
let other = Set::deserialize_from(&data[..]).unwrap();
assert_eq!(data.len(), other.size_in_bytes());

待办事项

• 添加基准测试代码。
• 添加 RePair 压缩变体。

许可

本库是免费软件，根据 MIT 许可证提供。