fraug/quality_benchmarking/
dtw.rs

1/// Implementation of Dynamic Time Warping (DTW) algorithm.
2/// This function computes the DTW distance between two sequences and returns the distance
3/// along with the optimal path.
4/// # Arguments
5/// * `a` - First sequence as a slice of f64 values.
6/// * `b` - Second sequence as a slice of f64 values.
7/// # Returns
8/// A tuple containing the DTW distance (f64) and a vector of tuples representing the
9/// optimal path as pairs of indices (usize, usize).
10/// # Examples
11/// ```
12/// use fraug::quality_benchmarking::dtw;
13/// let a = vec![1.0, 2.0, 3.0];
14/// let b = vec![2.0, 3.0, 4.0];
15/// let (distance, path) = dtw(&a, &b);
16/// ```
17
18pub fn dtw(a: &[f64], b: &[f64]) -> (f64, Vec<(usize, usize)>) {
19    let n = a.len();
20    let m = b.len();
21    let mut cost = vec![vec![f64::INFINITY; m + 1]; n + 1];
22    cost[0][0] = 0.0;
23    for i in 1..=n {
24        for j in 1..=m {
25            let diff = (a[i - 1] - b[j - 1]).abs();
26            let min_prev = cost[i - 1][j].min(cost[i][j - 1]).min(cost[i - 1][j - 1]);
27            cost[i][j] = diff + min_prev;
28        }
29    }
30    let distance = cost[n][m];
31    // Backtrack to get the best path
32    let mut path = Vec::new();
33    let (mut i, mut j) = (n, m);
34    while i > 0 || j > 0 {
35        path.push((i - 1, j - 1));
36        if i == 0 {
37            j -= 1;
38        } else if j == 0 {
39            i -= 1;
40        } else {
41            let diag = cost[i - 1][j - 1];
42            let up = cost[i - 1][j];
43            let left = cost[i][j - 1];
44            if diag <= up && diag <= left {
45                i -= 1;
46                j -= 1;
47            } else if up < left {
48                i -= 1;
49            } else {
50                j -= 1;
51            }
52        }
53    }
54    path.reverse();
55    (distance / n as f64, path)
56}
fraug/quality_benchmarking/dtw.rs

fraug/quality_benchmarking/
dtw.rs
