比较字符串数组的相似性

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; 
}