Beutel mit Wörtern Modell: 2 PHP-Funktionen, gleiche Ergebnisse: Warum?

Question

Ich habe zwei PHP-Funktionen, um die Beziehung zwischen zwei Texten zu berechnen. Sie benutzen beide den Beutel mit Wörtern, aber check2() ist viel schneller. Wie auch immer, beide Funktionen geben die gleichen Ergebnisse. Warum? check1() verwendet ein großes Dictionary-Array, das ALLE Wörter enthält - wie im Textbeutelmodell beschrieben. check2() verwendet kein großes Array, sondern ein Array, das nur die Wörter eines Textes enthält. Check2() sollte also nicht funktionieren, tut es aber nicht. Warum geben beide Funktionen die gleichen Ergebnisse?

function check1($terms_in_article1, $terms_in_article2) { 
    global $zeit_check1; 
    $zeit_s = microtime(TRUE); 
    $length1 = count($terms_in_article1); // number of words 
    $length2 = count($terms_in_article2); // number of words 
    $all_terms = array_merge($terms_in_article1, $terms_in_article2); 
    $all_terms = array_unique($all_terms); 
    foreach ($all_terms as $all_termsa) { 
     $term_vector1[$all_termsa] = 0; 
     $term_vector2[$all_termsa] = 0; 
    } 
    foreach ($terms_in_article1 as $terms_in_article1a) { 
     $term_vector1[$terms_in_article1a]++; 
    } 
    foreach ($terms_in_article2 as $terms_in_article2a) { 
     $term_vector2[$terms_in_article2a]++; 
    } 
    $score = 0; 
    foreach ($all_terms as $all_termsa) { 
     $score += $term_vector1[$all_termsa]*$term_vector2[$all_termsa]; 
    } 
    $score = $score/($length1*$length2); 
    $score *= 500; // for better readability 
    $zeit_e = microtime(TRUE); 
    $zeit_check1 += ($zeit_e-$zeit_s); 
    return $score; 
} 
function check2($terms_in_article1, $terms_in_article2) { 
    global $zeit_check2; 
    $zeit_s = microtime(TRUE); 
    $length1 = count($terms_in_article1); // number of words 
    $length2 = count($terms_in_article2); // number of words 
    $score_table = array(); 
    foreach($terms_in_article1 as $term){ 
     if(!isset($score_table[$term])) $score_table[$term] = 0; 
     $score_table[$term] += 1; 
    } 
    $score_table2 = array(); 
    foreach($terms_in_article2 as $term){ 
     if(isset($score_table[$term])){ 
      if(!isset($score_table2[$term])) $score_table2[$term] = 0; 
      $score_table2[$term] += 1; 
     } 
    } 
    $score = 0; 
    foreach($score_table2 as $key => $entry){ 
     $score += $score_table[$key] * $entry; 
    } 
    $score = $score/($length1*$length2); 
    $score *= 500; 
    $zeit_e = microtime(TRUE); 
    $zeit_check2 += ($zeit_e-$zeit_s); 
    return $score; 
} 

Ich hoffe, Sie können mir helfen. Danke im Voraus!

Answer 1

Beide Funktionen implementieren ziemlich den gleichen Algorithmus, aber während der erste es in direkter Weise tut, ist der zweite etwas cleverer und überspringt einen Teil unnötiger Arbeit.

check1 geht so:

// loop length(words1) times 
for each word in words1: 
    freq1[word]++ 

// loop length(words2) times 
for each word in words2: 
    freq2[word]++ 

// loop length(union(words1, words2)) times 
for each word in union(words1, words2): 
    score += freq1[word] * freq2[word] 

Aber denken Sie daran: Wenn Sie etwas mit Null multiplizieren, erhalten Sie Null bekommen.

Dies bedeutet, dass das Zählen der Häufigkeiten von Wörtern, die nicht in beiden Mengen sind, eine Verschwendung von Zeit ist - wir multiplizieren die Frequenz mit Null und das wird dem Ergebnis nichts hinzufügen.

check2 berücksichtigt dies:

// loop length(words1) times 
for each word in words1: 
    freq1[word]++ 

// loop length(words2) times 
for each word in words2: 
    if freq1[word] > 0: 
     freq2[word]++ 

// loop length(intersection(words1, words2)) times 
for each word in freq2: 
    score += freq1[word] * freq2[word] 

Answer 2

, da Sie über die Leistung zu besorgt scheinen, hier ist eine optimierte Version des Algorithmus in Ihrer check2 Funktion, die einige weitere integrierte Funktionen für eine verbesserte Geschwindigkeit verwendet.

function check ($terms1, $terms2) 
{ 
    $counts1 = array_count_values($terms1); 
    $totalScore = 0; 
    foreach ($terms2 as $term) { 
     if (isset($counts1[$term])) $totalScore += $counts1[$term]; 
    } 
    return $totalScore * 500/(count($terms1) * count($terms2)); 
}