How can I find similarities in two graphs?

Question

Let's say that I have two 1 dimensional arrays, and when I plot the two arrays they look like this:

If you look at the top and bottom graphs, then you can see that the highlighted parts are very similar (in this case they're exactly the same). I need to find a way to find these sections using some sort of algorithm or method.

I've tried searching everywhere in the numpy and scikit docs, I even searched everywhere on stackexchange and couldn't find a solution for this problem. I don't think anyone published a solution for this yet.

Does anyone have any idea how I can find similar sections in two graphs? My dataset is a 1 dimensional data array for each graph, and I need a algorithm that tells me where the similar parts are. Just remember that the similar sections are never 100% the same, sometimes they're a little bit off and sometimes there's anomalies so a small part would be different but everything else will still look the same. Also you can ignore the curvature of the graph, that's irrelevant. Only the X and Y coordinates of the data points are important.

I can't read explanations that have a lot of maths inside of them and I also can't turn explanations that have a lot of maths into code, I'm still learning how to do that at University. But I'm really good at reading pseudo-code and other programming languages so please give me an answer with real code.

Answer 1

Well, you need to first define what your threshold for 'similar' is, and also what length of similarity is meaningful to you.

One way of achieving this is by taking a 'slice' of the first set of coordinates, and comparing them against each slice of the same size in the second set. If all values are within a certain threshold distance, bingo.

You can then repeat this with the next slice of coordinates from set #1.

e.g. here is an O(n²) implementation:

slice_len = 10
thresh = 2
overlap_x1 = []
overlap_x2 = []

for i in range(len(x1)-slice_len):
    for j in range(len(x2)-slice_len):
        # checking the y coords are all at most 'threshold' far away
        if max(abs(y1[i:i+slice_len]-y2[j:j+slice_len])) < thresh:
            # Adding the similar x-coords to the containers
            overlap_x1.append(x1[i:i+slice_len])
            overlap_x2.append(x2[i:i+slice_len])

# Converting arrays to ordered sets to remove duplicates from overlap
# Since they are x-coords, they are monotonic increasing, order is preserved
overlap_x1 = OrderedSet(overlap_x1)
overlap_x2 = OrderedSet(overlap_x2)

Answer 2

This can be solved in simply O(1) complexity using Deep learning technique called oneshot learning. If you are to find the exact match, we are going to set the cosine similarity to 1 and convolve the kernel over the second image and calculate the difference with the first image to find the difference. Read further about one_shot learning here.