Algorithm for data alignment of float arrays in Java

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 havi开发者_C百科ng a size of about 30 000 and floats like -6.94709206

In principle, that's easy:

for (an=0;an<a.length;++an)
{
  for (bn=0;bn<b.length;++bn)
  {
    if (a[an]==b[bn])
    {
      boolean run=true;
      for (offset=1;offset<a.length-an && offset<b.length-bn;++offset)
      {
        if (a[an+offset]!=b[bn+offset])
        {
          run=false;
          break;
        }
      }
      if (run)
        ... match at a[an], etc matching b[bn], etc
    }
  }
}
... no match ...

With floats, you'd have the issue that they might not really have to be exactly equal to be considered a match if there's any possibilty of inexactness in your data. Instead of a[an]==b[bn] you might want to say abs(a[an]-b[bn])<errorMargin or some such.

Disclaimer: Code is off the top of my head and untested. No warranties expressed or implied. Your mileage may vary. Void where prohibited. If rash develops, consult your physician.

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.

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