最好的方法來比較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距離是單字符的最小數目編輯改變一個字到其他需要的（插入，缺失或取代）。

該算法將允許您將字符串直接，也許匹配，如果你編輯距離閾值是不夠嚴謹（雖然這可能提供假陽性）或通過確保比較單獨的標記時，你甚至可以佔到拼錯的產品來說吧它們處於彼此特定的編輯距離內。