极客时间-轻松学习，高效学习-极客邦

2019-01-07

老师讲解得非常好，谈下个人对前缀树的了解，前缀树主要应用于以下场景：
1.预测文本输入功能：搜索引擎的输入框中输入搜索关键词的预测文本提示、IDE代码编辑器和浏览器网址中输入时的预测文本提示，借助老师讲的前两节动态规划实现预测文本的纠错功能；
2.使用前缀树结构对字符串或单词按字母顺序实现排序并进行输出的功能；
3.前缀树也可用于实现近似匹配，包括拼写检查和连字软件使用的算法；

前缀树的主要优劣对比：
1.使用前缀树可以高效地进行前缀搜索字符串和插入字符串，时间复杂度为O(length)；
2.使用前缀树可以按字母顺序轻松打印所有字符串，该功能是散列表不易实现的，但前缀树的搜索效率可能不如散列表快；
3.前缀树的缺点在于，需要大量的内存来存储字符串，对于每个节点需要太多的节点指针。倘若关注内存空间上的优化，可以考虑使用三元搜索树。三元搜索树是实现字典的首选结构，其搜索字符串的时间复杂度是O(height)；

展开

作者回复: 总结的很好，还有实用的场景

 1

 24

Healtheon

2019-01-07

下面是构建前缀树和查询的代码实现：
package com.string.test;

/**
* Created by hanyonglu on 2019/1/7.
*/
public class TrieTest {
    private static final int CHARACTER_SIZE = 26;

    private TrieNode root;

    private static class TrieNode {
        private TrieNode[] children;

        private boolean isWordEnd;

        public TrieNode() {
            isWordEnd = false;

            children = new TrieNode[CHARACTER_SIZE];
            for (int index = 0; index < CHARACTER_SIZE; index++) {
                children[index] = null;
            }
        }
    }

    public void insert(String key) {
        TrieNode newNode = root;
        int index;

        for (int i = 0; i < key.length(); i++) {
            index = key.charAt(i) - 'a';

            if (newNode.children[index] == null) {
                newNode.children[index] = new TrieNode();
            }

            newNode = newNode.children[index];
        }

        newNode.isWordEnd = true;
    }

    public boolean search(String key) {
        TrieNode searchNode = root;
        int index;

        for (int i = 0; i < key.length(); i++) {
            index = key.charAt(i) - 'a';

            if (searchNode.children[index] == null) {
                return false;
            }

            searchNode = searchNode.children[index];
        }

        return (searchNode != null && searchNode.isWordEnd);
    }

    public static void main(String args[]) {
        String[] keys = {"my", "name", "is", "hanyonglu", "the", "son", "handongyang", "home", "near", "not", "their"};

        TrieTest trieTest = new TrieTest();
        trieTest.root = new TrieNode();

        for (int index = 0; index < keys.length ; index++) {
            trieTest.insert(keys[index]);
        }

        System.out.println("home result : " + trieTest.search("home"));
        System.out.println("their result : " + trieTest.search("their"));
        System.out.println("t result : " + trieTest.search("t"));
    }
}

展开

作者回复: 实现很简洁👍



 14

产品助理

2019-01-07

从起始点到终止点所经过的边之数量，就是通路的长度。这里我画了...

极客时间版权所有: https://time.geekbang.org/column/article/76481

这里的通路的长度应该是3啊。

边有：v1——v2，v2——v3，v3——v4 三条，所以边的长度是3对吗？

展开

作者回复: 对应该是3，我稍后该一下

 2

 5

cwtxz

2019-12-29

通过这段时间的学习，我明白了，数学提供的是解决问题的思路，而编程是实现这个思路的工具和手段。编程的语言多种多样，针对同一个问题，可以采用各种各样的编程语言来实现，也可以采用各种各样的方法和思路去解决，但是有一点是相同的：没有思想的上层指导，下层的技术实现就是无根浮萍，指望脱离了思想的技术来解决问题，完全是痴心妄想。数学是思想，以思想之道驾驭技术之术，才能无往不利，所向披靡。加油!!!继续钻研《程序员的数学基础课》。

 1

 1

Paul Shan

2019-08-22

树是一种递归结构，由根节点和若干子树构成。在建树和查找上也会充分利用这种递归结构。



 1

是我

2019-05-16

觉得二叉树跟正则表达式好像

作者回复: 具体是哪种正则表达式？

 1

 1

qinggeouye

2019-02-20

查找到一个 python 版本，分别用迭代循环和递归的方法，实现在树中添加和查找单词。动手实现了一遍：～
https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/11_deepFirstSearch/lesson11_1.py



 1

NullPointer

2019-01-09

老师讲的很好，非常容易理解。😁这次就不做作业了



 1

Being

2019-01-07

关于思考题的一点想法：其实可以将单词以及字母抽象出来，利用组合模式，形成树形关系，实现递归调用。

作者回复: 如果使用前缀树，对给定的一些单词进行处理，就无需排列组合了



 1

建强

2019-12-07

用Python写了一个简单的程序：
# 前缀树构造与查询

# 前缀树节点
class PrefixNode:
    def __init__(self, letter):
        self.letter = letter # 每个节点中存储一个单词的字母
        self.childnode = {} # 子节点用字典存储
        self.isend = False # isend表示单词是否结束

    def addchild(self, child):
        self.childnode[child.letter] = child

    # 寻找字母为letter的子节点
    def findchild(self, letter):
        return self.childnode.get(letter)

