tr 类似“出”

try 美 [traɪ]，transform 美 [trænsˈfɔːrm]，trade  美 [treɪd]，美 [traɪ]，tree 美 [triː]

dr 类似“猪”

drink  美 [drɪŋk]，dream 美 [driːm]，driver 美 [ˈdraɪvər]，drop 美 [drɑːp]

 

英语中“音的浊化”现象，此时需要注意浊化现象发生的条件：在同一个音节内，当一个清辅音前是/s/,而这个清辅音又有它对应的浊辅音，并且在该清辅音后还有元音。所以，要同时符合上面的这四个条件才有浊化现象的发生。

inspiring  美 [ɪnˈspaɪərɪŋ]，discussion  美 [dɪˈskʌʃn]，stand  美 [stænd]，stop  美 [stɑːp]，speak 美 [spiːk] 

 

tu 类似 “出”，注意音标tʃu

actual 美 [ˈæktʃuəl]

tu 类似 “吃”，注意音标tʃ

adventure 美 [ədˈventʃər]，architecture 美 [ˈɑːrkɪtektʃər] 

具体发音还要看音标是否含有u

还有其他tu音节的单词，但是发音却不同

autumn 美 [ˈɔːtəm]，attitude 美 [ˈætɪtuːd]

我们会发现tʃ 发的是“吃”的音

 

du 类似“猪”，注意音标dʒu

education 美 [ˌedʒuˈkeɪʃn] 

du 类似“知”，注意音标dʒ

procedure 美 [prəˈsiːdʒər]

还有其他du音节的单词，但是发音却不同

duck 美 [dʌk]，due  美 [duː] 

 

 

文章目录
什么是前缀树
前缀树的结构
前缀树的数组实现（基于26个单词的）
前缀树的用途
前缀树的Map方式实现
对比数组实现和map实现
为什么要实现前缀树，对比普通树的结构
对比平衡搜索树
对比哈希表

什么是前缀树
Trie (发音为 “try”) 或前缀树是一种树数据结构，用于检索字符串数据集中的键。这一高效的数据结构有多种应用：
1.自动补全
2.拼写检查
3.IP 路由 (最长前缀匹配)
4.打字预测

前缀树的结构
假设我们现在要做一个关于小写英文单词的前缀匹配，这个时候我们想起来可以使用我们的前缀树呀，那么什么是前缀树呢~

从一个根节点出发。每对下一个节点的映射都应该具有26种可能性（单指目前对小写英文单词的匹配的情况）。那么我们的Trie的结构是不是应该是这样的。
Class Node{
	//想象一下链表结构，本来是一个对象，现在这个对象是一个26个位置的数组，用来按顺序存放26个字母
	Node[] next=new Node[26];
}

请看下图

假设我们现在存入的是cat。root出发，在第一层当中匹配c，没有找到c，则new一个对象，并存入c。同时让一个临时节点指向当前存入的c。以此往下。
假设我们现在前缀树里面已经有dog了，但没有dear，我们现在要存入dear。那么我们从root出发，在第一层当中匹配d，找到了d，临时节点指向d，再去获取d中的数组，在判断是否具有e，没有找到e，则new一个新的对象存入，这个对象也带着26个位置，你只需要把e放进去，再重复往下就可以。

tip：有一种 一个节点对应26个往下的可能性   的感觉


那前缀树除了插入的功能之外，自然还有搜索的功能。比如前缀树具有boolean search(String word)的方法。那为了方便遍历完word之后，可以快速返回word是否是一个单词。我们可以对前缀树的结构进行调整，如下
Class Node{
	//想象一下链表结构，本来是一个对象，现在这个对象是一个26个位置的数组，用来按顺序存放26个字母
	boolean isWord=false;
	Node[] next=new Node[26];
}

这样在每一个叶子节点的时候，都会对当前这个叶子节点的对象标识上一个isWord为true的属性。如下图所示吗，每一个蓝色节点的位置的对象的isWord属性都为true。


假设我们已经插入了panda，现在要插入pan这个单词，因为这个pan是panda的前缀。所以再插入完pan之后，其实在n这个节点处的对象的isWord也应该是true。即如下图所示


前缀树的数组实现（基于26个单词的）
那我们来看一下这种26个单词前缀树搜索的java实现
class Trie {

    private Trie[] next=new Trie[26];
    private boolean isEnd=false;

    /** Initialize your data structure here. */
    public Trie() {}
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie root=this;
        char[] c=word.toCharArray();
        for(int i=0;i<c.length;i++){
            if(root.next[c[i]-'a']==null){
                root.next[c[i]-'a']=new Trie();
            }
            root=root.next[c[i]-'a'];
        }
        root.isEnd=true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie root=this;
        char[] c=word.toCharArray();
        for(int i=0;i<c.length;i++){
            if(root.next[c[i]-'a']==null){
                return false;
            }else{
                root=root.next[c[i]-'a'];
            }
        }
        return root.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Trie root=this;
        char[] c=prefix.toCharArray();
        for(int i=0;i<c.length;i++){
            if(root.next[c[i]-'a']==null){
                return false;
            }else{
                root=root.next[c[i]-'a'];
            }
        }
        return true;
    }

    public boolean contains(char c){
        return this.next[c-'a']!=null;
    }

}

