Algorithm for finding record with most matching attributes
I'm looking for some algorithm that for a given record with n properties with n possible values each (int, string etc) searches a number of existing records a开发者_如何学Cnd gives back the one that matches the most properties.
Example:
A = 1
B = 1
C = 1
D = f
A | B | C | D
----+-----+-----+----
1 | 1 | 9 | f <
2 | 3 | 1 | g
3 | 4 | 2 | h
2 | 5 | 8 | j
3 | 6 | 5 | h
The first row would be the one I'm looking for, as it has the most matching values. I think it doesn't need to calculate any closeness to the values, because then row 2 might be more matching.
Loop through each row, add one to the row score of a field matches (field one has a score of 2) and when that's done, you have a resultset of scores which you can sort.
The basic algorithm could look like (in java pseudo code):
int bestMatchIdx = -1;
int currMatches = 0;
int bestMatches = 0;
for ( int row = 0 ; row < numRows ; row++ ) {
currMatches = 0;
for ( int col = 0 ; col < numCols ; col++ ) {
if ( search[col].equals( rows[ row ][ cols] ))
currMatches++;
}
if ( currMatches > bestMatches ) {
bestMatchIdx = row;
bestMatches = currMatches;
}
}
This assumes that you have an equals function to compare, and the data stored in a 2D array. 'search' is the reference row to compare all other rows against it.
精彩评论