Skip to content

Cover Pruning #4

@PythonNut

Description

@PythonNut

Currently we evaluate all nodes of the valid prefix cover. However, this surely contains some paths that have vanishingly small probability. If our tree invariants are correct, we will always know the probability of a node before we expand its children. The next-byte distribution is built by summing the byte distributions for each node, weighted by the node probability. This means that we can take in a parameter describing the worst-case total-variation distortion allowed by pruning and prune optimally to meet that guarantee!

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