8. 静的辞書 (Static Dictionary)

圧縮データのデコード中の任意の時点で、これまでに生成された非圧縮データ内の重複文字列への参照には、最大後方距離値 (Maximum Backward Distance Value) があります。これは、ウィンドウサイズ (Window Size) と生成された非圧縮バイト数の最小値です。ただし、セクション 4 で説明されているように、圧縮ストリームから距離をデコードすると、この最大許容値よりも大きい距離が生成される場合があります。この場合、距離は付録 A で与えられる静的辞書 (Static Dictionary) 内の単語への参照として扱われます。静的辞書参照のコピー長 (Copy Length) は 4 から 24 の間でなければなりません。

静的辞書には 3 つの部分があります:

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

各静的辞書単語には、DICT 配列内のベース単語 (Base Word) に単語変換 (Word Transformation) を適用することによって与えられる 121 種類の異なる形式があります。単語変換のリストは付録 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 の基本変換 (Elementary Transforms) のいずれかです:

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

これらの基本変換の形式は次のとおりです:

Identity(word) = word

FermentFirst(word) = 以下を参照

FermentAll(word) = 以下を参照

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);
   }
}

付録 B には、それぞれのプレフィックス (Prefix)、基本変換 (Elementary Transform)、およびサフィックス (Suffix) コンポーネントを指定することにより、変換のリストが含まれています。OmitFirst8 基本変換は変換のリストでは使用されていないことに注意してください。付録 B の文字列は、エスケープ（バックスラッシュ）文字に関して C 文字列形式です。

変換がベース単語に追加する可能性のある追加バイトの最大数は 13 です。最大のベース単語は 24 バイト長であるため、38 バイトのバッファーは、変換されたすべての単語を格納するのに十分です（終端のゼロバイトを含む）。

出典 (Source): RFC 7932, Section 8
公式テキスト (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

8. 静的辞書 (Static Dictionary)​

8. 静的辞書 (Static Dictionary)