Wie kann ich Suchbegriffe in effizientere Abfragen bündeln?

Question

Ich muss eine Liste von Suchbegriffen in die effizienteste Kombination von Suchbegriffen umwandeln. Jedes Wort oder jede zitierte Phrase kann durch ein ODER getrennt werden. Viele Begriffe können in Klammern kombiniert werden. UNDs können ebenfalls verwendet werden.

Zum Beispiel, foo bar und boo bar teilen bar, so dass anstelle von zwei verschiedenen Suchbegriffe, die als (foo OR boo) AND bar kombiniert werden können.

Hier ist, was der Algorithmus tun muss. Angesichts dieser Datensatz:

foo bar 
boo bar 
goo bar 
hoo doo 
foo manchu 
moo bar 
too bar 
foo fighters 
"blue kazoo" bar 
baz 
qux 
quux 

Ich möchte folgendes zurück zu bekommen:

(foo OR boo OR goo OR moo OR too OR "blue kazoo") AND bar 
foo AND (manchu OR fighters) 
hoo doo 
baz OR qux OR quux 

Das funktioniert nicht:

(foo bar) OR (boo bar) OR (goo bar) OR (foo manchu) 

Ich werde arbeiten in PHP, aber ich Ich werde die Antwort in Pseudo-Code, PHP oder ich werde aus den wichtigsten Sprachen konvertieren.

Answer 1

Ich habe den folgenden Code:

function keyMultiSort(&$array, 
         $key, 
         $reverse = false, 
         $priority_last = false, 
         $save_key = true, 
         Callable $func = null) 
{ 
    if ($func === null) 
    { 
     $func = function ($first, $second) use ($key, $reverse, $priority_last) 
     { 
      if (!isset($first[$key])) 
      { 
       return ($reverse === false) ? -1 : 1; 
      } 
      if (!isset($second[$key])) 
      { 
       return ($reverse === false) ? 1 : -1; 
      } 

      if ($first[$key] > $second[$key]) 
      { 
       return ($reverse === false) ? 1 : -1; 
      } 
      if ($first[$key] < $second[$key]) 
      { 
       return ($reverse === false) ? -1 : 1; 
      } 
      if ($first[$key] === $second[$key]) 
      { 
       return ($priority_last === false) ? 1 : -1; 
      } 

      return 0; 
     }; 
    } 

    if ($save_key) 
    { 
     uasort($array, $func); 
    } 
    else 
    { 
     usort($array, $func); 
    } 
} 

$array = [ 
    ['foo', 'bar'], 
    ['boo', 'bar'], 
    ['goo', 'bar'], 
    ['hoo', 'doo'], 
    ['foo', 'manchu'], 
    ['moo', 'bar'], 
    ['too', 'bar'], 
    ['foo', 'fighters'], 
    ['blue kazoo', 'bar'], 
]; 

$pairs = []; 
$str = ''; 
foreach($array as $item) 
{ 
    if(!isset($pairs[$item[0]]['count'])) 
    { 
     $pairs[$item[0]]['count'] = 1; 
    } 
    else 
    { 
     $pairs[$item[0]]['count']++; 
    } 
    $pairs[$item[0]]['elements'][] = $item[1]; 

    if(!isset($pairs[$item[1]]['count'])) 
    { 
     $pairs[$item[1]]['count'] = 1; 
    } 
    else 
    { 
     $pairs[$item[1]]['count']++; 
    } 
    $pairs[$item[1]]['elements'][] = $item[0]; 
    keyMultiSort($pairs, 'count', true); 
} 

$remove = []; 
foreach($pairs as $elm=>$item) 
{ 
    $remove[] = $elm; 
    $elements = array_diff($item['elements'], $remove); 
    if(empty($elements)) 
    { 
     if (in_array($elm, $remove)) 
     { 
      continue; 
     } 
     $str .= $elm.PHP_EOL; 
    } 
    else 
    { 
     $str .= $elm.' AND ('.implode(' OR ', $elements).')'.PHP_EOL; 
    } 
    $remove = array_merge($remove, $elements); 
} 
var_dump($str); 

