Skip to content

Compact format for blocks with metadata #268

@lamphamsy

Description

@lamphamsy

It focuses on FNT(q = 2^p + 1).
Given a block of n symbols of FNT(q), a metadata part should indicate indices of all symbols whose value = 2^p.
If these symbols are uniformly distributed, we can use the frequency of 2^p to determine the size of metadata.
For general cases, the naive approach needs n indicators for n elements, i.e. metadata size = n.

For FNT(65537), the following approach results to metadata of only one indicator.
The indicator contains the index, e.g. i, of the first symbol = 2^p. Then the ith symbol will be used to contain index of the next symbol 2^p, and so on. If there is no more symbol 2^p, this symbol will be zero.

Example,
data = [1, 2, 65536, 3, 4, 65536, 5, 6, 7]
=> metadata = [2]
data = [1, 2, 5, 3, 4, 0, 5, 6, 7]

The approach can be used for FNT(257) for n < 257.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions