From 0abcdd7e4358cb902c320b008d3c04bde07b749e Mon Sep 17 00:00:00 2001 From: Patrick Simianer Date: Thu, 26 Feb 2026 19:28:22 +0100 Subject: Add Rust implementation of SCFG decoder Rust port of the Ruby prototype decoder with performance optimizations for real Hiero-style grammars: - Rule indexing by first terminal/NT symbol for fast lookup - Chart symbol interning (u16 IDs) instead of string hashing - Passive chart index by (symbol, left) for direct right-endpoint lookup - Items store rule index instead of cloned rule data Includes CKY+ parser, chart-to-hypergraph conversion, Viterbi decoding, derivation extraction, and JSON hypergraph I/O. Self-filling step in parse uses grammar lookup (not just remaining active items) to handle rules that were consumed during the parse loop or skipped by the has_any_at optimization. Produces identical output to the Ruby prototype on all test examples. Co-Authored-By: Claude Opus 4.6 --- rs/src/semiring.rs | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 rs/src/semiring.rs (limited to 'rs/src/semiring.rs') diff --git a/rs/src/semiring.rs b/rs/src/semiring.rs new file mode 100644 index 0000000..9a8fe3e --- /dev/null +++ b/rs/src/semiring.rs @@ -0,0 +1,39 @@ +pub trait Semiring { + fn one() -> f64; + fn null() -> f64; + fn add(a: f64, b: f64) -> f64; + fn multiply(a: f64, b: f64) -> f64; +} + +pub struct ViterbiSemiring; + +impl Semiring for ViterbiSemiring { + fn one() -> f64 { + 1.0 + } + + fn null() -> f64 { + 0.0 + } + + fn add(a: f64, b: f64) -> f64 { + a.max(b) + } + + fn multiply(a: f64, b: f64) -> f64 { + a * b + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_viterbi() { + assert_eq!(ViterbiSemiring::one(), 1.0); + assert_eq!(ViterbiSemiring::null(), 0.0); + assert_eq!(ViterbiSemiring::add(0.3, 0.7), 0.7); + assert_eq!(ViterbiSemiring::multiply(0.5, 0.6), 0.3); + } +} -- cgit v1.2.3