tessl/pypi-dtaidistance

Distance measures for time series with Dynamic Time Warping as the primary focus

—

Pending

Overview

Eval results

Files

Core DTW Distance Calculation

Name: tessl/pypi-dtaidistance
Author: tessl

Fundamental DTW distance computation between time series pairs. This module provides the primary algorithms for calculating Dynamic Time Warping distances with various constraint-based optimizations, early stopping mechanisms, and both Python and C implementations for performance flexibility.

Capabilities

Basic Distance Calculation

Compute DTW distance between two sequences using the compact matrix approach, which is memory-efficient for simple distance calculations without requiring the full warping paths matrix.

def distance(s1, s2, window=None, max_dist=None, max_step=None, 
             max_length_diff=None, penalty=None, psi=None, use_c=False):
    """
    Compute DTW distance between two sequences using compact matrix.
    
    Parameters:
    - s1, s2: array-like, input time series sequences
    - window: int, Sakoe-Chiba band constraint (warping window)
    - max_dist: float, early stopping threshold - computation stops if distance exceeds this
    - max_step: float, maximum allowable step size in warping path
    - max_length_diff: int, maximum allowed difference in sequence lengths
    - penalty: float, penalty for compression/expansion operations
    - psi: int, psi relaxation parameter for cyclical sequences
    - use_c: bool, whether to use optimized C implementation if available
    
    Returns:
    float: DTW distance between the two sequences
    """

Fast C Implementation

High-performance C implementation of DTW distance calculation with automatic fallback to Python implementation if C extensions are unavailable.

def distance_fast(s1, s2, window=None, max_dist=None, max_step=None,
                  max_length_diff=None, penalty=None, psi=None):
    """
    Fast C version of DTW distance calculation.
    
    Automatically uses the optimized C implementation without needing use_c=True.
    Falls back to Python implementation if C extensions unavailable.
    
    Parameters:
    Same as distance() function but automatically uses C implementation.
    
    Returns:
    float: DTW distance between the two sequences
    """

Lower Bound Calculation

Compute the LB_Keogh lower bound for DTW distance, which provides a fast approximation that can be used for pruning in large-scale similarity search applications.

def lb_keogh(s1, s2, window=None, max_dist=None, max_step=None, 
             max_length_diff=None):
    """
    Compute LB_Keogh lower bound for DTW distance.
    
    The LB_Keogh bound provides a fast lower bound estimate that can be used
    for pruning in nearest neighbor search and clustering applications.
    
    Parameters:
    - s1, s2: array-like, input sequences
    - window: int, warping window constraint
    - max_dist: float, early stopping threshold
    - max_step: float, maximum step size
    - max_length_diff: int, maximum length difference
    
    Returns:
    float: LB_Keogh lower bound distance
    """

Usage Examples

Basic Distance Calculation

from dtaidistance import dtw

# Simple distance calculation
s1 = [0, 0, 1, 2, 1, 0, 1, 0, 0]
s2 = [0, 1, 2, 0, 0, 0, 0, 0, 0]

# Basic DTW distance
distance = dtw.distance(s1, s2)
print(f"DTW distance: {distance}")

# Using fast C implementation
distance_fast = dtw.distance_fast(s1, s2)
print(f"Fast DTW distance: {distance_fast}")

Distance with Constraints

from dtaidistance import dtw

s1 = [1, 2, 3, 4, 5, 4, 3, 2, 1]
s2 = [2, 3, 4, 5, 4, 3, 2, 1, 0]

# DTW with Sakoe-Chiba band constraint
distance_windowed = dtw.distance(s1, s2, window=3)

# DTW with early stopping
distance_early_stop = dtw.distance(s1, s2, max_dist=10.0)

# DTW with step size constraint
distance_step_limited = dtw.distance(s1, s2, max_step=2.0)

# DTW with compression/expansion penalty
distance_penalty = dtw.distance(s1, s2, penalty=0.1)

print(f"Windowed DTW: {distance_windowed}")
print(f"Early stopping DTW: {distance_early_stop}")
print(f"Step-limited DTW: {distance_step_limited}")  
print(f"Penalty DTW: {distance_penalty}")

Performance Comparison

from dtaidistance import dtw
import time
import numpy as np

# Generate longer sequences for performance testing
s1 = np.random.randn(1000)
s2 = np.random.randn(1000)

# Time Python implementation
start = time.time()
dist_python = dtw.distance(s1, s2, use_c=False)
python_time = time.time() - start

# Time C implementation
start = time.time()
dist_c = dtw.distance_fast(s1, s2)
c_time = time.time() - start

print(f"Python DTW: {dist_python:.4f} in {python_time:.4f}s")
print(f"C DTW: {dist_c:.4f} in {c_time:.4f}s")
print(f"Speedup: {python_time/c_time:.2f}x")

Lower Bound for Pruning

from dtaidistance import dtw

def find_similar_series(query, candidates, threshold=10.0):
    """Find similar series using LB_Keogh pruning."""
    similar_series = []
    
    for i, candidate in enumerate(candidates):
        # Quick lower bound check
        lb = dtw.lb_keogh(query, candidate, window=5)
        
        if lb <= threshold:
            # Lower bound passed, compute exact DTW
            exact_dist = dtw.distance(query, candidate, window=5)
            if exact_dist <= threshold:
                similar_series.append((i, exact_dist))
    
    return similar_series

# Example usage
query = [1, 2, 3, 2, 1]
candidates = [
    [1, 2, 3, 2, 1],      # Very similar
    [2, 3, 4, 3, 2],      # Similar with offset
    [5, 6, 7, 8, 9],      # Very different
    [1, 3, 2, 1, 2]       # Somewhat similar
]

matches = find_similar_series(query, candidates, threshold=3.0)
print("Similar series found:", matches)

Common Constraint Parameters

Window Constraint (Sakoe-Chiba Band)

The window parameter constrains the warping path to stay within a diagonal band:

window=0: No warping allowed (Euclidean distance)
window=1: Very restrictive warping
window=len(sequence): No constraint (full DTW)

Early Stopping

The max_dist parameter enables early termination when the accumulated distance exceeds the threshold, significantly speeding up computations when only checking if distance is below a threshold.

Step Size Constraint

The max_step parameter limits how large steps can be in the warping path, preventing excessive stretching or compression of the time series.

Length Difference Constraint

The max_length_diff parameter rejects sequence pairs with length differences exceeding the threshold, useful for applications where sequences should be similar in length.

Penalty System

The penalty parameter adds a cost to non-diagonal moves in the warping path, discouraging excessive warping and encouraging more conservative alignments.