Сравнение массивов строк по сходству

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

Я думаю, что вам нужно " косинусное сходство ", и вы также можете посмотреть на модели векторного пространства . Если вы пишете код на Java, вы можете использовать пакет S-space с открытым исходным кодом.

(добавлено 31 октября) Каждый элемент вектора является счетчиком одной конкретной строки. Вам просто нужно преобразовать ваши массивы строк в такие векторы. В вашем примере у вас есть три слова - «холм», «голова», «долина». Если ваш вектор находится в таком порядке, векторы, соответствующие массивам, будут

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

Answer 2

Сортировка массивов по словам перед попыткой сравнения.После этого для сравнения двух массивов потребуется ровно 1 проход через каждый массив.

После сортировки массивов приведен алгоритм сравнения (psuedo-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;
}

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

Учитывая, что каждый массив должен сравниваться с любым другим массивом, вы смотрите на серьезную обработку по строкам, в ∑ (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 (массив4 и массив2) имеют самый высокий результат.К счастью, сравнение должно быть только одним способом, вам не нужно сравнивать a с b и b с a.