nl_tokens: Locate the best instance of pattern in text near loc using the Bitap algorithm . Returns - 1 if no match found .
pl_tokens: protected int match_bitap ( String text , String pattern , int loc ) { assert ( Match_MaxBits == 0 || pattern . length ( ) <= Match_MaxBits ) : "Pattern too long for this application." ; // Initialise the alphabet. Map < Character , Integer > s = match_alphabet ( pattern ) ; // Highest score beyond which we give up. double score_threshold = Match_Threshold ; // Is there a nearby exact match? (speedup) int best_loc = text . indexOf ( pattern , loc ) ; if ( best_loc != - 1 ) { score_threshold = Math . <mask> ( match_bitapScore ( 0 , best_loc , loc , pattern ) , score_threshold ) ; // What about in the other direction? (speedup) best_loc = text . lastIndexOf ( pattern , loc + pattern . length ( ) ) ; if ( best_loc != - 1 ) { score_threshold = Math . min ( match_bitapScore ( 0 , best_loc , loc , pattern ) , score_threshold ) ; } } // Initialise the bit arrays. int matchmask = 1 << ( pattern . length ( ) - 1 ) ; best_loc = - 1 ; int bin_min , bin_mid ; int bin_max = pattern . length ( ) + text . length ( ) ; // Empty initialization added to appease Java compiler. int [ ] last_rd = new int [ 0 ] ; for ( int d = 0 ; d < pattern . length ( ) ; d ++ ) { // Scan for the best match; each iteration allows for one more error. // Run a binary search to determine how far from 'loc' we can stray at // this error level. bin_min = 0 ; bin_mid = bin_max ; while ( bin_min < bin_mid ) { if ( match_bitapScore ( d , loc + bin_mid , loc , pattern ) <= score_threshold ) { bin_min = bin_mid ; } else { bin_max = bin_mid ; } bin_mid = ( bin_max - bin_min ) / 2 + bin_min ; } // Use the result from this iteration as the maximum for the next. bin_max = bin_mid ; int start = Math . max ( 1 , loc - bin_mid + 1 ) ; int finish = Math . min ( loc + bin_mid , text . length ( ) ) + pattern . length ( ) ; int [ ] rd = new int [ finish + 2 ] ; rd [ finish + 1 ] = ( 1 << d ) - 1 ; for ( int j = finish ; j >= start ; j -- ) { int charMatch ; if ( text . length ( ) <= j - 1 || ! s . containsKey ( text . charAt ( j - 1 ) ) ) { // Out of range. charMatch = 0 ; } else { charMatch = s . get ( text . charAt ( j - 1 ) ) ; } if ( d == 0 ) { // First pass: exact match. rd [ j ] = ( ( rd [ j + 1 ] << 1 ) | 1 ) & charMatch ; } else { // Subsequent passes: fuzzy match. rd [ j ] = ( ( ( rd [ j + 1 ] << 1 ) | 1 ) & charMatch ) | ( ( ( last_rd [ j + 1 ] | last_rd [ j ] ) << 1 ) | 1 ) | last_rd [ j + 1 ] ; } if ( ( rd [ j ] & matchmask ) != 0 ) { double score = match_bitapScore ( d , j - 1 , loc , pattern ) ; // This match will almost certainly be better than any existing // match.  But check anyway. if ( score <= score_threshold ) { // Told you so. score_threshold = score ; best_loc = j - 1 ; if ( best_loc > loc ) { // When passing loc, don't exceed our current distance from loc. start = Math . max ( 1 , 2 * loc - best_loc ) ; } else { // Already passed loc, downhill from here on in. break ; } } } } if ( match_bitapScore ( d + 1 , loc , loc , pattern ) > score_threshold ) { // No hope for a (better) match at greater error levels. break ; } last_rd = rd ; } return best_loc ; }