C#,单词查找树(Trie Tree)的插入与搜索算法与源代码
Trie Tree
又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
Trie是一种高效的信息检索数据结构。使用Trie,可以将搜索复杂性提高到最佳极限(密钥长度)。如果我们将密钥存储在二元搜索树中,那么平衡良好的BST将需要与M*log N成比例的时间,其中M是最大字符串长度,N是树中的密钥数。使用Trie,我们可以在O(M)时间内搜索关键字。但是,惩罚是基于Trie存储要求(有关更多详细信息,请参阅Trie的应用程序)
Trie的每个节点都由多个分支组成。每个分支表示键的一个可能字符。我们需要将每个键的最后一个节点标记为单词节点的结尾。Trie节点字段isEndOfWord用于将节点区分为单词node的结尾。
将密钥插入Trie是一种简单的方法。输入键的每个字符都作为单个Trie节点插入。请注意,子级是指向下一级trie节点的指针(或引用)数组。关键字符用作数组子级的索引。如果输入键是新的或现有键的扩展,我们需要构造键的不存在节点,并为最后一个节点标记单词的结尾。如果输入键是Trie中现有键的前缀,我们只需将键的最后一个节点标记为单词的结尾。键的长度决定了Trie的深度。
搜索键类似于插入操作,但是,我们只比较字符并下移。搜索可能会因字符串结尾或trie中缺少键而终止。在前一种情况下,如果最后一个节点的isEndofWord字段为true,则该键存在于trie中。在第二种情况下,由于trie中不存在密钥,因此搜索终止,而不检查密钥的所有字符。
有一些有效的trie节点表示(例如压缩的trie、三元搜索树等),以最小化trie的内存需求。
它有3个基本性质:
根节点不包含字符,除根节点外每一个节点都只包含一个字符; 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串; 每个节点的所有子节点包含的字符都不相同。
搜索字典项目的方法为:
(1) 从根结点开始一次搜索;
(2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;
(3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。
其他操作类似处理
应用
串的快速检索
给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中,我们可以用数组枚举,用哈希,用字典树,先把熟词建一棵树,然后读入文章进行比较,这种方法效率是比较高的。
“串”排序
给定N个互不相同的仅由一个单词构成的英文名,让你将他们按字典序从小到大输出
用字典树进行排序,采用数组的方式创建字典树,这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
最长公共前缀
对所有串建立字典树,对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数,于是,问题就转化为当时公共祖先问题。
节点信息
public class TrieNode
{
public TrieNode[] children { get; set; } = new TrieNode[26];
public bool isEndOfWord { get; set; } = false;
public TrieNode()
{
isEndOfWord = false;
for (int i = 0; i < 26; i++)
{
children[i] = null;
}
}
}
插入与搜搜算法
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
public class TrieTree
{
public static readonly int ALPHABET_SIZE = 26;
public static TrieNode root { get; set; } = null;
public static void Insert(string key)
{
TrieNode pCrawl = root;
for (int level = 0; level < key.Length; level++)
{
int index = key[level] - 'a';
if (pCrawl.children[index] == null)
{
pCrawl.children[index] = new TrieNode();
}
pCrawl = pCrawl.children[index];
}
pCrawl.isEndOfWord = true;
}
public static bool Search(string key)
{
TrieNode pCrawl = root;
for (int level = 0; level < key.Length; level++)
{
int index = key[level] - 'a';
if (pCrawl.children[index] == null)
{
return false;
}
pCrawl = pCrawl.children[index];
}
return (pCrawl.isEndOfWord);
}
}
}
相关文章
- C# JToken类的使用,实现解析动态json数据、遍历、查找
- c#中@标志的作用 C#通过序列化实现深表复制 细说并发编程-TPL 大数据量下DataTable To List效率对比 【转载】C#工具类:实现文件操作File的工具类 异步多线程 Async .net 多线程 Thread ThreadPool Task .Net 反射学习
- Newtonsoft.Json C# Json序列化和反序列化工具的使用、类型方法大全 C# 算法题系列(二) 各位相加、整数反转、回文数、罗马数字转整数 C# 算法题系列(一) 两数之和、无重复字符的最长子串 DateTime Tips c#发送邮件,可发送多个附件 MVC图片上传详解
- c#代码 天气接口 一分钟搞懂你的博客为什么没人看 看完python这段爬虫代码,java流泪了c#沉默了 图片二进制转换与存入数据库相关 C#7.0--引用返回值和引用局部变量 JS直接调用C#后台方法(ajax调用) Linq To Json SqlServer 递归查询
- EF+LINQ事物处理 C# 使用NLog记录日志入门操作 ASP.NET MVC多语言 仿微软网站效果(转) 详解C#特性和反射(一) c# API接受图片文件以Base64格式上传图片 .NET读取json数据并绑定到对象
- 常量,字段,构造方法 调试 ms 源代码 一个C#二维码图片识别的Demo 近期ASP.NET问题汇总及对应的解决办法 c# chart控件柱状图,改变柱子宽度 使用C#创建Windows服务 C#服务端判断客户端socket是否已断开的方法 线程 线程池 Task .NET 单元测试的利剑——模拟框架Moq
- c# 把一个匿名对象赋值给一个Object类型的变量后,怎么取这个变量? c# dynamic动态类型和匿名类 详解C# 匿名对象(匿名类型)、var、动态类型 dynamic 深入浅析C#中的var和dynamic
- C#中泛型方法与泛型接口 C#泛型接口 List<IAll> arssr = new List<IAll>(); interface IPerson<T> c# List<接口>小技巧 泛型接口协变逆变的几个问题
- 浅谈c#的三个高级参数ref out 和Params C#中is与as的区别分析 “登陆”与“登录”有何区别 经典SQL语句大全(绝对的经典)
- [C#基础]c#中的BeginInvoke和EndEndInvoke
- 【卷土重来之C#学习笔记】(二)c#编程概述
- Word控件Spire.Doc 【Table】教程(19):在 C# 中的 Word 中添加/获取表格的替代文本
- Word控件Spire.Doc 【页面设置】教程(3):在 C#、VB.NET 中设置 Word 页边距
- C#【必备技能篇】字节数组转16进制字符串,用空格分隔
- C#【必备技能篇】Marshal是什么?怎么用?
- C#【疑难杂症篇】VS“无法查找或打开PDB文件”是怎么回事?如何解决
- C#实现查找指定端口被哪个进程占用并处理进程及dos命令下操作
- 用C#开发基于自动化接口的OPC客户端
- C#与.NET Framework c#编程语言,和java是一样的。(c#,java) -->javaweb,asp.net