<?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\IndexShard;
use seekquarry\yioop\library\storage_formats\IndexDocumentBundle;
use seekquarry\yioop\library\IndexManager;
use seekquarry\yioop\models\ParallelModel;
use seekquarry\yioop\library\language_processing as LLP;
/**
* WordIterator walks the posting lists of one term in an
* IndexDocumentBundle, partition by partition, and gives back the
* documents that hold the term with their relevance and rank. A query
* has one for each term it reads, joined by UnionIterator,
* IntersectIterator and others.
*
* How terms and their documents are stored is described in the
* documentation of IndexDocumentBundle.
*
* @author Chris Pollett
* @see IndexArchiveBundle
*/
class WordIterator extends IndexBundleIterator
{
/**
* HOST_KEY_POS is where a document key's host hash starts. Bytes 0 to
* 15 of the key hold the url and page hashes, and byte 16 says if the
* key is a document, a link from inside its site or a link from
* outside.
*/
const HOST_KEY_POS = 17;
/**
* Length of a doc key part
*/
const KEY_LEN = 8;
/**
* NO_POSITIONS_RELEVANCE is the relevance of a posting with no
* positions, as a meta word such as media:news has. It is close to 0
* but not 0, so nothing divides by it as by 0.
*/
const NO_POSITIONS_RELEVANCE = 0.01;
/**
* $base64_word_key is the term's key written in Yioop's form of base64.
*
* @var string
*/
public $base64_word_key;
/**
* $current_doc_offset is the document map index of the posting the walk
* is at, or null until currentGenDocOffsetWithWord works it out.
*
* @var int
*/
public $current_doc_offset;
/**
* $current_generation is the number of the partition the walk is in.
*
* @var int
*/
public $current_generation;
/**
* $current_offset is the index, in the current partition's posting list,
* of the posting the walk is at.
*
* @var int
*/
public $current_offset;
/**
* $dictionary_info holds the dictionary rows of the term for the
* partitions of the current batch: each row's partition, posting list
* offset and length, and number of documents.
*
* @var array
*/
public $dictionary_info;
/**
* $empty says the term is in no partition of the index, so the walk
* has nothing to give.
*
* @var int
*/
public $empty;
/**
* $generation_pointer is the index, in dictionary_info, of the row of the
* partition the walk is in.
*
* @var int
*/
public $generation_pointer;
/**
* $batch_offset is the position, among all the dictionary rows of this
* iterator's word, of the first row now held in $dictionary_info. The
* rows are read generation_batch_size at a time, so a word found in
* many partitions is read in batches as the walk reaches each one.
* @var int
*/
public $batch_offset = 0;
/**
* $batch_full is true when the last batch of dictionary rows read held
* a full generation_batch_size rows, so the word may have more rows
* past it that an ascending walk still has to read.
* @var bool
*/
public $batch_full = false;
/**
* $generation_batch_size is how many dictionary rows of the word
* loadGenerationBatch reads in one lookup. It starts at
* NUM_DISTINCT_GENERATIONS; a test sets it lower to walk a word in
* several batches.
* @var int
*/
public $generation_batch_size = C\NUM_DISTINCT_GENERATIONS;
/**
* $scoring_partition holds, for the partition
* getDocKeyPositionsScoringInfo last scored postings of, [partition,
* positions file handle, positions file size, number of documents,
* index], so the many calls a union makes for one partition open its
* positions file, read its document count and look up the index once
* @var array
*/
public $scoring_partition = [];
/**
* $walk_started is when this iterator read its first batch of
* dictionary rows, as a microtime. In an index built before combined
* terms, later batches are read only while less than
* OLD_INDEX_BATCH_SECONDS have passed since then.
* @var float
*/
public $walk_started = 0;
/**
* $combined_terms is true when the iterator's index was built with
* combined terms, so its batch walk needs no time bound.
* @var bool
*/
public $combined_terms = false;
/**
* $is_meta says the term is a meta word, a name:value word Yioop adds to
* a page, as media:news is.
*
* @var string
*/
public $is_meta;
/**
* $last_offset is the index of the last posting in the current
* partition's posting list.
*
* @var int
*/
public $last_offset;
/**
* $next_offset is the index of the first posting after the block just
* read, where advance moves the walk to.
*
* @var int
*/
public $next_offset;
/**
* $num_generations is the number of partitions in the current batch
* of dictionary rows.
*
* @var int
*/
public $num_generations;
/**
* $max_items_per_partition is the most documents the index puts in one
* partition. It bounds a row's document count and is used in the
* rank of a document.
*
* @var int
*/
public $max_items_per_partition;
/**
* $avg_items_per_partition is the average number of the term's
* documents in a partition that holds it, used in the rank of a
* document.
*
* @var int
*/
public $avg_items_per_partition;
/**
* $total_number_of_partitions is the number of partitions in the index.
*
* @var int
*/
public $total_number_of_partitions;
/**
* $num_occurrences is the number of times the term is in the index,
* estimated from the partitions read where they are too many to count.
*
* @var int
*/
public $num_occurrences;
/**
* $threshold_exceeded says the term was in so many partitions that its
* counts are estimated rather than counted.
*
* @var int
*/
public $threshold_exceeded;
/**
* $archive_file is the name of an archive file holding the term. No
* dictionary lookup fills it at present, so it is the empty string.
*
* @var int
*/
public $archive_file;
/**
* $term_info_computed says termInfoIteratorFields has filled the term's
* counts, so they are not read again.
*
* @var int
*/
public $term_info_computed;
/**
* $total_num_docs_and_links is the number of documents and links in the
* index.
*
* @var int
*/
public $total_num_docs_and_links;
/**
* $ranking_factors holds the weights of host keywords, title words and
* path keywords, and the other factors used for relevance and rank.
*
* @var array
*/
public $ranking_factors;
/**
* $start_generation is the first partition the walk read the term's
* rows for.
*
* @var int
*/
public $start_generation;
/**
* $start_offset is the index of the first posting in the current
* partition's posting list.
*
* @var int
*/
public $start_offset;
/**
* $word_key is the key of the term or phrase the walk is over.
*
* @var string
*/
public $word_key;
/**
* __construct makes a walk over the postings of a term in an index.
*
* @param string $word_key hash of word or phrase to iterate docs
* of
* @param string $index_name the timestamp of the index this
* iterator is associated with
* @param bool $raw whether the $word_key is our variant of base64
* encoded
* @param SearchfiltersModel $filter model responsible for keeping
* track of edited and deleted search results
* @param int $results_per_block the maximum number of results
* that can be returned by a findDocsWithWord call
* @param int $direction when results are accessed from
* $index_name, in which order they should be presented.
* self::ASCENDING is from first added to last added,
* self::DESCENDING is from last added to first added. Note:
* this value is not saved permanently, so you could in
* theory open two read only versions of the same bundle but
* reading the results in different directions
* @param array $ranking_factors field says how url, keywords, and
* title words should influence relevance and doc rank
* calculations
* @param bool $retrieve_latest whether the latest indexed
* instance of a document should be returned or not (might
* have multiple instances if crawl indexes document more
* than once) (@see PhraseModel::lookupSummaryOffsetGeneration())
*/
public function __construct($word_key, public $index_name, $raw = false,
public $filter = null, $results_per_block =
IndexBundleIterator::RESULTS_PER_BLOCK,
public $direction = self::ASCENDING,
$ranking_factors = [], public $retrieve_latest = true)
{
if ($raw == false) {
//get rid of our modified base64 encoding
$word_key = L\unbase64Hash($word_key);
}
$this->word_key = $word_key;
$this->is_meta = LLP\PhraseParser::checkMetaTerm(
$this->word_key);
$this->base64_word_key = L\base64Hash($word_key);
$this->termInfoIteratorFields($index_name, $word_key);
$this->current_doc_offset = null;
$this->results_per_block = $results_per_block;
$this->current_block_fresh = false;
$this->start_generation = ($direction == self::ASCENDING) ? 0 :
"ACTIVE";
foreach (["CLD_URL_BONUS" => C\p('CLD_URL_BONUS'),
"HOST_URL_BONUS" => C\p('HOST_URL_BONUS'),
"HOST_KEYWORD_BONUS" => C\p('HOST_KEYWORD_BONUS'),
"PATH_KEYWORD_BONUS" => C\p('PATH_KEYWORD_BONUS'),
"TITLE_BONUS" => C\p('TITLE_BONUS'),
"WIKI_BONUS" => C\p('WIKI_BONUS'),
"NUM_SLASHES_BONUS" => C\p('NUM_SLASHES_BONUS'),
] as $factor => $default) {
$this->ranking_factors[$factor] = $ranking_factors[$factor] ??
$default;
}
if (!$this->empty) {
$this->reset();
}
}
/**
* getDirection tells which way the walk goes through the index:
* CrawlConstants::ASCENDING, from the first document added, or
* CrawlConstants::DESCENDING, from the last.
*
* @return int direction traversing underlying archive bundle
*/
public function getDirection()
{
return $this->direction;
}
/**
* reset moves the walk back to the term's first block of documents.
*/
public function reset()
{
if (!$this->empty) {//we shouldn't be called when empty - but to be safe
$this->termInfoIteratorFields($this->index_name,
$this->word_key);
if ($this->batch_offset != 0) {
$this->loadGenerationBatch(0);
}
$info = ($this->direction == self::ASCENDING) ?
$this->dictionary_info[0] : $this->dictionary_info[
$this->num_generations - 1];
$this->current_generation = $info['PARTITION'];
$this->start_offset = 0;
$this->last_offset = $info['NUM_DOCS'] - 1;
} else {
$this->start_offset = 0;
$this->last_offset = -1;
$this->num_generations = -1;
}
if ($this->direction == self::ASCENDING) {
$this->current_offset = $this->start_offset;
$this->generation_pointer = 0;
} else {
$this->current_offset = $this->last_offset;
/* reset pointer to the number of gens, which in reverse is the
first one we want
*/
$this->generation_pointer = $this->num_generations - 1;
}
$this->count_block = 0;
$this->seen_docs = 0;
$this->current_doc_offset = null;
}
/**
* termInfoIteratorFields reads the term's counts for the walk, for example
* $this->total_num_docs, from the first batch of its dictionary rows.
*
* @param string $index_name name of index to compute statistics with
* respect to
* @param string $word_key term to compute statics with respect to
*/
protected function termInfoIteratorFields($index_name, $word_key)
{
if (!empty($this->term_info_computed)) {
return;
}
$word_info = $this->loadGenerationBatch(0, $index_name, $word_key);
$this->total_num_docs = $word_info['TOTAL_NUM_DOCS'] ?? 0;
$this->total_num_docs_and_links =
$word_info['TOTAL_NUM_LINKS_AND_DOCS'] ?? 0;
$this->avg_items_per_partition =
$word_info['AVG_ITEMS_PER_PARTITION'] ?? C\NUM_DOCS_PER_PARTITION;
$this->total_number_of_partitions =
$word_info['TOTAL_NUMBER_OF_PARTITIONS'] ?? 0;
$this->num_docs = $word_info['TOTAL_COUNT'] ?? 0;
$this->num_occurrences = $word_info['TOTAL_OCCURRENCES'] ?? 0;
$this->threshold_exceeded = $word_info['THESHOLD_EXCEEDED'] ??
false;
$this->archive_file = $word_info['ARCHIVE_FILE'] ?? "";
$this->term_info_computed = true;
}
/**
* loadGenerationBatch reads the next generation_batch_size dictionary
* rows of this iterator's word, one row per partition holding the word,
* starting at the given position among all its rows, and makes them the
* partitions the walk steps through. termInfoIteratorFields calls it for
* the first batch, reset calls it to return to the first batch, and
* advanceGeneration calls it for the next batch when an ascending walk
* has stepped past the last row of a full one. Reading in batches keeps
* the rows held small for a common word, while a walk that goes on can
* still reach every partition the word is in. Only the first batch's
* totals are read, so only it asks for the word's whole count, which
* reads up to exact_count_partitions more rows past the batch.
*
* @param int $offset position among all the word's dictionary rows of
* the first row to read
* @param string $index_name name of the index to read, or the
* iterator's own index when left empty
* @param string $word_key the word to read rows for, or the iterator's
* own word when left empty
* @return array what IndexManager::getWordInfo gave for the batch,
* whose totals termInfoIteratorFields reads for the first batch
*/
public function loadGenerationBatch($offset, $index_name = "",
$word_key = "")
{
$read_start = microtime(true);
$word_info = IndexManager::getWordInfo(
$index_name ?: $this->index_name, $word_key ?: $this->word_key,
-1, $offset, $this->generation_batch_size, $offset == 0);
L\AnalyticsManager::addTiming("term dictionary lookups", $read_start);
/* The bundle's own MAX_ITEMS_PER_FILE, the most documents it puts in
a partition. An index made on a machine with another
MEMORY_PROFILE keeps the size it was made with, so the value is
read from the bundle, and NUM_DOCS_PER_PARTITION, the size this
machine makes, is only the fallback. */
$this->max_items_per_partition = $word_info['MAX_ITEMS_PER_FILE'] ??
C\NUM_DOCS_PER_PARTITION;
$this->dictionary_info = $word_info['ROWS'] ?? [];
/* A partition holds at most max_items_per_partition documents, so a
term cannot occur in more of a partition's documents than that. A
dictionary entry whose NUM_DOCS is larger is corrupt; left as read
it sets last_offset to a wild value and sends the posting walk
through that many nearly empty blocks, pinning the server in a
near-endless loop. Clamp each entry's count to the ceiling, which
leaves every healthy entry unchanged. */
$partition_ceiling = (int)$this->max_items_per_partition;
if ($partition_ceiling > 0) {
foreach ($this->dictionary_info as $row_index => $row) {
if (isset($row['NUM_DOCS']) &&
$row['NUM_DOCS'] > $partition_ceiling) {
$this->dictionary_info[$row_index]['NUM_DOCS'] =
$partition_ceiling;
}
}
}
$this->num_generations = count($this->dictionary_info);
$this->batch_offset = $offset;
if ($offset == 0) {
$this->walk_started = microtime(true);
$index = IndexManager::getIndex($index_name ?: $this->index_name);
$this->combined_terms = !empty(
$index->archive_info['COMBINED_TERMS'] ?? false);
}
/* getWordInfo gives the active partition's row only with a
word's last batch, so a batch holding it is the last one,
even where that row makes the batch full. */
$active_partition = ($word_info['TOTAL_NUMBER_OF_PARTITIONS'] ??
0) - 1;
$holds_active = in_array($active_partition,
array_column($this->dictionary_info, 'PARTITION'));
$this->batch_full = ($this->direction == self::ASCENDING &&
!$holds_active &&
$this->num_generations >= $this->generation_batch_size &&
($this->combined_terms || microtime(true) - $this->walk_started <
C\OLD_INDEX_BATCH_SECONDS));
if ($offset == 0) {
$this->empty = ($this->num_generations == 0);
}
return $word_info;
}
/**
* findDocsWithWord reads the next block of the term's documents, with
* their relevance and rank. currentDocsWithWord calls it when the
* block is not already read, and UnionIterator calls it itself.
*
* @return mixed doc ids and score if there are docs left, -1 otherwise
*/
public function findDocsWithWord()
{
if ($this->empty) {
return -1;
}
$ascending = ($this->direction == self::ASCENDING);
if ($ascending) {
/* The last partition of a full batch is not the word's last
partition, so a walk that has read past it goes on to the
next batch rather than stopping. */
if ($this->batch_full &&
$this->generation_pointer == $this->num_generations - 1 &&
$this->current_offset > $this->last_offset) {
$this->advanceGeneration();
}
if (($this->generation_pointer >= $this->num_generations) ||
$this->generation_pointer == $this->num_generations - 1 &&
$this->current_offset > $this->last_offset) {
return -1;
}
} else {
if (($this->generation_pointer < 0)
|| ($this->generation_pointer == 0 &&
$this->current_offset < $this->start_offset)) {
return -1;
}
}
$pre_results = [];
if (!$this->empty) {
$pre_results = $this->getPostingsSliceResults();
}
$results = [];
$doc_key_len = self::KEY_LEN;
foreach ($pre_results as $keys => $data) {
$host_key = substr($keys, self::HOST_KEY_POS, self::KEY_LEN);
if (!empty($this->filter) && $this->filter->isFiltered($host_key)) {
continue;
}
// inlinks is the domain of the inlink
$key_parts = str_split($keys, $doc_key_len);
$data[self::KEY] = $keys;
if (isset($key_parts[2])) {
list(, $data[self::HASH], $data[self::INLINKS]) =
$key_parts;
} else {
continue;
}
$data[self::CRAWL_TIME] = $this->index_name;
$results[$keys] = $data;
}
$this->count_block = count($results);
if ($this->generation_pointer == $this->num_generations - 1 &&
empty($pre_results) && !$this->batch_full) {
$results = -1;
}
$this->pages = $results;
return $results;
}
/**
* getPostingsSliceResults reads up to results_per_block postings of the
* term from the current partition, starting at current_offset and going
* the walk's way, and sets next_offset past them.
*
* @return array list of posting docs read from the index for the
* current slice; empty array when the iterator has walked past
* either end of the posting list
*/
public function getPostingsSliceResults()
{
$this->next_offset = $this->current_offset;
if ($this->direction == self::ASCENDING) {
if ($this->current_offset < $this->start_offset) {
$this->current_offset = $this->start_offset;
$this->next_offset = $this->current_offset;
}
if ($this->next_offset > $this->last_offset) {
return [];
}
$start_slice = $this->next_offset;
$num_slice = min($this->results_per_block,
$this->last_offset - $this->next_offset + 1);
$this->next_offset += $num_slice;
} else {
if ($this->current_offset > $this->last_offset) {
$this->current_offset = $this->last_offset;
$this->next_offset = $this->current_offset;
}
if ($this->next_offset < $this->start_offset) {
return [];
}
/* The block goes down from next_offset, so it holds the
postings left down to start_offset at most. */
$num_slice = min($this->results_per_block,
$this->next_offset - $this->start_offset + 1);
$this->next_offset -= $num_slice;
$start_slice = $this->next_offset + 1;
}
$postings = $this->getGenerationPostings($this->generation_pointer);
$postings = array_slice($postings, $start_slice, $num_slice);
$key_postings = $this->getDocKeyPositionsScoringInfo($postings,
$this->current_generation);
return $key_postings;
}
/**
* getPositionsFile opens the positions file of a partition folder.
*
* @param string $base_folder of index folder
* @return array [file handle, file size]
*/
public function getPositionsFile($base_folder)
{
$positions_filename = $base_folder . "/" .
IndexDocumentBundle::POSITIONS_FILENAME;
if (file_exists($positions_filename)) {
$fh = fopen($positions_filename, "r");
$file_size = filesize($positions_filename);
} else {
$fh = false;
$file_size = 0;
}
return [$fh, $file_size];
}
/**
* getPositionsList reads the positions in its document of the term one
* posting points to.
*
* @param array $posting of positions entry
* @param int $positions_file_size of positions file
* @param resource $positions_fh of positions file
* @return array of positions
*/
public function getPositionsList($posting,
$positions_file_size, $positions_fh)
{
if ($posting['POSITIONS_LEN'] > 0 &&
$posting['POSITIONS_LEN'] < $positions_file_size &&
!empty($positions_fh)) {
if ($posting['POSITIONS_LEN'] > C\MAX_POSTING_READ_LEN) {
L\crawlLog("getPositionsList: positions length " .
$posting['POSITIONS_LEN'] . " exceeds the maximum " .
"readable posting length " . C\MAX_POSTING_READ_LEN .
"; treating the entry as corrupt and skipping the read");
$position_list = [];
} else if (fseek($positions_fh,
$posting['POSITIONS_OFFSET']) >= 0) {
$encoded_positions = fread($positions_fh,
$posting['POSITIONS_LEN']);
$position_list = L\decodePositionList(
$encoded_positions, $posting['FREQUENCY']);
} else {
$position_list = [];
}
} else {
$position_list = [];
}
return $position_list;
}
/**
* getDocKeyPositionsScoringInfo fills in, for postings read from one
* partition, each document's key, positions of the term, rank and
* relevance, from the partition's positions file and document map.
*
* @param array $postings posting data to add scoring information to
* @param int $partition which partition from the PartitionDocumentBundle
* postings a re related to
* @return array $postings augmented with KEY/POSITION_LIST/SCORE/
* PROXIMITY values pulled from the position list file and
* doc_map for the given partition
*/
public function getDocKeyPositionsScoringInfo($postings, $partition)
{
$key_postings = [];
$read_start = microtime(true);
/* A union reads one posting at a time, so this is called many
times in a row for the same partition. The index, its positions
file and its number of documents are kept from the first call. */
if (($this->scoring_partition[0] ?? -1) !== $partition) {
if (!empty($this->scoring_partition[1])) {
fclose($this->scoring_partition[1]);
}
$this->scoring_partition = [];
$index = IndexManager::getIndex($this->index_name);
$base_folder = $index->getPartitionBaseFolder($partition);
$doc_map_filename = $base_folder . "/" .
IndexDocumentBundle::DOC_MAP_FILENAME;
list($fh, $file_size) = $this->getPositionsFile($base_folder);
$read_start = L\AnalyticsManager::addTiming(
"positions files opened", $read_start);
/* The document map's marks give its number of entries without
reading the map itself. */
$num_doc_keys = max(1,
$index->docMapMarks($doc_map_filename)[1] ?? 0);
$read_start = L\AnalyticsManager::addTiming(
"document maps loaded", $read_start);
$this->scoring_partition = [$partition, $fh, $file_size,
$num_doc_keys, $index];
}
[, $fh, $file_size, $num_doc_keys, $index] =
$this->scoring_partition;
$doc_map_tools = $index->doc_map_tools;
$number_of_partitions = $this->total_number_of_partitions;
/* The signal shares change only as partitions are added, so one
read serves the whole query. */
if (!isset($this->ranking_factors["SIGNAL_SHARES"])) {
$this->ranking_factors["SIGNAL_SHARES"] =
method_exists($index, "signalShares") ?
$index->signalShares() : [];
L\AnalyticsManager::addTiming("signal shares read", $read_start);
}
$is_ascending = ($this->direction == self::ASCENDING);
$num_seen_partitions = ($is_ascending) ?
$partition + 1 : $number_of_partitions - $partition;
$occurrences_per_doc = $this->num_occurrences /
max($this->total_num_docs, 1);
foreach ($postings as $posting) {
$posting[self::GENERATION] = $partition;
$read_start = microtime(true);
$posting[self::POSITION_LIST] = $this->getPositionsList($posting,
$file_size, $fh);
$read_start = L\AnalyticsManager::addTiming("positions reads",
$read_start);
$doc_map_index = $posting['DOC_MAP_INDEX'];
$entry = $index->docMapEntry($partition, $doc_map_index);
L\AnalyticsManager::addTiming("document map reads", $read_start);
$docid_len = IndexDocumentBundle::DOCID_LEN;
$termsfilter_len = IndexDocumentBundle::TERMSFILTER_LEN;
if (strlen($entry) < $docid_len) {
continue;
}
$doc_key = substr($entry, 0, $docid_len);
$is_text = IndexDocumentBundle::isType($doc_key, "text");
/*
For backward compatibility: only check for the latest
crawled version of a page if $entry[24] == 't'
(the beginning character of the term bloom
filter string attached to doc_map entries).
*/
$values = (strlen($entry) >= ($docid_len + $termsfilter_len + 1) &&
$entry[$docid_len] == 't') ?
substr($entry, $docid_len + $termsfilter_len + 1) :
substr($entry, $docid_len);
/* Whether a newer copy of the page replaces this one is
settled by GroupIterator::computeOutPages, for the pages
that reach the results only. It needs the word this posting
was found for, to check the newer copy still holds it. */
if ($this->retrieve_latest && $entry[$docid_len] == 't' &&
$is_text) {
$posting[self::TERM_KEY] = $this->word_key;
}
if (IndexDocumentBundle::isType($doc_key, "doc")) {
$posting[self::IS_DOC] = true;
}
$doc_info = $doc_map_tools->unpack($values);
if (empty($doc_info)) {
continue;
}
$time = time();
$posting[self::KEY] = $doc_key;
list($posting[self::DOC_LEN], $original_score) =
array_values(array_shift($doc_info));
$is_timestamp_score = ($original_score <= $time &&
$original_score > ($time >> 1));
/*
DOC_RANK calculate is a computes a document quality measure
either based on time item was added (freshness) or a
sum of signals (how early or late it was added to index),
whether the url was a CLD or HOST, whether page was a wiki
page, and the number of slashes in the url path
*/
if ($is_timestamp_score) {
$posting[self::DOC_RANK] = $time /
(max(1, $time - $original_score)) *
5;
} else {
$posting[self::DOC_RANK] = $this->computeDocRank($doc_key,
$doc_map_index, $num_seen_partitions, $number_of_partitions,
$num_doc_keys, $this->avg_items_per_partition,
$this->max_items_per_partition,
$this->ranking_factors, $is_ascending);
}
list($preface_positions, $num_description_scores) =
array_values(array_shift($doc_info));
$num_description_scores = intval($num_description_scores);
$posting["PATH_KEYWORDS_END_POS"] = ($preface_positions & 255);
$preface_positions = $preface_positions >> 8;
$posting["TITLE_END_POS"] = ($preface_positions & 255);
$preface_positions = $preface_positions >> 8;
$posting["HOST_KEYWORDS_END_POS"] = ($preface_positions & 255);
$posting[self::DESCRIPTION_SCORES] = array_slice($doc_info, 0,
$num_description_scores);
if ($posting['FREQUENCY'] > 0) {
list($bonuses, $frequency) =
$this->frequencyScoring(
$occurrences_per_doc,
$posting[self::POSITION_LIST],
$posting[self::DOC_LEN],
$posting["HOST_KEYWORDS_END_POS"],
$posting["TITLE_END_POS"],
$posting["PATH_KEYWORDS_END_POS"],
$posting[self::DESCRIPTION_SCORES]);
$posting[self::RELEVANCE] = self::divergenceScore(
$occurrences_per_doc, $bonuses + $frequency);
} else {
/*
this will typically be the relaveance score for a meta word
As will always be frequency 1 and have no position info
set close to 0. (Not zero to avoid div by 0's)
*/
$posting[self::RELEVANCE] = self::NO_POSITIONS_RELEVANCE;
}
$posting[self::SCORE] = $posting[self::DOC_RANK] +
$posting[self::RELEVANCE];
$posting[self::USER_RANKS] = array_slice($doc_info,
$num_description_scores);
$key_postings[$doc_key] = $posting;
}
return $key_postings;
}
/**
* fieldRelevance gives the relevance this iterator's key, a word's
* field key, gives a page, worked out from the posting of the same
* word's other key for that page. The index files a page under the
* field key when the word's first position comes before the end of the
* page's host, title and path words, and the field posting points at
* the same position list. So the relevance is the one
* getDocKeyPositionsScoringInfo would give the field posting: the same
* position list and document map values, scored with this key's own
* expected occurrences per document. UnionIterator::findDocsWithWord
* calls it for the pages a block already holds, in place of reading
* the field key's postings.
*
* @param array $posting a page's posting for the word's other key, as
* getDocKeyPositionsScoringInfo filled it in
* @return mixed the relevance, or null if the page is not filed under
* this key
*/
public function fieldRelevance($posting)
{
$position_list = $posting[self::POSITION_LIST] ?? [];
if (empty($position_list) || $position_list[0] >=
($posting["PATH_KEYWORDS_END_POS"] ?? 0)) {
return null;
}
if (($posting['FREQUENCY'] ?? 0) <= 0) {
return self::NO_POSITIONS_RELEVANCE;
}
$occurrences_per_doc = $this->num_occurrences /
max($this->total_num_docs, 1);
list($bonuses, $frequency) = $this->frequencyScoring(
$occurrences_per_doc, $position_list, $posting[self::DOC_LEN],
$posting["HOST_KEYWORDS_END_POS"], $posting["TITLE_END_POS"],
$posting["PATH_KEYWORDS_END_POS"],
$posting[self::DESCRIPTION_SCORES]);
return self::divergenceScore($occurrences_per_doc,
$bonuses + $frequency);
}
/**
* divergenceScore scores how far a term's frequency in one document is
* from what chance would put there, with Amati and van Rijsbergen's
* Bose-Einstein divergence-from-randomness model and Laplace
* after-effect: (log2(1 + o) + T * log2(1 + 1/o)) / (T + 1), where o is
* the term's expected occurrences per document in the index and T its
* frequency in this document. As in BM25F and its divergence form PL2F,
* T sums the term's frequency in each field of the document, the host
* keywords, the title, the path keywords and the body, each times its
* field's weight, before the one score is taken, so each field counts
* as more or fewer copies of the term rather than as a separate score.
* getDocKeyPositionsScoringInfo calls it with the sum of the two parts
* frequencyScoring gives.
*
* @param float $occurrences_per_doc expected occurrences of the term per
* document in the index
* @param float $field_frequency the term's weighted frequency summed
* over the document's fields
* @return float the score
*/
public static function divergenceScore($occurrences_per_doc,
$field_frequency)
{
$nonzero_occurrences_per_doc = ($occurrences_per_doc > 0) ?
$occurrences_per_doc : 1;
return (log(1 + $occurrences_per_doc, 2) + $field_frequency *
log(1 + 1 / $nonzero_occurrences_per_doc, 2)) /
($field_frequency + 1);
}
/**
* frequencyScoring works out a term's weighted frequency in a document,
* weighted by the part of the document each occurrence is in and by
* the document's length. It also adds up the host keyword, title and
* path keyword bonuses of the occurrences in those parts.
*
* @param float $occurrences_per_doc expected number of occurrence of term
* per/doc.
* @param array $positions positions of this iterators term in the document
* @param int $num_words number of terms in the document
* @param int $host_keywords_end_pos term offset into the document summary
* that demarks the end of the host keywords portion of the summary
* @param int $title_end_pos absolute term offset into the document summary
* that demarks the end of the title portion of the summary
* @param int $path_keywords_end_pos absolute term offset into the document
* summary that demarks the end of the title portion of the summary
* @param array $descriptions_scores boundaries and scores of different
* regions with document
* @return array [score for host title path keywords bonuses, frequency]
*/
public function frequencyScoring(
$occurrences_per_doc, $positions, $num_words, $host_keywords_end_pos,
$title_end_pos, $path_keywords_end_pos, $descriptions_scores)
{
$num_words = max($num_words, 1);
/*
* Amati and van Rijsbergen suggest a normalization of
* log_2(1 + l_avg/l_d) for divergence-from-randomness
* Here l_avg = average num words in a document, l_d = num words
* current document. C\MAX_DESCRIPTION_LEN is the max number
* of characters in a document. Assuming the average word is
* around 5 chars + whitespace char + punctuation, and most documents
* are summarized to close to the max character length, we
* approximate l_avg as C\MAX_DESCRIPTION_LEN/7 in the below.
*/
$pseudo_doc_length = 7 * $num_words;
$length_normalization = log(1 + C\MAX_DESCRIPTION_LEN/(7 * $num_words),
2);
if (empty($descriptions_scores)) {
/*
No per-section description scores were supplied,
so there's nothing to compute section-overlap
bonuses against; fall back to count-of-positions
* length-normalization as the frequency signal
and zero out the bonuses. Returning a 2-element
tuple here matches the contract above so the
caller's list() destructure works.
*/
return [0, count($positions) * $length_normalization];
}
$host_bonus = $this->ranking_factors["HOST_KEYWORD_BONUS"];
$path_bonus = $this->ranking_factors["PATH_KEYWORD_BONUS"];
$title_bonus = $this->ranking_factors["TITLE_BONUS"];
$len_term = strlen($this->word_key);
$first_index = 0;
$old_pos = 0;
/*
Sum of description scores without bonus scores we add below
is 1. So with the scores we add below is $max_doc_norm_score.
The foreach loop that follows measures what fraction of this
comes from $this->word_key occurrences, so will be a number
less than $max_doc_norm_score;
*/
$descriptions_scores = array_merge(
[['POS' => - $path_keywords_end_pos - 1,
'SCORE' => $host_bonus],
['POS' => $host_keywords_end_pos - $path_keywords_end_pos - 1,
'SCORE' => $title_bonus],
['POS' => $title_end_pos - $path_keywords_end_pos - 1,
'SCORE' => $path_bonus],
], $descriptions_scores);
$num_scores = count($descriptions_scores);
$weighted_frequency = 0;
$bonuses = 0;
foreach ($positions as $position) {
$last_index = $num_scores - 1;
/* description score offsets are with respect to the description
only so we subtract from the term position the offset of the
non-description
*/
$position -= ($path_keywords_end_pos + 1);
while ($first_index < $last_index) {
$mid_index = ceil(($first_index + $last_index)/2.0);
if ($descriptions_scores[$mid_index]['POS'] > $position) {
$last_index = $mid_index - 1;
} else {
$first_index = $mid_index;
}
}
$weight = $descriptions_scores[$first_index]['SCORE'];
$start_description_pos = $descriptions_scores[$first_index]['POS'];
$len_description = max(abs(($first_index == $num_scores - 1) ?
$pseudo_doc_length - $start_description_pos :
$descriptions_scores[$first_index + 1]['POS'] -
$start_description_pos), $len_term, 1);
$frequency_term = $weight * $len_term / $len_description;
if ($position <= 0) {
$bonuses += $weight; //$frequency_term;
} else {
$weighted_frequency += $frequency_term;
}
}
$frequency = $weighted_frequency * $length_normalization;
return [$bonuses, $frequency];
}
/**
* advanceSeenDocs moves next_offset past the block that starts at
* current_offset and adds the block's postings to seen_docs, as advance
* does before it moves on. A block read with currentDocsWithWord is
* counted as read. Otherwise, as when UnionIterator calls
* findDocsWithWord itself, the block is up to results_per_block of the
* postings left from current_offset to the end of the partition's list.
* They are counted from current_offset, where the block starts, since
* findDocsWithWord has already moved next_offset past it.
*/
public function advanceSeenDocs()
{
if ($this->current_block_fresh != true) {
if ($this->direction == self::ASCENDING) {
$remaining_postings = $this->last_offset -
$this->current_offset + 1;
$num_docs = min($this->results_per_block, $remaining_postings);
$delta_sign = 1;
} else {
$remaining_postings = $this->current_offset -
$this->start_offset + 1;
$num_docs = min($this->results_per_block,
$remaining_postings);
$delta_sign = -1;
}
$this->next_offset = $this->current_offset;
$this->next_offset += $delta_sign * $num_docs;
if ($num_docs <= 0) {
return;
}
} else {
$num_docs = $this->count_block;
}
$this->current_block_fresh = false;
$this->seen_docs += $num_docs;
}
/**
* advance moves the walk on by one block of documents, or to the first
* document at or past a given partition and document offset.
*
* @param array $gen_doc_offset a generation, doc_offset pair. If not null,
* (in the ascending search case opposite for descending), the pair
* must be of greater than or equal generation, and if equal the
* next block must all have $doc_offsets larger than or equal to
* this value.
*/
public function advance($gen_doc_offset = null)
{
if ($gen_doc_offset == null) {
$this->plainAdvance();
return;
}
$is_ascending = ($this->direction == self::ASCENDING);
$cur_gen_doc_offset = $this->currentGenDocOffsetWithWord();
if ($cur_gen_doc_offset == -1 ||
$this->genDocOffsetCmp($cur_gen_doc_offset,
$gen_doc_offset, $this->direction) >= 0) {
return;
}
$advance_check = ($is_ascending) ?
($this->current_generation < $gen_doc_offset[0]) :
($this->current_generation > $gen_doc_offset[0]);
if ($advance_check) {
$this->advanceGeneration($gen_doc_offset[0]);
$this->next_offset = $this->current_offset;
}
if ($this->current_generation == $gen_doc_offset[0]) {
$offset_pair = $this->nextDocIndexOffsetPair(
$gen_doc_offset[1]);
if ($offset_pair === false) {
$this->advanceGeneration();
$this->next_offset = $this->current_offset;
} else {
list($this->current_offset, $this->current_doc_offset) =
$offset_pair;
$this->next_offset = $this->current_offset;
}
}
if ($is_ascending) {
$this->seen_docs = ($this->current_offset - $this->start_offset);
} else {
$this->seen_docs = ($this->last_offset - $this->current_offset);
}
$this->current_block_fresh = false;
}
/**
* nextDocIndexOffsetPair finds, in the current partition, the first
* posting whose document comes after $doc_offset, and gives that
* posting's index and its document's index.
*
* @param int $doc_offset that we are try to find a posting whose
* doc_index has a bigger doc_offset
* @return array [posting_slice_offset, $doc_index]
*/
public function nextDocIndexOffsetPair($doc_offset)
{
$is_ascending = ($this->direction == self::ASCENDING);
$end_offset = ($is_ascending)? $this->last_offset : $this->start_offset;
$postings = $this->getGenerationPostings($this->generation_pointer);
if (empty($postings[$end_offset]) ) {
return false;
}
$last_doc = $postings[$end_offset]["DOC_MAP_INDEX"];
if (($is_ascending && $last_doc < $doc_offset) ||
(!$is_ascending && $last_doc > $doc_offset)) {
return false;
}
$next_offset = ($this->next_offset ?? $this->current_offset);
$last_offset = $next_offset;
$next_doc = $postings[$next_offset]["DOC_MAP_INDEX"] ?? $doc_offset;
$cmp = ($is_ascending) ?
($next_doc < $doc_offset && $next_offset <= $end_offset):
($next_doc > $doc_offset && $next_offset >= $end_offset);
$delta = ($is_ascending) ? 1 : -1;
while ($cmp) {
$last_offset = $next_offset;
$next_offset += $delta;
$delta *= 2;
$next_doc = $postings[$next_offset]["DOC_MAP_INDEX"] ?? $doc_offset;
$cmp = ($is_ascending) ?
($next_doc < $doc_offset && $next_offset <= $end_offset):
($next_doc > $doc_offset && $next_offset >= $end_offset);
}
if (($is_ascending && $next_offset > $end_offset) ||
(!$is_ascending && $next_offset < $end_offset)) {
$next_offset = $end_offset;
}
while(abs($next_offset - $last_offset) > 1) {
$mid_offset = ($next_offset + $last_offset) >> 1;
$mid_doc = $postings[$mid_offset]["DOC_MAP_INDEX"];
$cmp = ($is_ascending) ?
($mid_doc < $doc_offset) : ($mid_doc > $doc_offset);
if ($cmp) {
$last_offset = $mid_offset;
} else {
$next_offset = $mid_offset;
$next_doc = $mid_doc;
}
}
if (abs($next_offset - $last_offset) == 1) {
$next_doc = $postings[$next_offset]["DOC_MAP_INDEX"];
}
return [$next_offset, $next_doc];
}
/**
* plainAdvance moves the walk on by one block of documents, as advance
* does when it is not given an offset to reach.
*/
public function plainAdvance()
{
$is_ascending = ($this->direction == self::ASCENDING);
$this->advanceSeenDocs();
$this->current_doc_offset = null;
$update_check = ($is_ascending) ?
($this->current_offset < $this->next_offset) :
($this->current_offset > $this->next_offset);
if ($update_check) {
$this->current_offset = $this->next_offset;
$update_check = ($is_ascending) ?
($this->current_offset > $this->last_offset) :
($this->current_offset < $this->start_offset);
if ($update_check) {
$this->advanceGeneration();
$this->next_offset = $this->current_offset;
}
} else {
$this->advanceGeneration();
$this->next_offset = $this->current_offset;
}
}
/**
* advanceGeneration moves the walk to the next partition that holds the
* term, reading the next batch of dictionary rows when the current
* batch runs out.
*
* @param int $generation generation to advance beyond
*/
public function advanceGeneration($generation = null)
{
if ($generation === null) {
$generation = $this->current_generation;
}
$this->generation_pointer ??= 0; //if not set set to 0
$is_ascending = ($this->direction == self::ASCENDING);
do {
$gen_check = ($is_ascending) ?
($this->generation_pointer < $this->num_generations) :
($this->generation_pointer >= 0);
if ($gen_check) {
if ($is_ascending) {
$this->generation_pointer++;
} else {
$this->generation_pointer--;
}
}
if ($this->batch_full &&
$this->generation_pointer >= $this->num_generations) {
$this->loadGenerationBatch($this->batch_offset +
$this->num_generations);
$this->generation_pointer = 0;
}
$gen_check = ($is_ascending) ?
$this->generation_pointer < $this->num_generations :
$this->generation_pointer >= 0;
if ($gen_check) {
$partition_info =
$this->dictionary_info[$this->generation_pointer];
$this->current_generation = $partition_info['PARTITION'];
/* The document index kept from the last partition says
nothing about this one. Left in place, it would report
the walk as further into this partition than it is, and
an intersection would skip this partition's documents
below it. It is read again from the postings when next
asked for. */
$this->current_doc_offset = null;
$this->start_offset = 0;
$this->last_offset = ($partition_info['NUM_DOCS'] ?? 1) - 1;
$this->current_offset = ($is_ascending) ? $this->start_offset:
$this->last_offset;
}
$gen_check = ($is_ascending) ?
($this->current_generation < $generation &&
$this->generation_pointer < $this->num_generations) :
($this->current_generation > $generation &&
$this->generation_pointer >= 0);
} while($gen_check);
}
/**
* getGenerationPostings reads all the term's postings in one partition
* of the index's PartitionDocumentBundle.
*
* @param int $generation partition to get postings for
* @return array of posting items
*/
public function getGenerationPostings($generation)
{
static $test_time = 0;
if (empty($this->dictionary_info[$generation])) {
return [];
}
$generation_info = $this->dictionary_info[$generation];
if (!empty($generation_info['POSTINGS']) &&
is_array($generation_info['POSTINGS'])) {
return $generation_info['POSTINGS']; //already loaded
}
$index = IndexManager::getIndex($this->index_name);
if (empty($generation_info['POSTINGS_OFFSET']) ||
empty($generation_info['POSTINGS_LEN'])) {
$postings_entry = "";
} else {
$read_start = microtime(true);
$postings_entry = $index->getPostingsString(
$generation_info['PARTITION'],
$generation_info['POSTINGS_OFFSET'],
$generation_info['POSTINGS_LEN'], $this->word_key ?? "");
L\AnalyticsManager::addTiming("postings reads", $read_start);
}
$postings = [];
if (!empty($postings_entry)) {
$postings_info = $index->unpackPostings($postings_entry);
if (!empty($postings_info)) {
list($postings,) = $postings_info;
}
}
$this->dictionary_info[$generation]['POSTINGS'] = $postings;
return $postings;
}
/**
* currentGenDocOffsetWithWord gives the partition and document offset of
* the next document the walk would give back.
*
* @return mixed an array with the desired document offset
* and generation; -1 on fail
*/
public function currentGenDocOffsetWithWord()
{
if ($this->current_doc_offset !== null) {
return [$this->current_generation, $this->current_doc_offset];
}
$is_ascending = ($this->direction == self::ASCENDING);
$offset_check = ($is_ascending) ?
($this->current_offset > $this->last_offset ||
$this->generation_pointer >= $this->num_generations) :
($this->current_offset < $this->start_offset||
$this->generation_pointer < -1);
if ($offset_check ||
empty($this->dictionary_info[$this->generation_pointer])) {
return -1;
} else {
$partition_info = $this->dictionary_info[$this->generation_pointer];
$this->current_generation = $partition_info['PARTITION'];
$postings = $this->getGenerationPostings($this->generation_pointer);
$this->current_doc_offset =
$postings[$this->current_offset]['DOC_MAP_INDEX'] ?? -1;
}
return [$this->current_generation, $this->current_doc_offset];
}
}
- Yioop Repo - Seekquarry