#[derive(Debug, Clone)]
pub struct SignatureConfig {
pub dim: usize,
pub max_depth: usize,
}
pub fn signature_size(dim: usize, max_depth: usize) -> usize {
if dim == 0 || max_depth == 0 {
return 0;
}
if dim == 1 {
return max_depth;
}
let mut total: usize = 0;
let mut power: usize = 1;
for _ in 0..max_depth {
power = power.saturating_mul(dim);
total = total.saturating_add(power);
}
total
}
#[derive(Debug, Clone)]
pub struct SignatureExtractor {
dim: usize,
max_depth: usize,
terms: Vec<f64>,
offsets: Vec<usize>,
count: usize,
last: Option<Vec<f64>>,
}
impl SignatureExtractor {
pub fn new(dim: usize, max_depth: usize) -> Self {
let total = signature_size(dim, max_depth);
let mut offsets = Vec::with_capacity(max_depth + 1);
offsets.push(0);
let mut power = 1;
for _ in 0..max_depth {
power *= dim;
offsets.push(offsets.last().unwrap() + power);
}
Self {
dim,
max_depth,
terms: vec![0.0; total],
offsets,
count: 0,
last: None,
}
}
pub fn dim(&self) -> usize {
self.dim
}
pub fn max_depth(&self) -> usize {
self.max_depth
}
pub fn count(&self) -> usize {
self.count
}
pub fn num_terms(&self) -> usize {
self.terms.len()
}
pub fn observe(&mut self, point: &[f64]) {
assert_eq!(
point.len(),
self.dim,
"point dimension {} != extractor dimension {}",
point.len(),
self.dim
);
self.count += 1;
if let Some(ref last) = self.last {
let dx: Vec<f64> = point.iter().zip(last.iter()).map(|(a, b)| a - b).collect();
self.extend_signature(&dx);
}
self.last = Some(point.to_vec());
}
fn segment_exponential(&self, dx: &[f64]) -> Vec<f64> {
let mut seg = vec![0.0; self.terms.len()];
if self.dim == 0 || self.max_depth == 0 {
return seg;
}
seg[..self.dim].copy_from_slice(dx);
for m in 2..=self.max_depth {
let prev_start = self.offsets[m - 2];
let prev_end = self.offsets[m - 1];
let curr_start = self.offsets[m - 1];
let inv_m = 1.0 / (m as f64);
for p_idx in 0..(prev_end - prev_start) {
let parent_val = seg[prev_start + p_idx];
let row_offset = curr_start + p_idx * self.dim;
for (d_idx, &dx_val) in dx.iter().enumerate() {
seg[row_offset + d_idx] = parent_val * dx_val * inv_m;
}
}
}
seg
}
fn right_multiply_tensor(&mut self, rhs: &[f64]) {
if self.dim == 0 || self.max_depth == 0 {
return;
}
for k in (1..=self.max_depth).rev() {
let k_start = self.offsets[k - 1];
let k_end = self.offsets[k];
for m in 1..k {
let p = k - m;
let p_start = self.offsets[p - 1];
let p_count = self.offsets[p] - p_start;
let m_start = self.offsets[m - 1];
let m_count = self.offsets[m] - m_start;
for u in 0..p_count {
let a_val = self.terms[p_start + u];
if a_val == 0.0 {
continue;
}
let dst_base = k_start + u * m_count;
for v in 0..m_count {
self.terms[dst_base + v] += a_val * rhs[m_start + v];
}
}
}
for (dst, &b_val) in self.terms[k_start..k_end]
.iter_mut()
.zip(&rhs[k_start..k_end])
{
*dst += b_val;
}
}
}
fn extend_signature(&mut self, dx: &[f64]) {
let seg = self.segment_exponential(dx);
self.right_multiply_tensor(&seg);
}
pub fn concatenate(&self, other: &Self) -> Self {
assert_eq!(self.dim, other.dim, "dimension mismatch in concatenate");
assert_eq!(
self.max_depth, other.max_depth,
"max_depth mismatch in concatenate"
);
let mut combined = self.clone();
combined.right_multiply_tensor(&other.terms);
combined.count = self.count + other.count;
if other.last.is_some() {
combined.last = other.last.clone();
}
combined
}
pub fn levy_area(&self, i: usize, j: usize) -> Option<f64> {
if self.max_depth < 2 || i >= self.dim || j >= self.dim {
return None;
}
let d2 = self.signature_at_depth(2)?;
Some(0.5 * (d2[i * self.dim + j] - d2[j * self.dim + i]))
}
pub fn signature(&self) -> &[f64] {
&self.terms
}
pub fn signature_at_depth(&self, depth: usize) -> Option<&[f64]> {
if depth == 0 || depth > self.max_depth {
return None;
}
let start = self.offsets[depth - 1];
let end = self.offsets[depth];
Some(&self.terms[start..end])
}
pub fn norm(&self) -> f64 {
self.terms.iter().map(|x| x * x).sum::<f64>().sqrt()
}
pub fn reset(&mut self) {
self.terms.fill(0.0);
self.count = 0;
self.last = None;
}
}
pub fn signature_distance(a: &[f64], b: &[f64]) -> f64 {
assert_eq!(a.len(), b.len(), "signature length mismatch");
a.iter()
.zip(b.iter())
.map(|(x, y)| (x - y) * (x - y))
.sum::<f64>()
.sqrt()
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
#[test]
fn signature_size_basic() {
assert_eq!(signature_size(0, 3), 0);
assert_eq!(signature_size(3, 0), 0);
assert_eq!(signature_size(1, 3), 3); assert_eq!(signature_size(2, 1), 2); assert_eq!(signature_size(2, 2), 6); assert_eq!(signature_size(2, 3), 14); assert_eq!(signature_size(3, 2), 12); }
#[test]
fn extractor_initial_state() {
let ext = SignatureExtractor::new(2, 3);
assert_eq!(ext.dim(), 2);
assert_eq!(ext.max_depth(), 3);
assert_eq!(ext.count(), 0);
assert_eq!(ext.num_terms(), 14); assert!(ext.signature().iter().all(|&x| x == 0.0));
}
#[test]
fn single_observation_no_signature() {
let mut ext = SignatureExtractor::new(2, 2);
ext.observe(&[1.0, 2.0]);
assert!(ext.signature().iter().all(|&x| x == 0.0));
assert_eq!(ext.count(), 1);
}
#[test]
fn depth1_is_total_increment() {
let mut ext = SignatureExtractor::new(2, 2);
ext.observe(&[0.0, 0.0]);
ext.observe(&[1.0, 3.0]);
ext.observe(&[4.0, 5.0]);
let d1 = ext.signature_at_depth(1).unwrap();
assert!((d1[0] - 4.0).abs() < 1e-10);
assert!((d1[1] - 5.0).abs() < 1e-10);
}
#[test]
fn single_segment_closed_form_matches_tensor_exponential() {
let a = [2.0, -3.0];
let mut ext = SignatureExtractor::new(2, 3);
ext.observe(&[0.0, 0.0]);
ext.observe(&a);
let d1 = ext.signature_at_depth(1).unwrap();
assert!((d1[0] - 2.0).abs() < 1e-12);
assert!((d1[1] - (-3.0)).abs() < 1e-12);
let d2 = ext.signature_at_depth(2).unwrap();
assert!((d2[0] - 4.0 / 2.0).abs() < 1e-12); assert!((d2[1] - (-6.0) / 2.0).abs() < 1e-12); assert!((d2[2] - (-6.0) / 2.0).abs() < 1e-12); assert!((d2[3] - 9.0 / 2.0).abs() < 1e-12); assert!(ext.levy_area(0, 1).unwrap().abs() < 1e-12);
let d3 = ext.signature_at_depth(3).unwrap();
assert!((d3[0] - 8.0 / 6.0).abs() < 1e-12); assert!((d3[7] - (-27.0) / 6.0).abs() < 1e-12); }
#[test]
fn depth2_iterated_integrals() {
let mut ext = SignatureExtractor::new(1, 3);
ext.observe(&[0.0]);
ext.observe(&[1.0]);
ext.observe(&[3.0]);
ext.observe(&[6.0]);
let d1 = ext.signature_at_depth(1).unwrap();
assert!((d1[0] - 6.0).abs() < 1e-10);
let d2 = ext.signature_at_depth(2).unwrap();
assert!((d2[0] - 18.0).abs() < 1e-10);
let d3 = ext.signature_at_depth(3).unwrap();
assert!((d3[0] - 36.0).abs() < 1e-10);
}
#[test]
fn signature_depth_out_of_range() {
let ext = SignatureExtractor::new(2, 3);
assert!(ext.signature_at_depth(0).is_none());
assert!(ext.signature_at_depth(4).is_none());
assert!(ext.signature_at_depth(1).is_some());
assert!(ext.signature_at_depth(3).is_some());
}
#[test]
fn norm_computation() {
let mut ext = SignatureExtractor::new(1, 1);
ext.observe(&[0.0]);
ext.observe(&[3.0]);
assert!((ext.norm() - 3.0).abs() < 1e-10);
}
#[test]
fn distance_computation() {
let a = vec![1.0, 2.0, 3.0];
let b = vec![4.0, 6.0, 3.0];
assert!((signature_distance(&a, &b) - 5.0).abs() < 1e-10);
}
#[test]
fn reset() {
let mut ext = SignatureExtractor::new(2, 2);
ext.observe(&[0.0, 0.0]);
ext.observe(&[1.0, 1.0]);
assert!(ext.norm() > 0.0);
ext.reset();
assert_eq!(ext.count(), 0);
assert!(ext.signature().iter().all(|&x| x == 0.0));
}
#[test]
fn two_dim_depth3_l_shaped_path_and_levy_area() {
let mut ext = SignatureExtractor::new(2, 3);
ext.observe(&[0.0, 0.0]);
ext.observe(&[1.0, 0.0]);
ext.observe(&[1.0, 1.0]);
let d1 = ext.signature_at_depth(1).unwrap();
assert!((d1[0] - 1.0).abs() < 1e-10);
assert!((d1[1] - 1.0).abs() < 1e-10);
let d2 = ext.signature_at_depth(2).unwrap();
assert!((d2[0] - 0.5).abs() < 1e-10); assert!((d2[1] - 1.0).abs() < 1e-10); assert!((d2[2] - 0.0).abs() < 1e-10); assert!((d2[3] - 0.5).abs() < 1e-10);
assert!((ext.levy_area(0, 1).unwrap() - 0.5).abs() < 1e-10);
assert!((ext.levy_area(1, 0).unwrap() + 0.5).abs() < 1e-10);
let d3 = ext.signature_at_depth(3).unwrap();
assert!((d3[0] - 1.0 / 6.0).abs() < 1e-10); assert!((d3[1] - 0.5).abs() < 1e-10); assert!((d3[2] - 0.0).abs() < 1e-10); assert!((d3[3] - 0.5).abs() < 1e-10); assert!((d3[4] - 0.0).abs() < 1e-10); assert!((d3[5] - 0.0).abs() < 1e-10); assert!((d3[6] - 0.0).abs() < 1e-10); assert!((d3[7] - 1.0 / 6.0).abs() < 1e-10); }
#[test]
fn chens_identity_concatenation_matches_single_pass() {
let pts = [
[0.0, 0.0],
[1.5, -0.5],
[2.0, 1.25],
[-0.5, 2.0],
[0.75, -1.0],
];
let mut full = SignatureExtractor::new(2, 4);
for p in &pts {
full.observe(p);
}
let mut first = SignatureExtractor::new(2, 4);
for p in &pts[..=2] {
first.observe(p);
}
let mut second = SignatureExtractor::new(2, 4);
for p in &pts[2..] {
second.observe(p);
}
let joined = first.concatenate(&second);
for (idx, (&a, &b)) in full.signature().iter().zip(joined.signature()).enumerate() {
assert!(
(a - b).abs() < 1e-10,
"Chen concatenation mismatch at term {}: full={} joined={}",
idx,
a,
b
);
}
}
#[test]
fn tree_like_retracing_cancels_signature() {
let mut ext = SignatureExtractor::new(3, 4);
ext.observe(&[1.0, -2.0, 0.5]);
ext.observe(&[4.0, 2.5, -1.5]);
ext.observe(&[1.0, -2.0, 0.5]);
for (idx, &val) in ext.signature().iter().enumerate() {
assert!(
val.abs() < 1e-10,
"Retraced segment should have zero signature at term {}, got {}",
idx,
val
);
}
}
#[test]
fn translation_invariance() {
let mut ext1 = SignatureExtractor::new(2, 2);
ext1.observe(&[0.0, 0.0]);
ext1.observe(&[1.0, 2.0]);
ext1.observe(&[3.0, 1.0]);
let mut ext2 = SignatureExtractor::new(2, 2);
ext2.observe(&[100.0, 200.0]);
ext2.observe(&[101.0, 202.0]);
ext2.observe(&[103.0, 201.0]);
let s1 = ext1.signature();
let s2 = ext2.signature();
for (a, b) in s1.iter().zip(s2.iter()) {
assert!(
(a - b).abs() < 1e-10,
"Translation invariance violated: {} != {}",
a,
b
);
}
}
#[test]
fn constant_path_zero_signature() {
let mut ext = SignatureExtractor::new(3, 3);
for _ in 0..10 {
ext.observe(&[5.0, 5.0, 5.0]);
}
assert!(ext.signature().iter().all(|&x| x == 0.0));
}
#[test]
fn signature_distance_zero_for_same() {
let a = vec![1.0, 2.0, 3.0];
assert!((signature_distance(&a, &a)).abs() < 1e-15);
}
#[test]
#[should_panic(expected = "point dimension")]
fn wrong_dimension_panics() {
let mut ext = SignatureExtractor::new(2, 2);
ext.observe(&[1.0]); }
#[test]
fn frame_timing_anomaly_detection() {
let mut normal = SignatureExtractor::new(2, 3);
for (i, &t) in [16.0, 16.1, 15.9, 16.0, 16.2, 15.8, 16.0, 16.1]
.iter()
.enumerate()
{
normal.observe(&[i as f64, t]);
}
let mut anomalous = SignatureExtractor::new(2, 3);
for (i, &t) in [16.0, 16.1, 15.9, 64.0, 16.0, 16.0, 16.0, 16.0]
.iter()
.enumerate()
{
anomalous.observe(&[i as f64, t]);
}
let dist = signature_distance(normal.signature(), anomalous.signature());
assert!(
dist > 1.0,
"Anomalous path should be far from normal (dist={})",
dist
);
}
proptest! {
#[test]
fn proptest_reparametrization_invariance_under_subdivision(
pts in proptest::collection::vec(
proptest::array::uniform3(-10.0f64..10.0f64),
2..=6
),
splits in proptest::collection::vec(0.05f64..0.95f64, 1..=5),
) {
let mut coarse = SignatureExtractor::new(3, 3);
for p in &pts {
coarse.observe(p);
}
let mut refined = SignatureExtractor::new(3, 3);
refined.observe(&pts[0]);
for (seg_idx, window) in pts.windows(2).enumerate() {
let a = window[0];
let b = window[1];
let frac = splits[seg_idx % splits.len()];
let mid1 = [
a[0] + 0.5 * frac * (b[0] - a[0]),
a[1] + 0.5 * frac * (b[1] - a[1]),
a[2] + 0.5 * frac * (b[2] - a[2]),
];
let mid2 = [
a[0] + frac * (b[0] - a[0]),
a[1] + frac * (b[1] - a[1]),
a[2] + frac * (b[2] - a[2]),
];
refined.observe(&mid1);
refined.observe(&mid2);
refined.observe(&b);
}
for (idx, (&c, &r)) in coarse.signature().iter().zip(refined.signature()).enumerate() {
prop_assert!(
(c - r).abs() < 1e-7 * (1.0 + c.abs()),
"Subdivision invariance failed at term {}: coarse={} refined={}",
idx,
c,
r
);
}
}
}
}