<?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/>.
*
* @author Xianghong Sun sxh19911230@gmail.com
* @license https://www.gnu.org/licenses/ GPL3
* @link https://www.seekquarry.com/
* @copyright 2009 - 2026
* @filesource
*/
namespace seekquarry\yioop\library\language_processing;
use seekquarry\yioop\library as L;
use seekquarry\yioop\configs as C;
/**
* StochasticTermSegmenter splits text of a language written without spaces
* between words, such as Chinese, into words, by Stochastic Finite State
* Word Segmentation: of the ways to split a run of text, it picks the one
* whose words have the best total score, a word's score coming from how
* often a dictionary says it occurs.
*
* @author Xianghong Sun and Chris Pollett (tweaks to adding new language)
*/
class StochasticTermSegmenter
{
/**
* $cache_pct is the share, from 0 to 1.0, of the dictionary's sub-tries
* kept decoded in $cache. A machine short of memory should use a small
* share. Here is a comparison of setting it to 0 and to 1:
* In the test of Chinese Segmentation on pku dataset,
* the peak usage of memory is 26.288MB vs. 151.46MB
* The trade off is some efficiency,
* In the test of Chinese Segmentation on pku dataset,
* the speed is 43.803s vs. 1.540s
* Default value = 0.06
* The time and Peak Memory are 5.094s and 98.97MB
* @var number from 0 - 1.0
*/
private $cache_pct;
/**
* $cache holds the decoded sub-tries of the dictionary, one for each
* first character, most recently used first, so a word starting with
* that character is looked up without decoding its sub-trie again
* @var array
*/
private $cache = [];
/**
* $segmented_runs holds the words segmentSentence found for each run of
* text without spaces it segmented lately. Its keys are the runs. A
* fetcher segments a page's description to index it and then again,
* sentence by sentence, to find its questions and answers, so the
* second pass reads these.
* It starts over empty when it holds SEGMENTED_RUNS_KEPT runs and when
* the dictionary changes.
* @var array
*/
private $segmented_runs = [];
/**
* Most runs of text $segmented_runs holds before it starts over empty
*/
const SEGMENTED_RUNS_KEPT = 4096;
/**
* The language currently being used e.g. zh-CN, ja
* @var string
*/
public $lang;
/**
* $non_char_preg is a regular expression character class matching the
* characters of the current language, used to tell whether none of a
* term's characters are in that language. Recommended expressions:
* Chinese: \p{Han}
* Japanese: \x{4E00}-\x{9FBF}\x{3040}-\x{309F}\x{30A0}-\x{30FF}
* Korean: \x{3130}-\x{318F}\x{AC00}-\x{D7AF}
* @var string
*/
public $non_char_preg;
/**
* $unknown_term_score is the score given a term the dictionary does not
* hold, the score of a term seen once
* @var float
*/
public $unknown_term_score;
/**
* A dictionary that contains statistical information on terms for a
* language. A non-empty dictionary should have two fields:
* N, the number of terms in the dictionary; dic,
* a trie implemented using nested php arrays that implements the
* dictionary. The leaves of the trie have frequency counts for terms
* stored in the trie.
* @var array
*/
public $dictionary;
/**
* $dictionary_path is the file the segmenter's dictionary, its
* term_weights.txt.gz, is read from, and train writes to
* @var string
*/
public $dictionary_path;
/**
* Maximum character length of a term
*/
const MAX_TERM_LENGTH = 7;
/**
* MAX_JOINED_LENGTH is the most characters segmentSentence joins into
* one term when they are not in the dictionary: a run of characters not
* in the current language, a number or date, or a run of punctuation.
* Each such join checks the joined string again for every character
* added, so without a limit a run of m characters takes time that grows
* as m cubed. A longer run is cut into terms of at most this length.
*/
const MAX_JOINED_LENGTH = 64;
/**
* Holds instance of Tokenizer for $lang language
* @var object
*/
public $tokenizer;
/**
* $named_entity_tagger is $tokenizer's NamedEntityContextTagger, whose
* names of people, places and groups segmentRun scores as words
* @var object
*/
public $named_entity_tagger;
/**
* __construct makes a segmenter for the words of a locale, finding the
* locale's dictionary file and its Tokenizer, whose rules for numbers,
* dates and punctuation, and whose named entity tagger, it uses.
* @param string $lang locale this instance will do segmentation for
* @param float $cache_pct percentage of whole trie that can be
* cached for faster look-up
*/
function __construct($lang, $cache_pct = 0.06)
{
$lang = str_replace("-", "_", $lang);
$this->lang = $lang;
$this->dictionary_path = L\localeResource($lang,
"term_weights.txt.gz");
$this->cache_pct = $cache_pct;
$this->tokenizer = PhraseParser::getTokenizer($lang);
if (!is_object($this->tokenizer)) {
return;
}
/*
* To use a StocasticTermSegmenter, a locale's Tokenizer should
* implement isCardinalNumber, isOrdinalNumber, isDate,
* isPunctuation, isNotCurrentLang and optionally getNamedEntityTagger
*/
if (method_exists($this->tokenizer, "getNamedEntityTagger")) {
/*
* Named entity recognizer;
*/
$this->named_entity_tagger =
$this->tokenizer::getNamedEntityTagger();
}
}
/**
* isException says if a term is a number, an ordinal or a date, by the
* tokenizer's isCardinalNumber, isOrdinalNumber and isDate. Such terms
* are not looked up in the dictionary, since there are endless numbers
* and dates, and a tokenizer without those methods has none.
* @param string $term is a string that to be checked
* @return true if $term is an exception term, false otherwise
*/
public function isException($term)
{
if (!empty($this->tokenizer) &&
method_exists($this->tokenizer, "isCardinalNumber") &&
method_exists($this->tokenizer, "isOrdinalNumber") &&
method_exists($this->tokenizer, "isDate")) {
return $this->tokenizer::isCardinalNumber($term)
|| $this->tokenizer::isOrdinalNumber($term)
|| $this->tokenizer::isDate($term);
}
return false;
}
/**
* isPunctuation says if a term is punctuation, by the tokenizer's
* isPunctuation; with no such method nothing is punctuation.
* @param string $term is a string that to be checked
* @return true if $term is some kind of punctuation, false otherwise
*/
public function isPunctuation($term)
{
if (!empty($this->tokenizer) &&
method_exists($this->tokenizer, "isPunctuation")) {
return $this->tokenizer::isPunctuation($term);
}
return false;
}
/**
* notCurrentLang says if none of the characters of a term are in the
* current language, by the tokenizer's isNotCurrentLang
* @param string $term is a string that to be checked
* @return bool true if all the chars in $term are NOT from the current
* language false otherwise
*/
public function notCurrentLang($term)
{
if (!empty($this->tokenizer) &&
method_exists($this->tokenizer, "isNotCurrentLang")) {
return $this->tokenizer::isNotCurrentLang($term);
}
return false;
}
/**
* train makes the dictionary segmentation reads, counting each word of
* text files whose words are already split by spaces, and writes it
* to this site's own locale folder
* @param mixed $text_files is a string name or an array of files
* that to be trained; words in the files need to be segmented by space
* @param string $format currently only support default and CTB
*/
public function train($text_files, $format = "default")
{
$ctb_fmt = false;
switch ($format) {
case ("default"):
break;
case ("CTB"):
$ctb_fmt = true;
break;
default:
echo "Unrecognized format";
exit();
}
/* Training makes term weights for this site, so they are saved in
its own locale folder, never in the shipped one. */
$this->dictionary_path = C\LOCALE_DIR .
"/{$this->lang}/resources/term_weights.txt.gz";
L\makePath(dirname($this->dictionary_path));
echo "Saving file to: {$this->dictionary_path}\n";
$dictionary = [];
if (is_string($text_files)) {
$text_files = [$text_files];
}
foreach ($text_files as $text_file) {
if (file_exists($text_file) && !is_dir($text_file)) {
$fh = fopen($text_file, "r");
while(!feof($fh)) {
$line = fgets($fh);
if ($ctb_fmt and preg_match('/^<.*>$/', trim($line))) {
continue;
}
$words = preg_split("/[\s ]+/u", $line);
foreach ($words as $word) {
if (!empty($word) && !$this->isException($word) &&
!$this->notCurrentLang($word)) {
if (!empty($this->tokenizer) &&
method_exists($this->tokenizer, "normalize")) {
$word=$this->tokenizer::normalize($word);
}
if (!empty($dictionary[$word])) {
$dictionary[$word]++;
} else if (mb_strlen($word) <
self::MAX_TERM_LENGTH) {
$dictionary[$word] = 1;
}
}
}
}
fclose($fh);
}
}
$this->dictionary = [];
$this->segmented_runs = [];
$this->dictionary["N"] = 0;
$this->dictionary["dic"] = [];
ksort($dictionary);
$start_char = null;
$tmp_array = [];
foreach ($dictionary as $key => $value) {
if (mb_substr($key, 0, 1) != $start_char) {
$this->dictionary["dic"][$start_char] =
json_encode($tmp_array[$start_char] ?? []);
$tmp_array = [];
$start_char = mb_substr($key, 0, 1);
}
$this->add($key, $value, $tmp_array);
$this->dictionary["N"]++;
}
$this->unknown_term_score = $this->getScore(1);
file_put_contents($this->dictionary_path,
gzencode(json_encode($this->dictionary), 9));
}
/**
* segmentText segments each line of a text into words and gives the
* text back with its words split by spaces
* @param string $text to be segmented
* @param string $normalize return the normalized form
* 乾隆->干隆
* @return string segmented terms with space
*/
public function segmentText($text, $normalize=false)
{
$segmented_text = "";
$lines = explode("\n", $text);
foreach ($lines as $line) {
if (mb_strlen($line) > 0) {
$segmented_line = $this->segmentSentence($line);
if (!empty($segmented_line)) {
$segmented_text .= join(" ", $segmented_line) . "\n";
}
}
}
return mb_substr($segmented_text, 0, -1);
}
/**
* segmentSentence segments a sentence, which must have no new line in
* it, into an array of words. Each run of the sentence between white
* space is segmented by segmentRun, or read from $segmented_runs when
* it was segmented lately.
* @param string $sentence is a string without newline to be segmented
* @return array of segmented words
*/
public function segmentSentence($sentence)
{
$pieces = preg_split("/[\s ]+/u", trim($sentence));
if (count($pieces) > 1) {
$words = [];
foreach ($pieces as $piece) {
$segments = $this->segmentSentence($piece);
if (is_array($segments)) {
$words = array_merge($words, $segments);
}
}
return $words;
}
$run = trim($sentence);
if (isset($this->segmented_runs[$run])) {
return $this->segmented_runs[$run];
}
$words = $this->segmentRun($run);
if (is_array($words)) {
if (count($this->segmented_runs) >= self::SEGMENTED_RUNS_KEPT) {
$this->segmented_runs = [];
}
$this->segmented_runs[$run] = $words;
}
return $words;
}
/**
* segmentRun segments one run of text with no white space in it into
* words, choosing the split whose words the dictionary, the named entity
* tagger and the rules for numbers, dates, punctuation and text not in
* the current language score best.
* @param string $run text without white space to be segmented
* @return array the words of $run in order, or null when the
* dictionary file is missing
*/
private function segmentRun($run)
{
if (!$this->dictionary) {
$this->segmented_runs = [];
if (!file_exists($this->dictionary_path)) {
L\crawlLog("{$this->dictionary_path} does not exist!");
return null;
}
$this->dictionary =
json_decode(gzdecode(file_get_contents(
$this->dictionary_path)), true);
gc_collect_cycles();
$this->unknown_term_score = $this->getScore(1);
}
$cache_size =
floor(count($this->dictionary['dic']) * $this->cache_pct);
if ($cache_size == 0) {
$cache_size = 1;
}
$unnormalized = $run;
$normalized = (!empty($this->tokenizer) &&
method_exists($this->tokenizer, "normalize")) ?
$this->tokenizer::normalize($unnormalized) : $unnormalized;
$characters = preg_split('//u', $normalized, -1,
PREG_SPLIT_NO_EMPTY);
if (!count($characters)) {
return [];
}
$net_dict = [];
if (isset($this->named_entity_tagger)) {
$named_entities = $this->named_entity_tagger->predict(
$characters);
foreach ($named_entities as $entity) {
$this->add($entity[0], 1, $net_dict);
}
}
$score = [];
$path = [];
//init base
$score[-1] = 0;
for ($index = 0; $index < count($characters); $index++) {
$join_end = min(count($characters),
$index + self::MAX_JOINED_LENGTH);
//If not current language
if ($this->notCurrentLang($characters[$index]) &&
!$this->isPunctuation($characters[$index])) {
$current_char = $characters[$index];
for ($j = $index + 1; $j < $join_end; $j++) {
if ($this->notCurrentLang($current_char . $characters[$j])&&
!$this->isPunctuation($characters[$j])) {
$current_char .= $characters[$j];
} else {
break;
}
}
if (!isset($score[$j - 1]) || $score[$j - 1] >
$score[$index - 1] + $this->unknown_term_score) {
$score[$j - 1] = $score[$index - 1] +
$this->unknown_term_score;
$path[$j - 1] = $index - 1;
}
}
//If date or number
if ($this->isException($characters[$index])) {
$current_char = $characters[$index];
for ($j = $index + 1; $j < $join_end; $j++) {
if (!$this->isException(
$current_char . $characters[$j])) {
break;
}
$current_char .= $characters[$j];
}
if (!isset($score[$j - 1]) ||
$score[$j - 1] > $score[$index - 1] +
$this->unknown_term_score) {
$score[$j - 1] = $score[$index - 1] +
$this->unknown_term_score;
$path[$j - 1] = $index - 1;
}
}
//If is punctuation, give slightly better score than unknown words
if ($this->isPunctuation($characters[$index])) {
$current_char = $characters[$index];
for ($j = $index + 1; $j < $join_end; $j++) {
if (!$this->isPunctuation(
$current_char . $characters[$j])) {
break;
}
$current_char .= $characters[$j];
}
if (!isset($score[$j - 1]) ||
$score[$j - 1] > $score[$index - 1] +
$this->unknown_term_score / 1.1) {
$score[$j - 1] = $score[$index - 1] +
$this->unknown_term_score / 1.1;
$path[$j - 1] = $index - 1;
}
}
/* All case (Even not in current lang because dictionary may
contains those terms
check the first char, give score even nothing matches
*/
if (!isset($score[$index]) ||
$score[$index-1] + $this->unknown_term_score < $score[$index]) {
$score[$index] = $score[$index-1] +
$this->unknown_term_score;
$path[$index] = $index - 1;
}
//if entry exists, look for the term
if (isset($this->dictionary["dic"][$characters[$index]])) {
if (!isset($this->cache[$characters[$index]])) {
$this->cache = [$characters[$index] =>
json_decode(
$this->dictionary["dic"][$characters[$index]],
true)] + $this->cache;
while (count($this->cache) > $cache_size) {
array_pop($this->cache);
}
}
$subdic = $this->cache;
for ($j = $index; $j < count($characters); $j++) {
if (!isset($subdic[$characters[$j]])) {
break;
}
$subdic = $subdic[$characters[$j]];
if (isset($subdic['$']) && (!isset($score[$j]) ||
(isset($score[$index - 1]) && is_numeric($subdic['$'])
&& is_numeric($subdic['$']) &&
$score[$index - 1] + $subdic['$'] < $score[$j]))) {
$score[$j] = $score[$index - 1] +
$this->getScore($subdic['$']);
$path[$j] = $index - 1;
}
}
}
//Check Named Entity Tagger dictionary
if (isset($net_dict[$characters[$index]])) {
$subdic = $net_dict;
for ($j = $index; $j < count($characters); $j++) {
if (!isset($subdic[$characters[$j]])) {
break;
}
$subdic = $subdic[$characters[$j]];
if (isset($subdic['$']) && (!isset($score[$j]) ||
(isset($score[$index - 1]) &&
$score[$index - 1] + $subdic['$'] < $score[$j]))) {
$score[$j] = $score[$index - 1] +
$this->getScore($subdic['$']);
$path[$j] = $index - 1;
}
}
}
}
//trace path
$t = max(array_keys($path));
$tmp = [];
while($t != -1) {
$tmp[] = $t;
$t = $path[$t];
}
$result = [];
$t = 0;
foreach (array_reverse($tmp) as $next_node) {
$result_word = "";
while($t <= $next_node) {
$result_word .= $characters[$t];
$t++;
}
$result[] = $result_word;
}
return $result;
}
/**
* getScore gives the score of a term from how often it occurs against
* the number of terms in the dictionary, the negative log of their
* ratio, so a lower score is a likelier word.
* @param int $frequency is an integer tells the frequency of a word
* @return float the score of the term.
*/
public function getScore($frequency)
{
if (!empty($this->dictionary["N"]) &&
is_numeric($this->dictionary["N"])) {
return -log($frequency / $this->dictionary["N"]);
} else {
return 0;
}
}
/**
* Adds a (term, frequency) pair to an array based trie
*
* @param string $term the term to be inserted
* @param string $frequency the frequency to be inserted
* @param array &$trie array based trie we want to insert the key value
* pair into
*/
public function add($term, $frequency, &$trie)
{
$sub_trie = & $trie;
for ($i = 0; $i < mb_strlen($term, "utf-8"); $i++) {
$character = mb_substr($term, $i, 1, "utf-8");
$enc_char = $character;
/* a character not yet in the trie gets an empty sub-trie */
if (!isset($sub_trie[$enc_char])) {
$sub_trie[$enc_char] = [];
}
$sub_trie = &$sub_trie[$enc_char];
}
// Set end of term marker
$sub_trie['$'] = $frequency;
}
}
- Yioop Repo - Seekquarry