Ergebnis:

string(99) "bar AND (foo OR boo OR goo OR moo OR too OR blue kazoo) 
foo AND (manchu OR fighters) 
hoo AND (doo) 
" 

Es optimiert werden können, über die Ziele abhängig ...

Answer 2

Ich verstehe die Logik, aber Sie müssen wirklich die Frage klarer machen.

Wie auch immer, ich sehe dies als ein Graphproblem, wo wir die Menge von Knoten finden wollen, die den höchsten Grad haben und den gesamten Graphen überspannen können.

Ich glaube, wenn man es auf diese Weise vorstellen, können Sie eine beliebige Datenstruktur verwenden Sie den Zweck dienen. Sie könnten eine Adjazenzliste erstellen und dann Knoten mit höherem Grad finden und dann prüfen, ob alle Elemente durch diese Knoten abgedeckt sind. Das Hinzufügen von AND, OR ist einfach danach.

Answer 3

-Code für mehr als 2 Werte Verarbeitung

<?php 
function keyMultiSort(&$array, 
         $key, 
         $reverse = false, 
         $priority_last = false, 
         $save_key = true, 
         Callable $func = null) 
{ 
    if ($func === null) 
    { 
     $func = function ($first, $second) use ($key, $reverse, $priority_last) 
     { 
      if (!isset($first[$key])) 
      { 
       return ($reverse === false) ? -1 : 1; 
      } 
      if (!isset($second[$key])) 
      { 
       return ($reverse === false) ? 1 : -1; 
      } 

      if ($first[$key] > $second[$key]) 
      { 
       return ($reverse === false) ? 1 : -1; 
      } 
      if ($first[$key] < $second[$key]) 
      { 
       return ($reverse === false) ? -1 : 1; 
      } 
      if ($first[$key] === $second[$key]) 
      { 
       return ($priority_last === false) ? 1 : -1; 
      } 

      return 0; 
     }; 
    } 

    if ($save_key) 
    { 
     uasort($array, $func); 
    } 
    else 
    { 
     usort($array, $func); 
    } 
} 

$array = [ 
    ['foo', 'bar', 'test'], 
    ['boo', 'bar'], 
    ['goo', 'bar'], 
    ['hoo', 'doo', 'test', 'test2'], 
    ['foo', 'manchu'], 
    ['moo', 'bar'], 
    ['too', 'bar'], 
    ['foo', 'fighters'], 
    ['blue kazoo', 'bar', 'test'], 
]; 

$pairs = []; 
$str = ''; 
foreach($array as $item) 
{ 
    foreach($item as $key=>$elm) 
    { 
     foreach($item as $key2=>$elm2) 
     { 
      if($key !== $key2) 
      { 
       if(!isset($pairs[$elm]['count'])) 
       { 
        $pairs[$elm]['count'] = 1; 
       } 
       else 
       { 
        $pairs[$elm]['count']++; 
       } 
       $pairs[$elm]['elements'][] = $elm2; 
      } 
     } 
    } 

    keyMultiSort($pairs, 'count', true); 
} 
//var_dump($pairs); 
$remove = []; 
foreach($pairs as $elm=>$item) 
{ 
    $remove[] = $elm; 
    $elements = array_diff($item['elements'], $remove); 
    if(empty($elements)) 
    { 
     if (in_array($elm, $remove)) 
     { 
      continue; 
     } 
     $str .= $elm.PHP_EOL; 
    } 
    else 
    { 
     $str .= $elm.' AND ('.implode(' OR ', array_unique($elements)).')'.PHP_EOL; 
    } 
} 
var_dump($str); 

Antwort:

string(184) "bar AND (foo OR test OR boo OR goo OR moo OR too OR blue kazoo) 
test AND (foo OR hoo OR doo OR test2 OR blue kazoo) 
foo AND (manchu OR fighters) 
hoo AND (doo OR test2) 
doo AND (test2) 
" 

P. S. Ich hoffe, dass ich richtig die Aufgabe ...

verstanden haben

UPDATE Added-Code, der „Einzelwerte“ nicht außer Acht lässt. I geändert Logik:

