Crate duallity 

duallity — Levenshtein automata as lling-llang WFSTs.

This crate exposes liblevenshtein’s Levenshtein automata as lling-llang Wfst implementers, enabling participation in WFST composition pipelines.

Overview

The integration provides:

• LevenshteinWfst: A lazy WFST wrapper that presents the Levenshtein transducer × dictionary product as a Wfst<char, TropicalWeight>. States encode (dictionary_node, automaton_state) pairs.

• LevenshteinStateSource: A StateSource implementation for lazy state computation, enabling efficient composition without materializing the full product state space.

• DictionaryBackend: An adapter that implements lling-llang’s [LatticeBackend] trait using a liblevenshtein dictionary.

Architecture

The Levenshtein transducer produces a weighted transducer where:

• Input: Query characters (the misspelled word)
• Output: Dictionary characters (corrections)
• Weight: Edit distance as TropicalWeight (min-plus semiring)

State encoding uses a composite ID: state_id = dict_node * automaton_size + automaton_state

Example

use duallity::{LevenshteinWfst, DictionaryBackend};
use libdictenstein::dynamic_dawg::char::DynamicDawgChar;
use lling_llang::composition::compose;
use lling_llang::prelude::*;

// Build a dictionary
let dict = DynamicDawgChar::from_terms(vec!["hello", "help", "world"]);

// Create a Levenshtein WFST for the query "helo" with max distance 2
let lev_wfst = LevenshteinWfst::new(&dict, "helo", 2);

// Compose with a language model WFST
let composed = compose(lev_wfst, language_model);

// Find best corrections using composed transducer
for path in composed.accepting_paths() {
    println!("{:?} (weight: {:?})", path.labels(), path.weight());
}

Phonetic variants

Phonetic Levenshtein WFST variants are behind the phonetic-rules feature:

[dependencies]
duallity = { version = "0.1", features = ["phonetic-rules"] }

Modules

state_encoding

Composite state ID encoding for the product automaton.

Structs

BoundUniversalWfst

A pre-bound Universal WFST that can be cloned efficiently.

CommonPhoneticRules

Builder for common phonetic rewrite rules.

DictionaryBackend

Adapter that exposes a liblevenshtein dictionary as a lling-llang LatticeBackend.

GeneralizedWfst

Generalized Automaton WFST wrapper.

GeneralizedWfstBuilder

Builder for Generalized WFST.

LazyWfstWrapper

Generic lazy WFST wrapper that computes states on demand.

LevenshteinStateSource

State source for lazy Levenshtein WFST computation.

LevenshteinWfst

A Levenshtein transducer exposed as a lling-llang WFST.

PhoneticMatch

Result of a phonetic pipeline search.

PhoneticNfaWfst

A pure phonetic NFA exposed as a lling-llang WFST.

PhoneticPipelineBuilder

Builder for phonetic matching pipelines.

PhoneticPipelineConfig

Configuration for a phonetic matching pipeline.

PhoneticStateSource

State source for phonetic WFST composition.

PhoneticWfst

A phonetic transducer exposed as a lling-llang WFST.

PhoneticWfstBuilder

Builder for PhoneticWfst with pattern string support.

RewriteRule

A phonetic rewrite rule.

RewriteWfst

A rule-based phonetic rewrite WFST.

TropicalWeight

Tropical semiring weight.

UniversalLevenshteinStateSource

State source for Universal Levenshtein WFST computation.

UniversalLevenshteinWfst

A Universal Levenshtein transducer exposed as a lling-llang WFST.

UniversalStateRegistry

State registry for deduplicating Universal Levenshtein states.

WallBreakerWfst

WallBreaker WFST wrapper.

WallBreakerWfstBuilder

Builder for WallBreaker WFST.

WeightedTransition

A weighted transition in a WFST.

Enums

LazyState

A state that may or may not have been computed yet.

Traits

LazyWfst

Trait for WFSTs that support lazy (on-demand) state expansion.

Semiring

Algebraic semiring for WFST weight operations.

StateSource

Trait for types that can produce WFST states on demand.

Wfst

Core trait for immutable WFST access.

Type Aliases

StateId

State identifier for WFST states.

VocabId

A vocabulary identifier.