Locate the best instance of 'pattern' in 'text' near 'loc' using the Bitap algorithm. Returns -1 if no match found. @param text The text to search. @param pattern The pattern to search for. @param loc The location to search around. @return Best match index or -1.
(String text, String pattern, int loc)
| 1603 | * @return Best match index or -1. |
| 1604 | */ |
| 1605 | public int match_bitap(String text, String pattern, int loc) { |
| 1606 | assert (Match_MaxBits == 0 || pattern.length() <= Match_MaxBits) |
| 1607 | : "Pattern too long for this application."; |
| 1608 | |
| 1609 | // Initialise the alphabet. |
| 1610 | Map<Character, Integer> s = match_alphabet(pattern); |
| 1611 | |
| 1612 | // Highest score beyond which we give up. |
| 1613 | double score_threshold = Match_Threshold; |
| 1614 | // Is there a nearby exact match? (speedup) |
| 1615 | int best_loc = text.indexOf(pattern, loc); |
| 1616 | if (best_loc != -1) { |
| 1617 | score_threshold = Math.min(match_bitapScore(0, best_loc, loc, pattern), |
| 1618 | score_threshold); |
| 1619 | // What about in the other direction? (speedup) |
| 1620 | best_loc = text.lastIndexOf(pattern, loc + pattern.length()); |
| 1621 | if (best_loc != -1) { |
| 1622 | score_threshold = Math.min(match_bitapScore(0, best_loc, loc, pattern), |
| 1623 | score_threshold); |
| 1624 | } |
| 1625 | } |
| 1626 | |
| 1627 | // Initialise the bit arrays. |
| 1628 | int matchmask = 1 << (pattern.length() - 1); |
| 1629 | best_loc = -1; |
| 1630 | |
| 1631 | int bin_min, bin_mid; |
| 1632 | int bin_max = pattern.length() + text.length(); |
| 1633 | // Empty initialization added to appease Java compiler. |
| 1634 | int[] last_rd = new int[0]; |
| 1635 | for (int d = 0; d < pattern.length(); d++) { |
| 1636 | // Scan for the best match; each iteration allows for one more error. |
| 1637 | // Run a binary search to determine how far from 'loc' we can stray at |
| 1638 | // this error level. |
| 1639 | bin_min = 0; |
| 1640 | bin_mid = bin_max; |
| 1641 | while (bin_min < bin_mid) { |
| 1642 | if (match_bitapScore(d, loc + bin_mid, loc, pattern) |
| 1643 | <= score_threshold) { |
| 1644 | bin_min = bin_mid; |
| 1645 | } else { |
| 1646 | bin_max = bin_mid; |
| 1647 | } |
| 1648 | bin_mid = (bin_max - bin_min) / 2 + bin_min; |
| 1649 | } |
| 1650 | // Use the result from this iteration as the maximum for the next. |
| 1651 | bin_max = bin_mid; |
| 1652 | int start = Math.max(1, loc - bin_mid + 1); |
| 1653 | int finish = Math.min(loc + bin_mid, text.length()) + pattern.length(); |
| 1654 | |
| 1655 | int[] rd = new int[finish + 2]; |
| 1656 | rd[finish + 1] = (1 << d) - 1; |
| 1657 | for (int j = finish; j >= start; j--) { |
| 1658 | int charMatch; |
| 1659 | if (text.length() <= j - 1 || !s.containsKey(text.charAt(j - 1))) { |
| 1660 | // Out of range. |
| 1661 | charMatch = 0; |
| 1662 | } else { |
no test coverage detected