1 Востаннє редагувалося Replace (01.10.2012 16:27:25)

Тема: Розбиття пошукового запиту на частини (задачка на п'ятірку)

Написати функцію котра буде розбивати пошуковий запит спочатку на дві рівні частини, потім кожну з двох частин пробує розбити знову на 2 рівні частини і так до тих пір поки частини не стануть 1 словом. На виході має бути масив з усіма унікальними частинами початкового запиту.
Наприклад, запит "слово1 слово2 слово3 слово4 слово5 слово6 слово7 слово8 слово9 слово10 слово11 слово12", повинен перетворитися у наступний масив :

$parts = array(
"слово1 слово2 слово3 слово4 слово5 слово6",
"слово7 слово8 слово9 слово10 слово11 слово12",
"слово1 слово2 слово3",
"слово4 слово5 слово6",
"слово1 слово2",
"слово4 слово5",
"слово3",
"слово6",
"слово1",
"слово2",
"слово4",
"слово5",
"слово7 слово8 слово9",
"слово10 слово11 слово12",
"слово7 слово8",
"слово10 слово11",
"слово9",
"слово12",
"слово7",
"слово8",
"слово10",
"слово11"
);

Така функція може бути корисна коли ми хочемо знайти у базі даних максимально точне співпадання із пошуковим запитом. Наприклад, спочатку шукаємо входження цілого запиту, якщо немає відповідностей то шукаємо входження кожної із менших частин і т.д.

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }
Подякували: Replace1

2

Re: Розбиття пошукового запиту на частини (задачка на п'ятірку)

Patron, У мене є задача на 5+. Можна я потім створю тему? Десь через тиждень? :)
P.S. Потім можна буде збірник випустити :)

3 Востаннє редагувалося Patron (24.09.2012 00:08:36)

Re: Розбиття пошукового запиту на частини (задачка на п'ятірку)

якщо не цікаво то я можу не писати задачки. просто дивлюся що мало обговорення на форумі от і намагаюся трохи простимулювати.

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }
Подякували: Replace1

4

Re: Розбиття пошукового запиту на частини (задачка на п'ятірку)

Всім хай. Ось функція :)

$phrase = 'слово1 слово2 слово3 слово4 слово5 слово6 слово7 слово8 слово9 слово10 слово11 слово12';
$result = getUniquePhrases($phrase);
echo '<pre>'.__LINE__.'***'.print_r($result, true) .'</pre>';

function getUniquePhrases($string) {
  $result = array();

  $phraseArrayByWord = explode(' ', $string);
  if (count($phraseArrayByWord) > 2) {
    $halfItemNums = round(count($phraseArrayByWord) / 2);
    $firstPart    = implode(' ', array_slice($phraseArrayByWord, 0, $halfItemNums));
    $secondPart   = implode(' ', array_slice($phraseArrayByWord, $halfItemNums));

    $result[] = $firstPart;
    $result[] = $secondPart;

    foreach (array($firstPart, $secondPart) as $partPhrase) {
      $newResult = getUniquePhrases($partPhrase);
      $result    = array_merge($result, $newResult);
    }
  } else {
    $result = array_merge($result, $phraseArrayByWord);
  }

  $result = array_unique($result);
  return $result;
}


Ось результат роботи функції

5***Array
(
    [0] => слово1 слово2 слово3 слово4 слово5 слово6
    [1] => слово7 слово8 слово9 слово10 слово11 слово12
    [2] => слово1 слово2 слово3
    [3] => слово4 слово5 слово6
    [4] => слово1 слово2
    [5] => слово3
    [6] => слово1
    [7] => слово2
    [8] => слово4 слово5
    [9] => слово6
    [10] => слово4
    [11] => слово5
    [12] => слово7 слово8 слово9
    [13] => слово10 слово11 слово12
    [14] => слово7 слово8
    [15] => слово9
    [16] => слово7
    [17] => слово8
    [18] => слово10 слово11
    [19] => слово12
    [20] => слово10
    [21] => слово11
)

5

Re: Розбиття пошукового запиту на частини (задачка на п'ятірку)

Replace написав:

Patron, У мене є задача на 5+. Можна я потім створю тему? Десь через тиждень? :)
P.S. Потім можна буде збірник випустити :)

На своєму блозі я уже започаткував задачі по рнр правда там рівень трошки інший ;) Якщо є задача викладай ))

6

Re: Розбиття пошукового запиту на частини (задачка на п'ятірку)

Рішення 2 більш підходить для пошуку.
Наприклад, запит Ноутбук Asus Aspire One.
А в базі є лише Asus Aspire One.

По 1-му видасть всі товари, які мають Asus, а по другому знайде Asus Aspire.
Хоча найбільш ідеальним буде таке розбиття:

Ноутбук Asus Aspire One
Ноутбук Asus Aspire
Asus Aspire One
Ноутбук Asus
Asus Aspire
Aspire One
Ноутбук
Asus
Aspire
One

Але це буде занадто круто...

Рішення 1

$search_query = "слово1 слово2 слово3 слово4 слово5 слово6 слово7 слово8 слово9 слово10 слово11 слово12";

var_dump(explode_query($search_query));

function explode_query($query) {
    $parts = explode(' ', $query);
    
    for ($i = 2; $i < count($parts); $i++) {
        
        for ($j = 0; $j < count($parts); $j += (int) (count($parts) / $i)) {
            $result[] = implode(' ', array_slice($parts, $j, count($parts) / $i));
        }
    }
    
    return array_unique($result);
    
}


Рішення 2

$search_query = "слово1 слово2 слово3 слово4 слово5 слово6 слово7 слово8 слово9 слово10 слово11 слово12";

var_dump(explode_query($search_query));

function explode_query($query) {
    $parts = explode(' ', $query);
    
    for ($i = 2; $i < count($parts); $i++) {
        
        for ($j = 0; $j < count($parts); $j++) {
            $result[] = implode(' ', array_slice($parts, $j, count($parts) / $i));
        }
    }
    
    return array_unique($result);
    
}


Результат1

array(27) {
  [0]=>
  string(71) "слово1 слово2 слово3 слово4 слово5 слово6"
  [1]=>
  string(74) "слово7 слово8 слово9 слово10 слово11 слово12"
  [2]=>
  string(47) "слово1 слово2 слово3 слово4"
  [3]=>
  string(47) "слово5 слово6 слово7 слово8"
  [4]=>
  string(50) "слово9 слово10 слово11 слово12"
  [5]=>
  string(35) "слово1 слово2 слово3"
  [6]=>
  string(35) "слово4 слово5 слово6"
  [7]=>
  string(35) "слово7 слово8 слово9"
  [8]=>
  string(38) "слово10 слово11 слово12"
  [9]=>
  string(23) "слово1 слово2"
  [10]=>
  string(23) "слово3 слово4"
  [11]=>
  string(23) "слово5 слово6"
  [12]=>
  string(23) "слово7 слово8"
  [13]=>
  string(24) "слово9 слово10"
  [14]=>
  string(25) "слово11 слово12"
  [21]=>
  string(11) "слово1"
  [22]=>
  string(11) "слово2"
  [23]=>
  string(11) "слово3"
  [24]=>
  string(11) "слово4"
  [25]=>
  string(11) "слово5"
  [26]=>
  string(11) "слово6"
  [27]=>
  string(11) "слово7"
  [28]=>
  string(11) "слово8"
  [29]=>
  string(11) "слово9"
  [30]=>
  string(12) "слово10"
  [31]=>
  string(12) "слово11"
  [32]=>
  string(12) "слово12"
}


Результат 2

array(50) {
  [0]=>
  string(71) "слово1 слово2 слово3 слово4 слово5 слово6"
  [1]=>
  string(71) "слово2 слово3 слово4 слово5 слово6 слово7"
  [2]=>
  string(71) "слово3 слово4 слово5 слово6 слово7 слово8"
  [3]=>
  string(71) "слово4 слово5 слово6 слово7 слово8 слово9"
  [4]=>
  string(72) "слово5 слово6 слово7 слово8 слово9 слово10"
  [5]=>
  string(73) "слово6 слово7 слово8 слово9 слово10 слово11"
  [6]=>
  string(74) "слово7 слово8 слово9 слово10 слово11 слово12"
  [7]=>
  string(62) "слово8 слово9 слово10 слово11 слово12"
  [8]=>
  string(50) "слово9 слово10 слово11 слово12"
  [9]=>
  string(38) "слово10 слово11 слово12"
  [10]=>
  string(25) "слово11 слово12"
  [11]=>
  string(12) "слово12"
  [12]=>
  string(47) "слово1 слово2 слово3 слово4"
  [13]=>
  string(47) "слово2 слово3 слово4 слово5"
  [14]=>
  string(47) "слово3 слово4 слово5 слово6"
  [15]=>
  string(47) "слово4 слово5 слово6 слово7"
  [16]=>
  string(47) "слово5 слово6 слово7 слово8"
  [17]=>
  string(47) "слово6 слово7 слово8 слово9"
  [18]=>
  string(48) "слово7 слово8 слово9 слово10"
  [19]=>
  string(49) "слово8 слово9 слово10 слово11"
  [24]=>
  string(35) "слово1 слово2 слово3"
  [25]=>
  string(35) "слово2 слово3 слово4"
  [26]=>
  string(35) "слово3 слово4 слово5"
  [27]=>
  string(35) "слово4 слово5 слово6"
  [28]=>
  string(35) "слово5 слово6 слово7"
  [29]=>
  string(35) "слово6 слово7 слово8"
  [30]=>
  string(35) "слово7 слово8 слово9"
  [31]=>
  string(36) "слово8 слово9 слово10"
  [32]=>
  string(37) "слово9 слово10 слово11"
  [36]=>
  string(23) "слово1 слово2"
  [37]=>
  string(23) "слово2 слово3"
  [38]=>
  string(23) "слово3 слово4"
  [39]=>
  string(23) "слово4 слово5"
  [40]=>
  string(23) "слово5 слово6"
  [41]=>
  string(23) "слово6 слово7"
  [42]=>
  string(23) "слово7 слово8"
  [43]=>
  string(23) "слово8 слово9"
  [44]=>
  string(24) "слово9 слово10"
  [45]=>
  string(25) "слово10 слово11"
  [60]=>
  string(11) "слово1"
  [61]=>
  string(11) "слово2"
  [62]=>
  string(11) "слово3"
  [63]=>
  string(11) "слово4"
  [64]=>
  string(11) "слово5"
  [65]=>
  string(11) "слово6"
  [66]=>
  string(11) "слово7"
  [67]=>
  string(11) "слово8"
  [68]=>
  string(11) "слово9"
  [69]=>
  string(12) "слово10"
  [70]=>
  string(12) "слово11"
}

7

Re: Розбиття пошукового запиту на частини (задачка на п'ятірку)

А ще можна для повноти додати в результат декартовий добуток із усіх слів, тобто усі можливі комбінації із двох слів.

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }