A Python implementation of FastDTW

slaypni, updated 🕥 2023-03-25 20:37:09

fastdtw

Python implementation of FastDTW <http://cs.fit.edu/~pkc/papers/tdm04.pdf> [1], which is an approximate Dynamic Time Warping (DTW) algorithm that provides optimal or near-optimal alignments with an O(N) time and memory complexity.

Install

::

pip install fastdtw

Example

::

import numpy as np from scipy.spatial.distance import euclidean

from fastdtw import fastdtw

x = np.array([[1,1], [2,2], [3,3], [4,4], [5,5]]) y = np.array([[2,2], [3,3], [4,4]]) distance, path = fastdtw(x, y, dist=euclidean) print(distance)

References

.. [1] Stan Salvador, and Philip Chan. "FastDTW: Toward accurate dynamic time warping in linear time and space." Intelligent Data Analysis 11.5 (2007): 561-580.

Issues

Handling collections of strings as an input

opened on 2023-03-25 20:37:09 by PR0123

Can be used with edit distance algorithms. Example:

```python template = ["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"] query = ["the", "fox", "the", "dog"] out = fastdtw(template, query, dist=Levenshtein.distance)

output: (21, [(0, 0), (1, 1), (2, 1), (3, 1), (4, 2), (5, 2), (6, 2), (7, 3), (8, 3)])

```

Add partial matching

opened on 2023-03-20 15:19:11 by trueroad

Add partial matching

This pull request adds partial matching DTW like #27 . The difference between #27 and this is as follows.

  • This has both .py and .pyx implementations.
  • This allows a path's starting and ending points to be specified independently as full or partial matching.
  • This allows fine control of partial match precision by specifying different radius in the x-directions (long data) and y-directions (short data).

Examples

```

import numpy as np import fastdtw x = np.array([1, 2, 3, 4, 5], dtype='float') y = np.array([2, 3, 4], dtype='float') fastdtw.fastdtw(x, y) (2.0, [(0, 0), (1, 0), (2, 1), (3, 2), (4, 2)]) fastdtw.fastdtw(x, y, b_partial_start=True) (1.0, [(1, 0), (2, 1), (3, 2), (4, 2)]) fastdtw.fastdtw(x, y, b_partial_end=True) (1.0, [(0, 0), (1, 0), (2, 1), (3, 2)]) fastdtw.fastdtw(x, y, b_partial_start=True, b_partial_end=True) (0.0, [(1, 0), (2, 1), (3, 2)]) ```

I created this pull request with reference to SPRING [1][2].

SPRING is a streaming method for subsequence matching in data streams. It differs from regular DTW in that it calculates partial matching.

In SPRING, the starting point for partial matching is obtained by star-padding and STWM. This commit adds b_partial_start flag, and if it is True, __dtw() calculates the matching start point by the star-padding-like and the STWM-like behavior.

In SPRING, the ending point for the partial matching is obtained as the ending point of the optimal subsequence as the data streaming progresses. However, __dtw() does not handle data streams. This commit adds b_partial_end flag, and if it is True, __dtw() calculates the matching ending point as the point with the lowest DTW distance.

[1] Yasushi Sakurai, Christos Faloutsos, Masashi Yamamuro: Stream Monitoring under the Time Warping Distance, ICDE2007, https://doi.org/10.1109/ICDE.2007.368963

[2] Yasushi Sakurai, Christos Faloutsos, Masashi Yamamuro: Stream Processing under the Dynamic Time Warping Distance, DEWS2007, https://www.ieice.org/iss/de/DEWS/DEWS2007/pdf/l6-5.pdf

Question about __expand_window()

opened on 2022-12-28 17:56:30 by vascosantos

Hi!

Thank you for developing and sharing this library. I have been using it quite successfully.

In function __expand_window(), is there a reason for thickening the path with radius before doubling the search window axes rather than the other way around? This way the search window becomes 4 * radius instead of 2 * radius.

Thanks in advance, Vasco.

Bump certifi from 2019.3.9 to 2022.12.7

opened on 2022-12-08 04:58:00 by dependabot[bot]

Bumps certifi from 2019.3.9 to 2022.12.7.

Commits


Dependabot compatibility score

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.


Dependabot commands and options
You can trigger Dependabot actions by commenting on this PR: - `@dependabot rebase` will rebase this PR - `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it - `@dependabot merge` will merge this PR after your CI passes on it - `@dependabot squash and merge` will squash and merge this PR after your CI passes on it - `@dependabot cancel merge` will cancel a previously requested merge and block automerging - `@dependabot reopen` will reopen this PR if it is closed - `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually - `@dependabot ignore this major version` will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this minor version` will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this dependency` will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself) - `@dependabot use these labels` will set the current labels as the default for future PRs for this repo and language - `@dependabot use these reviewers` will set the current reviewers as the default for future PRs for this repo and language - `@dependabot use these assignees` will set the current assignees as the default for future PRs for this repo and language - `@dependabot use this milestone` will set the current milestone as the default for future PRs for this repo and language You can disable automated security fix PRs for this repo from the [Security Alerts page](https://github.com/slaypni/fastdtw/network/alerts).

Bump ipython from 7.4.0 to 7.16.3

opened on 2022-01-21 19:50:24 by dependabot[bot]

Bumps ipython from 7.4.0 to 7.16.3.

Commits


Dependabot compatibility score

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.


Dependabot commands and options
You can trigger Dependabot actions by commenting on this PR: - `@dependabot rebase` will rebase this PR - `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it - `@dependabot merge` will merge this PR after your CI passes on it - `@dependabot squash and merge` will squash and merge this PR after your CI passes on it - `@dependabot cancel merge` will cancel a previously requested merge and block automerging - `@dependabot reopen` will reopen this PR if it is closed - `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually - `@dependabot ignore this major version` will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this minor version` will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this dependency` will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself) - `@dependabot use these labels` will set the current labels as the default for future PRs for this repo and language - `@dependabot use these reviewers` will set the current reviewers as the default for future PRs for this repo and language - `@dependabot use these assignees` will set the current assignees as the default for future PRs for this repo and language - `@dependabot use this milestone` will set the current milestone as the default for future PRs for this repo and language You can disable automated security fix PRs for this repo from the [Security Alerts page](https://github.com/slaypni/fastdtw/network/alerts).

Accessing fastdtw from C language

opened on 2021-09-23 22:07:31 by sriharsha-sammeta

Hi, I see that the main library is implemented in C. Can you please point out steps to load and call the fastdtw function from C language instead of python?