Tag: levenshtein distance

最短的Levenshtein距离？我需要它吗？: 我想在String[]查找String以获得查询的最佳匹配。我听说过Levenshtein Distance。但我无法确定是否需要它。假设，我有一个String query = “Examples”和 String[] arrayStr = new String[] {“The Examples String”, “The Example String”, “Example”, “Examples String”, “Example String”, “Examplestring”}; 现在，我希望将String[]的Example作为最佳匹配。那么，我需要Levenshtein距离来做吗？或者，如果有人可以指出我快速实现Levenshtein Distance for Java，那就太棒了。我想检查它是否适用于我拥有的所有字符串。（基本上我有大约10k个字符串来匹配10k数组。）

LevensteinDistance – Commons Lang 3.0 API: 使用Commons Lang api，我可以通过LevensteinDistance计算两个字符串之间的相似性。结果是将一个字符串更改为另一个字符串所需的更改次数。我希望结果在0到1的范围内，这样可以更容易地识别字符串之间的相似性。结果将更接近0相似性。可能吗？在我正在使用的示例下面： public class TesteLevenstein { public static void main(String[] args) { int distance1 = StringUtils.getLevenshteinDistance(“Boat”, “Coat”); int distance2 = StringUtils.getLevenshteinDistance(“Remember”, “Alamo”); int distance3 = StringUtils.getLevenshteinDistance(“Steve”, “Stereo”); System.out.println(“distance(Boat, Coat): ” + distance1); System.out.println(“distance(Remember, Alamo): ” + distance2); System.out.println(“distance(Steve, Stereo): ” + distance3); } } 谢谢！

修改Levenshtein距离算法不计算所有距离: 我正在进行模糊搜索实现，作为实现的一部分，我们使用的是Apache的StringUtils.getLevenshteinDistance。目前，我们正在寻找模糊搜索的特定最大平均响应时间。经过各种改进和一些剖析后，花费最多时间的地方是计算Levenshtein距离。它占搜索字符串总时间的大约80-90％三个字母或更多。现在，我知道在这里可以做些什么有一些限制，但我已经读过以前的SO问题和LD的维基百科链接，如果有人愿意将阈值限制在设定的最大距离，这可能有助于遏制花在算法上的时间，但我不确定如何准确地做到这一点。如果我们仅对距离感兴趣，如果它小于阈值k，那么在矩阵中计算宽度为2k + 1的对角条纹就足够了。这样，算法可以在O（kl）时间内运行，其中l是最短字符串的长度。[3] 您将在下面看到StringUtils的原始LH代码。之后是我的修改。我试图基本上计算设定长度与i，j对角线的距离（因此，在我的例子中，i，j对角线上方和下方的两个对角线）。但是，这是不正确的，因为我已经这样做了。例如，在最高的对角线上，它总是会选择正上方的单元格值，这将是0.如果有人可以告诉我如何使这个function如我所描述的那样，或者如何使它成为如此的一般建议，这将不胜感激。 public static int getLevenshteinDistance(String s, String t) { if (s == null || t == null) { throw new IllegalArgumentException(“Strings must not be null”); } int n = s.length(); // length of s int m = t.length(); // length of […]

Java模糊字符串与名称匹配: 我有一个独立的CSV数据加载过程，我用Java编码，必须使用一些模糊的字符串匹配。这绝对不是理想的，但我没有太多选择。我使用名字和姓氏进行匹配，并在运行开始时缓存所有可能性。找到匹配后，我需要该人在运行期间对多个位置。我使用guava的Objects.hashCode()来创建firstname和lastname之外的哈希。缓存机制如下所示： Map personCache = Maps.newHashMap(); for(PersonDO p: dao.getPeople()) { personCache.put(Objects.hashCode(p.getFirstName(),p.getLastName()), p); } 大多数时候我会在firstname + lastname上点击，但是当它错过时我会使用Apache的StringUtils.getLevenshteinDistance()来尝试匹配它。这就是匹配逻辑流程的方式： person = personCache.get(Objects.hashCode(firstNameFromCSV,lastNameFromCSV)); if(person == null) {//fallback to fuzzy matching person = findClosetMatch(firstNameFromCSV+lastNameFromCSV); } 这是findClosetMatch()方法： private PersonDO findClosetMatch(String name) { int min = 15;//initial value int testVal=0; PersonDO matchedPerson = null; for(PersonDO person: personCache.values()) […]

Levenshtein到Damerau-Levenshtein: 我坐在这里为Java主程序编程一些算法（到目前为止第一个算法）。我编写了levenshtein算法就好了，这要归功于wiki对于newbeginners的假代码非常好以及一个很好的教程：D 然后我决定升级到Damerau并添加了额外的行，但后来我读到它不是DL算法而是OptimalStringAlignmentDistance。我尝试阅读actionscript代码，以了解我需要添加什么以使其成为DL但却感到困惑。我去过不同的地方，代码看起来与Java相似，但他们都使用了错误的伪代码。花了半天后，我放弃了，决定在这里问。是否有人可以帮助我将此代码升级到Java中的Damerau-Levenshtein？ public class LevensteinDistance { private static int Minimum(int a, int b, int c) { return Math.min(Math.min(a, b), c); } private static int Minimum (int a, int b) { return Math.min(a, b); } public static int computeLevensteinDistance(String s, String t){ int d[][]; int n; // length of s int […]