# 单词查找树 Trie

**Repository Path**: ghwolfs/trie_tree

## Basic Information

- **Project Name**: 单词查找树 Trie
- **Description**: 线程安全的，纯JDK8+原生代码实现单词查找树(Trie)数据结构。支持铭感词过滤基础功能，也有利用trie特性存储的扩展功能。
- **Primary Language**: Java
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2019-12-31
- **Last Updated**: 2021-11-03

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 单词查找树

## 所需环境
JDK 1.8+  
如果要使用缓存树包装类，则需要引入spring支持  

## 程序结构
> __TrieTree__ 核心顶级操作接口  
> --- __StringTrieTree__ 单词查找树  
> --- __StorageTrieTree__ 支持存储的单词查找树接口  
> ---  --- __SeparatorTrieTree__ 使用自定义分隔符进行单词分割的Trie树  
> ---  ---  --- __WildcardTrieTree__ 支持通配符的Trie树  
> ---  --- __CacheStorageTrieTreeWrapper__ 支持查询缓存的Trie树包装类  

各个树的具体使用细节均在类的javadoc注释中详细说明，包括通配符的解析，用法，优先级，注意事项等。

## 单词查找树StringTrieTree

单词查找树是利用字符串公共前缀的特性，以提供高效的查询速度。  
Trie树主要作用是相似前缀数据的高速查询，例如参数解析，字典数据解析，敏感词过滤，特殊词汇查询等。  

StringTrieTree采用ReinitOnWrite技术，因此是线程安全的，但同时新增的效率也是较差的。通常建议使用addAll或removeAll方法以提高性能。

目前版本经过简单性能测试，效率比直接replace替换所有铭感词的效率快5倍以上。  

## 支持存储的单词查找树StorageTrieTree

带有存储功能的单词查找树并不是用于存储和铭感词过滤的，而且他的性能也没有直接使用map查询快。
它更多地是进行特定条件的查询，例如使用WildcardTrieTree树的通配符特性进行特定优先级数据匹配查询操作。


树得节点数量对性能的影响是极小的，树的深度对性能影响较大。  
目前简单的测试结果如下（仅供参考）：
> 1、深度最高12，节点数从100 ~ 2w，进行200w次随机深度查询  
> 查询时间大约在300ms ~ 1s内  
> 2、深度最高102，节点数2w，进行200w次固定深度查询  
> 查询时间大约为7s左右

此代码设计是基于线程安全，并且提供了缓存，通配符等多种特性的扩展树。通常建议缓存在外部自己实现，但是如果你需要使用内部缓存，则需要引入spring开发包，因为需要ConcurrentReferenceHashMap类做缓存处理。  

## StorageTrieTree缓存包装类CacheStorageTrieTreeWrapper

使用CacheStorageTrieTreeWrapper类可以包装任何一个StorageTrieTree接口对象，使其查询方法拥有缓存功能。


## V1.1版本更新-2020-01-07

1. 调整了类结构，完成了以查找为目的的单词查找树和以特定查询条件和优先级进行匹配的存储型单词查找树的开发。  
2. 大幅度提升了SeparatorTrieTree类的性能，主要以提升split操作性能为主。内置一个FastSplit，针对字符进行分割，比string.split，StringUtils.split，StringTokenizer都要快。
3. SeparatorTrieTree不再支持正则表达式，而是字符  
4. 缓存树不再单独成为某一个类的子类，而是成为一个包装类用于包装任何StorageTrieTree接口子类。