Как я могу объединить поисковые запросы в более эффективные запросы?

Мне нужно преобразовать список поисковых терминов в наиболее эффективный набор комбинированных поисковых терминов. Любое слово или цитируемая фраза может быть отделена OR. Многие термины могут быть объединены в круглые скобки. AND также могут использоваться.

Например, foo bar и boo bar обмениваются bar, поэтому вместо двух разных поисковых терминов их можно объединить как (foo OR boo) AND bar.

Вот что должен делать алгоритм. С учетом этого набора данных:

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

Я хочу получить следующий ответ:

(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

Это не работает:

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

Я буду работать на PHP, но я отвечу на него в псевдокоде, PHP или перейду с основных языков.

Ответ 1

Я получил следующий код:

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

Результат:

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

Он может быть оптимизирован в зависимости от целей...

Ответ 2

Я понимаю логику, но вам действительно нужно сделать вопрос более ясным.

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

Я верю, что если вы это сделаете, вы можете использовать любую структуру данных, которая вам нравится, чтобы служить цели. Вы можете создать список смежности, а затем найти узлы с более высокой степенью, а затем проверить, все ли покрыты этими узлами. Вопрос добавления AND, OR просто после этого.

Ответ 3

Код для обработки более 2 значений

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

Ответ:

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. Надеюсь, я правильно понял задачу...

UPDATE Добавлен код, который не игнорирует "одиночные значения". Я изменил логику:

...

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

...

Возврат:

...

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

...

Мне кажется, что для этой задачи это правильно (чтобы объединить более двух значений).

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

Ответ:

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. На мой взгляд, эта проблема не относится к реальности