当前位置: 首页 > news >正文

网站建设优化现状图表长春制作网站哪家好

网站建设优化现状图表,长春制作网站哪家好,万网域名注册官网,wordpress主题模板下载失败文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。 1 Trie树的使用场景 搜索引擎中的搜索词建议。当你在搜索引擎中输入词#xff0c;搜索引擎提示给你一个词的列表#xff0c;帮助你快速输入想搜索的词。 这个功能…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。 1 Trie树的使用场景 搜索引擎中的搜索词建议。当你在搜索引擎中输入词搜索引擎提示给你一个词的列表帮助你快速输入想搜索的词。 这个功能要想想做得精准肯定需要很多优化工作。但这个功能的底层数据结构就是Trie树。 2 什么是Trie树 Trie树也叫字典树是一种树形结构专门用于处理在一个字符串集合中查找某个字符串。 2.1 Trie树的结构 例如需要在howhiherhellososee这六个字符串中查找某个字符串。我们也可以用字符串和这6个字符串逐个比较只是效率不高。使用Trie树只需要一次比较就可以。我们先用这六个字符串构建一个Trie树。 之后每次查找从Trie树的根节点开始查找。Trie树是利用字符串之间的公共前缀将重复的前缀合并在一起。根节点不包含任何信息每个节点是字符串中的一个字符。从根节点到红色节点的一条路径表示一个字符串。重点红色节点并不都是叶子节点例子中没有表示出来。 2.2 Trie树的构造过程 2.3 Trie树的查找过程 当我们查找一个字符串的时候从根节点开始。例如查找字符串her我们把字符串切分成字符h e r从根节点开始走出路径/-h-e-r并且r节点有字符串结束标志树中包含字符串her。 例如我们查找字符串he我们把字符串切分成字符h e。从根节点开始走出路径/-h-e。但是e没有字符串结束标志所以树中不包含he。 3 Trie树代码实现 Trie树的操作包括初始化和查找。 Trie树是一棵多叉树。在二叉树的时候节点每个节点是用左右指针指向子节点。 class BinaryTreeNode {char data;BinaryTreeNode left;BinaryTreeNode right; } Trie树是一个多叉树怎么存储节点的子节点呢一种方法是假设字符串只包含小写字母可以在字母和数组下标之间做映射使用数组存储子节点。如果子节点的字母是a存储在children[0]如果子节点的字母是b存储在children[1]… class TrieNode {char data;TrieNode children[26]; }整体代码 public class Trie {private TrieNode root new TrieNode(/);public void insert(String text){char[] chars text.toCharArray();TrieNode node root;for(int i0;ichars.length;i){int idx chars[i] - a;if(node.childern[idx]null){node.childern[idx] new TrieNode(chars[i]);}node node.childern[idx];}node.endWord true;}public boolean find(String text){TrieNode node root;char[] chars text.toCharArray();for(int i0;ichars.length;i){int idx chars[i] - a;if(node.childern[idx]null){return false;}node node.childern[idx];}return node.endWord;}class TrieNode{private char data;private TrieNode[] childern;private boolean endWord;public TrieNode(char ch){this.data ch;}} }Trie树的时间复杂度。Trie树构建的时候需要遍历所有的字符时间复杂度O(n)。n为 所有字符串长度之和。查找的时候每个字符遍历一次时间复杂度O(m)m是查找字符串长度。 4 Trie树适合解决的问题 4.1 Trie树的缺点耗内存 上面的代码中每个节点都需要长度为26的数组存储子节点。但是并不是每个字母后面都会跟着26个字母很多数组 中的值是空的。 这还是只考虑了小写字母的情况当要存储的包含数字、中文的时候按照这种方式存储会需要 更多的内容。这个时候可以考虑使用哈希表存储子节点。也可以使用有序数组、跳表、红黑树等牺牲一定的性能。例如使用有序数组那插入的时候要维护数组有序多消耗时间查询每一层子节点的时候不是O(1)而是需要二分。 4.2 Trie树的优点前缀匹配 对于支持动态数组高效操作的数据结构有散列表、红黑树、跳表等。这些数据结构也可以实现字符串查找。而Trie树除了字符串匹配之外更常用于字符串前缀匹配。就是前面提到的搜索词提示。词库是用户的热门搜索词这些词构建一棵Trie树。我们把用户输入的词作为前缀子串去Trie树中匹配将匹配到的字符串返回。 实际工程中会遇到 一些问题需要解决 1 词库中匹配到的词可能很多怎么排序 2 在用户拼写错误的情况下依然能够返回正确的提示词怎么做到
http://www.huolong8.cn/news/47223/

相关文章:

  • wordpress content widgetsseowhy
  • txt做网站如何加图片北京装饰公司十大排名
  • seo站内优化培训wordpress免登录支付
  • 外贸做的亚马逊网站是哪个北京网页制作公司
  • 莆田有哪几家做网站设计的晋江网站建设联系电话
  • 终身免费网站建设加强企业网站建设的通知
  • 镇平做网站wordpress+高性能
  • 广州网站建设大公司排名查看邮箱注册的网站
  • 福永响应式网站建设软件开发的步骤
  • 网站开发期末作品代码和数据库运行好大全阿里做外贸是哪个网站
  • 好看动漫网替代网站tk网站免费
  • seo优化网站推广专员招聘如何开网站赚钱
  • 网站标题栏怎么修改模板网会员
  • 崇信县门户网站wordpress 顶部栏
  • 网站开始怎么做的版式设计
  • 集团企业网站建设方案策划书自己制作app需要什么
  • 咋么做网站线上购买链接
  • 外接硬盘做创建立网站吴忠市住房和城乡建设厅网站
  • wordpress站点信息修改版权网站应用系统设计方案
  • 国内专门做情侣的网站商城福州电商网站设计
  • 盐山网站wordpress 主题框架
  • 济宁做网站的电话wordpress描述怎么改
  • 嘉兴建设公司网站仿站定制模板建站
  • 游戏网站设计模板可编辑wordpress主题
  • 网站备案怎么改广告推广平台赚取佣金
  • 做医采官方网站网站建设mus18
  • 企业网站规划案例企业自己怎么做网站推广
  • 南宁网站制作工具如何管理wordpress网站模板下载
  • 做自己的网站怎么赚钱经营地址怎么在国税网站做更改
  • 免费查企业app排行榜网络优化排名培训