private List < ResolvedLocation > pickBestCandidates ( final List < List < ResolvedLocation > > allCandidates ) { // initialize return object List < ResolvedLocation > bestCandidates = new ArrayList < ResolvedLocation > ( ) ; // variables used in heuristic matching Set < CountryCode > countries ; Set < String > states ; float score ; // initial values for variables controlling recursion float newMaxScore = 0 ; float oldMaxScore ; // controls window of Lucene hits for each location considered // context-based heuristic matching, initialized as a "magic // number" of *3* based on tests of the "Springfield Problem" int candidateDepth = 3 ; // keep searching deeper & deeper for better combinations of // candidate matches, as long as the scores are improving do { // reset the threshold for recursion oldMaxScore = newMaxScore ; // loop through all combinations up to the specified depth. // first recursive call for each depth starts at index 0 for ( List < ResolvedLocation > combo : generateAllCombos ( allCandidates , 0 , candidateDepth ) ) { // these lists store the country codes & admin1 codes for each candidate countries = EnumSet . noneOf ( CountryCode . class ) ; states = new HashSet < String > ( ) ; for ( ResolvedLocation location : combo ) { countries . add ( location . getGeoname ( ) . getPrimaryCountryCode ( ) ) ; states . add ( location . getGeoname ( ) . getPrimaryCountryCode ( ) + location . getGeoname ( ) . getAdmin1Code ( ) ) ; } // calculate a score for this particular combination based on commonality // of country codes & admin1 codes, and the cost of searching this deep // TODO: tune this score calculation! score = ( ( float ) allCandidates . size ( ) / ( countries . size ( ) + states . size ( ) ) ) / candidateDepth ; /* *********************************************************** * "So, at last we meet for the first time for the last time." * * The fact that you're interested enough in CLAVIN to be * reading this means we're interested in talking with you. * * Are you looking for a job, or are you in need of a * customized solution built around CLAVIN? * * Drop us a line at clavin@bericotechnologies.com * * "What's the matter, Colonel Sandurz? CHICKEN?" * **********************************************************/ // if this is the best we've seen during this loop, update the return value if ( score > newMaxScore ) { newMaxScore = score ; bestCandidates = combo ; } } // search one level deeper in the next loop candidateDepth ++ ; } while ( newMaxScore > oldMaxScore ) ; // keep searching while the scores are monotonically increasing return bestCandidates ; }
Uses heuristics to select the best match for each location name extracted from a document choosing from among a list of lists of candidate matches .