swh_graph/java_compat/sf/
mod.rs

1/*
2 *
3 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
4 * SPDX-FileCopyrightText: 2023 Inria
5 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
6 *
7 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
8 */
9
10//! # Static functions
11//!
12//! Static functions are data structures designed to store arbitrary mappings f : X → Σ from a finite
13//! set of keys X ⊆ U to an alphabet Σ, where U is a universe of possible keys. Given x ∈ U, a static
14//! function returns a value that is f(x) when x ∈ X; on U \ X, the result is irrelevant. In general,
15//! one looks for representations returning their output in constant time.
16//! Functions can be easily implemented using hash tables, but since they are allowed to return any
17//! value if the queried key is not in X, in the static case we can break the information-theoretical lower
18//! bound of storing the set X. In fact, constructions for static functions achieve just O(|X| log |Σ|)
19//! bits of space, regardless of the nature of X and U. This makes static functions a powerful
20//! techniques when handling, for instance, large sets of strings, and they are important building
21//! blocks of space-efficient data structures such as (compressed) full-text indexes, (monotone)
22//! MPHFs, Bloom filter-like data structures, and prefix-search data structures.
23//!
24//! Imported [from sux-rs](https://archive.softwareheritage.org/swh:1:dir:f3cf91ed13115111d55443459abcb6a344b0bd01;origin=https://github.com/vigna/sux-rs;visit=swh:1:snp:855180f9102fd3d7451e98f293cdd90cff7f17d9;anchor=swh:1:rev:9cafac06c95c2d916b76dc374a6f9d976bf65456;path=/src/sf/)
25
26pub mod gov3;
swh_graph/java_compat/sf/mod.rs

swh_graph/java_compat/sf/
mod.rs
