Algorithm for data alignment of float arrays in Java

Question

I have two float arrays representing y values in a line chart. Now I want to align these two charts. Are there any existing algorithms for alignment of the two arrays?

A very simple example

a:
2.5 1.3 1.6 4.2 3.6

b:
3.3 1.4 2.5 1.3 1.6

Now after alignment it should be:

        2.5 1.3 1.6 4.2 3.6
3.3 1.4 2.5 1.3 1.6

In reality it is much more complex with each array having a size of about 30 000 and floats like -6.94709206

Answer 1

This is basically normal pattern matching, you should be able to use most simple algorithms suitable for character matching as well.

Worst case for simple search would typically be n*m (assuming that n and m are the length of your float sequences), maybe you can reduce the runtime using an algorithm similar to Boyer-Moore towards being linear if one of the sequences remain the same.

Answer 2

Assuming, that both arrays match at a certain part.

1. Use binary search to find the position of the first element of a inside b
2. If there doesn't exist such a position, find position of first element of b inside a
3. If theres still no match, put a behind b, if first a > last b -- b behind a otherwise