Инвертированный индекс на PHP

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

Ниже приведён небольшой учебный код на PHP для построения такого индекса.

Работаем в однобайтовой кодировке, иначе придётся менять ряд функций на юникодовские. Также предполагаем, что у нас латиница, иначе нужно учесть, что кириллица может не обрабатываться стандартными функциями. Выполнялось на локальном хосте в Denwer.

<?php
function buildInvertedIndex ($filenames) { //Построение инвертированного индекса по словам файлов из $filenames
 $invertedIndex = [];
 foreach ($filenames as $filename) {
  $data = file_get_contents($filename);
  if ($data === false) die ('Unable to read file: '.$filename);
  preg_match_all('/(\w+)/', $data, $matches, PREG_SET_ORDER);
  foreach($matches as $match) {
   $word = strtolower($match[0]);
   if (!array_key_exists($word, $invertedIndex)) $invertedIndex[$word] = [];
   if (!in_array($filename, $invertedIndex[$word], true)) $invertedIndex[$word][] = $filename;
  }
 }
 return $invertedIndex;
}
 
function lookupWord($invertedIndex, $word) {
 return array_key_exists($word, $invertedIndex) ? $invertedIndex[$word] : false;
}

$files = Array ('file1.txt', 'file2.txt'); //Массив проверяемых файлов

//Пишем контент в файлы:
file_put_contents ($files[0],"Cat don't like bananas\n and apples");
file_put_contents ($files[1],"Banana, Banana Mama\n it is no no cat and balagana");

$words = Array ('cat', 'is', 'banana', 'game'); //Массив контрольных слов
 
$invertedIndex = buildInvertedIndex($files);
print_r($invertedIndex); //Вывод всего индекса для отладки

//Поиск контрольных слов в индексе:
foreach($words as $word) {
 $matches = lookupWord($invertedIndex, $word);
 if ($matches !== false) {
  echo "<br>Found the word \"$word\" in the following files: " . implode(', ', $matches) . "\n";
 }
 else {
  echo "<br>Unable to find the word \"$word\" in the index\n";
 }
}
?>

Вывод примера такой:

Array ( [cat] => Array ( [0] => file1.txt [1] => file2.txt ) [don] => Array ( [0] => file1.txt ) [t] => Array ( [0] => file1.txt ) [like] => Array ( [0] => file1.txt ) [bananas] => Array ( [0] => file1.txt ) [and] => Array ( [0] => file1.txt [1] => file2.txt ) [apples] => Array ( [0] => file1.txt ) [banana] => Array ( [0] => file2.txt ) [mama] => Array ( [0] => file2.txt ) [it] => Array ( [0] => file2.txt ) [is] => Array ( [0] => file2.txt ) [no] => Array ( [0] => file2.txt ) [balagana] => Array ( [0] => file2.txt ) )
Found the word "cat" in the following files: file1.txt, file2.txt
Found the word "is" in the following files: file2.txt
Found the word "banana" in the following files: file2.txt
Unable to find the word "game" in the index

22.09.2018, 12:59 [2107 просмотров]