优化Jaro-Winkler算法

我从这个网站获取了Jaro-Winkler算法的代码。我需要运行150,000次以获得差异之间的距离。这需要很长时间，因为我在Android移动设备上运行。

它可以更优化吗？

public class Jaro { /** * gets the similarity of the two strings using Jaro distance. * * @param string1 the first input string * @param string2 the second input string * @return a value between 0-1 of the similarity */ public float getSimilarity(final String string1, final String string2) { //get half the length of the string rounded up - (this is the distance used for acceptable transpositions) final int halflen = ((Math.min(string1.length(), string2.length())) / 2) + ((Math.min(string1.length(), string2.length())) % 2); //get common characters final StringBuffer common1 = getCommonCharacters(string1, string2, halflen); final StringBuffer common2 = getCommonCharacters(string2, string1, halflen); //check for zero in common if (common1.length() == 0 || common2.length() == 0) { return 0.0f; } //check for same length common strings returning 0.0f is not the same if (common1.length() != common2.length()) { return 0.0f; } //get the number of transpositions int transpositions = 0; int n=common1.length(); for (int i = 0; i < n; i++) { if (common1.charAt(i) != common2.charAt(i)) transpositions++; } transpositions /= 2.0f; //calculate jaro metric return (common1.length() / ((float) string1.length()) + common2.length() / ((float) string2.length()) + (common1.length() - transpositions) / ((float) common1.length())) / 3.0f; } /** * returns a string buffer of characters from string1 within string2 if they are of a given * distance seperation from the position in string1. * * @param string1 * @param string2 * @param distanceSep * @return a string buffer of characters from string1 within string2 if they are of a given * distance seperation from the position in string1 */ private static StringBuffer getCommonCharacters(final String string1, final String string2, final int distanceSep) { //create a return buffer of characters final StringBuffer returnCommons = new StringBuffer(); //create a copy of string2 for processing final StringBuffer copy = new StringBuffer(string2); //iterate over string1 int n=string1.length(); int m=string2.length(); for (int i = 0; i < n; i++) { final char ch = string1.charAt(i); //set boolean for quick loop exit if found boolean foundIt = false; //compare char with range of characters to either side for (int j = Math.max(0, i - distanceSep); !foundIt && j < Math.min(i + distanceSep, m - 1); j++) { //check if found if (copy.charAt(j) == ch) { foundIt = true; //append character found returnCommons.append(ch); //alter copied string2 for processing copy.setCharAt(j, (char)0); } } } return returnCommons; } }

我提到在整个过程中我只创建了脚本的实例，所以只有一次

 jaro= new Jaro();

如果你要测试并需要示例，那么不要破坏脚本，你可以在另一个python优化的线程中找到它

是的，但你不会喜欢它。将所有这些new编辑StringBuffers替换为在构造函数中分配的char数组，而不再使用整数索引来跟踪其中的内容。

这个待定的Commons-Lang补丁会给你一些味道。

我知道这个问题可能已经解决了一段时间，但我想对算法本身发表评论。将字符串与自身进行比较时，答案结果为1 / | string | 关闭。当比较稍微不同的值时，值也会变低。

解决方法是在getCommonCharacters方法的内部for语句中将’m-1’调整为’m’。然后代码就像一个魅力:)

有关示例，请参见http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance 。

尽量避免getCommonCharacters循环中的两个嵌套循环。
建议如何：将所有字符存储在某个地图中的较小字符串中（java有一些），其中键是字符，值是位置，这样你仍然可以计算距离，是共同的。我不太了解算法，但我认为这是可行的。
除了那个和bmargulies的回答之外，我真的没有看到除了比特之类的东西之外的进一步优化。如果这真的很关键，考虑用C重写这个部分？

我不太了解Android以及它如何与数据库一起使用。 WP7有（将有:)）SQL CE。下一步通常是处理您的数据。添加字符串长度并限制您的比较。在两列上添加索引并按长度排序，然后按值排序。长度索引也应该排序。我让它在一台旧服务器上运行，有15万个医学术语，在0.5秒内给我建议和拼写检查，用户几乎没有注意到它，特别是如果在一个单独的线程上运行。

我打算在很长一段时间内写博客（比如2年:)），因为有需要。但我终于设法写了几个关于它的文字，并提供了一些提示。请在这里查看：

ISolvable.blogspot.com

虽然它适用于Microsoft平台，但仍然是一般原则。

是的，这可以更快地完成。首先，您根本不需要StringBuffers。另一方面，您不需要单独的循环来计算换位。

你可以在这里找到我的实现，它应该快得多。它在Apache 2.0许可下。

而是使用GetCommonCharacters方法返回公共字符，使用几个数组来保存匹配，类似于此处的C版本https://github.com/miguelvps/c/blob/master/jarowinkler.c

 /*Calculate matching characters*/ for (i = 0; i < al; i++) { for (j = max(i - range, 0), l = min(i + range + 1, sl); j < l; j++) { if (a[i] == s[j] && !sflags[j]) { sflags[j] = 1; aflags[i] = 1; m++; break; } } }

另一个优化是预先计算每个字符串的位掩码。使用它，检查第一个字符串上的当前字符是否存在于第二个字符串上。这可以使用有效的按位运算来完成。

这将跳过计算缺失字符的最大值/最小值和循环。