var_byte_str

描述

创建一个表示`&str`的gap，然后使用可变字节编码方法进行压缩。该实现受到这篇gap文章和这篇文章的启发。

原理

主要思想是，使用UTF-8表示泰语字符串代价高昂。每个字符需要3个字节。由于大多数情况下，文本簇通常来自同一语言，而泰语可以在单个字节中表示，因此使用gap方法存储文本然后使用可变字节编码技术进行压缩将更加高效。

挑战在于，间隙编码通常是在有序文档ID上完成的，但字符流是无序的。它不能用无符号整数来表示。问题是，使用无符号整数，如何以最小的字节数高效地表示它？这很具挑战性，因为考虑以下文本："หก"。它是 0x0E2B 后跟 0x0E01。间隙是 -42。两个代码点之间的直接减法运算得到以下位值 0b11111111_11111111_11111111_11010110。如果我们像原始算法那样处理它，它将需要4个字节来表示。我们可以尝试直接将符号位编码到字节中，但这将消耗一个额外的位槽。原始算法已经消耗了一个位槽来标记间隙的最后一个字节。如果我们走这条路，这意味着我们每个字节只有6个可用位。这意味着许多英文文本将最终每个字符占用两个字节。例如，"incredibly small"。字符之间的间隙为 -89 和 83。由于我们每个字节只有6个可用位，1个字节只能表示到 63。我们将需要两个字节。

我选择的解决方案是将它存储为绝对值，并在 bitvec 上存储符号标志。现在，-89可以由1个字节+1个位存储。

使用一个额外的 bitvec 而不是单个 Vec<u8> 的成本是额外的一个指针和两个额外的 usize。在64位系统上，这将占用24个额外的字节。表示空文本的总字节数是48字节。

因此，如果文本很短，以这种方式编码将只会导致存储所需的更多字节。

如何使用

将以下行放入 cargo.toml

var_byte_str="*"

或者，如果您需要序列化/反序列化编码后的字符串，将以下行放入 cargo.toml

var_byte_str={version="*", default=false, features=["serialize"]}

1. 编码字符串并打印它

use var_byte_str::VarByteString;
let original = "Some really long text and may contains some different language like \"คำภาษาไทยที่ใช้พื้นที่เยอะกว่าเนื้อความภาษาอังกฤษเสียอีก\".";
let encoded = VarByteString::from(original);
println!("The text is {}", encoded);
println!("Internal structure is {:?}", encoded);
// Remember that the original is a slice to UTF-8 encoded bytes. It have 16 bytes overhead.
// The encoded one have 24 bytes overhead.
println!("UTF-8 took {} bytes while encoded took {} bytes", original.len() + 16, encoded.len() + 48);

2. 编码字符串，然后在稍后解码它。

use var_byte_str::VarByteString;
let original = "Some really long text and may contains some different language like \"คำภาษาไทยที่ใช้พื้นที่เยอะกว่าเนื้อความภาษาอังกฤษเสียอีก\".";
let encoded = VarByteString::from(original);
let decoded: String = encoded.into();
assert_eq!(original, decoded);

3. 遍历编码字符串以获取当前字节的表示

use var_byte_str::VarByteString;
let original = "Some really long text and may contains some different language like \"คำภาษาไทยที่ใช้พื้นที่เยอะกว่าเนื้อความภาษาอังกฤษเสียอีก\".";
let encoded = VarByteString::from(original);
encoded.gaps_bytes().take(11).for_each(|(sign, bytes)| {
    // some operation on obtained sign boolean and `SmallVec<[u8;5]>` object.
})

4. 遍历编码字符串以获取每个字符的 "gap"

use var_byte_str::VarByteString;
let original = "Some really long text and may contains some different language like \"คำภาษาไทยที่ใช้พื้นที่เยอะกว่าเนื้อความภาษาอังกฤษเสียอีก\".";
let encoded = VarByteString::from(original);
encoded.gaps().take(11).for_each(|gap| {
    // some operation on gap
})

注意：实际上您不必先编码它。您可以使用 chars 方法在 &str 上计算 "gap"，如下所示

let chars = original.chars();
let first_chars = chars.next().unwrap();
chars.fold(first_chars as i64, |prev, ch| {
    let ch = ch as i64;
    let gap = ch - prev;
    // Do something with gap
    ch 
}) ;

但是，如果您已经使用了 VarByteString，则可以通过简单地使用方法 gaps 来节省一些代码行

5. 遍历编码字符串以获取一些字符

use var_byte_str::VarByteString;
let original = "Some really long text and may contains some different language like \"คำภาษาไทยที่ใช้พื้นที่เยอะกว่าเนื้อความภาษาอังกฤษเสียอีก\".";
let encoded = VarByteString::from(original);
encoded.chars().take(11).for_each(|c| {
    // some operation on char
})

6. 将编码字符串与任何Rust的字符串进行比较

use var_byte_str::VarByteString;
let original = "Some really long text and may contains some different language like \"คำภาษาไทยที่ใช้พื้นที่เยอะกว่าเนื้อความภาษาอังกฤษเสียอีก\".";
let encoded = VarByteString::from(original);
assert!(encoded == original);

7. 将编码字符串与任何Rust的字符串进行比较以检查二进制顺序

use var_byte_str::VarByteString;
let original = "Some really long text and may contains some different language like \"คำภาษาไทยที่ใช้พื้นที่เยอะกว่าเนื้อความภาษาอังกฤษเสียอีก\".";
let encoded = VarByteString::from(original);
let other = original + " extra text";
assert!(encoded < other);

8. 现在这个对象可以像常规字符串一样用作哈希键

use var_byte_str::VarByteString;
let original = "Some really long text and may contains some different language like \"คำภาษาไทยที่ใช้พื้นที่เยอะกว่าเนื้อความภาษาอังกฤษเสียอีก\".";
let encoded = VarByteString::from(original);
let mut hm = HashMap::new();
hm.insert(encoded.clone(), 1);
assert_eq!(hm.get(&encoded), Some(&1));