<?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\storage_formats;
use seekquarry\yioop\library as L;
use seekquarry\yioop\configs as C;
use seekquarry\yioop\library\CrawlConstants;
use seekquarry\yioop\library\CrawlDaemon;
use seekquarry\yioop\library\data_structures\PersistentStructure;
/**
* Load charCopy
*/
require_once __DIR__ . "/../Utility.php";
/**
* Data structure used to store one generation worth of the word document
* index (inverted index). This data structure consists of three main
* components a word entries, word_doc entries, and document entries.
*
* Word entries are described in the documentation for the words field.
* Word-doc entries are described in the documentation for the word_docs field
* Document entries are described in the documentation for the doc_infos field
*
* IndexShards also have two access modes a $read_only_from_disk mode and
* a loaded in memory mode. Loaded in memory mode is mainly for writing new
* data to the shard. When in memory, data in the shard can also be in one of
* two states packed or unpacked. Roughly, when it is in a packed state it is
* ready to be serialized to disk; when it is an unpacked state it methods
* for adding data can be used.
*
* Serialized on disk, a shard has a header with document statistics followed
* by the a prefix index into the words component, followed by the word
* component itself, then the word-docs component, and finally the document
* component.
*
* @author Chris Pollett
*/
class IndexShard extends PersistentStructure implements CrawlConstants
{
/**
* Fraction of NUM_DOCS_PER_PARTITION document inserts before data
* from the words array is flattened to word_postings. (It will
* also be flattened during periodic index saves)
*/
const FLATTEN_FREQUENCY = 10000;
/**
* Bytes of tmp string allowed during flattenings
*/
const WORD_POSTING_COPY_LEN = 32000;
/**
* Used to keep track of whether a record in document infos is for a
* document or for a link
*/
const LINK_FLAG = 0x800000;
/**
* Shard block size is 1<< this power
*/
const SHARD_BLOCK_POWER = 12;
/**
* Size in bytes of one block in IndexShard
*/
const SHARD_BLOCK_SIZE = 4096;
/**
* Header Length of an IndexShard (sum of its non-variable length fields)
*/
const HEADER_LENGTH = 40;
/**
* Length of the data portion of a word entry in bytes in the shard
*/
const WORD_DATA_LEN = 12;
/**
* Length of a word entry's key in bytes
*/
const WORD_KEY_LEN = 20;
/**
* Length of a key in a DOC ID.
*/
const DOC_KEY_LEN = 8;
/**
* Length of DOC ID.
*/
const DOC_ID_LEN = 24;
/**
* Maximum number of auxiliary document keys;
*/
const MAX_AUX_DOC_KEYS = 200;
/**
* Length of one posting ( a doc offset occurrence pair) in a posting list
*/
const POSTING_LEN = 4;
/**
* Represents an empty prefix item
*/
const BLANK = "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF";
/**
* Flag used to indicate that a word item should not be packed or unpacked
*/
const HALF_BLANK = "\xFF\xFF\xFF\xFF";
/**
* Represents an empty prefix item
*/
const STORE_FLAG = "\x80";
/**
* BM25F weight factor for terms in title
*/
const TITLE_WEIGHT = 4.0;
/**
* BM25F weight factor for terms in description
*/
const DESCRIPTION_WEIGHT = 2.0;
/**
* BM25F weight factor for terms in a link
*/
const LINK_WEIGHT = 1.0;
/**
* Stores document id's and links to documents id's together with
* summary offset information, and number of words in the doc/link
* The format for a record is 4 byte offset, followed by
* 3 bytes for the document length, followed by 1 byte containing
* the number of 8 byte doc key strings that make up the doc id (2 for
* a doc, 3 for a link), followed by the doc key strings themselves.
* In the case of a document the first doc key string has a hash of the
* url, the second a hash a tag stripped version of the document.
* In the case of a link, the keys are a unique identifier for the link
* context, followed by 8 bytes for
* the hash of the url being pointed to by the link, followed by 8
* bytes for the hash of "info:url_pointed_to_by_link".
* @var string
*/
public $doc_infos;
/**
* Length of $doc_infos as a string
* @var int
*/
public $docids_len;
/**
* This string is non-empty when shard is loaded and in its packed state.
* It consists of a sequence of posting records. Each posting
* consists of a offset into the document entries structure
* for a document containing the word this is the posting for,
* as well as the number of occurrences of that word in that document.
* @var string
*/
public $word_docs;
/**
* Length of $word_docs as a string
* @var int
*/
public $word_docs_len;
/**
* Stores the array of word entries for this shard
* In the packed state, word entries consist of the word id,
* a generation number, an offset into the word_docs structure
* where the posting list for that word begins,
* and a length of this posting list. In the unpacked state
* each entry is a string of all the posting items for that word
* Periodically data in this words array is flattened to the word_postings
* string which is a more memory efficient was of storing data in PHP
* @var array
*/
public $words;
/**
* Stores length of the words array in the shard on disk. Only set if
* we're in $read_only_from_disk mode
*
* @var int
*/
public $words_len;
/**
* An array representing offsets into the words dictionary of the index of
* the first occurrence of a two byte prefix of a word_id.
*
* @var array
*/
public $prefixes;
/**
* Length of the prefix index into the dictionary of the shard
*
* @var int
*/
public $prefixes_len;
/**
* Number of documents (not links) stored in this shard
* @var int
*/
public $num_docs;
/**
* Keeps track of the number of documents a word is in
* @var array
*/
public $num_docs_word;
/**
* Number of links (not documents) stored in this shard
* @var int
*/
public $num_link_docs;
/**
* Number of words stored in total in all documents in this shard
* @var int
*/
public $len_all_docs;
/**
* Number of words stored in total in all links in this shard
* @var int
*/
public $len_all_link_docs;
/**
* File handle for a shard if we are going to use it in read mode
* and not completely load it.
*
* @var resource
*/
public $fh;
/**
* An cached array of disk blocks for an index shard that has not
* been completely loaded into memory.
* @var array
*/
public $blocks;
/**
* Keeps track of the packed/unpacked state of the word_docs list
*
* @var bool
*/
public $word_docs_packed;
/**
* Keeps track of the length of the shard as a file
*
* @var int
*/
public $file_len;
/**
* Number of document inserts since the last time word data was flattened
* to the word_postings string.
* @var int
*/
public $last_flattened_words_count;
/**
* Used to hold word_id, posting_len, posting triples as a memory efficient
* string
* @var string
*/
public $word_postings;
/**
* Used to hold the computed 8 byte hash of the index shard filename
* @var string
*/
public $hash_name;
/**
* Stores $blocks contents in (32 bit) unsigned int
* @var array
*/
public $blocks_words;
/**
* Holds offset of the word_docs strings
* @var int
*/
public $word_doc_offset;
/**
* Holds offset of the doc_infos strings
* @var int
*/
public $doc_info_offset;
/**
* Makes an index shard with the given file name and generation offset
*
* @param string $fname filename to store the index shard with
* @param int $generation when returning documents from the shard
* pretend there are this many earlier documents (the number
* of earlier shards, prior to the current shard)
* @param int $num_docs_per_generation the number of documents
* that a given shard can hold
* @param bool $read_only_from_disk used to determine if this
* shard is going to be largely kept on disk and to be in
* read only mode; otherwise, shard will assume to be
* completely held in memory and be read/writable
*/
public function __construct($fname, public $generation = 0,
public $num_docs_per_generation = C\NUM_DOCS_PER_PARTITION,
public $read_only_from_disk = false)
{
parent::__construct($fname, -1);
$this->hash_name = L\crawlHash($fname);
$this->word_docs = "";
$this->word_postings = "";
$this->words_len = 0;
$this->word_docs_len = 0;
$this->last_flattened_words_count = 0;
$this->words = [];
$this->docids_len = 0;
$this->doc_infos = "";
$this->num_docs = 0;
$this->num_link_docs = 0;
$this->len_all_docs = 0;
$this->len_all_link_docs = 0;
$this->blocks = [];
$this->fh = null;
$this->word_docs_packed = false;
$this->blocks_words= [];
}
/**
* Used to pack a list of description scores and user ranks as a
* string of auxiliary keys for a document map entry in the shard.
* A document map entry consists of a four byte offset into a WebArchive,
* three more bytes for the document length as, one byte for the
* number of 8 byte aux keys, followed by a 24 byte key derived usually
* from the url, host, etc, followed by the description scores,
* user rank auxiliary keys.
*
* @param array $description_scores pairs position in document =>
* weight score that position got during summarization process.
* @param array $user_ranks float scores gotten by a user classifier/ranker
* defined using Manage Classfiers.
* @return string a string padded to length a multiple of 16 where
* @see packValues has been used to map each of the above array into a
* string
*/
public function packAuxiliaryDocumentKeys($description_scores = [],
$user_ranks = [])
{
$max_short = 2<<16 - 1;
$aux_keys = "";
$num_description_scores = count($description_scores);
$num_ranks = count($user_ranks);
if ($num_description_scores + $num_ranks > self::MAX_AUX_DOC_KEYS) {
return $aux_keys;
}
$description_positions = ($num_description_scores > 0) ?
L\deltaList(array_keys($description_scores)) : [];
if ($num_description_scores > 0 && max($description_positions) <
$max_short) {
$aux_keys = "\xFF\xFF" . $this->packValues($description_positions) .
$this->packValues($description_scores, "f");
}
if ($num_ranks > 0) {
$aux_keys .= $this->packValues($user_ranks, "f");
}
$pad_len = 8 - (strlen($aux_keys) % 8);
$padding = str_pad("", $pad_len, "\x00");
return $aux_keys . $padding;
}
/**
* Used to pack either an array of nonnegative ints each less than
* 65535 or array of floats. Pack is done into a string of 2 bytes/
* entry shorts.
* @param array $values nonnegative integers or floats to pack
* @param string $type if is "i" then assuming integers we are packing
* otherwise floats
* @return string with packed values
*/
public function packValues($values, $type = "i")
{
$num_values = count($values);
if ($type == "i") {
array_unshift($values, $num_values);
array_unshift($values, "S*");
return call_user_func_array("pack", $values);
}
$max_short = 2<<16 - 1;
$max_minus_one = $max_short - 1;
$packed_values = pack("S", $num_values);
foreach ($values as $key => $value) {
$short_value = floor($value * $max_short);
if ($short_value > $max_minus_one) {
$short_value = $max_minus_one;
}
$packed_values .= pack("S", $short_value);
}
return $packed_values;
}
/**
* Add a new document to the index shard with the given summary offset.
* Associate with this document the supplied list of words and word counts.
* Finally, associate the given meta words with this document.
*
* @param string $doc_keys a string of concatenated keys for a document
* to insert. Each key is assumed to be a string of DOC_KEY_LEN many
* bytes. This whole set of keys is viewed as fixing one document.
* @param int $summary_offset its offset into the word archive the
* document's data is stored in
* @param array $word_lists (word => array of word positions in doc)
* @param array $meta_ids meta words to be associated with the document
* an example meta word would be filetype:pdf for a PDF document.
* @param bool $is_doc flag used to indicate if what is being scored is
* a document or a link to a document
* @param mixed $rank either false if not used, or a 4 bit estimate of the
* rank of this document item
* @param array $description_scores per-position importance weights
* for the description text (map position -> 0..15 score) used
* for boosting summary terms in scoring
* @param array $user_ranks per-classifier rank contributions
* (map classifier_label -> 0..15 score) appended to the
* auxiliary doc-key block
* @return bool success or failure of performing the add
*/
public function addDocumentWords($doc_keys, $summary_offset, $word_lists,
$meta_ids = [], $is_doc = false, $rank = false,
$description_scores = [], $user_ranks = [])
{
if ($this->word_docs_packed == true) {
$this->words = [];
$this->word_docs = "";
$this->word_docs_packed = false;
}
$doc_len = 0;
$link_doc_len = 0;
$doc_keys .= $this->packAuxiliaryDocumentKeys($description_scores,
$user_ranks);
$len_key = strlen($doc_keys);
$num_keys = floor($len_key/self::DOC_KEY_LEN);
if ($num_keys * self::DOC_KEY_LEN != $len_key) {
return false;
}
if ($num_keys % 2 == 0 ) {
$doc_keys .= self::BLANK; //want to keep docids_len divisible by 16
}
$summary_offset_string = L\packInt($summary_offset);
$added_len = strlen($summary_offset_string);
$this->doc_infos .= $summary_offset_string;
if ($is_doc) {
$this->num_docs++;
} else { //link item
$this->num_link_docs++;
}
foreach ($meta_ids as $meta_id) {
$word_lists[$meta_id] = [];
}
//using $this->docids_len divisible by 16
$doc_offset = $this->docids_len >> 4;
foreach ($word_lists as $word => $position_list) {
$word_id = L\crawlHashWord($word, true);
$occurrences = count($position_list);
$store = L\packPosting($doc_offset, $position_list);
if (!isset($this->words[$word_id])) {
$this->words[$word_id] = $store;
} else {
$this->words[$word_id] .= $store;
}
if (!isset($this->num_docs_word[$word_id])) {
$this->num_docs_word[$word_id] = 1;
} else {
$this->num_docs_word[$word_id]++;
}
if ($occurrences > 0) {
if ($is_doc == true) {
$doc_len += $occurrences;
} else {
$link_doc_len += $occurrences;
}
}
$this->word_docs_len += strlen($store);
}
$this->len_all_docs += $doc_len;
$this->len_all_link_docs += $link_doc_len;
$flags = ($is_doc) ? 0 : self::LINK_FLAG;
if ($rank !== false) {
$rank &= 0x0f;
$rank <<= 19;
$flags += $rank;
}
$item_len = ($is_doc) ? $doc_len: $link_doc_len;
$len_num_keys = (L\packInt(((($flags + $item_len)) << 8) + $num_keys));
$this->doc_infos .= $len_num_keys;
$added_len += strlen($len_num_keys);
$this->doc_infos .= $doc_keys;
$added_len += strlen($doc_keys);
$this->docids_len += $added_len;
return true;
}
/**
* Returns the first offset, last offset, and number of documents the
* word occurred in for this shard. The first offset (similarly, the last
* offset) is the byte offset into the word_docs string of the first
* (last) record involving that word.
*
* @param string $word_id id of the word one wants to look up
* @param bool $raw whether the id is our version of base64 encoded or not
* @return array first offset, last offset, count, exact matching id
*/
public function getWordInfo($word_id, $raw = false)
{
if ($raw == false) {
//get rid of out modified base64 encoding
$word_id = L\unbase64Hash($word_id);
}
$is_disk = $this->read_only_from_disk;
$word_item_len = self::WORD_KEY_LEN + self::WORD_DATA_LEN;
$word_key_len = self::WORD_KEY_LEN;
if ($is_disk) {
$this->readShardHeader();
if (!isset($word_id[1])) {
return false;
}
$prefix = (ord($word_id[0]) << 8) + ord($word_id[1]);
$prefix_info = $this->getShardSubstring(
self::HEADER_LENGTH + 8 * $prefix, 8);
if ($prefix_info == self::BLANK || !isset($prefix_info[2])) {
return false;
}
list(,$offset, $high) = unpack("N*", $prefix_info);
$high--;
$start = self::HEADER_LENGTH + $this->prefixes_len + $offset;
} else {
if ($this->word_docs_packed == false) {
$this->mergeWordPostingsToString();
$this->packWords(null);
$this->outputPostingLists();
}
$start = 0;
$high = (strlen($this->words) - $word_item_len)/$word_item_len;
}
$low = 0;
$check_loc = (($low + $high) >> 1);
do {
$old_check_loc = $check_loc;
$word_string = $this->getWordString($is_disk, $start, $check_loc,
$word_item_len);
if ($word_string == false) {
return false;
}
$id = substr($word_string, 0, $word_key_len);
$cmp = L\compareWordHashes($word_id, $id);
if ($cmp === 0) {
$tmp_info = $this->getWordInfoFromString(
substr($word_string, $word_key_len));
$tmp_info[] = $id;
return $tmp_info;
} else if ($cmp < 0) {
$high = $check_loc;
$check_loc = (($low + $check_loc) >> 1);
} else {
if ($check_loc + 1 == $high) {
$check_loc++;
}
$low = $check_loc;
$check_loc = (($high + $check_loc) >> 1);
}
} while($old_check_loc != $check_loc);
return false;
}
/**
* Return word record (word key + posting lookup data )from the shard
* from the shard posting list
*
* @param bool $is_disk whether the shard is on disk or in memory
* @param int $start offset to start of the dictionary
* @param int $location index of record to extract from dictionary
* @param int $word_item_len length of a word + data record
* @return string the word-key-plus-posting-lookup record at the given
* slot, read from disk or from the in-memory dictionary
*/
function getWordString($is_disk, $start, $location, $word_item_len)
{
if ($is_disk) {
$word_string = $this->getShardSubstring($start +
$location * $word_item_len, $word_item_len);
} else {
$word_string = substr($this->words, $start +
$location * $word_item_len, $word_item_len);
}
return $word_string;
}
/**
* Used to flatten the words associative array to a more memory
* efficient word_postings string.
*
* $this->words is an associative array with associations
* wordid => postinglistforid
* this format is relatively wasteful of memory
*
* $this->word_postings is a string in the format
* wordid1len1postings1wordid2len2postings2 ...
* wordids are lex ordered. This is more memory efficient as the
* former relies on the more wasteful php implementation of associative
* arrays.
*
* mergeWordPostingsToString converts the former format to the latter
* for each of the current wordids. $this->words is then set to [];
* Note before this operation is done $this->word_postings might have
* data from earlier times mergeWordPostingsToString was called, in which
* case the behavior is controlled by $replace.
*
* @param bool $replace whether to overwrite existing word_id postings
* (true) or to append (false)
*/
public function mergeWordPostingsToString($replace = false)
{
if ($this->word_docs_packed) {
return;
}
L\crawlLog("Merge index shard postings to string to save memory.");
ksort($this->words, SORT_STRING);
$tmp_string = "";
$offset = 0;
$write_offset = 0;
$len = strlen($this->word_postings);
$key_len = self::WORD_KEY_LEN;
$posting_len = self::POSTING_LEN;
$item_len = $key_len + $posting_len;
$num_words = count($this->words);
$i = 0;
foreach ($this->words as $word_id => $postings) {
$cmp = -1;
while($cmp < 0 && $offset + $item_len <= $len) {
L\crawlTimeoutLog("..merging index word postings to string ..".
" processing %s of %s at offset %s less than %s", $i,
$num_words, $offset, $len);
$key = substr($this->word_postings, $offset, $key_len);
$pack_key_posts_len = substr(
$this->word_postings, $offset + $key_len, $posting_len);
$key_posts_len = L\unpackInt($pack_key_posts_len);
$key_postings = substr($this->word_postings,
$offset + $item_len, $key_posts_len);
$word_id_posts_len = strlen($postings);
$cmp = strcmp($key, $word_id);
if ($cmp == 0) {
if ($replace) {
$tmp_string .= $key .
L\packInt($word_id_posts_len) . $postings;
} else {
$tmp_string .= $key .
L\packInt($key_posts_len + $word_id_posts_len) .
$key_postings . $postings;
$offset += $item_len + $key_posts_len;
}
} else if ($cmp < 0) {
$tmp_string .= $key .$pack_key_posts_len. $key_postings;
$offset += $item_len + $key_posts_len;
} else {
$tmp_string .= $word_id .
L\packInt($word_id_posts_len). $postings;
}
$tmp_len = strlen($tmp_string);
$copy_data_len = min(self::WORD_POSTING_COPY_LEN, $tmp_len);
$copy_to_len = min($offset - $write_offset,
$len - $write_offset);
if ($copy_to_len > $copy_data_len &&
$tmp_len > $copy_data_len) {
L\charCopy($tmp_string, $this->word_postings, $write_offset,
$copy_data_len, "merge index charCopy 1");
$write_offset += $copy_data_len;
$tmp_string = substr($tmp_string, $copy_data_len);
}
}
L\crawlTimeoutLog("..outer loop merge index postings to string ..".
" processing %s of %s.", $i, $num_words);
if ($offset + $item_len > $len) {
$word_id_posts_len = strlen($postings);
if ($write_offset < $len) {
$tmp_len = strlen($tmp_string);
$copy_data_len = $len - $write_offset;
if ($tmp_len < $copy_data_len) {//this case shouldn't occur
$this->word_postings =
substr($this->word_postings, 0, $write_offset);
$this->word_postings .= $tmp_string;
} else {
L\charCopy($tmp_string, $this->word_postings,
$write_offset, $copy_data_len,
"merge index charCopy 2");
$tmp_string = substr($tmp_string, $copy_data_len);
$this->word_postings .= $tmp_string;
}
$tmp_string = "";
$write_offset = $len;
}
$this->word_postings .=
$word_id . L\packInt($word_id_posts_len). $postings;
}
$i++;
}
L\crawlLog("..Merge Index Posting Final Copy");
$this->words = [];
// garbage collection may take a while, call with true so don't time out
CrawlDaemon::processHandler(true);
if ($tmp_string != "") {
L\crawlLog("..Merge Index Posting Final Copy 1 ".
"Current Memory: ". memory_get_usage());
$tmp_string .= substr($this->word_postings, $offset);
L\crawlLog("..Merge Index Posting Final Copy 2 ".
"Current Memory: ". memory_get_usage());
$this->word_postings = substr($this->word_postings, 0,
$write_offset);
L\crawlLog("..Merge Index Posting Final Copy 3 ".
"Current Memory: ". memory_get_usage());
$this->word_postings .= $tmp_string;
}
$this->last_flattened_words_count = $this->num_docs;
L\crawlLog("..Done Merge Index Posting Final Copy");
}
/**
* Save the IndexShard to its filename
*
* @param bool $to_string whether output should be written to a string
* rather than the default file location
* @param bool $with_logging whether log messages should be written
* as the shard save progresses
* @return string serialized shard if output was to string else empty
* string
*/
public function save($to_string = false, $with_logging = false)
{
$out = "";
$this->mergeWordPostingsToString();
if ($with_logging) {
L\crawlLog("Saving index shard .. done merge postings to string");
}
$this->prepareWordsAndPrefixes($with_logging);
if ($with_logging) {
L\crawlLog("Saving index shard .. make prefixes");
}
$header = pack("N*", $this->prefixes_len,
$this->words_len,
$this->word_docs_len,
$this->docids_len,
$this->generation,
$this->num_docs_per_generation,
$this->num_docs,
$this->num_link_docs,
$this->len_all_docs,
$this->len_all_link_docs);
if ($with_logging) {
L\crawlLog("Saving index shard .. packed header");
}
if ($to_string) {
$out = $header;
$this->packWords(null);
$out .= $this->words;
$this->outputPostingLists(null, $with_logging);
$out .= $this->word_docs;
$out .= $this->doc_infos;
} else {
$fh = fopen($this->filename, "wb");
fwrite($fh, $header);
fwrite($fh, $this->prefixes);
$this->packWords($fh, $with_logging);
if ($with_logging) {
L\crawlLog("Saving index shard .. wrote dictionary");
}
$this->outputPostingLists($fh, $with_logging);
if ($with_logging) {
L\crawlLog("Saving index shard .. wrote postings lists");
}
fwrite($fh, $this->doc_infos);
fclose($fh);
}
if ($with_logging) {
L\crawlLog("Saving index shard .. wrote doc map. Done save");
}
// clean up by returning to state where could add more docs
$this->words = [];
$this->word_docs = "";
$this->prefixes = "";
$this->word_docs_packed = false;
return $out;
}
/**
* This method re-saves a saved shard without the prefixes and dictionary.
* It would typically be called after this information has been stored
* in an IndexDictionary obbject so that the data is not redundantly stored
* @param bool $with_logging whether log messages should be written
* as the shard save progresses
*/
public function saveWithoutDictionary($with_logging = false)
{
$this->readShardHeader(true);
if ($with_logging) {
L\crawlLog(
"Opening without dictionary version of shard to write...");
}
$fh = fopen($this->filename . "-tmp", "wb");
$header = pack("N*", 0, 0,
$this->word_docs_len,
$this->docids_len,
$this->generation,
$this->num_docs_per_generation,
$this->num_docs,
$this->num_link_docs,
$this->len_all_docs,
$this->len_all_link_docs);
fwrite($fh, $header);
if ($with_logging) {
L\crawlLog("..without dictionary version of shard header written");
}
if (!$this->read_only_from_disk) {
$this->packWords(null, $with_logging);
}
$remaining = $this->word_docs_len;
$offset = 0;
$buffer_size = 16 * self::SHARD_BLOCK_SIZE;
while ($remaining > 0) {
$len = min($remaining, $buffer_size);
$data = $this->getWordDocsSubstring($offset, $len, false);
fwrite($fh, $data);
$offset += $len;
$remaining -= $len;
}
if ($with_logging) {
L\crawlLog(
"..without dictionary version of shard word docs written");
}
$remaining = $this->docids_len;
$offset = 0;
while ($remaining > 0) {
$len = min($remaining, $buffer_size);
$data = $this->getDocInfoSubstring($offset, $len, false);
fwrite($fh, $data);
$offset += $len;
$remaining -= $len;
}
if ($with_logging) {
L\crawlLog(
"..without dictionary version of shard doc infos written");
}
fclose($fh);
if (file_exists($this->filename . "-tmp")) {
if (!empty($this->fh)) {
fclose($this->fh);
}
unlink($this->filename);
rename($this->filename . "-tmp", $this->filename);
}
if ($with_logging) {
L\crawlLog("done replacing version of shard.");
}
}
/**
* Computes the prefix string index for the current words array.
* This index gives offsets of the first occurrences of the lead two char's
* of a word_id in the words array. This method assumes that the word
* data is already in >word_postings
* @param bool $with_logging whether log messages should be written
* as progresses
*/
public function prepareWordsAndPrefixes($with_logging = false)
{
$word_item_len = IndexShard::WORD_KEY_LEN + IndexShard::WORD_DATA_LEN;
$key_len = self::WORD_KEY_LEN;
$posting_len = self::POSTING_LEN;
$this->words_len = 0;
$word_postings_len = strlen($this->word_postings);
$pos = 0;
$tmp = [];
$offset = 0;
$num_words = 0;
$old_prefix = false;
while($pos < $word_postings_len) {
if ($with_logging) {
L\crawlTimeoutLog("..Outputting to position %s of" .
" %s of prefixes.", $pos, $word_postings_len);
}
$this->words_len += $word_item_len;
$first = substr($this->word_postings, $pos, $key_len);
$post_len = L\unpackInt(substr($this->word_postings,
$pos + $key_len, $posting_len));
$pos += $key_len + $posting_len + $post_len;
$prefix = (ord($first[0]) << 8) + ord($first[1]);
if ($old_prefix === $prefix) {
$num_words++;
} else {
if ($old_prefix !== false) {
$tmp[$old_prefix] = pack("N*", $offset, $num_words);
$offset += $num_words * $word_item_len;
}
$old_prefix = $prefix;
$num_words = 1;
}
}
$tmp[$old_prefix] = pack("N*", $offset, $num_words);
$num_prefixes = 2 << 16;
$this->prefixes = "";
for ($i = 0; $i < $num_prefixes; $i++) {
if (isset($tmp[$i])) {
$this->prefixes .= $tmp[$i];
} else {
$this->prefixes .= self::BLANK;
}
}
$this->prefixes_len = strlen($this->prefixes);
}
/**
* Posting lists are initially stored associated with a word as a key
* value pair. The merge operation then merges them these to a string
* by word_postings. packWords separates words from postings.
* After being applied words is a string consisting of
* triples (as concatenated strings) word_id, start_offset, end_offset.
* The offsets refer to integers offsets into a string $this->word_docs
* Finally, if a file handle is given, it writes the word dictionary out
* to the file as a long string. This function assumes
* mergeWordPostingsToString has just been called.
*
* @param resource $fh a file handle to write the dictionary to, if desired
* @param bool $with_logging whether to write progress log messages every
* 30 seconds
*/
public function packWords($fh = null, $with_logging = false)
{
if ($this->word_docs_packed) {
return;
}
$word_item_len = IndexShard::WORD_KEY_LEN + IndexShard::WORD_DATA_LEN;
$key_len = self::WORD_KEY_LEN;
$posting_len = self::POSTING_LEN;
$this->word_docs_len = 0;
$this->words = "";
$total_out = "";
$word_postings_len = strlen($this->word_postings);
$pos = 0;
$two_doc_len = 2 * self::DOC_KEY_LEN;
while($pos < $word_postings_len) {
if ($with_logging) {
L\crawlTimeoutLog("..packing index shard words at %s of %s.",
$pos, $word_postings_len);
}
$word_id = substr($this->word_postings, $pos, $key_len);
$len = L\unpackInt(substr($this->word_postings,
$pos + $key_len, $posting_len));
if (!isset($this->num_docs_word[$word_id])) {
L\crawlLog("No number count in index for " .
L\toHexString($word_id));
$this->num_docs_word[$word_id] = ($len >> 2);
}
$num_docs_word = $this->num_docs_word[$word_id];
$postings = substr($this->word_postings,
$pos + $key_len + $posting_len, $len);
$pos += $key_len + $posting_len + $len;
/*
we pack generation info to make it easier to build the global
dictionary
*/
if ($len != $two_doc_len ||
strncmp($postings, self::HALF_BLANK, self::POSTING_LEN) != 0) {
/* if len is small code count in high order half word.
In my experimentation all but a 100 or so word counts out of
all the words in 40000 or so docs can be coded in this way
*/
$orig_len = $len;
if ($len < 32767 && $num_docs_word <= $len) {
$len += ($num_docs_word << 16) + (1 << 31);
}
$out = pack("N*", $this->generation, $this->word_docs_len,
$len);
$this->word_docs_len += $orig_len;
$this->words .= $word_id . $out;
} else {
/* single occurrence case - high word blank except high bit,
low word has posting (so don't go to posting list,
operate only in dictionary)
*/
$out = substr($postings,
self::POSTING_LEN, $word_item_len);
$out[0] = chr((0x80 | ord($out[0])));
$this->words .= $word_id . $out;
}
}
if ($fh != null) {
fwrite($fh, $this->words);
}
$this->words_len = strlen($this->words);
$this->word_docs_packed = true;
}
/**
* Used to convert the word_postings string into a word_docs string
* or if a file handle is provided write out the word_docs sequence
* of postings to the provided file handle.
*
* @param resource $fh a filehandle to write to
* @param bool $with_logging whether to log progress
*/
public function outputPostingLists($fh = null, $with_logging = false)
{
$word_item_len = IndexShard::WORD_KEY_LEN + IndexShard::WORD_DATA_LEN;
$key_len = self::WORD_KEY_LEN;
$posting_len = self::POSTING_LEN;
$this->word_docs = "";
$total_out = "";
$word_postings_len = strlen($this->word_postings);
$pos = 0;
$tmp_string = "";
$tmp_len = 0;
$two_doc_len = 2 * self::DOC_KEY_LEN;
while($pos < $word_postings_len) {
if ($with_logging) {
L\crawlTimeoutLog("..Outputting to position %s of" .
" %s in posting lists.", $pos,
$word_postings_len);
}
$word_id = substr($this->word_postings, $pos, $key_len);
$len = L\unpackInt(substr($this->word_postings,
$pos + $key_len, $posting_len));
$postings = substr($this->word_postings,
$pos + $key_len + $posting_len, $len);
$pos += $key_len + $posting_len + $len;
if ($len != $two_doc_len ||
strncmp($postings, self::HALF_BLANK, self::POSTING_LEN) != 0) {
if ($fh != null) {
if ($tmp_len < self::SHARD_BLOCK_SIZE) {
$tmp_string .= $postings;
$tmp_len += $len;
} else {
fwrite($fh, $tmp_string);
$tmp_string = $postings;
$tmp_len = $len;
}
} else {
$this->word_docs .= $postings;
}
}
}
if ($tmp_len > 0) {
if ($fh == null ) {
$this->word_docs .= $tmp_string;
} else {
fwrite($fh, $tmp_string);
}
}
}
/**
* Takes the word docs string and splits it into posting lists which are
* assigned to particular words in the words dictionary array.
* This method is memory expensive as it briefly has essentially
* two copies of what's in word_docs.
*/
public function unpackWordDocs()
{
if (!$this->word_docs_packed) {
return;
}
$num_lists = count($this->words);
$cnt = 0;
foreach ($this->words as $word_id => $postings_info) {
/* we are ignoring the first four bytes which contains
generation info
*/
L\crawlTimeoutLog("..still unpacking index posting lists. At" .
" list %s of %s.", $cnt, $num_lists);
if ((ord($postings_info[0]) & 0x80) > 0 ) {
$postings_info[0] = chr(ord($postings_info[0]) - 0x80);
$postings_info = self::HALF_BLANK . $postings_info;
$this->words[$word_id] = $postings_info;
$this->num_docs_word[$word_id] = 1;
} else {
$tmp = unpack("N*", substr($postings_info, 4,
8));
if (!isset($tmp[2])) {
continue;
}
list(, $offset, $len) = $tmp;
if (($len & (1 << 31))) {
$this->num_docs_word[$word_id] = (($len >> 16) & 32767);
$len = ($len & 65535);
} else {
//only approximate assuming each posting 4 bytes
$this->num_docs_word[$word_id] = $len >> 2;
}
$postings = substr($this->word_docs, $offset, $len);
$this->words[$word_id] = $postings;
}
$cnt++;
}
unset($this->word_docs);
$this->word_docs_packed = false;
}
/**
* From disk gets $len many bytes starting from $offset in the word_docs
* strings
*
* @param $offset byte offset to begin getting data out of disk-based
* word_docs
* @param $len number of bytes to get
* @param bool $cache whether to cache disk blocks read from disk
* @return desired string
*/
public function getWordDocsSubstring($offset = 0, $len = 0, $cache = true)
{
if ($len <= 0) {
$len = $this->word_docs_len;
}
if ($this->read_only_from_disk) {
return $this->getShardSubstring($this->word_doc_offset + $offset,
$len, $cache);
}
return substr($this->word_docs, $offset, $len);
}
/**
* From disk gets $len many bytes starting from $offset in the doc_infos
* strings
*
* @param $offset byte offset to begin getting data out of disk-based
* doc_infos
* @param $len number of bytes to get
* @param bool $cache whether to cache disk blocks read from disk
* @return string desired
*/
public function getDocInfoSubstring($offset = 0, $len = 0, $cache = false)
{
if ($len <= 0) {
$len = $this->docids_len;
}
if ($this->read_only_from_disk) {
return $this->getShardSubstring(
$this->doc_info_offset + $offset, $len, $cache);
}
return substr($this->doc_infos, $offset, $len);
}
/**
* Gets from Disk Data $len many bytes beginning at $offset from the
* current IndexShard
*
* @param int $offset byte offset to start reading from
* @param int $len number of bytes to read
* @param bool $cache whether to cache disk blocks read from disk
* @return string data from that location in the shard
*/
public function getShardSubstring($offset, $len, $cache = true)
{
$block_offset = ($offset >> self::SHARD_BLOCK_POWER)
<< self::SHARD_BLOCK_POWER;
$start_loc = $offset - $block_offset;
//if all in one block do it quickly
if ($start_loc + $len < self::SHARD_BLOCK_SIZE) {
return substr($this->readBlockShardAtOffset($block_offset, $cache),
$start_loc, $len);
}
// otherwise, this loop is slower, but handles general case
$data = $this->readBlockShardAtOffset($block_offset, $cache);
if ($data === false) {
return "";
}
$substring = substr($data, $start_loc);
$block_size = self::SHARD_BLOCK_SIZE;
$block_offset += $block_size;
while (strlen($substring) < $len) {
$data = $this->readBlockShardAtOffset($block_offset, $cache);
if ($data === false) {
return $substring;
}
$block_offset += $block_size;
$substring .= $data;
}
return substr($substring, 0, $len);
}
/**
* Reads SHARD_BLOCK_SIZE from the current IndexShard's file beginning
* at byte offset $bytes
*
* @param int $bytes byte offset to start reading from
* @param bool $cache whether to cache disk blocks that have been read to
* RAM
* @return mixed data fromIndexShard file if found, false otherwise
*/
public function readBlockShardAtOffset($bytes, $cache = true)
{
if (isset($this->blocks[$bytes]) && $cache) {
return $this->blocks[$bytes];
}
if ($this->fh === null) {
if (!file_exists($this->filename)) {
return false;
}
$this->fh = fopen($this->filename, "rb");
if ($this->fh === false) {
return false;
}
$this->file_len = filesize($this->filename);
}
if ($bytes >= $this->file_len) {
return false;
}
$seek = fseek($this->fh, $bytes, SEEK_SET);
if ($seek < 0) {
return false;
}
if (!$cache) {
return fread($this->fh, self::SHARD_BLOCK_SIZE);
}
if (count($this->blocks) > self::SHARD_BLOCK_SIZE) {
$this->blocks = [];
$this->blocks_words = [];
}
$this->blocks[$bytes] = fread($this->fh, self::SHARD_BLOCK_SIZE);
$tmp = & $this->blocks[$bytes];
$this->blocks_words += array_combine(
range($bytes, $bytes + strlen($tmp) - 1, 4),
unpack("N*", $tmp));
return $tmp;
}
/**
* If not already loaded, reads in from disk the fixed-length'd field
* variables of this IndexShard ($this->words_len, etc)
* @param bool $force If true
* @return bool whether was able to read in or not
*/
public function readShardHeader($force = false)
{
if (!empty($this->num_docs) && $this->num_docs > 0 && !$force) {
return true; // if $this->num_docs > 0 assume have read in
}
$header = substr($this->readBlockShardAtOffset(0, false),
0, self::HEADER_LENGTH);
if (!$header) {
return false;
}
self::headerToShardFields($header, $this);
$this->doc_info_offset = $this->file_len - $this->docids_len;
return true;
}
/**
* Converts $str into 3 ints for a first offset into word_docs,
* a last offset into word_docs, and a count of number of docs
* with that word.
*
* @param string $str 12 or 16-byte packed binary string read out
* of a dictionary entry
* @param bool $include_generation when true the generation number
* is prepended to the returned tuple (used by callers that
* walk a posting list across generations); when false (default)
* only the three offset/len/count ints are returned
* @return array of these three or four int's
*/
public static function getWordInfoFromString($str,
$include_generation = false)
{
list(, $generation, $first_offset, $len) = unpack("N*", $str);
$orig = $len;
if (($len & (1 << 31))) {
$count = (($len >> 16) & 32767);
$len = ($len & 65535);
} else {
$count = $len >> 2;
}
$last_offset = $first_offset + $len - self::POSTING_LEN;
if ($include_generation) {
return [$generation, $first_offset, $last_offset, $count];
}
return [$first_offset, $last_offset, $count];
}
/**
* Load an IndexShard from a file or string
*
* @param string $fname the name of the file to the IndexShard from/to
* @param string &$data stringified shard data to load shard from. If null
* then the data is loaded from the $fname if possible
* @return IndexShard the IndexShard loaded
*/
public static function load($fname, &$data = null)
{
L\crawlLog("Loading index shard $fname");
$shard = new IndexShard($fname);
if ($data === null) {
$fh = fopen($fname, "rb");
$shard->file_len = filesize($fname);
$header = fread($fh, self::HEADER_LENGTH);
} else {
$shard->file_len = strlen($data);
$header = substr($data, 0, self::HEADER_LENGTH);
$pos = self::HEADER_LENGTH;
}
self::headerToShardFields($header, $shard);
L\crawlLog("..done reading index shard header");
if ($data === null) {
if (!($shard->prefixes_len > 0 ) || !($shard->words_len > 0 ) ||
!($shard->word_docs_len > 0 )|| !($shard->docids_len > 0 ) ) {
fclose($fh);
return null;
}
fread($fh, $shard->prefixes_len);
$words = fread($fh, $shard->words_len);
$shard->word_docs = fread($fh, $shard->word_docs_len);
$shard->doc_infos = fread($fh, $shard->docids_len);
fclose($fh);
} else {
$words = substr($data, $pos, $shard->words_len);
$pos += $shard->words_len;
$shard->word_docs = substr($data, $pos, $shard->word_docs_len);
$pos += $shard->word_docs_len;
$shard->doc_infos = substr($data, $pos, $shard->docids_len);
}
$pre_words_array = str_split($words, self::WORD_KEY_LEN +
self::WORD_DATA_LEN);
unset($words);
$make_words = C\NS_LIB . 'storage_formats\\IndexShard::makeWords';
array_walk($pre_words_array, $make_words,
$shard);
L\crawlLog("..done reading making index shard word structure");
$shard->word_docs_packed = true;
$shard->unpackWordDocs();
L\crawlLog("..done unpacking index shard posting lists");
return $shard;
}
/**
* Split a header string into a shards field variable
*
* @param string $header a string with packed shard header data
* @param object $shard IndexShard to put data into
*/
public static function headerToShardFields($header, $shard)
{
list(,
$shard->prefixes_len,
$shard->words_len,
$shard->word_docs_len,
$shard->docids_len,
$shard->generation,
$shard->num_docs_per_generation,
$shard->num_docs,
$shard->num_link_docs,
$shard->len_all_docs,
$shard->len_all_link_docs
) = unpack("N*", $header);
$shard->word_doc_offset = self::HEADER_LENGTH +
$shard->prefixes_len + $shard->words_len;
}
/**
* Callback function for load method. splits a word_key . word_info string
* into an entry in the passed shard $shard->words[word_key] = $word_info.
*
* @param string &$value the word_key . word_info string
* @param int $key index in array - we don't use
* @param object $shard IndexShard to add the entry to word table for
*/
public static function makeWords(&$value, $key, $shard)
{
$shard->words[substr($value, 0, self::WORD_KEY_LEN)] =
substr($value, self::WORD_KEY_LEN,
self::WORD_DATA_LEN);
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software