<?php
/**
* SeekQuarry/Yioop --
* Open Source Pure PHP Search Engine, Crawler, and Indexer
*
* Copyright (C) 2009 - 2026 Chris Pollett chris@pollett.org
*
* LICENSE:
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*
* END LICENSE
*
* @author Chris Pollett chris@pollett.org
* @license https://www.gnu.org/licenses/ GPL3
* @link https://www.seekquarry.com/
* @copyright 2009 - 2026
* @filesource
*/
namespace seekquarry\yioop\library\index_bundle_iterators;
use seekquarry\yioop\configs as C;
use seekquarry\yioop\library as L;
use seekquarry\yioop\library\storage_formats\IndexDocumentBundle;
/**
* GroupIterator joins into one result the documents and document parts a
* search finds that share one url. For instance, the queue server stores
* both a link to a page and the page itself in the index bundle, an
* IndexDocumentBundle, or an IndexArchiveBundle for an older index. This
* iterator makes one result of the two, scored from both, whose summary
* may hold text from both. It does for a search what GROUP BY does for a
* database query.
*
* @author Chris Pollett
* @see IndexArchiveBundle
*/
class GroupIterator extends IndexBundleIterator
{
/**
* $count_block_unfiltered is the number of documents in the current
* block before pages without the words asked for are taken out
* @var int
*/
public $count_block_unfiltered;
/**
* $count_block is the number of groups in the current block after
* pages without the words asked for are taken out
* @var int
*/
public $count_block;
/**
* $current_block_hashes holds the url hashes first seen in the block
* the last call to findDocsWithWord returned
* @var array
*/
public $current_block_hashes;
/**
* $current_seen_hashes holds, for each page content hash seen in the
* current block, the url hashes with that content and the highest doc
* rank of each, so only the best page with that content is kept
* @var array
*/
public $current_seen_hashes;
/**
* $seen_docs_unfiltered is the number of documents walked so far,
* counted before pages without the words asked for are taken out
* @var int
*/
public $seen_docs_unfiltered;
/**
* $grouped_keys holds the url hashes of the groups returned in earlier
* blocks, so a later block does not return them again
* @var array
*/
public $grouped_keys;
/**
* $grouped_hashes holds the page content hashes of the groups
* returned in earlier blocks, so a copy of a page found under another
* url is not returned again
* @var array
*/
public $grouped_hashes;
/**
* $latest_copy_fraction is the share of a block of results, those of
* highest doc rank, whose newest copy computeOutPages looks up. It
* starts at LATEST_COPY_FRACTION; a test sets it to 1 to check every
* page.
* @var float
*/
public $latest_copy_fraction = C\LATEST_COPY_FRACTION;
/**
* __construct makes a group iterator over the documents another
* iterator finds, and reads its first block of documents.
*
* @param object $index_bundle_iterator the iterator whose documents are
* grouped
* @param int $num_iterators number of word iterators below this one;
* the more there are, the fewer documents are grouped per block
* @param int $current_machine when the index is spread over several
* queue servers, the number of the queue server this iterator
* runs on
*/
public function __construct(public $index_bundle_iterator,
$num_iterators = 1, public $current_machine = 0)
{
$this->num_docs = $this->index_bundle_iterator->num_docs;
$this->results_per_block = max(
$this->index_bundle_iterator->results_per_block,
C\p('MIN_RESULTS_TO_GROUP'));
$this->results_per_block /= ceil($num_iterators/2);
$this->reset();
}
/**
* getDirection gives the direction, CrawlConstants::ASCENDING or
* CrawlConstants::DESCENDING, in which the iterator below this one
* walks the partitions of the index.
*
* @return int direction of the walk
*/
public function getDirection()
{
if (!empty($this->index_bundle_iterator)) {
return $this->index_bundle_iterator->getDirection();
}
return self::ASCENDING;
}
/**
* reset moves the iterator below this one back to its first block of
* documents and forgets the groups already returned.
*/
public function reset()
{
$this->index_bundle_iterator->reset();
$this->grouped_keys = [];
$this->grouped_hashes = [];
// -1 == never save, so file name not used using time to be safer
$this->seen_docs = 0;
$this->seen_docs_unfiltered = 0;
}
/**
* findDocsWithWord makes the current block of groups when
* currentDocsWithWord has none kept. It takes a block of documents
* from the iterator below, groups them by url and by page content,
* and makes one result per group.
*
* @return mixed the block's results by document key, or -1 when there
* are no documents left
*/
public function findDocsWithWord()
{
// first get a block of documents on which grouping can be done
$pages = $this->getPagesToGroup();
if (is_array($pages)) {
$this->count_block_unfiltered = count($pages);
} else {
$this->count_block_unfiltered = 0;
return $pages;
}
$this->current_block_hashes = [];
$this->current_seen_hashes = [];
if ($this->count_block_unfiltered > 0 ) {
/* next we group like documents by url and remember
which urls we've seen this block
*/
$pre_out_pages = $this->groupByHashUrl($pages);
/*get doc page for groups of link data if exists and don't have
also aggregate by hash
*/
$this->groupByHashAndAggregate($pre_out_pages);
$this->count_block = count($pre_out_pages);
/*
Calculate aggregate values for each field of the groups we
found
*/
$pages = $this->computeOutPages($pre_out_pages);
}
$this->pages = $pages;
return $pages;
}
/**
* getPagesToGroup takes blocks of documents from the iterator below
* until it has at least results_per_block of them, or there are no
* more.
*
* @return mixed the documents' details by document key, or -1 when
* there are no documents left
*/
public function getPagesToGroup()
{
$pages = [];
$count = 0;
$done = false;
do {
$new_pages = $this->index_bundle_iterator->currentDocsWithWord();
if (!is_array($new_pages)) {
$done = true;
if (count($pages) == 0) {
$pages = -1;
}
} else if (!empty($new_pages)) {
$pages = array_merge($pages, $new_pages);
$count = count($pages);
}
if ($count < $this->results_per_block && !$done) {
$this->index_bundle_iterator->advance();
} else {
$done = true;
}
} while($done != true);
return $pages;
}
/**
* groupByHashUrl puts the documents of a block, and the link records
* that point to them, into lists by url hash, the document itself
* first. A url returned in an earlier block, and so held in
* $grouped_keys, is left out.
*
* @param array &$pages pages to group
* @return array $pre_out_pages pages after grouping
*/
public function groupByHashUrl(&$pages)
{
$pre_out_pages = [];
foreach ($pages as $doc_key => $doc_info) {
if (!is_array($doc_info)) {
continue;
}
$hash_url = substr($doc_key, 0, WordIterator::KEY_LEN);
// initial aggregate domain score vector for given domain
if (!empty($doc_info[self::IS_DOC])) {
if (!isset($pre_out_pages[$hash_url])) {
$pre_out_pages[$hash_url] = [];
}
array_unshift($pre_out_pages[$hash_url], $doc_info);
} else {
$pre_out_pages[$hash_url][] = $doc_info;
}
if (!isset($this->grouped_keys[$hash_url])) {
/*
new urls found in this block
*/
$this->current_block_hashes[] = $hash_url;
} else {
unset($pre_out_pages[$hash_url]);
}
}
return $pre_out_pages;
}
/**
* groupByHashAndAggregate scores each url group, then joins url groups
* whose pages have the same content hash. Of each such set, the group
* with the highest score is kept, and groups whose content was
* returned in an earlier block are left out.
*
* @param array &$pre_out_pages documents previously grouped by hash of url
*/
public function groupByHashAndAggregate(&$pre_out_pages)
{
foreach ($pre_out_pages as $hash_url => $data) {
$this->aggregateScores($hash_url, $pre_out_pages[$hash_url]);
if (isset($pre_out_pages[$hash_url][0][self::HASH])) {
$hash = $pre_out_pages[$hash_url][0][self::HASH];
if (IndexDocumentBundle::isType($data[0][self::KEY], "text")) {
//in this case the first four bytes is the hash of the title
$hash = substr($hash, 0, 4);
}
if (isset($this->grouped_hashes[$hash])) {
unset($pre_out_pages[$hash_url]);
} else {
if (!isset($this->current_seen_hashes[$hash])) {
$this->current_seen_hashes[$hash] = [];
}
if (!isset($this->current_seen_hashes[$hash][$hash_url])) {
$this->current_seen_hashes[$hash][$hash_url] = 0;
}
$this->current_seen_hashes[$hash][$hash_url] = max(
$pre_out_pages[$hash_url][0][self::DOC_RANK],
$this->current_seen_hashes[$hash][$hash_url]);
}
}
}
// delete all except highest scoring group with given hash
foreach ($this->current_seen_hashes as $hash => $url_data) {
if (count($url_data) == 1) {
continue;
}
arsort($url_data);
$first_time = true;
foreach ($url_data as $hash_url => $value) {
if ($first_time) {
$first_hash_url = $hash_url;
$first_time = false;
} else if ($pre_out_pages[$first_hash_url][0][self::SCORE] <
$pre_out_pages[$hash_url][0][self::SCORE]) {
$pre_out_pages[$first_hash_url] =
$pre_out_pages[$hash_url];
unset($pre_out_pages[$hash_url]);
}
}
}
}
/**
* computeOutPages makes one result per group, with the group's score
* and the places of the summaries of every copy in it. For the pages
* of highest doc rank it shows the newest copy, using newestCopy.
*
* @param array &$pre_out_pages array of groups of pages for which out pages
* are to be generated.
* @return array $out_pages array of single summarized documents
*/
public function computeOutPages(&$pre_out_pages)
{
$out_pages = [];
/* A newer copy of a page changes what it says, and so its
relevance, but not its doc rank. So only the pages whose doc
rank is in the top latest_copy_fraction of the block have their
newest copy looked up; the rest are shown as scored. */
$doc_ranks = [];
foreach ($pre_out_pages as $group_infos) {
$doc_ranks[] = $group_infos[0][self::DOC_RANK] ?? 0;
}
rsort($doc_ranks);
$num_checked = (int)ceil(count($doc_ranks) *
$this->latest_copy_fraction);
$least_checked_rank = ($num_checked > 0) ?
$doc_ranks[$num_checked - 1] : INF;
foreach ($pre_out_pages as $hash_url => $group_infos) {
$check_newest = ($group_infos[0][self::DOC_RANK] ?? 0) >=
$least_checked_rank;
$out_pages[$hash_url] = $pre_out_pages[$hash_url][0];
$add_lookup = false;
$hash = $out_pages[$hash_url][self::HASH];
$is_location =
(L\crawlHash($hash_url . "LOCATION", true) == $hash);
if (empty($out_pages[$hash_url][self::IS_DOC]) || $is_location) {
$add_lookup = true;
}
$out_pages[$hash_url][self::SUMMARY_OFFSET] = [];
unset($out_pages[$hash_url][self::GENERATION]);
$hash_count = $out_pages[$hash_url][self::HASH_URL_COUNT];
$num_copies = 0;
$num_dropped = 0;
$offset_keys = [];
for ($i = 0; $i < $hash_count; $i++) {
$doc_info = $group_infos[$i];
if (isset($doc_info[self::GENERATION])) {
$num_copies++;
if ($check_newest) {
$doc_info = $this->newestCopy($doc_info);
}
if ($doc_info === null) {
$num_dropped++;
continue;
}
if ($i == 0) {
$out_pages[$hash_url][self::KEY] =
$doc_info[self::KEY];
}
if (isset($offset_keys[$doc_info[self::KEY]])) {
continue;
}
$offset_keys[$doc_info[self::KEY]] = true;
$machine_id = (isset($doc_info[self::MACHINE_ID])) ?
$doc_info[self::MACHINE_ID] :$this->current_machine;
$out_pages[$hash_url][self::SUMMARY_OFFSET][] =
[$machine_id, $doc_info[self::KEY],
$doc_info[self::CRAWL_TIME],
$doc_info[self::GENERATION],
"PDB"];
}
}
/* Every copy found has a newer copy without the word it was
found for, so the page does not match. */
if ($num_copies > 0 && $num_dropped == $num_copies) {
unset($out_pages[$hash_url]);
continue;
}
if ($add_lookup) {
$prefix = ($is_location) ? "location:" : "info:";
$word_key = $prefix . L\base64Hash($hash_url);
array_unshift($out_pages[$hash_url][self::SUMMARY_OFFSET],
[$word_key, $group_infos[0][self::CRAWL_TIME]]);
}
}
return $out_pages;
}
/**
* newestCopy gives the document a search should show in place of a
* scored copy of a page. WordIterator marks a text page's posting
* with TERM_KEY, the word it was found for, and leaves this check to
* the pages that reach the results, rather than making it for every
* posting scored. The newest copy of the page's address is looked up
* with IndexManager::lookupLatestVersionPage. If it is the scored
* copy, or none is found, the copy is kept as it is. If the newest
* copy no longer holds the word, null is returned and the copy is
* dropped. Otherwise the copy's key, partition and document map index
* become the newest copy's, so the newest copy's summary is shown; its
* score stays the scored copy's.
*
* @param array $doc_info a scored copy of a page
* @return array|null the copy to show, or null if the page no longer
* holds the word
*/
public function newestCopy($doc_info)
{
if (empty($doc_info[self::TERM_KEY]) ||
!isset($doc_info['DOC_MAP_INDEX'])) {
return $doc_info;
}
$index_name = $doc_info[self::CRAWL_TIME];
$url_hash = substr($doc_info[self::KEY], 0,
IndexDocumentBundle::DOCID_PART_LEN);
$latest = L\IndexManager::lookupLatestVersionPage($url_hash,
$index_name);
if ($latest === null) {
return $doc_info;
}
[$latest_partition, $latest_posting] = $latest;
$latest_doc_map_index = $latest_posting['DOC_MAP_INDEX'] ?? -1;
if ($latest_partition == $doc_info[self::GENERATION] &&
$latest_doc_map_index == $doc_info['DOC_MAP_INDEX']) {
return $doc_info;
}
if (empty(L\IndexManager::termPostingInPartition($index_name,
$doc_info[self::TERM_KEY], $latest_partition,
$latest_doc_map_index))) {
return null;
}
$index = L\IndexManager::getIndex($index_name);
$entry = $index ? $index->docMapEntry($latest_partition,
$latest_doc_map_index) : "";
if (strlen($entry) < IndexDocumentBundle::DOCID_LEN) {
return $doc_info;
}
$doc_info[self::KEY] = substr($entry, 0,
IndexDocumentBundle::DOCID_LEN);
$doc_info[self::GENERATION] = $latest_partition;
$doc_info['DOC_MAP_INDEX'] = $latest_doc_map_index;
return $doc_info;
}
/**
* aggregateScores gives a group of pages with one url the highest doc
* rank and the highest relevance of its pages, their sum as its score,
* and its number of pages. They are stored in the group's first page.
* https://www.seekquarry.com/?c=main&p=ranking#search describes this.
*
* @param string $hash_url the crawlHash of the url of the page we are
* scoring which will be compared with that of the host to see if
* the current page has the url of a hostname.
* @param array &$pre_hash_page pages to compute scores for
*/
public function aggregateScores($hash_url, &$pre_hash_page)
{
$max_rank = 0;
$max_relevance = 0;
$domain_weights = [];
foreach ($pre_hash_page as $hash_page) {
if (isset($hash_page[self::SCORE])) {
$max_rank = max($max_rank, $hash_page[self::DOC_RANK]);
$max_relevance = max($max_relevance,
$hash_page[self::RELEVANCE]);
}
}
$pre_hash_page[0][self::SCORE] = $max_rank + $max_relevance;
$pre_hash_page[0][self::DOC_RANK] = $max_rank;
$pre_hash_page[0][self::HASH_URL_COUNT] = count($pre_hash_page);
$pre_hash_page[0][self::RELEVANCE] = $max_relevance;
}
/**
* advance moves the iterator on by one block of groups. It updates the
* estimate of the number of groups, and remembers the urls and page
* contents of this block so later blocks leave them out.
*
* @param array $gen_doc_offset a partition and document offset pair.
* If given, the next block starts at a partition no earlier than
* it, and in that partition at a document offset no smaller.
*/
public function advance($gen_doc_offset = null)
{
$this->advanceSeenDocs();
$this->seen_docs_unfiltered += $this->count_block_unfiltered;
if ($this->seen_docs_unfiltered > 0) {
if ( $this->count_block_unfiltered < $this->results_per_block) {
$this->num_docs = $this->seen_docs;
} else {
$this->num_docs =
floor(
($this->seen_docs * $this->index_bundle_iterator->num_docs)/
$this->seen_docs_unfiltered);
}
} else {
$this->num_docs = 0;
}
foreach ($this->current_block_hashes as $hash_url) {
$this->grouped_keys[$hash_url] = true;
}
foreach ($this->current_seen_hashes as $hash => $url_data) {
$this->grouped_hashes[$hash] = true;
}
$this->index_bundle_iterator->advance($gen_doc_offset);
}
/**
* currentGenDocOffsetWithWord gives the partition and document offset
* of the next document this iterator would return.
*
* @return mixed an array of the partition and document offset, or -1
* when there are no documents left
*/
public function currentGenDocOffsetWithWord()
{
return $this->index_bundle_iterator->currentGenDocOffsetWithWord();
}
}
- Yioop Repo - Seekquarry