# 前缀树
class PrefixTree:
    def __init__(self):
        self.root = PrefixNode('#') # 用#号代表根节点

    # 向字典树中加入一个单词
    def addWord(self, word):
        p = self.root
        for w in word:
            childnode = p.findchild(w)
            if childnode is None:
                # 前缀树中没有找到对应的字母，则重新构造一个新的子节点
                childnode = PrefixNode(w)
                p.addchild(childnode)

            p = childnode

        p.isend = True

    # 在字典树中查找一个单词
    def searchWord(self, word):
        p = self.root
        for w in word:
            childnode = p.findchild(w)

            if childnode is None:
                # 前缀树中没有找到对应的字母，则直接返回False
                return False

            p = childnode

        return p.isend

# 主程序
def main():
    # 构造字典树
    dict_tree = PrefixTree()

    # 向字典树中加入一些单词
    for word in ['beautiful','student','computer','desk','table','design','book','bookshelf']:
        dict_tree.addWord(word)

    print('prefix tree is maded')

    # 在字典树中查找单词
    for word in ['beau', 'book','student', 'conputer', 'bookshelf', 'desks']:
        if dict_tree.searchWord(word):
            print('"{}" was founded.'.format(word))
        else:
            print('"{}" was not founded.'.format(word))

if __name__ == '__main__':
    main()

展开





aoe

2019-12-02

这次通俗易懂，感谢老师

作者回复: 很高兴对你有价值





Eleven

2019-11-25

老师，这篇概念有点多啊，文章中说的有向边该怎么理解呢？

作者回复: 有向边是指从某个节点到另一个节点存在方向，顺向可以走通，逆向就不行





花指令

2019-11-04

发现大家用循环遍历确定节点，既然是字母，大小写最多就52个，那应该用ascii做二分搜索更快，分布均匀的话还可以直接用数组下标

作者回复: 如果只限定在英文，这是个好方法👍





MC

2019-09-30

Golang 版：

package main

import "fmt"

func main() {
    dict := NewDictionary()
    dict.Insert("hello", "你好")
    dict.Insert("世界", "word")

    fmt.Println(*dict.Explain("hello"))
    fmt.Println(*dict.Explain("世界"))
}

type trieNode struct {
    char rune
    children []*trieNode
    explanation *string
}

type Dictionary struct {
    root *trieNode
}

// Insert adds the word to the dictionary
func (dict *Dictionary) Insert(word string, explanation string) {
    current := dict.root
    for _, ch := range []rune(word) {
        found := false

        if len(current.children) > 0 {
            for _, node := range current.children {
                if node.char == ch {
                    current = node
                    found = true
                    break
                }
            }
        }

        if !found {
            child := &trieNode{char: ch}
            current.children = append(current.children, child)
            current = child
        }
    }

    if current.explanation == nil || *current.explanation != explanation {
        current.explanation = &explanation
    }
}

// Explain returns the explanation of the given word
func (dict *Dictionary) Explain(word string) *string {
    current := dict.root
    for _, ch := range []rune(word) {
        found := false
        for _, node := range current.children {
            if node.char == ch {
                current = node
                found = true
                break
            }
        }

        if !found {
            return nil
        }
    }

    return current.explanation
}

// NewDictionary create a empty Trie
func NewDictionary() *Dictionary {
    return &Dictionary{
        root: &trieNode{
            char: ' ',
        },
    }
}

展开





Better me

2019-07-28

想问下老师最后小结中对应的左子树为0右子树为1对应的二进制数有什么实际应用场景吗

作者回复: 其实二进制表示的本身就是最好的应用场景。当然，二分法也是一种对应的实现





梦倚栏杆

2019-03-26

对于二叉树而言，深度优先遍历是不是就是二叉树的先序遍历啊

作者回复: 确切的说，先序、中序和后序是深度优先遍历的三种方式





pyhhou

2019-01-18

简单实现了下，跑了几个例子是可以work的，这里build的时候用Map是考虑到字典里面的单词和解释以key-value的形式出现，search函数输入是单词输出是解释，没有该单词的话返回null

public class Trie {
     private class TrieNode {
          private TrieNode[] children = new TrieNode[26];
          private String word = null;
          private String explanation = null;
     }

     private TrieNode root = new TrieNode();

          public void buildTrie(Map<String, String> dictionary) {
               if (dictionary == null || dictionary.size() == 0) {
                    return;
               }

               for (String word : dictionary.keySet()) {
                    char[] wordArr = word.toCharArray();
                    TrieNode tmp = root;

                     for (char c : wordArr) {
                          if (tmp.children[c - 'a'] == null) {
                               tmp.children[c - 'a'] = new TrieNode();
                          }
                          tmp = tmp.children[c - 'a'];
                     }

                     tmp.word = word;
                     tmp.explanation = dictionary.get(word);
                }
           }

          public String searchTrie(String targetWord) {
               if (targetWord == null || targetWord.isEmpty()) {
                    return null;
               }

               char[] targetWordArr = targetWord.toCharArray();
               TrieNode tmp = root;

               for (char c : targetWordArr) {
                    if (tmp.children[c - 'a'] == null) {
                         return null;
                    }

                    tmp = tmp.children[c - 'a'];
                }

           return tmp.explanation;
      }

展开

作者回复: 逻辑上没问题，使用26个英文字母对于字典而言足够了👍



