как найти два предложения, которые имеют наибольшее количество общих слов?

Question

Учитывая список предложений, найдите два предложения, которые имеют наибольшее количество общих слов. Общим словам не нужно находить в том же положении в предложениях (порядок не имеет значения).

Спасибо!

обновление:

ли существуют не-попарно алгоритм для этой проблемы? Потому что попарно очень просто.

моей идеей является использование инвертированного индекса для хранения, где это слово появляется. Эта потребность проходит каждое слово в каждом предложении. А затем создайте n * n 2D-массив, который используется для подсчета, сколько раз два предложения появляются в одном и том же ведрах в инвертированном индексе.

Answer 1

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

После того как вы этот алгоритм реализован, вам потребуется цикл, который будет выглядеть следующим образом:

for (i = 0; i < sentenceCount - 1; i++) { 
    for (j = i+1; j < sentenceCount; j++) { 
    } 
} 

Внутри цикла вы называете функцию, которая вычисляет количество слов общего, используя предложения по индексам i и j. Вы будете отслеживать наибольшее количество общих слов, встречающихся до этого момента, и два предложения, в которых оно было найдено. Если новое предложение имеет большее количество общих слов, вы сохраните этот счет и два предложения, которые дали этот счет. В конце вы получите два предложения, которые вы хотите.

Answer 2

Предположим, у вас есть массив предложений:

String[] sentences 

Создать некоторые переменные, которые содержат значения по умолчанию для отслеживания двух предложений с наиболее употребительных слов

sentence1Index = -1 
sentence2Index = -1 
maxCount = -1 

ли вложенный цикл на приговоры массив

for i : 0 -> sentences.length 
    for j : 0 -> sentences.length 

Убедитесь, что вы не проверяете одно и то же сообщение сть

if i != j 

Split Струны пустым пространством (которые обычно дают вам каждое слово, предполагая считать некоторые символы как слова)

String[] words1 = sentences[i].splitAt(" ") 
    String[] words2 = sentences[j].splitAt(" ") 

Создание временного значения счетчика для этого пробега

tempCount = 0 

Петля между двумя массивами слов (полученная из двух предложений, которые вы сравниваете)

Если слово одно и то же, то увеличивает количество Темпа

  if words[a] equal-to-ignore-case words[b] 
       tempCount++ 

После окончания сравнивающих слов, если tempCount больше текущего MAXCOUNT, обновить все значения, которые отслеживают вы ищете

if tempCount > maxCount 
     sentence1Index = i 
     sentence2Index = j 
     maxCount = tempCount 

Возврат вновь созданный массив, который два предложения

if sentence1Index != -1 and sentence2Index != -1 
    String[] retArray = sentences[sentence1Index], sentences[sentence2Index ] 
    return retArray 

return null 

Все псевдо-код:

String[] sentences 
sentence1Index = -1 
sentence2Index = -1 
maxCount = -1 

for i : 0 -> sentences.length 
    for j : 0 -> sentences.length 
     if i != j 
      String[] words1 = sentences[i].splitAt(" ") 
      String[] words2 = sentences[j].splitAt(" ") 
      tempCount = 0 
      for a : 0 -> words1 .length 
       for b : 0 -> words2.length 
        if words[a] equal-to-ignore-case words[b] 
         tempCount++ 
      if tempCount > maxCount 
       sentence1Index = i 
       sentence2Index = j 
       maxCount = tempCount 

if sentence1Index != -1 and sentence2Index != -1 
    String[] retArray = sentences[sentence1Index], sentences[sentence2Index ] 
    return retArray 

return null