如何在2个不同的长ArrayLists之间找到2个字符串的最佳匹配

Question

可以说,我已经说过两个清单:

A = { "ABC" , "DEF" , "JKL"};

在其他一些项目中还有第二个清单:

A = { "ABC.com" , "DEF" , "JKL" };

现在ABC和ABC.com是相同的,因为我在手动看到之后就知道了.但是列表包含10000或100万个条目.我需要在另一个列表中找到String ABC的最佳匹配,因为没有固定的模式,它必须有.com,它可能是.inc或类似的东西,并且它确定,没有其他条目将其中有ABC,因为实际上它是设备的型号名称.例如,它将类似于"Cisco"和"Cisco.Inc".

为2个字符串找到最佳匹配的最佳策略或正则表达式是什么？

Answer 1

您需要定义一个函数来了解两个字符串之间的"距离".

基本上你需要一个在输入中带两个字符串并返回表示距离的值的函数.比较不同的距离,您可以找到最相似的字符串.

距离函数的一个例子是Levenshtein函数.

在这里,您可以找到实现Levenshtein函数的不同语言的函数.以下代码是从该站点获取的java实现:

public class LevenshteinDistance {                                               
    private static int minimum(int a, int b, int c) {                            
        return Math.min(Math.min(a, b), c);                                      
    }                                                                            

    public static int computeLevenshteinDistance(CharSequence lhs, CharSequence rhs) {      
        int[][] distance = new int[lhs.length() + 1][rhs.length() + 1];        

        for (int i = 0; i <= lhs.length(); i++)                                 
            distance[i][0] = i;                                                  
        for (int j = 1; j <= rhs.length(); j++)                                 
            distance[0][j] = j;                                                  

        for (int i = 1; i <= lhs.length(); i++)                                 
            for (int j = 1; j <= rhs.length(); j++)                             
                distance[i][j] = minimum(                                        
                        distance[i - 1][j] + 1,                                  
                        distance[i][j - 1] + 1,                                  
                        distance[i - 1][j - 1] + ((lhs.charAt(i - 1) == rhs.charAt(j - 1)) ? 0 : 1));

        return distance[lhs.length()][rhs.length()];                           
    }                                                                            
}

您可以按如下方式使用它:

public String mostSimilar(String toBeCompared, String[] strings) {
    int minDistance = Integer.MAX_VALUE;
    String similar = null;
    for (String str : strings) {
        int d = LevenshteinDistance.computeLevenshteinDistance(str, toBeCompared);
        if (d < minDistance) {
            minDistance = d;
            similar = str;
        }
    }
    return similar;
}

这是一个非常完整的字符串度量函数列表.