zstd实践
首先明确，所有的压缩，和不压缩比，都是cpu换带宽/硬盘。
按我对教科书huffman编码和lzma算法的了解，他们都适合对大文件的压缩，基本原理都是“给高频pattern最短路”。
数据库/数据流压缩，情景不同。操作的对象是许许多多的单行（小文件），而非一个大文件。这导致行与行之间的重复内容无法复用。
zstd可以提前编译字典，字典可以定制化。
在我们的业务数据上，能节省35%的CPU，压缩率提升63%。代价是维护字典，所以适合内网使用（否则需要客户端也参与字典的版本维护），比如我们自己跨AZ的数据搬运。
在一定范围内，字典越大，压缩越慢，压缩率越高，也需要配合更高的压缩等级。字典的体积在100k-500k之间，一般不超过1M。
zstd这个字典也有训练和测试的说法，这个不难理解。构造一个接近实际数据的字典才能有好的压缩效果。好比我们的操作手册，肯定得记录我们自己实际遇到的问题，查询的时候才能较好命中。
gzip比较老，而且是单线程的。pigz是gzip的多线程版。zstd是facebook在2016发布的，自然是支持多线程。spark从3.0开始支持ZSTD，对比默认的snappy，压缩率可以提升30%，降低存储和传输成本。
当然，刚刚提及的所有压缩算法，对hash值这种都没法压缩，因为hash的灵魂就是防碰撞，每个都是低频。hash的压缩需要考虑其它原理的方法。
命题思路
一方面是初次接触rust，一方面是实现一个类似zstd的算法。
命题思路上，我会写两个rust编译后生成的可执行程序，一个用于压缩，一个用于解压缩。
公开放出的是压缩可执行程序，字典，压缩结果。
验题时使用解压缩可执行程序，字典，压缩结果。
题目难点将是，陌生的语言，以及并无现成代码。
给输出求输入的模式，避免了flag在执行过程中在内存里出现。
flag长度准备弄长一点，避免强制破解。
rust背景
Rust 语言可以用于开发：
传统命令行程序 - Rust 编译器可以直接生成目标可执行程序，不需要任何解释程序。
Web 应用 - Rust 可以被编译成 WebAssembly，WebAssembly 是一种 JavaScript 的高效替代品。
网络服务器 - Rust 用极低的资源消耗做到安全高效，且具备很强的大规模并发处理能力。
嵌入式设备 - Rust 同时具有JavaScript的开发速度和 C 语言的执行效率，支持底层平台的开发。
编译器，rustc。
包管理，cargo。
rust的一些特征
导入用的是use，print用的是println!。
函数尾部不带分号，隐式return此表达式。
match关键字作用类似switch。
rust的异常处理
rust函数往往返回一个复合的result类型，它里面的内容可能是好消息，也可能是坏消息。
一句话一般来说以分号结尾，在分号之前加上一个问号，其实是一种match的简写，如果ok就正常返回，如果报错就返回error。
unwrap()也是异常处理，相当于把result解包，如果ok就会返回正常结果，如果出错，就panic崩溃。
具体算法逻辑
本来想自己实现zstd，
发现有点复杂，而且二手资料很少，感觉不值当。
http://www.ezcodesample.com/abs/abs_article.html
上面的链接介绍了ANS，asymmetric numeral system。zstd基于它实现。
这个链接的复杂度更适合出题。
算法理解
出现频率高的，在码表中的行数比较多，输出的bit数就少。
这一点和huffman的思路倒是很像。
精度和码表大小的关系：
码表的构造和frequency高度相关，如果想让frequency很精确的话，码表就要足够大。
妥协
上面的英文链接里有C语言实现，但我肯定不想直接用那个。
自己写的算法，解压时发现不可逆，可以有两种fetch方法。
所以我在想重新设计一下算法，使之更加简化。
每次输出时都加校验码，表示这次输出几bit。恐怕已经不能再称之为“压缩”，不过作为题目没关系。
代码
上面是编码，下面是解码。
use std::fmt::format;
use std::fs;
use std::io::Write;
use fs::File;
fn main() -> Result<(), std::io::Error>{
let array_a: [usize; 14] = [2,4,7,9,12,13,16,18,19,23,24,27,29,31];
let array_b: [usize; 10] = [3,6,8,11,14,17,21,22,26,28];
let array_c: [usize; 6] = [5,10,15,20,25,30];
let flag_path: &str = "flag.txt";
let flag = fs::read_to_string(flag_path);
// println!("Data read: {:?}", flag);
let mut state: usize= 31;
let mut binary_string = String::new();
let mut bit_string: String;
for c in flag?.chars() {
println!("before:{}", state);
let cur_len: usize;
let outputbit: &str;
let outputlen: String;
let head_two: usize = state >> 3;
let head_three: usize = state >> 2;
let head_four: usize = state >> 1;
bit_string = format!("{:b}", state);
if bit_string.len() < 5 {
bit_string = format!("{}{}", '0'.to_string().repeat(5-bit_string.len()), bit_string);
// println!("padding!");
}
let bit_str: &str = &bit_string.as_str();
match c {
'a' => cur_len = 14,
'b' => cur_len = 10,
'c' => cur_len = 6,
_ => cur_len = 99999
}
if state > cur_len {
if head_four <= cur_len {
state = head_four;
outputbit = &bit_str[4..];
outputlen = format!("01");
}
else if head_three <= cur_len {
state = head_three;
outputbit = &bit_str[3..];
outputlen = format!("10");
}
else {
state = head_two;
outputbit = &bit_str[2..];
outputlen = format!("11");
}
println!("output bits:{}", outputbit);
binary_string.push_str(outputbit);
binary_string = format!("{}{}", binary_string, outputlen);
}
else {
outputlen = format!("00");
binary_string = format!("{}{}", binary_string, outputlen);
}
println!("after output:{}", state);
match c {
'a' => state = array_a[state - 1],
'b' => state = array_b[state - 1],
'c' => state = array_c[state - 1],
_ => ()
}
}
bit_string = format!("{:b}", state);
if bit_string.len() < 5 {
bit_string = format!("{}{}", '0'.to_string().repeat(5-bit_string.len()), bit_string);
// println!("padding!");
}
println!("last state {}", state);
println!("last state {}", bit_string);
binary_string = format!("{}{}", binary_string, bit_string);
println!("{}", binary_string);
let mut byte_array: Vec<u8> = vec![binary_string.len() as u8];
let mut content: Vec<u8> = binary_string.as_bytes()
.chunks(8)
.map(|chunk| {
let bit_str = std::str::from_utf8(chunk).unwrap();
u8::from_str_radix(bit_str, 2).unwrap()
})
.collect();
byte_array.append(&mut content);
println!("{:?}", byte_array);
let mut file = File::create("output")?;
file.write_all(&byte_array)?;
file.flush()?;
Ok(())
}
use std::fs;
use std::fs::File;
use std::io::{
self, Read};
fn main() -> io::Result<()>{
let mut file = File::open("output")?;
let mut buffer: Vec<u8> = Vec::new();
file.read_to_end(&mut buffer)?;
// println!("File content as bytes: {:?}", buffer);
let length: usize = buffer[0] as usize;
// println!("length of initial bit stream: {}", length);
let mut binary_string: String = String::new();
for i in 1..buffer.len() {
let mut byte_string: String = format!("{:b}", buffer[i]);
if i < buffer.len() - 1 && byte_string.len() < 8 {
let pad: String = '0'.to_string().repeat(8-byte_string.len());
byte_string = format!("{}{}", pad, byte_string);
// println!("padding!");
}
if i == buffer.len() - 1 {
let pad: String = '0'.to_string().repeat(length - binary_string.len() - byte_string.len());
byte_string = format!("{}{}", pad, byte_string);
}
binary_string.push_str(byte_string.as_str());
}
println!("initial binary string: {}", binary_string);
assert_eq!(binary_string.len(), length, "The decoded binary string does not have the expected length.");
let array_a: [usize; 14] = [2,4,7,9,12,13,16,18,19,23,24,27,29,31];
let array_b: [usize; 10] = [3,6,8,11,14,17,21,22,26,28];
let array_c: [usize; 6] = [5,10,15,20,25,30];
let mut res: String = String::new();
let mut state_str: String = binary_string[binary_string.len()-5..binary_string.len()].to_string();
binary_string = binary_string[0..binary_string.len()-5].to_string();
let mut state: usize = u8::from_str_radix(state_str.as_str(), 2).unwrap() as usize;
while binary_string.len() > 0 {
// println!("state: {}, state_str:{}, binary string: {}", state, state_str, binary_string);
let mut symbol: char = ' ';
if let Some(index) = array_a.iter().position(|&x| x == state) {
symbol = 'a';
state = index + 1;
}
else if let Some(index) = array_b.iter().position(|&x| x == state) {
symbol = 'b';
state = index + 1;
}
else if let Some(index) = array_c.iter().position(|&x| x == state) {
symbol = 'c';
state = index + 1;
}
else {
println!("Error, not found in table, {}", state);
break;
}
state_str = format!("{:b}", state);
let mut fetch_string: String = String::new();
if state_str.len() < 5 {
// fetch几个？
let fetch_num: usize = u8::from_str_radix(&binary_string[binary_string.len()-2..], 2).unwrap() as usize;
binary_string = binary_string[0..binary_string.len()-2].to_string();
fetch_string = binary_string[(binary_string.len()-fetch_num)..binary_string.len()].to_string();
if fetch_num < 5 - state_str.len() {
state_str = format!("{}{}{}", '0'.to_string().repeat(5 - state_str.len() - fetch_num), state_str, fetch_string);
}
else {
state_str = format!("{}{}", state_str, fetch_string);
}
binary_string = binary_string[0..binary_string.len()-fetch_num].to_string();
}
if state_str.len() != 5 {
println!("state_str {}, fetch_string {}", state_str, fetch_string);
}
println!("symbol:{}, state:{}, fetch string:{}", symbol, state, fetch_string);
state = u8::from_str_radix(state_str.as_str(), 2).unwrap() as usize;
res.push(symbol as char);
}
let reversed_res: String = res.chars().rev().collect();
println!("{}", reversed_res);
Ok(())
}
