MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: dynamic time warping algorithm

  • To: mathgroup at smc.vnet.net
  • Subject: [mg43080] Re: [mg43057] Re: [mg42867] dynamic time warping algorithm
  • From: Dr Bob <drbob at bigfoot.com>
  • Date: Mon, 11 Aug 2003 02:15:58 -0400 (EDT)
  • References: <200308100546.BAA26284@smc.vnet.net>
  • Reply-to: drbob at bigfoot.com
  • Sender: owner-wri-mathgroup at wolfram.com

> (* Convert the given strings to lists of numbers 1, 2, 3, 4. *)
> rules = {A->1, B->2, C->3, D->4};
> q = ToExpression[Characters[ToString[AAAAABBCCCCCCCCDDD]]]/.rules;
> c = ToExpression[Characters[ToString[AABBBBBBCDDDDDD]]]/.rules;

I'd use

ToCharacterCode["aAZz"] - 64

or

ToCharacterCode@ToUpperCase["aAZz"] - 64

Bobby

On Sun, 10 Aug 2003 01:46:47 -0400 (EDT), Rob Pratt <rpratt at email.unc.edu> 
wrote:

> On Thu, 31 Jul 2003, Sujai wrote:
>
>> i came across an algorithm for dynamic time warping in this article:
>> http://citeseer.nj.nec.com/keogh00scaling.html
>>
>> we are trying to use the algorithm to calculate the distance between two
>> sequences (of letters, for eg: AAAAABBCCCCCCCCDDD and AABBBBBBCDDDDDD).
>>
>> i understand the algorithm but have never used the dynamic programming
>> technique described in the article.
>>
>> would anyone here know how this could be implemented in mathematica or
>> if there is a resource where this has been done before? i have no idea
>> where to even begin.
>>
>> thanks in advance,
>>
>> - sujai
>
>
> The following should get you started.  The key idea is the use of
> f[x_] := f[x] = some function of x
> to store values of a function once they are computed.
>
> (* Convert the given strings to lists of numbers 1, 2, 3, 4. *)
> rules = {A->1, B->2, C->3, D->4};
> q = ToExpression[Characters[ToString[AAAAABBCCCCCCCCDDD]]]/.rules;
> c = ToExpression[Characters[ToString[AABBBBBBCDDDDDD]]]/.rules;
>
> d[x_,y_] := d[x,y] = Abs[x-y];
> (* I'm assuming this is the appropriate distance function, but you can 
> use
> whatever you want. *)
>
> (* boundary conditions *)
> g[1, 1] = d[q[[1]], c[[1]]];
>
> g[1, j_] := g[1, j] = d[q[[1]], c[[j]]] + g[1, j - 1]
>
> g[i_, 1] := g[i, 1] = d[q[[i]], c[[1]]] + g[i - 1, 1]
>
> (* main recursion: equation (5) in the article *)
> g[i_, j_] := g[i, j] =
> d[q[[i]], c[[j]]] + Min[g[i - 1, j - 1], g[i - 1, j], g[i, j - 1]]
>
> In the notation of the article, n = Length[q] = 18 and m = Length[c] = 
> 15.
> So the distance between the two sequences is g[n,m] = g[18,15], which
> turns out to be 0.
>
> You can use Outer[d,q,c] to see the distance matrix and
> Outer[g,Range[n],Range[m]] to see the cumulative distance matrix.
>
> left corner to the bottom right corner consisting entirely of zeros.  (In
> the article, the vertical axis is reversed so that the warping path goes
> from bottom left corner to top right corner.)
>
> Note that your sequences can be preprocessed by the following
> distance-preserving transformation: replace all runs by a single element.
> In other words, your q and c both become {1, 2, 3, 4}, from which it is
> even more obvious that the distance between them is zero.  This
> transformation can be accomplished using Map[First,Split[q]].
>
> Rob Pratt
> Department of Operations Research
> The University of North Carolina at Chapel Hill
>
> rpratt at email.unc.edu
>
> http://www.unc.edu/~rpratt/
>
>



-- 
majort at cox-internet.com
Bobby R. Treat


  • Prev by Date: Re: Re: solve errors...
  • Next by Date: Re: Writing graphics to another notebook?
  • Previous by thread: Re: dynamic time warping algorithm
  • Next by thread: Re: Mathematica 5.0: small change in fundamental behavior.