1
$\begingroup$

I have a linear numerical array source and I want to find/match test array as pattern :

source = [39,36,23,21,28,36,30,22,34,37]
test = [36,23,21,28]

we can use brute force or similar method for finding the exact match, by checking test array from index 0 to len(source)-len(test)

but in our problem, we can accept this pattern too ( order is important )

test = [36,24,21,28] // changed 23 to 24

since we have many different ways of solving this problem ( maybe fuzzy!), I want to know the title of some solutions.

$\endgroup$
  • $\begingroup$ It's not clear from your question what a correct match should be? Does the test have to be a consecutive subsequence with minor modification? Does order matter or a sequence with the same numbers in a different order can also be a match? Are you interested in a similarity score? $\endgroup$ – Erwan Jan 27 at 21:00
  • $\begingroup$ the big problem is I am in the middle of a problem without any background knowledge.The answer for your first and second questions are <yes>. the order is important too. lets put it in this way , I can accept the array as matched with ±2 units change for each element. $\endgroup$ – Mironline Jan 27 at 21:24
1
$\begingroup$

According to your definition (consecutive, order matters, max +/-2 difference), it's not a fuzzy matching case. It's just a minor variant of searching a subsequence:

for i=0 to len(source)-len(test) {
  j=0
  while (j<len(test)) && (abs(source[i+j]-test[j]) <= 2) {
    j++
  if (j == len(test)) { 
     // match found
  }
}

This is the simple version, in case efficiency is an issue there is a more efficient version using dynamic programming.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.