parameters: (self, text, pattern, loc)
return_statement: return best_loc
docstring: Locate the best instance of 'pattern' in 'text' near 'loc' using the
      Bitap algorithm.
  
      Args:
        text: The text to search.
        pattern: The pattern to search for.
        loc: The location to search around.
  
      Returns:
        Best match index or -1.
docstring_summary: Locate the best instance of 'pattern' in 'text' near 'loc' using the
      Bitap algorithm.
docstring_tokens: Locate the best instance of pattern in text near loc using the Bitap algorithm .
function: def match_bitap(self, text, pattern, loc):
      """Locate the best instance of 'pattern' in 'text' near 'loc' using the
      Bitap algorithm.
  
      Args:
        text: The text to search.
        pattern: The pattern to search for.
        loc: The location to search around.
  
      Returns:
        Best match index or -1.
      """
      # Python doesn't have a maxint limit, so ignore this check.
      #if self.Match_MaxBits != 0 and len(pattern) > self.Match_MaxBits:
      #  raise ValueError("Pattern too long for this application.")
  
      # Initialise the alphabet.
      s = self.match_alphabet(pattern)
  
      def match_bitapScore(e, x):
        """Compute and return the score for a match with e errors and x location.
        Accesses loc and pattern through being a closure.
  
        Args:
          e: Number of errors in match.
          x: Location of match.
  
        Returns:
          Overall score for match (0.0 = good, 1.0 = bad).
        """
        accuracy = float(e) / len(pattern)
        proximity = abs(loc - x)
        if not self.Match_Distance:
          # Dodge divide by zero error.
          return proximity and 1.0 or accuracy
        return accuracy + (proximity / float(self.Match_Distance))
  
      # Highest score beyond which we give up.
      score_threshold = self.Match_Threshold
      # Is there a nearby exact match? (speedup)
      best_loc = text.find(pattern, loc)
      if best_loc != -1:
        score_threshold = min(match_bitapScore(0, best_loc), score_threshold)
        # What about in the other direction? (speedup)
        best_loc = text.rfind(pattern, loc + len(pattern))
        if best_loc != -1:
          score_threshold = min(match_bitapScore(0, best_loc), score_threshold)
  
      # Initialise the bit arrays.
      matchmask = 1 << (len(pattern) - 1)
      best_loc = -1
  
      bin_max = len(pattern) + len(text)
      # Empty initialization added to appease pychecker.
      last_rd = None
      for d in xrange(len(pattern)):
        # 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) <= 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
        start = max(1, loc - bin_mid + 1)
        finish = min(loc + bin_mid, len(text)) + len(pattern)
  
        rd = range(finish + 1)
        rd.append((1 << d) - 1)
        for j in xrange(finish, start - 1, -1):
          if len(text) <= j - 1:
            # Out of range.
            charMatch = 0
          else:
            charMatch = s.get(text[j - 1], 0)
          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:
            score = match_bitapScore(d, j - 1)
            # 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 = max(1, 2 * loc - best_loc)
              else:
                # Already passed loc, downhill from here on in.
                break
        # No hope for a (better) match at greater error levels.
        if match_bitapScore(d + 1, loc) > score_threshold:
          break
        last_rd = rd
      return best_loc
function_tokens: def match_bitap ( self , text , pattern , loc ) : # Python doesn't have a maxint limit, so ignore this check. #if self.Match_MaxBits != 0 and len(pattern) > self.Match_MaxBits: #  raise ValueError("Pattern too long for this application.") # Initialise the alphabet. s = self . match_alphabet ( pattern ) def match_bitapScore ( e , x ) : """Compute and return the score for a match with e errors and x location.
        Accesses loc and pattern through being a closure.
  
        Args:
          e: Number of errors in match.
          x: Location of match.
  
        Returns:
          Overall score for match (0.0 = good, 1.0 = bad).
        """ accuracy = float ( e ) / len ( pattern ) proximity = abs ( loc - x ) if not self . Match_Distance : # Dodge divide by zero error. return proximity and 1.0 or accuracy return accuracy + ( proximity / float ( self . Match_Distance ) ) # Highest score beyond which we give up. score_threshold = self . Match_Threshold # Is there a nearby exact match? (speedup) best_loc = text . find ( pattern , loc ) if best_loc != - 1 : score_threshold = min ( match_bitapScore ( 0 , best_loc ) , score_threshold ) # What about in the other direction? (speedup) best_loc = text . rfind ( pattern , loc + len ( pattern ) ) if best_loc != - 1 : score_threshold = min ( match_bitapScore ( 0 , best_loc ) , score_threshold ) # Initialise the bit arrays. matchmask = 1 << ( len ( pattern ) - 1 ) best_loc = - 1 bin_max = len ( pattern ) + len ( text ) # Empty initialization added to appease pychecker. last_rd = None for d in xrange ( len ( pattern ) ) : # 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 ) <= 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 start = max ( 1 , loc - bin_mid + 1 ) finish = min ( loc + bin_mid , len ( text ) ) + len ( pattern ) rd = range ( finish + 1 ) rd . append ( ( 1 << d ) - 1 ) for j in xrange ( finish , start - 1 , - 1 ) : if len ( text ) <= j - 1 : # Out of range. charMatch = 0 else : charMatch = s . get ( text [ j - 1 ] , 0 ) 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 : score = match_bitapScore ( d , j - 1 ) # 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 = max ( 1 , 2 * loc - best_loc ) else : # Already passed loc, downhill from here on in. break # No hope for a (better) match at greater error levels. if match_bitapScore ( d + 1 , loc ) > score_threshold : break last_rd = rd return best_loc