javascript - 创建一个算法来定义 Javascript 中字符串的匹配概率

Question

我正在使用谷歌地图并尝试找到指定的地方。但是，有时我会得到指定地点的更多结果(因为我试图在整个城市中搜索该地点及其名称)。因此，我将输出限制为前三个匹配的建议，并排除了除此之外的所有结果。但问题是，前 3 个匹配的建议仍然有可能位于同一位置，我只想显示其中的一个建议以使建议更加精确。例如:

• 我搜索过“必胜客”
• 我得到的前三个结果如下:
  1. 必胜客，MI 路，斋浦尔 --- 第一个建议
  2. 必胜客，MI 路，Ajmeri 门，斋浦尔 --- 第二条建议
  3. 必胜客，Malviya Nagar，斋浦尔 --- 第三条建议

第一个和第二个建议指示相同的地点。

现在我想应用预测方法(使用概率)来发现第一个和第二个建议是相同的地方，而第三个建议是不同的地方。

我的方法是什么:-

var p = [], ap = []; //p -- places & ap -- array of splitted strings
    p[0] = "Pizza Hut, MI Road, Jaipur";
    p[1] = "Pizza Hut, MI Road, Ajmeri Gate, Jaipur";
    p[2] = "Pizza Hut, Malviya Nagar, Jaipur";

    //split all places
    ap[0] = p[0].split(",");
    ap[1] = p[1].split(",");
    ap[2] = p[2].split(",");

    /*
     --- Theoretically ---
     ### Splitting strings into symbols ###
     string_symbols_1 = a1, a2, a3;  --- a1 = "Pizza Hut", a2 = "MI Road", a3="Jaipur"; 
     string_symbols_2 = b1, b2, b3, b4; --- b1 = "Pizza Hut", b2 = "MI Road", b3 = "Ajmeri 
     Gate", b4 = "Jaipur"
     string_symbols_3 = c1, c2, c3; --- c1 = "Pizza Hut", c2 = "Malviya Nagar", c3 = 
     "Jaipur"

     ### On Prediction Basis ###
     I am trying to evaluate that if 60% of the symbols match with 
     another string symbols then there is probability that both strings are 
     same. 
     From above case I am considering if I am able to find >40% unique 
     symbols in both strings (that is being compared) then there is 
     probability that both strings are unique. (It will reduce the 60% 
     comparison to 40% comparison in best cases).
     Once found the unique strings return their indexes;
    */

    //pseudo implementation
    function findUniquePlaces(ap){
       //stuck here..
       //now match the splitted string arrays to find the unique places 
       //what should be the logic
       return index(0 and 2)
    }

我知道如何实现这个。但我想知道实现这一目标的最佳方法是什么。我想确保这个任务不能是计算密集型任务。我听说过 map 缩减技术。我应该使用 map 缩减技术还是有一些其他技术可以在计算上更便宜。

Answer 1

这背后的一般理论是字符串度量 https://en.wikipedia.org/wiki/String_metric计算字符串之间的距离，然后使用现成的解决方案之一:

https://www.npmjs.com/package/fast-levenshtein

https://www.npmjs.com/package/js-levenshtein

https://www.npmjs.com/package/string-similarity

或者在 google npm string distance 中查找您可以找到的任何其他内容

这些速度非常快，因此您的问题可能更多是大小而不是速度。

或者您可以使用模糊搜索 https://glench.github.io/fuzzyset.js/

此外，您获得的这个列表很可能已经使用了下面的这些算法，所以只需先使用？