...

['"yellow balloon"', 'foo', 'bar', 'baz', 'qut'], 

...

Rückkehr:

...

qut AND ("yellow balloon" OR baz) 
baz AND ("yellow balloon") 

...

Es scheint mir, für diese Aufgabe, das ist richtig (zu Bedingungen mehr als 2 Werte zu kombinieren).

function keyMultiSort(&$array, 
         $key, 
         $reverse = false, 
         $priority_last = false, 
         $save_key = true, 
         Callable $func = null) 
{ 
    if ($func === null) 
    { 
     $func = function ($first, $second) use ($key, $reverse, $priority_last) 
     { 
      if (!isset($first[$key])) 
      { 
       return ($reverse === false) ? -1 : 1; 
      } 
      if (!isset($second[$key])) 
      { 
       return ($reverse === false) ? 1 : -1; 
      } 

      if ($first[$key] > $second[$key]) 
      { 
       return ($reverse === false) ? 1 : -1; 
      } 
      if ($first[$key] < $second[$key]) 
      { 
       return ($reverse === false) ? -1 : 1; 
      } 
      if ($first[$key] === $second[$key]) 
      { 
       return ($priority_last === false) ? 1 : -1; 
      } 

      return 0; 
     }; 
    } 

    if ($save_key) 
    { 
     uasort($array, $func); 
    } 
    else 
    { 
     usort($array, $func); 
    } 
} 

$array = [ 
    ['foo', 'bar', 'test'], 
    ['boo', 'bar'], 
    ['goo', 'bar'], 
    ['hoo', 'doo', 'test', 'test2'], 
    ['foo', 'manchu'], 
    ['moo', 'bar'], 
    ['too', 'bar'], 
    ['foo', 'fighters'], 
    ['"blue kazoo"', 'bar', 'test'], 
    ['"red panda"', 'bar', 'test'], 
    ['"yellow balloon"', 'foo', 'bar', 'baz', 'qut'], 
    ['"red panda"', 'fighters', 'moo'], 
    ['"foo fighters"'], 
    ['foo'], 
    ['bar'], 
]; 

$pairs = []; 
$singles = []; 
$str = ''; 
foreach ($array as $item) 
{ 
    foreach ($item as $key => $elm) 
    { 
     if(count($item) === 1) 
     { 
      $singles[$elm] = 1; 
     } 
     else 
     { 
      if (!isset($pairs[$elm])) 
      { 
       $pairs[$elm]['count'] = 0; 
       $pairs[$elm]['elements'] = []; 
      } 
      foreach ($item as $key2 => $elm2) 
      { 
       if ($key !== $key2) 
       { 
        $pairs[$elm]['count']++; 
        $pairs[$elm]['elements'][] = $elm2; 
       } 
      } 
     } 
    } 

    keyMultiSort($pairs, 'count', true); 
} 
//var_dump($pairs);exit; 
$remove = []; 
foreach ($pairs as $elm => $item) 
{ 
    $remove[] = $elm; 
    $elements = array_diff($item['elements'], $remove); 
    $elements = array_unique($elements); 
    if (!empty($elements)){ 
     $str .= $elm.' AND ('.implode(' OR ', $elements).')'.PHP_EOL; 
    } 
} 
foreach ($singles as $elm => $item) 
{ 
    $str .= $elm.PHP_EOL; 
} 
var_dump($str); 

Antwort:

string(421) "bar AND (foo OR test OR boo OR goo OR moo OR too OR "blue kazoo" OR "red panda" OR "yellow balloon" OR baz OR qut) 
test AND (foo OR hoo OR doo OR test2 OR "blue kazoo" OR "red panda") 
foo AND (manchu OR fighters OR "yellow balloon" OR baz OR qut) 
"red panda" AND (fighters OR moo) 
qut AND ("yellow balloon" OR baz) 
baz AND ("yellow balloon") 
test2 AND (hoo OR doo) 
fighters AND (moo) 
doo AND (hoo) 
"foo fighters" 
foo 
bar 
" 

P. S. Meiner Meinung nach gilt dieses Problem nicht für die Realität