java文本对比工具源码5
/**
* 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.
*/
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.min(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;
}
/**
* Compute and return the score for a match with e errors and x location.
* @param e Number of errors in match.
* @param x Location of match.
* @param loc Expected location of match.
* @param pattern Pattern being sought.
* @return Overall score for match (0.0 = good, 1.0 = bad).
*/
private double match_bitapScore(int e, int x, int loc, String pattern) {
float accuracy = (float) e / pattern.length();
int proximity = Math.abs(loc - x);
if (Match_Distance == 0) {
// Dodge divide by zero error.
return proximity == 0 ? accuracy : 1.0;
}
return accuracy + (proximity / (float) Match_Distance);
}
/**
* Initialise the alphabet for the Bitap algorithm.
* @param pattern The text to encode.
* @return Hash of character locations.
*/
protected Map<Character, Integer> match_alphabet(String pattern) {
Map<Character, Integer> s = new HashMap<Character, Integer>();
char[] char_pattern = pattern.toCharArray();
for (char c : char_pattern) {
s.put(c, 0);
}
int i = 0;
for (char c : char_pattern) {
s.put(c, s.get(c) | (1 << (pattern.length() - i - 1)));
i++;
}
return s;
}
// PATCH FUNCTIONS
/**
* Increase the context until it is unique,
* but don't let the pattern expand beyond Match_MaxBits.
* @param patch The patch to grow.
* @param text Source text.
*/
protected void patch_addContext(Patch patch, String text) {
if (text.length() == 0) {
return;
}
String pattern = text.substring(patch.start2, patch.start2 + patch.length1);
int padding = 0;
// Look for the first and last matches of pattern in text. If two different
// matches are found, increase the pattern length.
while (text.indexOf(pattern) != text.lastIndexOf(pattern)
&& pattern.length() < Match_MaxBits - Patch_Margin - Patch_Margin) {
padding += Patch_Margin;
pattern = text.substring(Math.max(0, patch.start2 - padding),
Math.min(text.length(), patch.start2 + patch.length1 + padding));
}
// Add one chunk for good luck.
padding += Patch_Margin;
// Add the prefix.
String prefix = text.substring(Math.max(0, patch.start2 - padding),
patch.start2);
if (prefix.length() != 0) {
patch.diffs.addFirst(new Diff(Operation.EQUAL, prefix));
}
// Add the suffix.
String suffix = text.substring(patch.start2 + patch.length1,
Math.min(text.length(), patch.start2 + patch.length1 + padding));
if (suffix.length() != 0) {
patch.diffs.addLast(new Diff(Operation.EQUAL, suffix));
}
// Roll back the start points.
patch.start1 -= prefix.length();
patch.start2 -= prefix.length();
// Extend the lengths.
patch.length1 += prefix.length() + suffix.length();
patch.length2 += prefix.length() + suffix.length();
}