前缀树的用途
上面讲的前缀树，通过了一个26大小的数组实现。那假设我们的前缀树现在不是要去匹配单词呢，而是要匹配大小写单词呢，那是不是可以把数组变成52个。那如果是要去匹配ip地址的话，那是不是也要调整大小。如果是邮箱什么的，那是不是得把@也加上。
所以如果使用数组实现，则需要固定好内容。那对于若干个下一个节点的情况，我们可以采用下述结构，由数组改为Map来实现。（实现还是以单词为例子，这里Map的key为Character，可根据实际需要更改）
    class Node{
        boolean isWord=false;
        Map<Character,Node> next=new HashMap<>();
    }

前缀树的Map方式实现
class Trie {

    private Node node;

    class Node{
        boolean isWord=false;
        Map<Character,Node> next=new HashMap<>();
    }

    /** Initialize your data structure here. */
    public Trie() {
        node=new Node();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        insert(word,node);
    }

    public void insert(String word,Node node){
        if (word == null || word.isEmpty()) {
            return;
        }
        char[] c=word.toCharArray();
        for(int i=0;i<c.length;i++){
            if(!node.next.containsKey(c[i])){
                node.next.put(c[i],new Node());
            }
            node=node.next.get(c[i]);
        }
        node.isWord=true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return search(word,node);
    }
    
    public boolean search(String word,Node node){
        if (word == null || word.isEmpty()) {
            return false;
        }
        char[] c=word.toCharArray();
        for(int i=0;i<c.length;i++){
            if(!node.next.containsKey(c[i])){
                return false;
            }
            node=node.next.get(c[i]);
        }
        return node.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return startsWith(prefix,node);
    }

    public boolean startsWith(String prefix,Node node){
        if (prefix == null || prefix.isEmpty()) {
            return false;
        }
        char[] c=prefix.toCharArray();
        for(int i=0;i<c.length;i++){
            if(!node.next.containsKey(c[i])){
                return false;
            }
            node=node.next.get(c[i]);
        }
        return true;
    }
}

对比数组实现和map实现
数组很明显的特点是下标寻址快，而map更注重平衡搜索和增删。

在单词的前缀树的实现当中，所有方法都是我们通过数组下标的访问方式进行查找下一个字母，显然要比通过Map去找一下个字母的方式要快。所以在明确像字母这样的实现方式的时候，我认为数组要更快一些。
为什么要实现前缀树，对比普通树的结构
对比平衡搜索树
如果有n个条目，使用树的结构，查询的时间复杂度是O(logn)。

那么有100万个（2^20）的时候，那么logn大约为20。
而Trie查询每个条目的时间复杂度与字典中一共具有多少条目无关，时间复杂度为O(m)，m为查询单词的长度。而英文单词中大多数单词长度小于10。
对比哈希表
尽管哈希表可以在 O(1)时间内寻找键值，却无法高效的完成以下操作：
找到具有同一前缀的全部键值。
按词典序枚举字符串的数据集。

Trie 树优于哈希表的另一个理由是，随着哈希表大小增加，会出现大量的冲突，时间复杂度可能增加到 O(n)，其中 n 是插入的键的数量。与哈希表相比，Trie 树在存储多个具有相同前缀的键时可以使用较少的空间。
这么一对比，Trie是不是就高效了很多。

