最好的方法来比较2个相似的字符串？

Question

原题：

我有很多的产品具有不同的名字，我的 名字两个版本我需要进行比较（基本上查不到，如果这两个字符串 是相同的产品）。我不想要任何错误的标志，有没有人有我如何实现这一目标的建议？

这里是一个产品例如：

Canon 50mm f/1.2L VS Canon EF 50mm f/1.2L USM Lens

有其他变化，但是这将是典型的差。 是否有任何简单的功能可以实现以获得某个 答案？只有我能想到的可能是将字符串和 进行比较，并说如果x匹配a，b或c。

---

我原来的问题是有点含糊。最终目标是能够比较两个字符串并查看它们的相似程度 - 例如， 0％，50％或100％相似。在这种情况下，我使用来自不同来源的镜头产品，他们使用类似的名称 - 但我没有产品sku/id进行适当的比较。

string score plugin已解决我的问题，并提供similar这些产品的价值。

Answer 1

在生物信息学字，我相信在其他领域，这种模式匹配的/搜索算法称为fuzzy search。

有一个叫string_score它一个模块的NodeJS。从本质上说，你用2个字符串提供API，它会返回你的分数。

实施例：

var test = require('string_score'); 

var match_percent = "Canon EF 50mm f/1.2L USM Lens".score("Canon 50mm f/1.2L"); 
console.log("Match score= " + match_percent); 

输出：

匹配得分= 0.7938133874239354

使用得分作为用于比较的基线。你可以说，如果它有一个得分装备或以上80那么匹配。

更多例子：

var score = 0; 
 

 
score = "hello world".score("he");   
 
console.log("Match score => " + score); 
 

 
score = "hello world".score("hel"); 
 
console.log("Match score => " + score); 
 

 
score = "hello world".score("hell"); 
 
console.log("Match score => " + score); 
 

 
score = "hello world".score("hello"); 
 
console.log("Match score => " + score);

<script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/string_score/0.1.10/string_score.min.js"></script>

参考文献：

String_score：https://github.com/joshaven/string_score

Answer 2

你必须思考，如果两个字符串是你自己的产品，只要阅读它们，你会如何认识。

仅基于您提供的示例，似乎告诉两个字符串表示产品的方式是相同的，即如果较长字符串中包含较短字符串的每个单词（由空格分隔的令牌）。

您可能还想忽略大小写。

像这样的东西应该的基本用法工作：

const tokens = s => s.toLowerCase().split(/\s+/g); 
 

 
const sameProducts = (s1, s2) => { 
 

 
    const s1Tokens = tokens(s1); 
 
    const s2Tokens = tokens(s2); 
 

 
    const [shorterTokens, longerTokens] = s1Tokens.length > s2Tokens.length 
 
    ? [s2Tokens, s1Tokens] 
 
    : [s1Tokens, s2Tokens]; 
 

 
    return shorterTokens.every(st => longerTokens.includes(st)); 
 
} 
 

 
console.log(
 
    sameProducts(
 
    'Canon 50mm f/1.2L', 
 
    'Canon EF 50mm f/1.2L USM Lens' 
 
) 
 
)

此代码将有二次的时间复杂度，因为最昂贵的操作是指，相对于短串在每一个令牌，你必须迭代长字符串中的每个标记。

一个简单的优化就是从较长的字符串中构建一个Set<token>。这将使操作线性化，因为搜索一个集合是O(1)。

const tokens = s => s.toLowerCase().split(/\s+/g); 
 

 
const sameProducts = (s1, s2) => { 
 

 
    const s1Tokens = tokens(s1); 
 
    const s2Tokens = tokens(s2); 
 

 
    const [shorterTokens, longerTokens] = s1Tokens.length > s2Tokens.length 
 
    ? [s2Tokens, s1Tokens] 
 
    : [s1Tokens, s2Tokens]; 
 

 
    const longerTokensSet = longerTokens.reduce((s, t) => { 
 
    s.add(t); 
 
    return s; 
 
    }, new Set()); 
 

 
    return shorterTokens.every(st => longerTokensSet.has(st)); 
 
} 
 

 
console.log(
 
    sameProducts(
 
    'Canon 50mm f/1.2L', 
 
    'Canon EF 50mm f/1.2L USM Lens' 
 
) 
 
)

现在你必须要考虑，做所有令牌必须匹配？也许只有与品牌和焦距对应的令牌才能匹配。

如果是这样的话，你可能还需要验证两个字符串在分析它们并立即返回false如果产品均被认为是无效。

这里有一个粗略的想法：

const productSet = new Set(['canon']) 
 
const focalLengthsSet = new Set(['50mm']); 
 

 
const isMeaningful = t => productSet.has(t) || focalLengthsSet.has(t); 
 

 
const meaningfulTokens = s => s.toLowerCase().split(/\s+/g).filter(isMeaningful); 
 

 
const validTokens = (tokens, s) => { 
 
    const valid = tokens.length === 2; // <-- could do better validation here 
 
    console.assert(valid, `Missing token(s) in ${s}`); 
 
    return valid; 
 
} 
 

 
const sameProducts = (s1, s2) => { 
 

 
    const s1Tokens = meaningfulTokens(s1); 
 
    if (!validTokens(s1Tokens, s1)) { return false; } 
 
    
 
    const s2Tokens = meaningfulTokens(s2); 
 
    if (!validTokens(s2Tokens, s2)) { return false; } 
 

 
    const [shorterTokens, longerTokens] = s1Tokens.length > s2Tokens.length 
 
    ? [s2Tokens, s1Tokens] 
 
    : [s1Tokens, s2Tokens]; 
 

 
    const longerTokensSet = longerTokens.reduce((s, t) => { 
 
    s.add(t); 
 
    return s; 
 
    }, new Set()); 
 

 
    return shorterTokens.every(st => longerTokensSet.has(st)); 
 
} 
 

 
console.log(
 
    sameProducts(
 
    'Canon 50mm f/1.3', 
 
    'Canon EF 50mm f/1.2' 
 
) 
 
) 
 

 
console.log(
 
    sameProducts(
 
    'Canon 50mm f/1.3', 
 
    'Canon EF f/1.2' // <-- missing focal length 
 
) 
 
)

现在你可以考虑不每个焦距对应于每一个产品或者是更具体产品？

做令牌包含明确依赖于先前匹配的令牌逻辑是什么？

以上所有的都只是基本方法和技巧，你可以使用，但实际的解决方案将在很大程度上取决于你的具体情况而定。

---

测量字符串相似性的常用算法叫做Levenstein distance。

两个单词之间的Levenshtein距离是单字符的最小数目编辑改变一个字到其他需要的（插入，缺失或取代）。

该算法将允许您将字符串直接，也许匹配，如果你编辑距离阈值是不够严谨（虽然这可能提供假阳性）或通过确保比较单独的标记时，你甚至可以占到拼错的产品来说吧它们处于彼此特定的编辑距离内。