sicada

Weighted finite-state transducers in Rust. This workspace contains two crates:

• sicada is an independent implementation of OpenFst's openfst/lib and is compatible with the OpenFst binary file format.
• sicada-decode provides frame-synchronous speech decoding, lattices over Kaldi's semirings, CTC topologies, and exact forced alignment without beam pruning.

Both crates are pre-1.0 and their APIs may change. The remainder of this README describes sicada.

Differences from OpenFst

• No FFI is used. The library has no build script and links no C++ code. Only sicada-bench links OpenFst for comparative benchmarks.
• FSTs can be exchanged with OpenFst through the compatible binary format.
• Algorithms are generic over an arc type rather than a weight type. Required semiring properties are expressed with trait bounds.
• Runtime type discovery uses a closed enum instead of OpenFst's dynamic type registry and dlopen plugin mechanism.

Differences from rustfst

• rustfst and sicada are independent implementations of OpenFst semantics.
• sicada uses generic associated types for iterators, so Fst is not object-safe and there is no Box<dyn Fst>.
• sicada takes inputs by reference and writes to a mutable output argument, so Rust can infer every type parameter. In rustfst 1.3.1, compose(owned, &borrowed) produces E0283 unless all six type parameters are specified (rustfst#235). The trade-off is that sicada operations cannot be nested as expressions.

Benchmarks

These results come from a single build in which all four implementations were linked into one executable and measured in alternating rounds. Each table shows the best round. Ratios divide the other implementation's time by sicada's, so a ratio above 1.00x means sicada was faster. The comparison used OpenFst 1.8.5-377-ge6bbae9, rustfst 1.3.1, and arcweight 0.3.0 on x86_64 Linux with GCC 15.2 and rustc 1.97. C++ used -O3; Rust used the release profile.

Before timing, each benchmark checks the number of states and arcs and the semiring sum over all paths.

Data structures

rustfst and arcweight do not expose these data structures, so only OpenFst is included in this comparison. The C++ benchmark uses the relevant upstream implementations verbatim.

Algorithms

Two rows show clear regressions rather than measurement noise. For cyclic shortest-distance, arcweight reaches 0.68x because sicada follows OpenFst and decomposes the graph into strongly connected components before selecting a queue. That setup cost is recovered on acyclic inputs. For shortest-path/10000x4-acyclic, rustfst reaches 0.73x because sicada first runs a depth-first search to obtain the topological order used by the general distance algorithm, while rustfst uses a dedicated shortest-path search. Ratios within a few percent of 1.00x vary between runs and should be treated as ties.

Some implementations are omitted from individual rows because their output structure differed from the other three. The total path weight still agrees in these tropical-semiring benchmarks because ⊕ is min, which absorbs duplicate paths and dominated parallel arcs. With the log semiring, cases 1 and 4 would also change the total weight. The counts below come from diag, which reports the same three validation metrics:

1. arcweight's remove_epsilons appends the closure's arcs without combining parallel arcs. A state reached both directly and through an epsilon path therefore retains both arcs: 1437 arcs versus sicada's 1432 on 1000x4, with 283 states in both results. Each extra arc duplicates a label and destination at a higher weight, so tropical ⊕ discards it. DIAG_EPS=1 diag confirms that all five differences have this form.
2. rustfst's determinize rebuilds each subset from a HashMap and compares subsets as an ordered Vec. Consequently, the same subset can be represented in different orders and become multiple states. Four runs on 1000x4 produced 3064, 3125, 3065, and 3057 states, compared with sicada's stable 2497. Minimization produces 952 states in both implementations, confirming language equivalence.
3. arcweight's minimize produces 1032 states on 1000x4 where the other three produce 952. It is Brzozowski's algorithm, reverse and determinize twice, not the weight pushing and encoded minimization OpenFst uses. Its documentation specifies no weight-pushing precondition and states that the operation preserves the weighted language and returns the unique canonical minimal FST.
4. arcweight's compose produces 4733 states on 1000x4 where the other three produce 307. Its default filter is stateless: an epsilon-sequencing filter needs state to record which side may advance on an epsilon, but this filter's FilterState is (). Although compose accepts a filter parameter, DefaultComposeFilter is the only implementation provided by the crate.

Graph inputs contain states states with arcs outgoing arcs per state, labels in 1..64, and weights quantized to quarters. In -acyclic inputs, every arc points forward. Automaton inputs are acyclic acceptors with an epsilon on one in eight arcs. The minimize benchmark determinizes before minimization, and the compose benchmark sorts both inputs first. Determinization results are passed through connect before comparison. The compose/dense-* benchmark also measures two sicada variants not shown in the table: look-ahead composition that builds its index for each call (486.6 µs and 1.60 ms), and composition with a prebuilt index (187.0 µs and 746.2 µs).

Reproducing

git submodule update --init
cmake -S vendor/openfst -B /path/to/ofst-build \
      -DCMAKE_BUILD_TYPE=Release -DOPENFST_BUILD_TESTS=OFF \
      -DOPENFST_ENABLE_BIN=OFF -DOPENFST_ENABLE_INSTALL=OFF
cmake --build /path/to/ofst-build -j 4
OPENFST_BUILD_DIR=/path/to/ofst-build cargo run --release -p sicada-bench --bin ab

Without OPENFST_BUILD_DIR, the OpenFst algorithm columns are omitted. The data structure benchmarks still run because their C++ implementations are compiled directly into the benchmark crate.

Only measurements from the same build are comparable. Relinking changes the placement and alignment of the C++ hot loops by enough to affect these results.

Building

cargo build
cargo test

The OpenFst submodule is required only for comparative benchmarks and source reference.

License

Apache License 2.0.

The library does not link against third-party C++ code. Its algorithm semantics and binary format are based on OpenFst (Apache License 2.0), whose source is vendored as a reference submodule and remains under its original license. Four OpenFst data structures are included in sicada-bench/cpp/openfst_shim.cc for direct benchmark comparison; that file retains the OpenFst copyright notice. The lattice semirings and decoder structure in sicada-decode are based on Kaldi (Apache License 2.0).