Скажем, у меня есть 5 строк текста. Как найти 2, которые являются самыми «отличными» от остальных?

Question

Я использую PHP.

Скажем, у меня есть 5 строк:

"The quick brown fox" 
"The sly brown fox" 
"The sly brown chicken" 
"Totally different text here" 
"Not like the others" 

и я хочу, чтобы найти 2, которые наиболее «отличается» от остальных. Я хотел бы расширить его до 1000 текстовых строк и получить, скажем, 300 самых «разных».

Любые идеи, с чего начать?

EDIT

Как определить "разные" вверх для обсуждения!

* EDIT 2 *

Мы определили "разные" отличаться в зависимости от функции PHP similar_text. Но могут быть и другие определения. Реальные проблемы - это сравнение всех текстовых строк. Жан предложил считать итоги, и это взломанный вариант кода Филиппом, что делает так:

$strings = array(
    "The quick brown fox", 
    "The sly brown fox", 
    "The sly brown chicken", 
    "Totally different text here", 
    "Not like the others" 
); 

$n = 3; 
$sim = array(); 

for ($i = 0; $i < count($strings); $i++) { 

    $total = 0; 

    for ($j = 0; $j < count($strings); $j++) { 

     if($strings[$i] != $strings[$j]) { 

      $sim_val = similar_text($strings[$i], $strings[$j]); 
      $total += $sim_val; 
      $sim[$strings[$i]][] = array(
       "sim" => $sim_val, 
       "w1" => $strings[$i], 
       "w2" => $strings[$j] 
      ); 

     } 
    } 

    $sim[$strings[$i]]['total'] = $total; 

} 

uasort($sim, function($w1, $w2) { 
    return $w1["total"] > $w2["total"]; 
}); 

$sim = array_keys($sim); 
$sim = array_slice($sim,0,$n); 

Это возвращает

Array 
(
    [0] => Not like the others 
    [1] => Totally different text here 
    [2] => The quick brown fox 
) 

, который, похоже, как правильный ответ. Спасибо всем (за исключением тех, кто downvoted вопрос. Booo вам ;-)

EDIT 3 *

ОК, так что я тестировал это с моим 1000 строк. Каждый из них имеет около 500 уникальных слов и strlen около 14000. Итак ... чтобы быстро запустить это, мы сразу можем забыть о similar_text 'cos, как указано, это медленно. Я написал краткую функцию «compare_words»:

function same_words($text1,$text2) { 

    $words_1 = array_unique(explode(" ",$text1)); 
    $words_2 = array_flip(array_unique(explode(" ",$text2)));  

    foreach($words_1 AS $word) { 
     if($words_2[$word]) { 
      $count++; 
     } 
    } 

    return $count; 

} 

, но это слишком медленно.

Answer 1

Используйте функцию similar_text() и получите самые низкие проценты.

http://php.net/manual/en/function.similar-text.php

Answer 2

Ну, вот мысль: Определите, что вы называете быть разными. Определите много различий и приведите им оценку. Например:

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

Чем выше балл, тем выше разница между строками для исследуемых критериев.

Затем вычислите оценку «разницы» для двух строк. Самый высокий балл, самые разные.

Этот подход обычно используется, когда требуется принять решение на основе нескольких разных параметров. Это то, как некоторые антиспамовые программы идентифицируют спам. За исключением того, что они вычисляют оценку, чтобы определить, насколько похожа электронная почта на спам.

Вопрос: это всегда о сравнении. Таким образом, вы можете сравнить две строки вместе, но не одну строку для остальных. Таким образом, чтобы определить две самые разные строки, вам нужно будет прибегнуть к некоторой средней системе ... и выбрать те, чей счет больше, чем средний.

Answer 3

То, что вы должны сделать, это немного перебор и проверить каждое слово с другими словами, сохранить сходство (т.е. основанного на similar_text), а затем заказать результат по сходству

$strings = array(
    "The quick brown fox", 
    "The sly brown fox", 
    "The sly brown chicken", 
    "Totally different text here", 
    "Not like the others" 
); 

$n = 5; 
$sim = array(); 
$sum = 0; 

for ($i = 0; $i < count($strings); $i++) { 
    $t = 0; 
    for ($j = 0; $j < count($strings); $j++) { 
     if ($j != $i) { 
      $t += similar_text($strings[$i], $strings[$j]); 
     } 
    } 

    $avg = $t/(count($strings) - 1); 
    $sim[] = array(
     "sim" => $avg, 
     "word" => $strings[$i] 
    ); 

    $sum += $avg; 
} 

$avg = $sum/count($strings); 
usort($sim, function($w1, $w2) use ($avg) { 
    return abs($w1["sim"] - $avg) < abs($w2["sim"] - $avg); 
}); 

for ($i = 0; $i < $n && $i < count($sim); $i++) { 
    echo $sim[$i]['word'] . "<br />"; 
} 

Но у вас есть иметь в виду, что этот подход не очень быстро и работает в O(n^2 * m^3 + n log n)

Вместо similar_text вы можете также использовать Левенштейн, который выполняет очень лучше и результаты в чем-то вроде O(n^2*m^2 + n log n) (где т максимальная длина входных строк)