0
# Core DTW Distance Calculation
1

2
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.
3

4
## Capabilities
5

6
### Basic Distance Calculation
7

8
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.
9

10
```python { .api }
11
def distance(s1, s2, window=None, max_dist=None, max_step=None, 
12
             max_length_diff=None, penalty=None, psi=None, use_c=False):
13
    """
14
    Compute DTW distance between two sequences using compact matrix.
15
    
16
    Parameters:
17
    - s1, s2: array-like, input time series sequences
18
    - window: int, Sakoe-Chiba band constraint (warping window)
19
    - max_dist: float, early stopping threshold - computation stops if distance exceeds this
20
    - max_step: float, maximum allowable step size in warping path
21
    - max_length_diff: int, maximum allowed difference in sequence lengths
22
    - penalty: float, penalty for compression/expansion operations
23
    - psi: int, psi relaxation parameter for cyclical sequences
24
    - use_c: bool, whether to use optimized C implementation if available
25
    
26
    Returns:
27
    float: DTW distance between the two sequences
28
    """
29
```
30

31
### Fast C Implementation
32

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

35
```python { .api }
36
def distance_fast(s1, s2, window=None, max_dist=None, max_step=None,
37
                  max_length_diff=None, penalty=None, psi=None):
38
    """
39
    Fast C version of DTW distance calculation.
40
    
41
    Automatically uses the optimized C implementation without needing use_c=True.
42
    Falls back to Python implementation if C extensions unavailable.
43
    
44
    Parameters:
45
    Same as distance() function but automatically uses C implementation.
46
    
47
    Returns:
48
    float: DTW distance between the two sequences
49
    """
50
```
51

52
### Lower Bound Calculation
53

54
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.
55

56
```python { .api }
57
def lb_keogh(s1, s2, window=None, max_dist=None, max_step=None, 
58
             max_length_diff=None):
59
    """
60
    Compute LB_Keogh lower bound for DTW distance.
61
    
62
    The LB_Keogh bound provides a fast lower bound estimate that can be used
63
    for pruning in nearest neighbor search and clustering applications.
64
    
65
    Parameters:
66
    - s1, s2: array-like, input sequences
67
    - window: int, warping window constraint
68
    - max_dist: float, early stopping threshold
69
    - max_step: float, maximum step size
70
    - max_length_diff: int, maximum length difference
71
    
72
    Returns:
73
    float: LB_Keogh lower bound distance
74
    """
75
```
76

77
## Usage Examples
78

79
### Basic Distance Calculation
80

81
```python
82
from dtaidistance import dtw
83

84
# Simple distance calculation
85
s1 = [0, 0, 1, 2, 1, 0, 1, 0, 0]
86
s2 = [0, 1, 2, 0, 0, 0, 0, 0, 0]
87

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

92
# Using fast C implementation
93
distance_fast = dtw.distance_fast(s1, s2)
94
print(f"Fast DTW distance: {distance_fast}")
95
```
96

97
### Distance with Constraints
98

99
```python
100
from dtaidistance import dtw
101

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

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

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

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

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

117
print(f"Windowed DTW: {distance_windowed}")
118
print(f"Early stopping DTW: {distance_early_stop}")
119
print(f"Step-limited DTW: {distance_step_limited}")  
120
print(f"Penalty DTW: {distance_penalty}")
121
```
122

123
### Performance Comparison
124

125
```python
126
from dtaidistance import dtw
127
import time
128
import numpy as np
129

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

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

139
# Time C implementation
140
start = time.time()
141
dist_c = dtw.distance_fast(s1, s2)
142
c_time = time.time() - start
143

144
print(f"Python DTW: {dist_python:.4f} in {python_time:.4f}s")
145
print(f"C DTW: {dist_c:.4f} in {c_time:.4f}s")
146
print(f"Speedup: {python_time/c_time:.2f}x")
147
```
148

149
### Lower Bound for Pruning
150

151
```python
152
from dtaidistance import dtw
153

154
def find_similar_series(query, candidates, threshold=10.0):
155
    """Find similar series using LB_Keogh pruning."""
156
    similar_series = []
157
    
158
    for i, candidate in enumerate(candidates):
159
        # Quick lower bound check
160
        lb = dtw.lb_keogh(query, candidate, window=5)
161
        
162
        if lb <= threshold:
163
            # Lower bound passed, compute exact DTW
164
            exact_dist = dtw.distance(query, candidate, window=5)
165
            if exact_dist <= threshold:
166
                similar_series.append((i, exact_dist))
167
    
168
    return similar_series
169

170
# Example usage
171
query = [1, 2, 3, 2, 1]
172
candidates = [
173
    [1, 2, 3, 2, 1],      # Very similar
174
    [2, 3, 4, 3, 2],      # Similar with offset
175
    [5, 6, 7, 8, 9],      # Very different
176
    [1, 3, 2, 1, 2]       # Somewhat similar
177
]
178

179
matches = find_similar_series(query, candidates, threshold=3.0)
180
print("Similar series found:", matches)
181
```
182

183
## Common Constraint Parameters
184

185
### Window Constraint (Sakoe-Chiba Band)
186

187
The `window` parameter constrains the warping path to stay within a diagonal band:
188
- `window=0`: No warping allowed (Euclidean distance)  
189
- `window=1`: Very restrictive warping
190
- `window=len(sequence)`: No constraint (full DTW)
191

192
### Early Stopping
193

194
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.
195

196
### Step Size Constraint
197

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

200
### Length Difference Constraint  
201

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

204
### Penalty System
205

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

208
### Psi Relaxation
209

210
The `psi` parameter is designed for cyclical or periodic sequences, allowing relaxed boundary conditions at the beginning and end of sequences.