比較字符串數組的相似性

Question

我可以使用數百個JSON字符串。其中每個包含15-20個字的數組，按照一定的重量排序。如果值得注意的話，這個重量是這些詞在一些文本塊中找到的次數。找出像這樣構造的單詞陣列之間的相似性的最佳方式是什麼？

我頭腦中的第一個想法是創建所有單詞的數值散列，並基本比較這些值以確定相似性。我並不是非常成功，因爲非常相似的字符串所產生的散列值並不是非常接近。經過一些關於字符串比較算法的研究，我來到Stackoverflow希望得到更多的指導。在此先感謝您，如果您需要更詳細的問題，請告訴我。

編輯1：澄清我想做的事情：我想根據這些詞中的每一個詞來確定兩個數組的相似程度。我還想考慮每個單詞在每個數組中的重量。例如：

var array1 = [{"word":"hill","count":5},{"word":"head","count":5}]; 
var array2 = [{"word":"valley","count":7},{"word":"head","count":5}]; 
var array3 = [{"word":"head", "count": 6}, {"word": "valley", "count": 5}]; 
var array4 = [{"word": "valley", "count": 7}, {"word":"head", "count": 5}]; 

在該示例中，陣列4和陣列2比陣列2和陣列3更相似的，因爲，儘管具有相同的話，其重量爲兩者相同的在陣列4和2.我希望這可以更容易理解。提前致謝。

Answer 1

我認爲，你想要的是「cosine similarity」，你可能也想看看vector space models。如果您在Java中編寫代碼，則可以使用開源代碼S-space包。

（於10月31日添加）向量的每個元素都是一個特定字符串的計數。你只需要將你的字符串數組轉換成這樣的向量。在你的例子中，你有三個詞 - 「山」，「頭」，「谷」。如果您的矢量按照該順序排列，則與陣列對應的矢量將爲

// array: #hill, #head, #valley 
array1: {5,  5,  0} 
array2: {0,  5,  7} 
array3: {0,  6,  5} 
array4: {0,  5,  7} 

Answer 2

鑑於每個陣列必須與其他陣列進行比較，您正在沿着Σ（n-1）乘以每個陣列中「單詞」的平均數量的線尋找大量處理。您需要存儲每個比較的分數，然後對其進行一些瞭解。

例如

var array1 = [{"word":"hill","count":5},{"word":"head","count":5}]; 
var array2 = [{"word":"valley","count":7},{"word":"head","count":5}]; 
var array3 = [{"word":"head", "count": 6}, {"word": "valley", "count": 5}]; 
var array4 = [{"word": "valley", "count": 7}, {"word":"head", "count": 5}]; 

// Comparison score is summed product of matching word counts 
function compareThings() { 

    var a, b, i = arguments.length, 
     j, m, mLen, n, nLen; 
    var word, score, result = []; 

    if (i < 2) return; 

    // For each array 
    while (i--) { 
    a = arguments[i]; 
    j = i; 

    // Compare with every other array 
    while (j--) { 
     b = arguments[j]; 
     score = 0; 

     // For each word in array 
     for (m=0, mLen = b.length; m<mLen; m++) { 
     word = b[m].word 

     // Compare with each word in other array 
     for (n=0, nLen=a.length; n<nLen; n++) { 

      // Add to score 
      if (a[n].word == word) { 
      score += a[n].count * b[m].count; 
      } 
     } 
     } 

     // Put score in result 
     result.push(i + '-' + j + ':' + score); 
    } 
    } 
    return result; 
} 

var results = compareThings(array1, array2, array3, array4); 

alert('Raw results:\n' + results.join('\n')); 
/* 
Raw results: 
3-2:65 
3-1:74 
3-0:25 
2-1:65 
2-0:30 
1-0:25 
*/ 

results.sort(function(a, b) { 
    a = a.split(':')[1]; 
    b = b.split(':')[1]; 
    return b - a; 
}); 

alert('Sorted results:\n' + results.join('\n')); 
/* 
Sorted results: 
3-1:74 
3-2:65 
2-1:65 
2-0:30 
3-0:25 
1-0:25 
*/ 

所以3-1（array4和array2）得分最高。幸運的是，比較只需要一種方法，您不必將a與b和b進行比較。

Answer 3

這是一個嘗試。該算法是不是很聰明（差別> 20是一樣的不具有同樣的話），但可能是一個有益的開端：

var wordArrays = [ 
    [{"word":"hill","count":5},{"word":"head","count":5}] 
    , [{"word":"valley","count":7},{"word":"head","count":5}] 
    , [{"word":"head", "count": 6}, {"word": "valley", "count": 5}] 
    , [{"word": "valley", "count": 7}, {"word":"head", "count": 5}] 
] 

function getSimilarTo(index){ 
    var src = wordArrays[index] 
     , values 

    if (!src) return null; 

    // compare with other arrays 
    weighted = wordArrays.map(function(arr, i){ 
     var diff = 0 
     src.forEach(function(item){ 
      arr.forEach(function(other){ 
       if (other.word === item.word){ 
        // add the absolute distance in count 
        diff += Math.abs(item.count - other.count) 
       } else { 
        // mismatches 
        diff += 20 
       } 
      }) 
     }) 
     return { 
      arr : JSON.stringify(arr) 
      , index : i 
      , diff : diff 
     } 
    }) 

    return weighted.sort(function(a,b){ 
     if (a.diff > b.diff) return 1 
     if (a.diff < b.diff) return -1 
     return 0 
    }) 
} 

/* 
getSimilarTo(3) 
[ { arr: '[{"word":"valley","count":7},{"word":"head","count":5}]', 
    index: 1, 
    diff: 100 }, 
    { arr: '[{"word":"valley","count":7},{"word":"head","count":5}]', 
    index: 3, 
    diff: 100 }, 
    { arr: '[{"word":"head","count":6},{"word":"valley","count":5}]', 
    index: 2, 
    diff: 103 }, 
    { arr: '[{"word":"hill","count":5},{"word":"head","count":5}]', 
    index: 0, 
    diff: 150 } ] 
*/ 

Answer 4

在嘗試比較之前按字排序數組。一旦完成，比較兩個數組就需要每個數組精確的1次通過。

排序陣列之後，這裏是一個比較算法（僞JAVA）：

int compare(array1, array2) 
{ 
    returnValue = 0; 
    array1Index = 0 
    array2Index = 0; 

    while (array1Index < array1.length) 
    { 
    if (array2Index < array2.length) 
    { 
     if (array1[array1Index].word == array2[array2Index].word) // words match. 
     { 
     returnValue += abs(array1[array1Index].count - array2[array2Index].count); 
     ++array1Index; 
     ++array2Index; 
     } 
     else // account for the unmatched array2 word. 
     { 
     // 100 is just a number to give xtra weight to unmatched numbers. 
     returnValue += 100 + array2[array2Index].count; 
     ++array2Index; 
     } 
    } 
    else // array2 empty and array1 is not empty. 
    { 
     // 100 is just a number to give xtra weight to unmatched numbers. 
     returnValue += 100 + array1[array1Index].count; 
    } 
    } 

    // account for any extra unmatched array 2 values. 
    while (array2Index < array2.length) 
    { 
     // 100 is just a number to give xtra weight to unmatched numbers. 
     returnValue += 100 + array2[array2Index].count; 
    } 

    return returnValue; 
}