for different length prefixes of the string P,
and in my table,
essentially this means that I'm going to go in a top-down manner.
In this case, what I'm going to do is I will start with two,
then I will add two to two,
this is going to give me the value four,
then I am going to add value five to four,
this is going to give me value nine,
that I'm going to add the value three to my value nine,
this going to give me value 12 and so on.
This way, first I fill left right
the first row and then I fill in a bottom-up manner the first column,
and I'm done with the first row and first column.
What do I do next?
Then I move to the next row and the next column.
After that, I will compute the following row and the following column,
and after that I will compute the following row and the following column,
and this way I will fill the entire table.
That's essentially basically how the dynamic time warping works.
So, let's see the following step,
in the following step,
as I mentioned I will fill the following row starting from this entry.
So, how do I obtain the value of the ten three.
Let's take a look at this, so first of all in my table,
I know that the cost of replacing nine with five is four.
So, that I know that my table records
that it tells me that the cost of replacement is four.
Then I have three options,
I need to to either move on the string P
or move on string Q or move on both strings or both time series.
The cost of moving on time series P,
I'd already computed its value was four.
The cost of moving on time-series Q,
once again I had computed before,
its cost is two.
The cost of moving on both time series again I had computed earlier,
its cost was two.
So, the cost of
moving on P on
Q or on both of them,
is either four plus four eight,
or four plus two six,
or four plus two six.
So, given that I'm trying to find the minimum distance,
essentially what I will do I will simply select the smallest of these values.
That is basically what algorithm is telling me to do,
the algorithm is telling me to do is,
either move on P or move on Q or move on both of them,
at the cost of replacement and select the minimum among them.
So, if I do that essentially what I have to do,
as you can see is replaced the entry with three.
The next one let's do it again,
so the cost of replacement is three,
I can either basically move on P, would cost nine,
I can move on Q with cost
12 or I can move on both of them with the cost three plus two cost five.
So, obviously, I will select the smallest one which is
five and then I repeat this process to fill the entire table.
So, once I fill the entire table, essentially,
the last entry here tells me the cost
of dynamic time warping between these two strings 80.
So essentially, what this tells me that the cost of converting from
one time series to the other using the dynamic time warping algorithm has caused 80.
The difference between these two time series is 18,
that's the minimum error that I have to introduce to warp one time series to the others.
Note that this eighteen essentially can correspond to different ways of warping the time.
So, one alternative of this is to see that essentially what we are doing is,
we are first aligning for an eight.
Then, we are aligning four and five.
Then, we are aligning five and five.
Then, we are aligning five and six.
Then, we are aligning four and seven, and so on.
Essentially, the way you're going to find
the alignments is to remember how the algorithm is working.
So, remember the first step
is basically the way algorithm works data lines, the last elements.
In this case, the alignment of four and eight is given,
I align those elements.
After that, remember, I basically when I compute this 18,
I compute that by selecting the
smallest of the three alternative replacement that I have.
In this case, I can either select 17, 14, 14.
Seventeen is a large replacement,
I will not select that for sure.
So I will basically select either this 14 or that 14.
Let's assume that I had selected this 14 to compute 18.
Which essentially would mean that basically I'm aligning this entry with this actually.
Now, once I have this alignment,
I will again select basically between 14, 14, and 13.
Obviously, dynamic tower the way it works
is that I would have selected the smallest among
them which is the 13 which is basically alignment between five and five,
so I would align as the next element five and five.