跳到主要内容

8. 静态字典

  1. 静态字典

在解码压缩数据的任意时刻, 对目前已产生的未压缩数据中重复字符串的引用都有一个最大向后距离值, 该值为窗口大小与已产生未压缩字节数两者中的较小值. 然而, 如第 4 节所述, 从压缩流解码距离时可能产生大于此最大允许值的距离. 在这种情况下, 该距离被视为对 Appendix A 中给出的静态字典内某个词的引用. 静态字典引用的复制长度必须介于 4 和 24 之间. 静态字典包含三部分:

  * DICT[0..DICTSIZE], 字节数组
  * DOFFSET[0..24], 每个长度对应的字节偏移值数组
 * NDBITS[0..24], 每个长度对应的位深值数组

给定长度的静态字典词数量为:

 NWORDS[length] = 0                       (if length < 4)
 NWORDS[length] = (1 << NDBITS[length])   (if length >= 4)

DOFFSET 和 DICTSIZE 由以下递推定义:

 DOFFSET[0] = 0
  DOFFSET[length + 1] = DOFFSET[length] + length * NWORDS[length]
  DICTSIZE = DOFFSET[24] + 24 * NWORDS[24]

对于给定长度和索引, 词在 DICT 数组中的偏移为:

  offset(length, index) = DOFFSET[length] + index * length

每个静态字典词都有 121 种不同形式, 这些形式通过对 DICT 数组中的基础词应用词变换得到. 词变换列表见 Appendix B. 对于 <length, distance> 对, 静态字典词可按如下方式重构:

  word_id = distance - (max allowed distance + 1)
  index = word_id % NWORDS[length]
  base_word = DICT[offset(length, index)..offset(length, index+1)-1]
  transform_id = word_id >> NDBITS[length]

复制到未压缩流的字符串通过对基础字典词应用该变换来计算. 如果 transform_id 大于 120, 或长度小于 4 或大于 24, 则应将该压缩流拒绝为无效.

每个词变换具有以下形式:

  transform_i(word) = prefix_i + T_i(word) + suffix_i

其中下标 _i 表示上面的 transform_id. 每个 T_i 是以下 21 个基本变换之一:

  Identity, FermentFirst, FermentAll,
  OmitFirst1, ..., OmitFirst9, OmitLast1, ..., OmitLast9

这些基本变换的形式如下:

  Identity(word) = word

  FermentFirst(word) = see below

  FermentAll(word) = see below

  OmitFirstk(word) = word 的最后 (length(word) - k) 个字节, 或
                     如果 length(word) < k 则为空字符串

  OmitLastk(word) = word 的前 (length(word) - k) 个字节, 或
                    如果 length(word) < k 则为空字符串

本规范使用的 FermentFirst 和 FermentAll 变换由以下 C 语言函数定义:

     int Ferment(uint8_t* word, int word_len, int pos) {
        if (word[pos] < 192) {
           if (word[pos] >= 97 and word[pos] <= 122) {
              word[pos] = word[pos] ^ 32;
           }
           return 1;
        } else if (word[pos] < 224) {
           if (pos + 1 < word_len) {
              word[pos + 1] = word[pos + 1] ^ 32;
           }
           return 2;
        } else {
           if (pos + 2 < word_len) {
              word[pos + 2] = word[pos + 2] ^ 5;
           }
           return 3;
        }
     }

     void FermentFirst(uint8_t* word, int word_len) {
        if (word_len > 0) {
           Ferment(word, word_len, 0);
        }
     }

     void FermentAll(uint8_t* word, int word_len) {
        int i = 0;
        while (i < word_len) {
           i += Ferment(word, word_len, i);
        }
     }

Appendix B 通过指定每个变换的前缀, 基本变换和后缀组成部分给出了变换列表. 注意, OmitFirst8 基本变换没有在该变换列表中使用. Appendix B 中的字符串在转义 (反斜杠) 字符方面采用 C 字符串格式.

一个变换最多可向基础词添加 13 个额外字节. 由于最长基础词为 24 字节, 38 字节的缓冲区足以存放任意变换后的词 (包括终止零字节).

Source: RFC 7932 Official Text: https://www.rfc-editor.org/rfc/rfc7932.txt

最后于 更新