systile 1.0.0

Matmul-native data structures & algorithms: 17 structures (holographic memory, semiring graphs, automata, attention, DFT, Viterbi, k-NN, Bloom, sort, scan, …) whose core operation reduces to a dense matmul, built on a TPU-style tiled tensor with a systolic reference engine.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//! Levenshtein edit distance as a shortest path over the tropical semiring.
//!
//! Run with `cargo run --release --example edit_distance`.

use systile::prelude::*;

fn main() {
    let ed = TensorEditDistance::new();

    let pairs = [
        ("kitten", "sitting"),
        ("flaw", "lawn"),
        ("gumbo", "gambol"),
        ("", "abc"),
        ("same", "same"),
    ];

    println!("edit distance via tropical (min-plus) matmul:\n");
    for (a, b) in pairs {
        let d = ed.distance_str(a, b);
        println!("  {a:>8} -> {b:<8}  {d}");
    }

    // The classic example.
    assert_eq!(ed.distance_str("kitten", "sitting"), 3);
    assert_eq!(ed.distance_str("same", "same"), 0);
    println!("\n✓ alignment-grid shortest path computed by iterated min-plus matmul.");
}