Come posso raggruppare i termini di ricerca in query più efficienti?

Question

Devo convertire un elenco di termini di ricerca nel più efficiente insieme di termini di ricerca combinati. Qualsiasi parola o frase citata può essere separata da un OR. Molti termini possono essere combinati tra parentesi. Gli AND possono anche essere usati.

Per esempio, foo bar e boo bar parti bar, così invece di due differenti termini di ricerca, la possono essere combinati come (foo OR boo) AND bar.

Ecco cosa deve fare l'algoritmo. Dato questo insieme di dati:

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

voglio ottenere le seguenti posteriore:

(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 

Questo non funziona:

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

lavorerò in PHP, ma io' Prenderò la risposta in pseudo-codice, PHP o convertirò dalle principali lingue.

Answer 1

ho ottenuto il seguente codice:

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); 

Risultato:

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

Può essere ottimizzato, a seconda degli obiettivi ...

Answer 2

Capisco la logica ma è davvero necessario rendere la domanda più chiara.

In ogni caso, vedo questo come un problema grafico in cui vogliamo trovare l'insieme di nodi che hanno il massimo grado e possono estendersi su tutto il grafico.

Credo che se si immagina in questo modo, è possibile utilizzare qualsiasi struttura di dati che ti piace per servire allo scopo. È possibile creare un elenco di adiacenza e quindi trovare i nodi con un grado superiore e quindi verificare se tutti gli elementi sono coperti da tali nodi. La questione dell'aggiunta di AND, OR è solo semplice in seguito.

Answer 3

Codice in materia di trattamento più di 2 valori

<?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); 

Risposta:

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. Spero di aver capito bene il compito ...

UPDATE codice Aggiunto che non ignora "valori singoli". Ho cambiato la logica:

...

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

...

ritorno:

...

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

...

Mi sembra, per questo compito, che è corretta (per le condizioni di combinare più di 2 valori).

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); 

Risposta:

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. A mio parere, questo problema non si applica alla realtà