404-solution / includes / spelling / SpellCandidateDistanceRanker.php

SpellCandidateDistanceRanker.php in 404 Solution trunk, at includes/spelling/SpellCandidateDistanceRanker.php

229 lines 8.7 KB

Raw Download Zip

1	<?php
2
3	if (!defined('ABSPATH')) {
4	exit;
5	}
6
7	/**
8	* Per-call accumulator that ranks candidate page IDs by approximate edit
9	* distance for the spell-checking subsystem.
10	*
11	* One instance is created for each {@see ABJ_404_Solution_SpellLevenshteinEngine::getLikelyMatchIDs()}
12	* call. The engine feeds it one candidate at a time via {@see score()}; the
13	* ranker files each candidate into min/max edit-distance buckets. Once the
14	* batch is exhausted the engine calls {@see prioritize()} to harvest the
15	* closest-matching IDs (closest distance first, IDs that share whole words
16	* with the requested URL promoted ahead of the rest).
17	*
18	* This responsibility was extracted from the engine: holding the bucket state
19	* here (rather than passing three accumulator arrays through the hot loop by
20	* reference) keeps the scoring logic independently testable and the engine's
21	* orchestration loop allocation-clean.
22	*/
23	// allow-no-test-found: behavior-identical extraction from ABJ_404_Solution_SpellLevenshteinEngine::getLikelyMatchIDs; exercised end-to-end through that path in SpellCheckerMatchingTest, SpellCheckerAlgorithmTest, SpellCheckerPrefilteringTest and the @group integration SpellCheckerLargeScaleTest. Same integration-coverage strategy as the sibling spell collaborators (SpellNGramPrefilter, SpellCandidatePermalinkLookup).
24	class ABJ_404_Solution_SpellCandidateDistanceRanker {
25
26	const MAX_DIST = 2083;
27
28	const MAX_LIKELY_DISTANCE = 300;
29
30	/** @var ABJ_404_Solution_Functions */
31	private $f;
32
33	/** @var ABJ_404_Solution_PluginLogic */
34	private $logic;
35
36	/** @var ABJ_404_Solution_Logging */
37	private $logger;
38
39	/** @var ABJ_404_Solution_SpellURLMatcher */
40	private $urlMatcher;
41
42	/** @var array<int, string> */
43	private array $separatingCharacters;
44
45	/** @var ABJ_404_Solution_SpellNGramPrefilter */
46	private $ngramPrefilter;
47
48	/** @var array<int, array<int, mixed>> candidate IDs keyed by minimum possible edit distance */
49	private array $minDistances;
50
51	/** @var array<int, array<int, mixed>> candidate IDs keyed by maximum possible edit distance */
52	private array $maxDistances;
53
54	/** @var array<int, mixed> candidate IDs that share at least one whole word with the request */
55	private array $idsWithWordsInCommon = array();
56
57	/**
58	* @param ABJ_404_Solution_SpellLevenshteinEngineDependencies $deps shared collaborator bundle
59	* @param ABJ_404_Solution_SpellNGramPrefilter $ngramPrefilter the engine's prefilter, reused for the secondary filter
60	*/
61	public function __construct(ABJ_404_Solution_SpellLevenshteinEngineDependencies $deps,
62	ABJ_404_Solution_SpellNGramPrefilter $ngramPrefilter) {
63	$this->f = $deps->functions;
64	$this->logic = $deps->logic;
65	$this->logger = $deps->logger;
66	$this->urlMatcher = $deps->urlMatcher;
67	$this->separatingCharacters = $deps->separatingCharacters;
68	$this->ngramPrefilter = $ngramPrefilter;
69
70	// Allocate the empty min/max edit-distance bucket arrays, one slot per
71	// possible distance from 0 to self::MAX_DIST inclusive.
72	$this->minDistances = array();
73	$this->maxDistances = array();
74	for ($currentDistanceIndex = 0; $currentDistanceIndex <= self::MAX_DIST; $currentDistanceIndex++) {
75	$this->maxDistances[$currentDistanceIndex] = array();
76	$this->minDistances[$currentDistanceIndex] = array();
77	}
78	}
79
80	/**
81	* Compute the min/max edit-distance bounds for one candidate URL and file
82	* its id into the distance buckets. Pure scoring: no I/O, mutates only this
83	* instance's bucket state.
84	*
85	* @param mixed $id the raw candidate id, as gathered from the row
86	* @param string $existingPageURLPath the candidate URL path (urlParts['path'])
87	* @param int $requestedURLCleanedLength
88	* @param string $fullURLspaces
89	* @param int $fullURLspacesLength
90	* @param array<int, string> $userRequestedURLWords
91	*/
92	public function score($id, string $existingPageURLPath, int $requestedURLCleanedLength,
93	string $fullURLspaces, int $fullURLspacesLength, array $userRequestedURLWords): void {
94	$existingPageURL = $this->logic->urlNormalization()->removeHomeDirectory($existingPageURLPath);
95
96	$existingPageURLSpaces = $this->f->str_replace($this->separatingCharacters, " ", $existingPageURL);
97
98	$existingPageURLCleaned = $this->urlMatcher->getLastURLPart($existingPageURLSpaces);
99	$existingPageURLSpaces = null;
100
101	$minDist = abs($this->f->strlen($existingPageURLCleaned) - $requestedURLCleanedLength);
102	if ($fullURLspaces != '') {
103	$minDist = min($minDist, abs($fullURLspacesLength - $requestedURLCleanedLength));
104	}
105	$maxDist = $this->f->strlen($existingPageURLCleaned);
106	if ($fullURLspaces != '') {
107	$maxDist = min($maxDist, $fullURLspacesLength);
108	}
109
110	$existingPageURLCleanedWords = explode(" ", $existingPageURLCleaned);
111	$wordsInCommon = array_intersect($userRequestedURLWords, $existingPageURLCleanedWords);
112	$wordsInCommon = array_merge(array_unique($wordsInCommon, SORT_REGULAR), array());
113	if (count($wordsInCommon) > 0) {
114	array_push($this->idsWithWordsInCommon, $id);
115	$lengthOfTheLongestWordInCommon = max(array_map(array($this->f,'strlen'), $wordsInCommon));
116	$maxDist = $maxDist - $lengthOfTheLongestWordInCommon;
117	}
118
119	if (isset($this->minDistances[$minDist])) {
120	array_push($this->minDistances[$minDist], $id);
121	} else {
122	$this->minDistances[$minDist] = [$id];
123	}
124
125	if ($maxDist < 0) {
126	$this->logger->errorMessage("maxDist is less than 0 (" . $maxDist .
127	") for '" . $existingPageURLCleaned . "', wordsInCommon: " .
128	json_encode($wordsInCommon) . ", ");
129	$maxDist = 0;
130	} else if ($maxDist > self::MAX_DIST) {
131	$maxDist = self::MAX_DIST;
132	}
133
134	if (is_array($this->maxDistances[$maxDist])) {
135	array_push($this->maxDistances[$maxDist], $id);
136	}
137	}
138
139	/**
140	* The largest max-distance bucket index we need to scan to have seen at
141	* least $onlyNeedThisManyPages candidates, scaled up 10% for headroom.
142	* Used by the engine to bound how many more rows it pulls from the batch.
143	*
144	* @param int $onlyNeedThisManyPages
145	* @return int
146	*/
147	public function getMaxAcceptableDistance(int $onlyNeedThisManyPages): int {
148	$pagesSeenSoFar = 0;
149	$maxDistFound = self::MAX_LIKELY_DISTANCE;
150	for ($currentDistanceIndex = 0; $currentDistanceIndex <= self::MAX_LIKELY_DISTANCE; $currentDistanceIndex++) {
151	$pagesSeenSoFar += sizeof($this->maxDistances[$currentDistanceIndex]);
152
153	if ($pagesSeenSoFar >= $onlyNeedThisManyPages) {
154	$maxDistFound = $currentDistanceIndex;
155	break;
156	}
157	}
158
159	$acceptableDistance = (int)($maxDistFound * 1.1);
160	return $acceptableDistance;
161	}
162
163	/**
164	* Harvest the prioritized candidate IDs from the accumulated buckets:
165	* closest min-distance first, IDs sharing whole words promoted ahead of
166	* the rest, then the n-gram secondary filter applied.
167	*
168	* @param int $onlyNeedThisManyPages
169	* @param bool $ngramPrefilterApplied
170	* @param string $requestedURLCleaned
171	* @return array<int, mixed>
172	*/
173	public function prioritize(int $onlyNeedThisManyPages, bool $ngramPrefilterApplied,
174	string $requestedURLCleaned): array {
175	$pagesSeenSoFar = 0;
176	$maxDistFound = self::MAX_LIKELY_DISTANCE;
177	for ($currentDistanceIndex = 0; $currentDistanceIndex <= self::MAX_LIKELY_DISTANCE; $currentDistanceIndex++) {
178	$pagesSeenSoFar += sizeof($this->maxDistances[$currentDistanceIndex]);
179	if ($pagesSeenSoFar >= $onlyNeedThisManyPages) {
180	$maxDistFound = $currentDistanceIndex;
181	break;
182	}
183	}
184
185	$listOfIDsToReturn = array();
186	for ($currentDistanceIndex = 0; $currentDistanceIndex <= $maxDistFound; $currentDistanceIndex++) {
187	$listOfMinDistanceIDs = $this->minDistances[$currentDistanceIndex];
188	$listOfIDsToReturn = array_merge($listOfIDsToReturn, $listOfMinDistanceIDs);
189	}
190
191	$listOfIDsToReturn = $this->normalizeScalarIds($listOfIDsToReturn);
192	$idsWithWordsInCommon = $this->normalizeScalarIds($this->idsWithWordsInCommon);
193	$idsWithWords = array_intersect($listOfIDsToReturn, $idsWithWordsInCommon);
194	$idsWithoutWords = array_diff($listOfIDsToReturn, $idsWithWordsInCommon);
195	$listOfIDsToReturn = array_merge($idsWithWords, $idsWithoutWords);
196
197	$listOfIDsToReturn = $this->normalizeScalarIds(
198	$this->ngramPrefilter->applySecondaryFilter(
199	$listOfIDsToReturn,
200	$ngramPrefilterApplied,
201	$requestedURLCleaned
202	)
203	);
204
205	if (count($listOfIDsToReturn) > 300 && count($idsWithWordsInCommon) >= $onlyNeedThisManyPages) {
206	$maybeOKguesses = array_intersect($listOfIDsToReturn, $idsWithWordsInCommon);
207	return (count($maybeOKguesses) >= $onlyNeedThisManyPages)
208	? $maybeOKguesses : $idsWithWordsInCommon;
209	}
210	return $listOfIDsToReturn;
211	}
212
213	/**
214	* @param array<int, mixed> $ids
215	* @return array<int, int\|string>
216	*/
217	private function normalizeScalarIds(array $ids): array {
218	$normalized = array();
219	foreach ($ids as $id) {
220	if (is_int($id) \|\| is_string($id)) {
221	$normalized[] = $id;
222	} else if (is_scalar($id)) {
223	$normalized[] = (string)$id;
224	}
225	}
226	return $normalized;
227	}
228	}
229