tries 数据结构



 Trie（通常发音为“ try”）是针对特定类型的搜索进行优化的树数据结构。 当您想获取部分值并返回一组可能的完整值时，可以使用Trie。 一个典型的例子是自动完成。 
 上图显示了Trie的结构，以暗示其工作原理。 您可以将Trie视为一组相关值。 这些值的共同点是它们的前缀。 
 当您搜索更特定的前缀时，您将获得更特定的返回值。 使用上图所示的Trie，搜索与前缀“ b”匹配的结果将返回6个值：be，bear，bell，bid，bull，buy。 



 搜索与前缀“ be”匹配的结果将返回2个值：bear，bell 



 何时使用Tries 
 只要您想将前缀与可能的完整值匹配，就可以使用Trie。 这就是Trie如何获得有趣名称的方式。 “ Trie”一词是“ re trie val”一词的后缀。 
 尝试通常用于实现以下内容： 

 自动完成/提前输入 
 搜索 
 拼写检查 
 分类 

 您不仅限于前缀匹配的单词。 可以存储： 

 IP地址 
 电话号码， 
 对象（您可以搜索对象的属性）， 
 和更多… 

 您是否应该在前端应用程序中使用Tries？ 
 在使用JavaScript固有的数据结构之前，需要考虑一些实际因素，例如： 

 这种结构是否可以提高性能？ 性能提升值得吗？ 
 这种结构是否更易于使用？或者至少不再困难？ 
 这种结构是否为我的数据提供了更多的语义？ 它使我的代码更容易理解吗？ 
 此结构会对我的构建大小有多大影响？ 这种增加的构建大小值得吗？ 

 为了回答这些问题，我们将比较Tries和Arrays-数组是JavaScript中最常用的Collection结构。 
 对比的尝试和数组 
 注意： 各种JavaScript引擎将实现JavaScript规范。 不一样 因此，环境之间的性能结果可能会有所不同。 
 这是我们用来对比Tries和Arrays的标准： 

 性能（运行时间和加载时间） 
 易于使用和可读性 
 构建大小（数组不添加任何额外的代码。我们将分析Trie。） 

 建立 
 我使用create-react-app在React中编写了快速自动完成功能。 看起来是这样的： 




 我使用Josh Jung的trie-search作为我的Trie实现。 
 我使用faker者生成了10,000个名称集。 我不在乎名称是否唯一。 

 码 
 这是自动完成的基本代码。 注意，它不使用任何特定的Collection数据结构。 下面是Trie和Array的实现细节。 
 这是基于数组的代码： 
 这是基于TrieSearch的代码： 
 性能 
 我在代码中测试了两个地方的性能： 

 将数据项加载到数据结构中。 
 在数据结构中搜索项目。 

 所有测试均使用Chrome 65.x进行。 
 加载数据项 
 使用Trie，您将比数组经历更长的初始化时间。 尝试在O（n * m）时间中初始化。 为了让您有一个实际的认识，平均花费90毫秒将10,000个项目添加到测试代码中的Trie。 这是一次性费用。 可以（即应该）将Trie初始化推迟到页面加载完成之后。 
 最常见的是，您将从数组初始化Trie。 如果需要添加更多数据，则可以手动将项目添加到Trie。 
 当搜索是应用程序的主要重点之一时，尝试会增加价值。 由于初始化成本高，如果用户搜索量不大，使用Trie可能不适合您的应用程序。 
 运行 
 在每个测试中，我在自动完成输入中键入“ Cath”，并测量了搜索花费了多长时间。 
 TrieSearch的表现优于Array.filter 。 它快了50％。 
 使用方便 
 如上面的代码示例所示，使用TrieSearch并不比使用Array复杂。 但是，要记住一些差异： 
 有关使用TrieSearch的更多详细信息，请参阅文档 。 
 尺寸 
 TrieSearch最小为7.4kb。 它具有13个依赖项。 整个产品的构建大小约为10kb。 确定这是否会对您的应用程序产生重大影响取决于您。 
 摘要 
 当您拥有进行大量搜索的应用程序时，Trie是一种出色的数据结构。 尝试相对容易使用-而且速度很快。 
 在阵列上使用Trie会降低性能，例如： 

 尝试初始化。 （因此，建议您将Trie的初始化推迟到页面加载之后）。 
 较大的捆束尺寸。 

翻译自: https://hackernoon.com/practical-data-structures-for-frontend-applications-when-to-use-tries-5428a565eba4
tries 数据结构

前言

蒟蒻做题。

已有工作

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

结构如图一所示



图一 字典树结构图

其基本操作有：查找、插入和删除,当然删除操作比较少见。

题目内容

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。

void insert(String word) 向前缀树中插入字符串 word 。

boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。

boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]

[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

输出

[null, null, true, false, true, null, true]

解释

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple");   // 返回 True

trie.search("app");     // 返回 False

trie.startsWith("app"); // 返回 True

trie.insert("app");

trie.search("app");     // 返回 True

提示：

1 <= word.length, prefix.length <= 2000

word 和 prefix 仅由小写英文字母组成

insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

解题代码​​​​​​​

class Trie {public:    bool vis;    Trie *next[26];    /** Initialize your data structure here. */    Trie() {        vis = false;//当前是否是end        for(int i = 0;i<26;i++)        {            next[i]=NULL;        }    }        /** Inserts a word into the trie. */    void insert(string word) {        int len = word.size();        Trie *p = this;        for(int i = 0;i<len;i++)        {            int id = word[i]-'a';            if(p->next[id]==NULL)            {                p->next[id] = new Trie();            }            p = p->next[id];        }        p->vis=true;    }        /** Returns if the word is in the trie. */    bool search(string word) {        Trie* p = this;        for(int i = 0;i<word.size();i++)        {            int id = word[i]-'a';            if(p->next[id]==NULL)            return false;            else p = p->next[id];        }        return p->vis?true:false;    }        /** Returns if there is any word in the trie that starts with the given prefix. */    bool startsWith(string prefix) {        Trie* p = this;        for(int i = 0;i<prefix.size();i++)        {            int id = prefix[i]-'a';            if(p->next[id]==NULL)            return false;            else p = p->next[id];        }        return p?true:false;    }};
/** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */