arcweight 0.3.0

//! Finite State Transducer (FST) implementations for weighted automata.
//!
//! This module provides a comprehensive suite of FST implementations optimized for
//! different use cases in speech recognition, natural language processing, and
//! computational linguistics. The implementations are based on the theoretical
//! framework of weighted finite-state transducers as described in the seminal
//! work by Mohri and colleagues.
//!
//! # Theoretical Background
//!
//! A weighted finite-state transducer (WFST) is a finite automaton where each
//! transition carries an input label, an output label, and a weight from a
//! semiring. Formally, a WFST $`T`$ over a semiring $`(K, \oplus, \otimes, \bar{0}, \bar{1})`$
//! is defined as an 8-tuple $`T = (\Sigma, \Delta, Q, I, F, E, \lambda, \rho)`$ where:
//!
//! - $`\Sigma`$ is the finite input alphabet
//! - $`\Delta`$ is the finite output alphabet
//! - $`Q`$ is a finite set of states
//! - $`I \subseteq Q`$ is the set of initial states
//! - $`F \subseteq Q`$ is the set of final states
//! - $`E \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times (\Delta \cup \{\epsilon\}) \times K \times Q`$
//!   is a finite set of transitions
//! - $`\lambda: I \to K`$ is the initial weight function
//! - $`\rho: F \to K`$ is the final weight function
//!
//! # FST Types
//!
//! ## [`VectorFst`] - Mutable Vector-Based FST
//!
//! The primary mutable FST implementation using dynamic vectors for state and arc
//! storage. Provides $`O(1)`$ amortized insertion and $`O(1)`$ random access.
//!
//! - **Use case:** General-purpose FST construction and modification
//! - **Performance:** Fast random access, $`O(1)`$ state/arc insertion (amortized)
//! - **Memory:** Moderate overhead with dynamic growth
//! - **Best for:** Building FSTs incrementally, algorithm development
//!
//! ## [`ConstFst`] - Immutable Optimized FST
//!
//! Read-only FST with contiguous memory layout for optimal cache performance.
//! Derived from `VectorFst` after construction is complete.
//!
//! - **Use case:** Production deployment of finalized FSTs
//! - **Performance:** Excellent traversal speed with $`O(1)`$ state access
//! - **Memory:** 15-25% less than `VectorFst` with better cache locality
//! - **Best for:** Large read-only FSTs, production systems
//!
//! ## [`CompactFst`] - Memory-Efficient Compressed FST
//!
//! Compression-oriented FST using pluggable compaction strategies for minimal
//! memory footprint. Trades computation for memory savings.
//!
//! - **Use case:** Memory-constrained environments, very large FSTs
//! - **Performance:** Slower access due to decompression overhead
//! - **Memory:** 40-70% reduction compared to `VectorFst`
//! - **Best for:** Mobile deployment, embedded systems, storage optimization
//!
//! ## [`CacheFst`] - Caching Wrapper
//!
//! Thread-safe caching wrapper for any FST implementation. Caches computed
//! arcs and weights for accelerated repeated access patterns.
//!
//! - **Use case:** Expensive computations with locality of reference
//! - **Performance:** $`O(1)`$ for cached accesses, base FST cost for misses
//! - **Memory:** Base FST size plus cache overhead
//! - **Best for:** Wrapping lazy FSTs, composition results
//!
//! ## [`LazyFstImpl`] - On-Demand Computation
//!
//! Lazy FST implementation that computes states dynamically using a user-provided
//! function. Enables handling of potentially infinite state spaces.
//!
//! - **Use case:** Dynamic FST generation, search space exploration
//! - **Performance:** Varies by computation function complexity
//! - **Memory:** $`O(\text{accessed states})`$, not full FST size
//! - **Best for:** Large composition chains, grammar intersection
//!
//! ## [`LazyComposeFst`] - On-the-fly Composition
//!
//! Specialized lazy FST for computing composition results on demand without
//! materializing the full composed automaton.
//!
//! - **Use case:** Composition where only a subset of paths is needed
//! - **Performance:** 10-100x faster than full materialization for sparse access
//! - **Memory:** Only stores accessed state pairs
//! - **Best for:** Shortest path through composed FSTs, beam search
//!
//! ## [`ConcurrentFst`] - Thread-Safe Mutable FST
//!
//! Lock-free concurrent FST implementation for multi-threaded construction
//! and traversal. Uses epoch-based memory reclamation.
//!
//! - **Use case:** Parallel FST construction and concurrent access
//! - **Performance:** Near-linear scaling for read operations
//! - **Memory:** Higher overhead due to synchronization primitives
//! - **Best for:** Server applications, parallel algorithms
//!
//! ## [`CsrFst`] - Cache-Optimized CSR Format
//!
//! Compressed Sparse Row format with Structure-of-Arrays layout for
//! SIMD-friendly traversal and optimal cache utilization.
//!
//! - **Use case:** High-performance batch processing
//! - **Performance:** Excellent for sequential traversal, SIMD-accelerated
//! - **Memory:** Minimal overhead with cache-line alignment
//! - **Best for:** Large-scale decoding, parallel shortest path
//!
//! ## [`FailureFst`] - Failure Transition Wrapper
//!
//! Wrapper that adds Aho-Corasick style failure transitions to any FST
//! for compact representation of large automata.
//!
//! - **Use case:** Pattern matching, dictionary lookup
//! - **Performance:** Efficient failure arc traversal
//! - **Memory:** Base FST plus failure transition map
//! - **Best for:** Multiple pattern matching, large lexicons
//!
//! # Choosing an FST Type
//!
//! ```
//! use arcweight::prelude::*;
//! use arcweight::fst::CacheFst;
//!
//! // For building and modifying FSTs
//! let mut mutable_fst = VectorFst::<TropicalWeight>::new();
//! mutable_fst.add_state();
//!
//! // For read-only, high-performance access
//! let const_fst = ConstFst::from_fst(&mutable_fst)?;
//!
//! // For caching expensive operations
//! let cached_fst = CacheFst::new(const_fst);
//! # Ok::<(), arcweight::Error>(())
//! ```
//!
//! # Core Traits
//!
//! All FST types implement the core [`Fst`] trait for read operations,
//! while mutable types also implement [`MutableFst`] for modifications.
//! Some types implement [`ExpandedFst`] for direct slice access to arcs.
//!
//! # References
//!
//! - Mohri, M. (1997). Finite-State Transducers in Language and Speech Processing.
//!   *Computational Linguistics*, 23(2), 269-311.
//!
//! - Mohri, M., Pereira, F., & Riley, M. (2002). Weighted Finite-State Transducers
//!   in Speech Recognition. *Computer Speech & Language*, 16(1), 69-88.
//!
//! - Allauzen, C., Riley, M., Schalkwyk, J., Skut, W., & Mohri, M. (2007).
//!   OpenFst: A General and Efficient Weighted Finite-State Transducer Library.
//!   In *Proc. CIAA 2007*, LNCS 4783, pp. 11-23. Springer.

mod cache_fst;
mod compact_fst;
mod concurrent_fst;
mod const_fst;
mod conversion;
mod csr_fst;
mod failure_fst;
mod lazy_compose_fst;
mod lazy_fst;
mod traits;
mod vector_fst;

pub use cache_fst::CacheFst;
pub use compact_fst::{
    AdaptiveConfig, BitPackCompactor, CompactFst, Compactor, ContextCompactor, DefaultCompactor,
    DeltaCompactor, HuffmanCompactor, LZ4Compactor, QuantizationMode, QuantizedCompactor,
    RunLengthCompactor, StreamingConfig, VarIntCompactor,
};
pub use concurrent_fst::{ConcurrentFst, ConcurrentFstSnapshot};
pub use const_fst::ConstFst;
pub use conversion::{
    auto_convert, convert_to_cache, convert_to_compact, convert_to_compact_with, convert_to_const,
    convert_to_evicting_cache, convert_to_lazy, convert_to_vector, estimate_conversion_metrics,
    BatchConverter, ConversionMetrics, ConversionStrategy, ConvertedFst,
};
pub use csr_fst::CsrFst;
pub use failure_fst::FailureFst;
pub use lazy_compose_fst::{LazyComposeArcIterator, LazyComposeFst};
pub use lazy_fst::{
    CacheConfig, CacheStats, EvictingCacheFst, EvictionPolicy, LazyFstImpl, LazyState,
    LazyStreamingConfig, MemoryMappedProvider, StateGenerator, StreamingLazyFst, StreamingStats,
};
pub use traits::*;
pub use vector_fst::VectorFst;