当前位置: 首页 > Trie树
  • 最近在学习Trie树相关知识,自己实现了一个Java的例子,主要功能是通过添加英文单词建立trie树,然后实现前缀查找,模糊匹配。

    阅读全文
    Java 1,914 人阅读 抢沙发
  • 在搜索过程中,用户输入了拼音,我们需要把拼音转化为中文,去搜索。在实际应用中,一个拼音组合对应的是一些常用短语。为了先简易实现,我们考虑用词典方法,用Map去存储。一个短语的拼音作为key,短语拼音对应的中文作为value,用set存储。

    阅读全文
    搜索 1,192 人阅读 抢沙发 , ,
  • Trie 插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题;Trie 的缺点是空间消耗很高。Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

    阅读全文
    网站开发 718 人阅读 抢沙发 , ,