Length-limited byte Huffman tree construction for wavelet indexes. More...

#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <span>

Classes
struct	pixie::detail::HuffmanBuildNode

struct	pixie::detail::HuffmanBuildTable

struct	pixie::detail::huffman_build_detail::FrequencyLeaf

struct	pixie::detail::huffman_build_detail::CanonicalChunk

Functions
void	pixie::detail::huffman_build_detail::sort_leaves_by_frequency (std::span< FrequencyLeaf > leaves, std::array< FrequencyLeaf, kByteAlphabetSize > &temporary)

std::array< std::uint8_t, kByteAlphabetSize >	pixie::detail::huffman_build_detail::build_code_lengths (std::span< const std::size_t > frequencies, std::span< const std::uint16_t > used_symbols)

void	pixie::detail::huffman_build_detail::limit_code_lengths (std::array< std::uint8_t, kByteAlphabetSize > &lengths)

std::uint16_t	pixie::detail::huffman_build_detail::assign_inorder_ranks (HuffmanBuildTable &table, std::int16_t node_id, std::uint16_t rank)

void	pixie::detail::huffman_build_detail::build_canonical_tree (const std::array< std::uint8_t, kByteAlphabetSize > &lengths, HuffmanBuildTable &table)

HuffmanBuildTable	pixie::detail::build_huffman_table (std::span< const std::size_t > frequencies)
	Build PivCo's sibling-paired, non-flat byte Huffman tree.

Variables
constexpr std::size_t	pixie::detail::kByteAlphabetSize = 256

constexpr std::size_t	pixie::detail::kMaximumHuffmanNodes = 2 * kByteAlphabetSize - 1

constexpr std::size_t	pixie::detail::kMaximumHuffmanCodeLength = 11

Detailed Description

Length-limited byte Huffman tree construction for wavelet indexes.

This file is derived from PivCo's huffman_table.c and has been modified for Pixie's header-only C++ representation. Wire-format, flat-subtree, entropy-coding, and decoder tables were removed. The two-queue length builder, length limiter, sibling-paired canonical tree shaping, and in-order rank assignment are retained. Both projects are distributed under Apache-2.0.

Function Documentation

◆ build_huffman_table()

HuffmanBuildTable pixie::detail::build_huffman_table ( std::span< const std::size_t > frequencies )

inline

Build PivCo's sibling-paired, non-flat byte Huffman tree.

Parameters

frequencies Frequencies for a dense alphabet of at most 256 symbols.

Returns: Tree, symbol ranks, and split ranks.

Classes

Functions

Variables

Detailed Description

Function Documentation

◆ build_huffman_table()