徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
自由
比浏览器更快的访问!
 

Trie

指数 Trie

在计算机科学中,trie,又称前缀树或字典樹,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。 Trie这个术语来自于retrieval。根据词源学,trie的发明者Edward Fredkin把它读作 "tree"。但是,其他作者把它读作 "try"。 在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。 键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示trie的原理。 trie中的键通常是字符串,但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie中的键是一串位元,可以用于表示整数或者内存地址。.

9 关系: 字符串二元搜尋樹关联数组前綴确定有限状态自动机计算机科学词源学Glibc树 (数据结构)

字符串

字符串(String),是由零个或多个字符组成的有限序列。一般记为s.

新!!: Trie和字符串 · 查看更多 »

二元搜尋樹

二叉查找树(Binary Search Tree),也--有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:.

新!!: Trie和二元搜尋樹 · 查看更多 »

关联数组

在计算机科学中,关联数组(),又称映射()、字典()是一个抽象的数据结构,它包含着类似于(键,值)的有序对。一个关联数组中的有序对可以重复(如C++中的multimap)也可以不重复(如C++中的map)。 这种数据结构包含以下几种常见的操作:.

新!!: Trie和关联数组 · 查看更多 »

前綴

在語言學裡,前綴(Prefix)又稱字首或詞頭,屬於一種前置於其他詞素的詞綴,由於其無法以單字的方式獨立存在,故亦為一種附著詞素;此外在歐洲語言裡,前綴也幾乎都屬於衍生語素(屈折變化則多以後綴表達)。 多數的語言同時擁有前綴與後綴,但不管是哪種語系語族的語言,前綴的使用都普遍地比後綴少,一些語言甚至幾乎沒有前綴。 經統計後發現,前綴的存在常伴隨其他語言學的特徵,例如 V-O(主語-賓語)的語序以及前置詞的使用。.

新!!: Trie和前綴 · 查看更多 »

确定有限状态自动机

在计算理论中,确定有限状态自动机或确定有限自动机(deterministic finite automation, DFA)是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表\Sigma的字符,它都能根据事先给定的转移函数转移到下一个状态(这个状态可以是先前那个状态)。.

新!!: Trie和确定有限状态自动机 · 查看更多 »

计算机科学

计算机科学用于解决信息与计算的理论基础,以及实现和应用它们的实用技术。 计算机科学(computer science,有时缩写为CS)是系统性研究信息与计算的理论基础以及它们在计算机系统中如何与应用的实用技术的学科。 它通常被形容为对那些创造、描述以及转换信息的算法处理的系统研究。计算机科学包含很多分支领域;有些强调特定结果的计算,比如计算机图形学;而有些是探討计算问题的性质,比如计算复杂性理论;还有一些领域專注于怎样实现计算,比如程式語言理論是研究描述计算的方法,而程式设计是应用特定的程式語言解决特定的计算问题,人机交互则是專注于怎样使计算机和计算变得有用、好用,以及随时随地为人所用。 有时公众会误以为计算机科学就是解决计算机问题的事业(比如信息技术),或者只是与使用计算机的经验有关,如玩游戏、上网或者文字处理。其实计算机科学所关注的,不仅仅是去理解实现类似游戏、浏览器这些软件的程序的性质,更要通过现有的知识创造新的程序或者改进已有的程序。 尽管计算机科学(computer science)的名字里包含计算机这几个字,但实际上计算机科学相当数量的领域都不涉及计算机本身的研究。因此,一些新的名字被提议出来。某些重点大学的院系倾向于术语计算科学(computing science),以精确强调两者之间的不同。丹麦科学家Peter Naur建议使用术语"datalogy",以反映这一事实,即科学学科是围绕着数据和数据处理,而不一定要涉及计算机。第一个使用这个术语的科学机构是哥本哈根大学Datalogy学院,该学院成立于1969年,Peter Naur便是第一任教授。这个术语主要被用于北欧国家。同时,在计算技术发展初期,《ACM通讯》建议了一些针对计算领域从业人员的术语:turingineer,turologist,flow-charts-man,applied meta-mathematician及applied epistemologist。 三个月后在同样的期刊上,comptologist被提出,第二年又变成了hypologist。 术语computics也曾经被提议过。在欧洲大陆,起源于信息(information)和数学或者自动(automatic)的名字比起源于计算机或者计算(computation)更常见,如informatique(法语),Informatik(德语),informatika(斯拉夫语族)。 著名计算机科学家Edsger Dijkstra曾经指出:“计算机科学并不只是关于计算机,就像天文学并不只是关于望远镜一样。”("Computer science is no more about computers than astronomy is about telescopes.")设计、部署计算机和计算机系统通常被认为是非计算机科学学科的领域。例如,研究计算机硬件被看作是计算机工程的一部分,而对于商业计算机系统的研究和部署被称为信息技术或者信息系统。然而,现如今也越来越多地融合了各类计算机相关学科的思想。计算机科学研究也经常与其它学科交叉,比如心理学,认知科学,语言学,数学,物理学,统计学和经济学。 计算机科学被认为比其它科学学科与数学的联系更加密切,一些观察者说计算就是一门数学科学。 早期计算机科学受数学研究成果的影响很大,如Kurt Gödel和Alan Turing,这两个领域在某些学科,例如数理逻辑、范畴论、域理论和代数,也不断有有益的思想交流。.

新!!: Trie和计算机科学 · 查看更多 »

词源学

#重定向 语源学.

新!!: Trie和词源学 · 查看更多 »

Glibc

#重定向 GNU C函式庫.

新!!: Trie和Glibc · 查看更多 »

树 (数据结构)

在計算機科學中,樹(tree)是一种抽象数据类型(ADT)或是實作這種抽象数据类型的数据结构,用來模擬具有樹狀結構性質的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:.

新!!: Trie和树 (数据结构) · 查看更多 »

重定向到这里:

Trie树字典树字母树前缀树索回树键树

传出传入
嘿!我们在Facebook上吧! »