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 = [0] * (finish + 2)
      rd[finish + 1] = (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
dataset/ETHPy150Open JT5D/Alfred-Popclip-Sublime/Sublime Text 2/JsFormat/libs/diff_match_patch/python2/diff_match_patch.py/diff_match_patch.match_bitap/original