Tire 字典树、前缀树

2024-05-03 05:52
文章标签 字典 前缀 tire

本文主要是介绍Tire 字典树、前缀树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

字典树(又称单词查找树或Trie树)是一种树形结构,它是哈希树的变种,通常用于统计、排序和保存大量的字符串(但不仅限于字符串)。字典树在搜索引擎系统中常用于文本词频统计。它的主要优点在于能够利用字符串的公共前缀来减少查询时间,从而最大限度地减少无谓的字符串比较,因此查询效率通常比哈希树高。

字典树有三个基本性质:

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

字典树的基本操作包括查找、插入和删除,但删除操作相对较少见。在查找操作中,通常从根节点开始,依次搜索关键词的每个字母,直到找到对应的节点或确定关键词不存在于树中。

字典树的应用场景非常广泛,包括但不限于:

  1. 字符串检索:将已知的一些字符串(如字典)的有关信息保存到字典树中,然后查找其他未知字符串是否出现过或出现的频率。
  2. 文本过滤:给定一个词典,其中的单词为不良单词,然后判断一段文本中是否含有任何不良单词。
  3. 字符串去重和排序:处理大量字符串时,可以使用字典树来去除重复字符串,并按字典序进行排序。
  4. 热门查询统计:搜索引擎可以通过日志文件记录用户每次检索使用的检索串,并使用字典树来统计热门查询。
  5. 字符串最长公共前缀:利用字典树可以快速得到某些字符串的公共前缀。

下面是使用java程序来实现该数据结构(仅限于26个英文字母)

class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {Trie node = searchPrefix(word);return node != null && node.isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private Trie searchPrefix(String prefix) {Trie node = this;for (int i = 0; i < prefix.length(); i++) {char ch = prefix.charAt(i);int index = ch - 'a';if (node.children[index] == null) {return null;}node = node.children[index];}return node;}
}

这篇关于Tire 字典树、前缀树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/955964

相关文章

POJ2001字典树

给出n个单词,求出每个单词的非公共前缀,如果没有,则输出自己。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.io.UnsupportedEncodingException;

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目,分别是:【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci

前缀和 — 利用前缀信息解决子数组问题

【前缀和的核心思想是预先处理数组来快速计算任意子数组的和,基本上用于数组和序列问题。】 前缀和算法具体步骤 构造前缀和数组: 给定一个数组nums,其前缀和数组prex定义为prex[i]表示为数组nums从起始位置到第i个位置的元素累加和。构建前缀和公式: p r e x [ i ] = n u m s [ i ] ( i = = 0 ) p r e x [ i ] = p r e x

python 实现第k个字典排列算法

第k个字典排列算法介绍 "第k个字典排列"算法通常指的是在给定的字符集合(例如,字符串中的字符)中,找到所有可能排列的第k个排列。这个问题可以通过多种方法解决,但一个常见且高效的方法是使用“下一个排列”算法的变种,或称为“第k个排列”的直接算法。 方法一:使用“下一个排列”的变种 生成所有排列:首先生成所有排列,但显然这种方法对于较大的输入集合是不切实际的,因为它涉及到大量的计算和存储。 排序

POJ3617(字典序最小问题)

书中43页 此题有坑点,PE了40分钟.也是醉了....题目要求每80个字符才换行,而且最后一个如果恰好就不用换,这不是无聊嘛....... #include <iostream>#include <cstdio>#include <cstring>using namespace std;int n,m;char S[2100],P[2100];int main(){#ifd

POJ 2001 Shortest Prefixes(字典树入门)

题目: http://poj.org/problem?id=2001 题意: 找到多个字符串中,各自唯一的最短子串,例如 carte 与 carce 各自唯一的最短子串为cart与carc,即不会与其它字符串的子串重复。 思路: 字典树 解题心得: 更新关键值的时机很重要 代码: #include<stdio.h>#include<string>typedef str

每日一题~cf 970 div3 (A思维,B小模拟,C二分,D排列数建图成环,E 26个字母暴力+前缀和,F 逆元,G 数论gcd )

A 题意: 有 a 个1 ,b 个2.问是否能将这些数划分为两个数值相等的集合。 输出 YES 或者 NO —————— 问题等价于 将数组 分成两个数值相同的数组。所以sum 应该是偶数。也就是说 1 的个数是偶数。在i1的个数是偶数的情况下,将 2 分成两份,如果2 的个数是偶数,OK。如果是奇数那么需要1来补齐,如果1 的个数大于等于2那么可以补齐。(1 的个数是偶数,需要2个1来补齐,剩下

Oracle数据库(数据字典、表空间、表的创建、视图)

知识点引用: http://www.2cto.com/database/201207/142874.html http://blog.csdn.net/haiross/article/details/11772847 一. 彻底卸载Oracle 方式1、重装操作系统 方式2、 2.1 DBCA删除数据库开始 → 程序 → Oracle → 开发与移植工具 → Datab

Python的字符串,list,tuple,set,字典操作详解

1.字符串python是要创建成字符串的元素,其中的每个字母都是单一的子串,把它放在' '单引号或是'' ''引号中,就完成了python 字符串的创建。#str强制转换>>> a=123>>> b=str(a) #将整数转化为字符串>>> b'123'>>> a=[1,2,3]>>> b=str(a) #将list转化为字符串>>> b'[1, 2, 3]'#字符串下

【数据结构-二维前缀和】力扣1504. 统计全 1 子矩形

给你一个 m x n 的二进制矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。 示例 1: 输入:mat = [[1,0,1],[1,1,0],[1,1,0]] 输出:13 解释: 有 6 个 1x1 的矩形。 有 2 个 1x2 的矩形。 有 3 个 2x1 的矩形。 有 1 个 2x2 的矩形。 有 1 个 3x1 的矩形。 矩形数目总共 = 6 + 2 + 3 + 1 +