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