My problem is generalization of the simple problem:
Search for item $x$ in a set $S$.
This is trivial to do it fast if the elements are comparable. Sort the $S$, and do the binary search.
My problem is that I'm interested in partial match. That is, my items are ordered sets of $n = 15$ numbers, and I consider them equal if they have $m = 10$ numbers (at same position) same. For smaller numbers (like 5 out of 6), I can use $n = 6$ sorted sets that have all $m = 5$ number subsets of preprocessed items and then just do 6 binary searches. But for large numbers $n$ and $m$ where $n - m > 2$ number of sets (the binomial coefficient) explodes.
Is there efficient way to search for a partial match?
The only thing that I could think of is to index each number of the set. For example, when preprocessing size 3 sets:
1->(set0,pos0)(position is important), 2->(set0,pos1),(set1,pos0) ... (4->set1,pos2)
and then when I get a new number, I just go for the each number in it and check the sets in which it appears. If there is a set that has many hits (say 10 or more), they are declared the same.
Of course I could use an array trick (i.e. array contains the pointer to the list of sets that contain 1234). This works for small ranges. For large ranges, I could hash the number and do modulo.
Of course this could go very very wrong for some distributions of preprocessed data.
So is there a better way?