<?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;
use seekquarry\yioop\configs as C;
/** For Yioop global defines */
require_once __DIR__ . "/../configs/Config.php";
/**
* Makes up the pages of a web that is never fetched from the internet, so a
* crawl of any size can be run on one machine. A page's links and its words
* are worked out from the page's own number and the crawl's seed, with no
* shared state between fetchers, so any fetcher makes the same page for the
* same number and a whole run repeats exactly. SyntheticGetPages, the stand
* in for FetchUrl::getPages, calls these to build the page for each url a
* fetcher was handed.
*
* @author Chris Pollett
*/
class SyntheticWeb
{
/**
* How many bits of a hash are kept when turning it into a number in a
* range. Fifty two bits stay exact as a PHP float, so a page number
* drawn from a hash is spread evenly with no rounding surprise up to a
* few thousand million million pages.
*/
const HASH_BITS = 52;
/**
* How wide the made-up image for an image url is drawn, in pixels.
*/
const IMAGE_WIDE = 240;
/**
* How tall the made-up image for an image url is drawn, in pixels.
*/
const IMAGE_HIGH = 60;
/**
* The gray shade the made-up image is filled with before the url is
* drawn on it, from zero for black to 255 for white.
*/
const IMAGE_BACKGROUND = 220;
/**
* How far in from the top left corner, in pixels, the url is drawn on
* the made-up image.
*/
const IMAGE_MARGIN = 5;
/**
* The host every path-addressed page of a made-up web sits on. One
* host, so one robots.txt and one company level domain for the whole
* web when links vary by path.
*/
const PATH_HOST = "synth.web";
/**
* The top level domain every domain-addressed page sits under. The
* page's tuple, joined by hyphens, is the one label before it, so each
* page is its own company level domain in any number of dimensions.
*/
const DOMAIN_SUFFIX = "web";
/**
* The most digits a host label of a domain-addressed page may hold.
* Yioop rejects a host with five or more consonants or digits in a row
* as a spam domain, so a component is split into labels of four.
*/
const MAX_LABEL_DIGITS = 4;
/**
* pageTuple reads a page's coordinates out of a made-up url.
*
* A made-up page is named by a tuple of numbers. Addressed by domain
* the tuple, joined by hyphens, is the one label before the top level
* domain, http://i-j-k.web/index.html, so each page is its own company
* level domain; addressed by path it is the path under the one path
* host, http://synth.web/i/j/k/index.html.
* syntheticGetPages calls this to learn which page it was asked for,
* so it can work out that page's links and words. Any other url, a
* robots.txt or favicon above all, is not a page.
*
* @param string $url the made-up url a fetcher was handed
* @param string $graph_type "grid", "tree", or "power_law"; a power
* law page is one number, which by domain is split into hyphened
* groups of digits and is joined back here
* @return array the page's coordinates as integers, or an empty array
* where the url is not one of this web's own pages
*/
public static function pageTuple($url, $graph_type = "grid")
{
$leaf = '(?:index\.html|image\.jpg)';
if (preg_match('@^https?://' . self::PATH_HOST .
'/([0-9]+(?:/[0-9]+)*)/' . $leaf . '$@', $url, $by_path)) {
return array_map('intval', explode("/", $by_path[1]));
}
if (preg_match('@^https?://([0-9]+(?:-[0-9]+)*)\.' .
self::DOMAIN_SUFFIX . '/' . $leaf . '$@', $url, $by_domain)) {
$parts = explode("-", $by_domain[1]);
if ($graph_type == "power_law") {
return [intval(implode("", $parts))];
}
return array_map('intval', $parts);
}
return [];
}
/**
* urlForTuple builds the url of a made-up page from its coordinates.
*
* A link on a made-up page points at another page by its tuple. This
* gives that page's url, with the tuple joined by hyphens as the one
* label under the top level domain when the link varies by domain,
* http://i-j.web/index.html, so each page is its own company level
* domain, or in the path under the one path host when it varies by
* path. A number is split into groups of a few digits, since Yioop
* takes five digits in a row for a spam host.
* pageHtml uses it to write the links onto a page and seedUrl to name
* the page a crawl starts from.
*
* @param array $tuple the page's coordinates
* @param bool $by_domain true to put the tuple in the host, false to
* put it in the path
* @return string the made-up page's url
*/
public static function urlForTuple($tuple, $by_domain = false,
$leaf = "index.html")
{
if ($by_domain) {
$parts = [];
foreach ($tuple as $component) {
$parts = array_merge($parts,
str_split((string)$component, self::MAX_LABEL_DIGITS));
}
return "http://" . implode("-", $parts) . "." .
self::DOMAIN_SUFFIX . "/" . $leaf;
}
$path = ($tuple === []) ? "" : implode("/", $tuple) . "/";
return "http://" . self::PATH_HOST . "/" . $path . $leaf;
}
/**
* imageUrlForTuple gives the url of the made-up image a page links to,
* which is the page url with an image.jpg leaf in place of index.html.
* pageHtml uses it to write an image link, and isImageUrl and
* syntheticGetPages read the leaf to know a url names an image.
* @param array $tuple the image page's coordinates
* @param bool $by_domain true to put the tuple in the host
* @return string the made-up image's url
*/
public static function imageUrlForTuple($tuple, $by_domain = false)
{
return self::urlForTuple($tuple, $by_domain, "image.jpg");
}
/**
* isImageUrl says whether a made-up url names an image rather than a
* page: an image url ends in the image.jpg leaf. syntheticGetPages
* asks this to know whether to return image bytes or html.
* @param string $url a made-up url
* @return bool true where the url names an image
*/
public static function isImageUrl($url)
{
return (bool)preg_match('/\/image\.jpg$/', $url);
}
/**
* imageBytes makes the bytes of the made-up image a url names: a small
* jpeg with the url drawn on it, so a synthetic image is a real image
* a viewer and the image processor can read. syntheticGetPages returns
* these bytes for an image url, the same as a real fetch would return
* an image body. The image is drawn the same way every time for a url,
* so a re-fetch gives the same bytes.
* @param string $url the made-up image's url
* @return string the jpeg bytes of the image
*/
public static function imageBytes($url)
{
$image = imagecreatetruecolor(self::IMAGE_WIDE, self::IMAGE_HIGH);
$background = imagecolorallocate($image, self::IMAGE_BACKGROUND,
self::IMAGE_BACKGROUND, self::IMAGE_BACKGROUND);
$ink = imagecolorallocate($image, 0, 0, 0);
imagefilledrectangle($image, 0, 0, self::IMAGE_WIDE,
self::IMAGE_HIGH, $background);
imagestring($image, 2, self::IMAGE_MARGIN, self::IMAGE_MARGIN,
$url, $ink);
ob_start();
imagejpeg($image);
return ob_get_clean();
}
/**
* seedUrl names the page a made-up web is crawled from.
*
* Every graph type starts at the origin: the all-zero tuple with as
* many components as the out degree for a grid, and the single root
* component for a tree or a power law web. startCrawl calls this to
* seed a synthetic crawl.
*
* @param string $graph_type "grid", "tree", or "power_law"
* @param int $out_degree how many links each page carries
* @param float $domain_link_probability the probability that a link
* goes to another domain rather than a deeper path;
* the seed is addressed by domain when this is at least a half
* @return string the url of the first page
*/
public static function seedUrl($graph_type, $out_degree,
$domain_link_probability)
{
if ($graph_type == "grid") {
$tuple = array_fill(0, $out_degree, 0);
} else if ($graph_type == "tree") {
$tuple = [];
} else {
$tuple = [0];
}
return self::urlForTuple($tuple, $domain_link_probability >= 0.5);
}
/**
* outLinks works out the pages a made-up page links to.
*
* The graph type says the shape. A grid page with coordinates in d
* components links to the d pages one step along in each component.
* A tree page, named by its path from the root, links to its d
* children, the path with each child number appended. A power law
* page, named by one number, links to d pages drawn so low numbered
* pages gather many links and become hubs. pageHtml calls this to
* learn where a page's links go, then writes them onto the page.
*
* @param array $tuple the coordinates of the page whose links are
* wanted
* @param string $graph_type "grid", "tree", or "power_law"
* @param int $out_degree how many links the page should carry
* @param int $seed the crawl's seed, so a run repeats exactly
* @param float $power_law_exponent steepens a power law web, ignored
* by the other types
* @return array the tuples this page links to
*/
public static function outLinks($tuple, $graph_type, $out_degree,
$seed, $power_law_exponent = 2.0)
{
$links = [];
if ($graph_type == "grid") {
for ($component = 0; $component < count($tuple); $component++) {
$step = $tuple;
$step[$component]++;
$links[] = $step;
}
return $links;
}
if ($graph_type == "tree") {
for ($child = 0; $child < $out_degree; $child++) {
$links[] = array_merge($tuple, [$child]);
}
return $links;
}
$page_key = implode(".", $tuple);
for ($which = 0; $which < $out_degree; $which++) {
$unit = self::hashUnit("$seed:$page_key:$which");
$links[] = [self::skewToLowPages($unit, $power_law_exponent)];
}
return $links;
}
/**
* skewToLowPages turns an even number between zero and one into a page
* number that favours low numbered pages.
*
* A power law web has a few pages that very many others link to. Raising
* an even draw to a power above one pushes it toward zero, so the page
* numbers a link lands on pile onto the small ones. outLinks uses it for
* each link of a power law page.
*
* @param float $unit an even draw between zero and one
* @param float $exponent how steeply to favour low pages, one is even
* @return int the page number the draw lands on, within a very large
* bound so the web has no fixed size
*/
public static function skewToLowPages($unit, $exponent)
{
$bound = 1 << 30;
return (int)floor($bound * pow($unit, $exponent));
}
/**
* hashUnit turns a string into an even number between zero and one.
*
* The made-up web is worked out from hashes so it needs no stored graph
* and repeats exactly. This gives an even draw from a string, which the
* link and word choices lean on. outLinks and words call it.
*
* @param string $string what to draw a number from
* @return float an even number that is at least zero and below one
*/
public static function hashUnit($string)
{
$bytes = substr(md5($string, true), 0, 8);
$value = 0;
for ($at = 0; $at < 8; $at++) {
$value = $value * 256 + ord($bytes[$at]);
}
$top = pow(2, 64);
return $value / $top;
}
/**
* ipAddress works out the address a made-up page answers at.
*
* A real crawl resolves a url to an address; a made-up web has no DNS,
* so the address is a hash of the page's url spread across the sixteen
* bytes of an IPv6 address. Spreading a hash this wide makes two pages
* sharing an address very unlikely for crawls under a few thousand
* million pages. syntheticGetPages hands this back so the ip meta word
* is filled as it would be on a real page.
*
* @param string $url the made-up page's url
* @return string the page's address, written as an IPv6 address
*/
public static function ipAddress($url)
{
$bytes = md5($url, true);
$parts = [];
for ($at = 0; $at < 16; $at += 2) {
$parts[] = sprintf("%02x%02x", ord($bytes[$at]),
ord($bytes[$at + 1]));
}
return implode(":", $parts);
}
/**
* pageHtml builds the html body of a made-up page.
*
* A made-up page is an html page whose links are the graph's out-links
* written as anchors, so Yioop's own processing draws the same link and
* word meta words it would from a fetched page, and whose text is the
* page's made-up words. Each link is addressed by domain or by path,
* chosen by hash against the domain link probability, so the same
* page always
* chooses the same way. syntheticGetPages calls this to fill the page
* content for a url.
*
* @param array $tuple the coordinates of the page to build
* @param array $settings the crawl's synthetic settings: graph_type,
* out_degree, seed, power_law_exponent, term_exponent, doc_length,
* length_spread, domain_link_probability, image_link_probability
* @param int $timestamp the crawl the page belongs to, or zero for a
* page built with no links wired; when set, each link is wired to
* open through the synthetic activity once the page has loaded
* @return string the page's html
*/
public static function pageHtml($tuple, $settings, $timestamp = 0)
{
$seed = $settings['seed'];
$page_key = implode(".", $tuple);
$is_seed_page = (max($tuple) == 0);
$links = self::outLinks($tuple, $settings['graph_type'],
$settings['out_degree'], $seed,
$settings['power_law_exponent']);
$anchors = "";
$which = 0;
foreach ($links as $target) {
$to_domain = self::hashUnit("$seed:dom:$page_key:$which") <
$settings['domain_link_probability'];
$is_image = !$is_seed_page &&
self::hashUnit("$seed:img:$page_key:$which") <
$settings['image_link_probability'];
$target_url = self::urlForTuple($target, $to_domain);
if ($is_image) {
$image_url = self::imageUrlForTuple($target, $to_domain);
$anchors .= "<a href='$image_url'>link $which</a>\n";
} else {
$anchors .= "<a href='$target_url'>link $which</a>\n";
}
$which++;
}
$words = self::words($page_key, $seed, $settings['term_exponent'],
$settings['doc_length'], $settings['length_spread']);
$text = implode(" ", $words);
$open_script = ($timestamp > 0) ?
self::linkOpenScript(intval($timestamp)) : "";
return "<html><head><title>page $page_key</title></head><body>" .
"<p>$text</p>\n$anchors$open_script</body></html>";
}
/**
* linkOpenScript gives the script a generated page carries so that,
* once it has loaded, each of its links opens the page it names by
* building it from the crawl's seeds: a generated page has no stored
* copy of its own, so its links go straight to the synthetic activity
* rather than through the cache. The hrefs stay as the crawl saw them.
* pageHtml adds this when it is given a crawl time. A stored cached
* page uses linkScriptBody instead, whose links try the cache first.
* @param int $timestamp the crawl the page belongs to
* @return string a script element for the end of the page
*/
public static function linkOpenScript($timestamp)
{
$timestamp = intval($timestamp);
return "<script>\n" .
"for (const link of " .
"document.querySelectorAll('a[href^=\"http\"]')) {\n" .
" link.onclick = function () {\n" .
" var target = encodeURIComponent(" .
"link.getAttribute('href'));\n" .
" window.location = '?c=search&a=synthetic&its=" .
$timestamp . "&arg=' + target;\n" .
" return false;\n };\n}\n</script>";
}
/**
* linkScriptBody gives the javascript, without a script element around
* it, that wires each link on a stored cached page to open the page
* it names once the page has loaded: the search cache is tried first
* and a miss sends the reader on to the synthetic activity, which
* builds the page from the crawl's seeds. The href is left as the
* crawl saw it. The search controller puts this in a dom script node
* on a cached page of a synthetic crawl; a generated page uses
* linkOpenScript, whose links go straight to the synthetic activity.
* @param int $timestamp the crawl the page belongs to
* @return string the body of the link-wiring script
*/
public static function linkScriptBody($timestamp)
{
$timestamp = intval($timestamp);
return "for (const link of " .
"document.querySelectorAll('a[href^=\"http\"]')) {\n" .
" link.onclick = function () {\n" .
" var target = encodeURIComponent(" .
"link.getAttribute('href'));\n" .
" window.location = '?c=search&a=cache&its=" .
$timestamp . "&arg=' + target;\n" .
" return false;\n };\n}";
}
/**
* settingsFromSeedInfo reads the synthetic settings a crawl was run
* with out of its seed info into the array pageHtml takes, so a page
* can be built again with the same seeds the fetchers used. The
* search controller calls this when a made-up page is asked for.
* @param array $seed_info a crawl's seed info as CrawlModel reads it
* @return array the settings pageHtml takes, empty where the crawl
* was not a synthetic one
*/
public static function settingsFromSeedInfo($seed_info)
{
$general = $seed_info['general'] ?? [];
if (empty($general['graph_type'])) {
return [];
}
return ['graph_type' => $general['graph_type'],
'out_degree' => intval($general['out_degree'] ??
C\SYNTHETIC_OUT_DEGREE),
'seed' => intval($general['synthetic_seed'] ??
C\SYNTHETIC_SEED),
'power_law_exponent' => floatval(
$general['power_law_alpha'] ??
C\SYNTHETIC_POWER_LAW_ALPHA),
'term_exponent' => floatval($general['text_alpha'] ??
C\SYNTHETIC_TEXT_ALPHA),
'doc_length' => intval($general['doc_length'] ??
C\SYNTHETIC_DOC_LENGTH),
'length_spread' => intval($general['doc_length_sigma'] ??
C\SYNTHETIC_DOC_LENGTH_SIGMA),
'domain_link_probability' => floatval(
$general['domain_link_probability'] ??
C\SYNTHETIC_DOMAIN_LINK_PROBABILITY),
'image_link_probability' => floatval(
$general['image_link_probability'] ??
C\SYNTHETIC_IMAGE_LINK_PROBABILITY)];
}
/**
* words makes up the words on a made-up page.
*
* The words are numbered strings drawn so that a few words appear often
* and most appear rarely, the way words fall off in real writing, set by
* the term frequency exponent. How many words a page has is drawn around
* an average with a spread. syntheticGetPages calls this to fill a
* page's body.
*
* @param string $page_key the page whose words are wanted, its
* coordinates joined by dots
* @param int $seed the crawl's seed, so a run repeats exactly
* @param float $term_exponent how steeply a few words dominate, near one
* matches real writing
* @param int $average_length the average number of words on a page
* @param int $length_spread how far a page's word count may sit from the
* average
* @return array the words on the page, as numbered strings
*/
public static function words($page_key, $seed, $term_exponent,
$average_length, $length_spread)
{
$length_draw = self::hashUnit("$seed:len:$page_key");
$length = (int)round($average_length +
($length_draw * 2 - 1) * $length_spread);
if ($length < 1) {
$length = 1;
}
$vocabulary = ($average_length > 0) ? $average_length * 10 : 10;
$words = [];
for ($which = 0; $which < $length; $which++) {
$unit = self::hashUnit("$seed:word:$page_key:$which");
$rank = self::skewToLowPages($unit, $term_exponent) % $vocabulary;
$words[] = sprintf("%08d", $rank);
}
return $words;
}
}
- Yioop Repo - Seekquarry