Heim Backend-Entwicklung PHP-Tutorial 字 PHP实现Trie树(字典树)

字 PHP实现Trie树(字典树)

Jul 29, 2016 am 08:33 AM

Trie树的概念(百度的解释):字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

我的理解是用来做字符串搜索的,每个节点只包含一个字符,比如录入单词"world",则树的结构是:

 PHP实现Trie树(字典树)

这时再录入单词"worab",则树的结构为:

 PHP实现Trie树(字典树)

所以每个节点必须还要一个字段is_end标识是否为结束单词。比如用户输入wor,搜索所有wor开头的单词,假设现在有一个单词就是wor,从"w"开始检索,当检索到"r"的时候需要判断"r"节点的is_end为true,则把wor加入到结果列表,然后继续往下面检索。

PHP实现代码:

<?php class Node{

	public $value;                 // 节点值
	public $is_end = false;        // 是否为结束--是否为某个单词的结束节点
	public $childNode = array();   // 子节点
	
	/* 添加孩子节点--注意:可以不为引用函数,因为PHP对象赋值本身就是引用赋值 */
	public function &addChildNode($value, $is_end = false){
		$node = $this->searchChildNode($value);
		if(empty($node)){
			// 不存在节点,添加为子节点
			$node = new Node();
			$node->value = $value;
			$this->childNode[] = $node;
		}
		$node->is_end = $is_end;
		return $node;
	}

	/* 查询子节点 */
	public function searchChildNode($value){
		foreach ($this->childNode as $k => $v) {
			if($v->value == $value){
				// 存在节点,返回该节点
				return $this->childNode[$k];
			}
		}
		return false;
	}
}



/* 添加字符串 */
function addString(&$head, $str){
	$node = null;
	for ($i=0; $i addChildNode($str[$i], $is_end);
			}else{
				$node = $node->addChildNode($str[$i], $is_end);
			}
		}
	}
}

/* 获取所有字符串--递归 */
function getChildString($node, $str_array = array(), $str = ''){
	if($node->is_end == true){
		$str_array[] = $str;
	}
	if(empty($node->childNode)){
		return $str_array;
	}else{
		foreach ($node->childNode as $k => $v) {
			$str_array = getChildString($v, $str_array, $str . $v->value);
		}
		return $str_array;
	}
}

/* 搜索 */
function searchString($node, $str){
	for ($i=0; $i searchChildNode($str[$i]);
			// print_r($node);
			if(empty($node)){
				// 不存在返回空
				return false;
			}
		}
	}
	return getChildString($node);
}


/* 调用测试开始 */
$head = new Node;   // 树的head

// 添加单词
addString($head, 'hewol');
addString($head, 'hemy');
addString($head, 'heml');
addString($head, 'you');
addString($head, 'yo');

// 获取所有单词
$str_array = getChildString($head);

// 搜索
$search_array = searchString($head, 'hem');
// 循环打印所有搜索结果
foreach ($search_array as $key => $value) {
	echo 'hem' . $value . '<br>';  // 输出带上搜索前缀
}
Nach dem Login kopieren

以上就介绍了字 PHP实现Trie树(字典树),包括了字方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
1 Monate vor By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

11 beste PHP -URL -Shortener -Skripte (kostenlos und Premium) 11 beste PHP -URL -Shortener -Skripte (kostenlos und Premium) Mar 03, 2025 am 10:49 AM

Lange URLs, die oft mit Schlüsselwörtern und Tracking -Parametern überfüllt sind, können Besucher abschrecken. Ein URL -Verkürzungsskript bietet eine Lösung, die präzise Links erstellt, die ideal für soziale Medien und andere Plattformen sind. Diese Skripte sind für einzelne Websites a wertvoll

Arbeiten mit Flash -Sitzungsdaten in Laravel Arbeiten mit Flash -Sitzungsdaten in Laravel Mar 12, 2025 pm 05:08 PM

Laravel vereinfacht die Behandlung von temporären Sitzungsdaten mithilfe seiner intuitiven Flash -Methoden. Dies ist perfekt zum Anzeigen von kurzen Nachrichten, Warnungen oder Benachrichtigungen in Ihrer Anwendung. Die Daten bestehen nur für die nachfolgende Anfrage standardmäßig: $ Anfrage-

Erstellen Sie eine React -App mit einem Laravel -Back -Ende: Teil 2, reagieren Erstellen Sie eine React -App mit einem Laravel -Back -Ende: Teil 2, reagieren Mar 04, 2025 am 09:33 AM

Dies ist der zweite und letzte Teil der Serie zum Aufbau einer Reaktionsanwendung mit einem Laravel-Back-End. Im ersten Teil der Serie haben wir eine erholsame API erstellt, die Laravel für eine grundlegende Produktlistenanwendung unter Verwendung von Laravel erstellt hat. In diesem Tutorial werden wir Dev sein

Vereinfachte HTTP -Reaktion verspottet in Laravel -Tests Vereinfachte HTTP -Reaktion verspottet in Laravel -Tests Mar 12, 2025 pm 05:09 PM

Laravel bietet eine kurze HTTP -Antwortsimulationssyntax und vereinfache HTTP -Interaktionstests. Dieser Ansatz reduziert die Code -Redundanz erheblich, während Ihre Testsimulation intuitiver wird. Die grundlegende Implementierung bietet eine Vielzahl von Verknüpfungen zum Antworttyp: Verwenden Sie Illuminate \ Support \ facades \ http; Http :: fake ([ 'Google.com' => 'Hallo Welt',, 'github.com' => ['foo' => 'bar'], 'Forge.laravel.com' =>

Curl in PHP: So verwenden Sie die PHP -Curl -Erweiterung in REST -APIs Curl in PHP: So verwenden Sie die PHP -Curl -Erweiterung in REST -APIs Mar 14, 2025 am 11:42 AM

Die PHP Client -URL -Erweiterung (CURL) ist ein leistungsstarkes Tool für Entwickler, das eine nahtlose Interaktion mit Remote -Servern und REST -APIs ermöglicht. Durch die Nutzung von Libcurl, einer angesehenen Bibliothek mit Multi-Protokoll-Dateien, erleichtert PHP Curl effiziente Execu

12 Beste PHP -Chat -Skripte auf Codecanyon 12 Beste PHP -Chat -Skripte auf Codecanyon Mar 13, 2025 pm 12:08 PM

Möchten Sie den dringlichsten Problemen Ihrer Kunden in Echtzeit und Sofortlösungen anbieten? Mit Live-Chat können Sie Echtzeitgespräche mit Kunden führen und ihre Probleme sofort lösen. Sie ermöglichen es Ihnen, Ihrem Brauch einen schnelleren Service zu bieten

Ankündigung von 2025 PHP Situation Survey Ankündigung von 2025 PHP Situation Survey Mar 03, 2025 pm 04:20 PM

Die 2025 PHP Landscape Survey untersucht die aktuellen PHP -Entwicklungstrends. Es untersucht Framework -Nutzung, Bereitstellungsmethoden und Herausforderungen, die darauf abzielen, Entwicklern und Unternehmen Einblicke zu geben. Die Umfrage erwartet das Wachstum der modernen PHP -Versio

Benachrichtigungen in Laravel Benachrichtigungen in Laravel Mar 04, 2025 am 09:22 AM

In diesem Artikel werden wir das Benachrichtigungssystem im Laravel -Web -Framework untersuchen. Mit dem Benachrichtigungssystem in Laravel können Sie Benachrichtigungen an Benutzer über verschiedene Kanäle senden. Heute werden wir diskutieren, wie Sie Benachrichtigungen OV senden können

See all articles