字 PHP实现Trie树(字典树)
Trie树的概念(百度的解释):字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
我的理解是用来做字符串搜索的,每个节点只包含一个字符,比如录入单词"world",则树的结构是:
这时再录入单词"worab",则树的结构为:
所以每个节点必须还要一个字段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>'; // 输出带上搜索前缀 }
以上就介绍了字 PHP实现Trie树(字典树),包括了字方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

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

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-

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

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' =>

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

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

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

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
