Java学习指南
  • Java 编程的逻辑
  • Java进阶
  • Java FrameWorks
  • 了解 USB Type-A,B,C 三大标准接口
  • 深入浅出DDD
  • 重构:改善既有代码的设计
  • 面试大纲
  • 云原生
    • 什么是无服务器(what is serverless)?
  • 博客
    • 深入分析Log4j 漏洞
  • 博客
    • Serverless之快速搭建Spring Boot应用
  • 博客
    • 使用 Prometheus + Grafana + Spring Boot Actuator 监控应用
  • 博客
    • 使用 Prometheus + Grafana 监控 MySQL
  • 博客
    • 使用Github Actions + Docker 部署Spring Boot应用
  • 博客
    • Redis分布式锁之Redisson的原理和实践
  • 博客
    • 数据库中的树结构应该怎样去设计
  • 学习&成长
    • 如何成为技术大牛
  • 开发工具
    • Git Commit Message Guidelines
  • 开发工具
    • git命名大全
  • 开发工具
    • Gradle vs Maven Comparison
  • 开发工具
    • Swagger2常用注解及其说明
  • 开发工具
    • 简明 VIM 练级攻略
  • 微服务
    • 十大微服务设计模式和原则
  • 微服务
    • 微服务下的身份认证和令牌管理
  • 微服务
    • 微服务坏味道之循环依赖
  • 设计模式
    • 设计模式 - JDK中的设计模式
  • 设计模式
    • 设计模式 - Java三种代理模式
  • 设计模式
    • 设计模式 - 六大设计原则
  • 设计模式
    • 设计模式 - 单例模式
  • 设计模式
    • 设计模式 - 命名模式
  • 设计模式
    • 设计模式 - 备忘录模式
  • 设计模式
    • 设计模式 - 概览
  • 设计模式
    • 设计模式 - 没用的设计模式
  • 质量&效率
    • Homebrew 替换国内镜像源
  • 质量&效率
    • 工作中如何做好技术积累
  • Java FrameWorks
    • Logback
      • 自定义 logback 日志过滤器
  • Java FrameWorks
    • Mybatis
      • MyBatis(十三) - 整合Spring
  • Java FrameWorks
    • Mybatis
      • MyBatis(十二) - 一些API
  • Java FrameWorks
    • Mybatis
      • Mybatis(一) - 概述
  • Java FrameWorks
    • Mybatis
      • Mybatis(七) - 结果集的封装与映射
  • Java FrameWorks
    • Mybatis
      • Mybatis(三) - mapper.xml及其加载机制
  • Java FrameWorks
    • Mybatis
      • Mybatis(九) - 事务
  • Java FrameWorks
    • Mybatis
      • Mybatis(二) - 全局配置文件及其加载机制
  • Java FrameWorks
    • Mybatis
      • Mybatis(五) - SqlSession执行流程
  • Java FrameWorks
    • Mybatis
      • Mybatis(八) - 缓存
  • Java FrameWorks
    • Mybatis
      • Mybatis(六) - 动态SQL的参数绑定与执行
  • Java FrameWorks
    • Mybatis
      • Mybatis(十) - 插件
  • Java FrameWorks
    • Mybatis
      • Mybatis(十一) - 日志
  • Java FrameWorks
    • Mybatis
      • Mybatis(四) - Mapper接口解析
  • Java FrameWorks
    • Netty
      • Netty 可靠性分析
  • Java FrameWorks
    • Netty
      • Netty - Netty 线程模型
  • Java FrameWorks
    • Netty
      • Netty堆外内存泄露排查盛宴
  • Java FrameWorks
    • Netty
      • Netty高级 - 高性能之道
  • Java FrameWorks
    • Shiro
      • Shiro + JWT + Spring Boot Restful 简易教程
  • Java FrameWorks
    • Shiro
      • 非常详尽的 Shiro 架构解析!
  • Java FrameWorks
    • Spring
      • Spring AOP 使用介绍,从前世到今生
  • Java FrameWorks
    • Spring
      • Spring AOP 源码解析
  • Java FrameWorks
    • Spring
      • Spring Event 实现原理
  • Java FrameWorks
    • Spring
      • Spring Events
  • Java FrameWorks
    • Spring
      • Spring IOC容器源码分析
  • Java FrameWorks
    • Spring
      • Spring Integration简介
  • Java FrameWorks
    • Spring
      • Spring MVC 框架中拦截器 Interceptor 的使用方法
  • Java FrameWorks
    • Spring
      • Spring bean 解析、注册、实例化流程源码剖析
  • Java FrameWorks
    • Spring
      • Spring validation中@NotNull、@NotEmpty、@NotBlank的区别
  • Java FrameWorks
    • Spring
      • Spring 如何解决循环依赖?
  • Java FrameWorks
    • Spring
      • Spring 异步实现原理与实战分享
  • Java FrameWorks
    • Spring
      • Spring中的“for update”问题
  • Java FrameWorks
    • Spring
      • Spring中的设计模式
  • Java FrameWorks
    • Spring
      • Spring事务失效的 8 大原因
  • Java FrameWorks
    • Spring
      • Spring事务管理详解
  • Java FrameWorks
    • Spring
      • Spring计时器StopWatch使用
  • Java FrameWorks
    • Spring
      • 详述 Spring MVC 框架中拦截器 Interceptor 的使用方法
  • Java FrameWorks
    • Spring
      • 透彻的掌握 Spring 中@transactional 的使用
  • Java
    • Java IO&NIO&AIO
      • Java IO - BIO 详解
  • Java
    • Java IO&NIO&AIO
      • Java NIO - IO多路复用详解
  • Java
    • Java IO&NIO&AIO
      • Java N(A)IO - Netty
  • Java
    • Java IO&NIO&AIO
      • Java IO - Unix IO模型
  • Java
    • Java IO&NIO&AIO
      • Java IO - 分类
  • Java
    • Java IO&NIO&AIO
      • Java NIO - 基础详解
  • Java
    • Java IO&NIO&AIO
      • Java IO - 常见类使用
  • Java
    • Java IO&NIO&AIO
      • Java AIO - 异步IO详解
  • Java
    • Java IO&NIO&AIO
      • Java IO概述
  • Java
    • Java IO&NIO&AIO
      • Java IO - 设计模式
  • Java
    • Java IO&NIO&AIO
      • Java NIO - 零拷贝实现
  • Java
    • Java JVM
      • JVM 优化经验总结
  • Java
    • Java JVM
      • JVM 内存结构
  • Java
    • Java JVM
      • JVM参数设置
  • Java
    • Java JVM
      • Java 内存模型
  • Java
    • Java JVM
      • 从实际案例聊聊Java应用的GC优化
  • Java
    • Java JVM
      • Java 垃圾回收器G1详解
  • Java
    • Java JVM
      • 垃圾回收器Shenandoah GC详解
  • Java
    • Java JVM
      • 垃圾回收器ZGC详解
  • Java
    • Java JVM
      • 垃圾回收基础
  • Java
    • Java JVM
      • 如何优化Java GC
  • Java
    • Java JVM
      • 类加载机制
  • Java
    • Java JVM
      • 类字节码详解
  • Java
    • Java 基础
      • Java hashCode() 和 equals()
  • Java
    • Java 基础
      • Java 基础 - Java native方法以及JNI实践
  • Java
    • Java 基础
      • Java serialVersionUID 有什么作用?
  • Java
    • Java 基础
      • Java 泛型的类型擦除
  • Java
    • Java 基础
      • Java 基础 - Unsafe类解析
  • Java
    • Java 基础
      • Difference Between Statement and PreparedStatement
  • Java
    • Java 基础
      • Java 基础 - SPI机制详解
  • Java
    • Java 基础
      • Java 基础 - final
  • Java
    • Java 基础
      • Java中static关键字详解
  • Java
    • Java 基础
      • 为什么说Java中只有值传递?
  • Java
    • Java 基础
      • Java 基础 - 即时编译器原理解析及实践
  • Java
    • Java 基础
      • Java 基础 - 反射
  • Java
    • Java 基础
      • Java多态的面试题
  • Java
    • Java 基础
      • Java 基础 - 异常机制详解
  • Java
    • Java 基础
      • 为什么要有抽象类?
  • Java
    • Java 基础
      • 接口的本质
  • Java
    • Java 基础
      • Java 基础 - 枚举
  • Java
    • Java 基础
      • Java 基础 - 泛型机制详解
  • Java
    • Java 基础
      • Java 基础 - 注解机制详解
  • Java
    • Java 基础
      • 为什么 String hashCode 方法选择数字31作为乘子
  • Java
    • Java 并发
      • Java 并发 - 14个Java并发容器
  • Java
    • Java 并发
      • Java 并发 - AQS
  • Java
    • Java 并发
      • Java 并发 - BlockingQueue
  • Java
    • Java 并发
      • Java 并发 - CAS
  • Java
    • Java 并发
      • Java 并发 - Condition接口
  • Java
    • Java 并发
      • Java 并发 - CopyOnWriteArrayList
  • Java
    • Java 并发
      • Java 并发 - CountDownLatch、CyclicBarrier和Phaser对比
  • Java
    • Java 并发
      • Java 并发 - Fork&Join框架
  • Java
    • Java 并发
      • Java 并发 - Java CompletableFuture 详解
  • Java
    • Java 并发
      • Java 并发 - Java 线程池
  • Java
    • Java 并发
      • Java 并发 - Lock接口
  • Java
    • Java 并发
      • Java 并发 - ReentrantLock
  • Java
    • Java 并发
      • Java 并发 - ReentrantReadWriteLock
  • Java
    • Java 并发
      • Java 并发 - Synchronized
  • Java
    • Java 并发
      • Java 并发 - ThreadLocal 内存泄漏问题
  • Java
    • Java 并发
      • Java 并发 - ThreadLocal
  • Java
    • Java 并发
      • Java 并发 - Volatile
  • Java
    • Java 并发
      • Java 并发 - 从ReentrantLock的实现看AQS的原理及应用
  • Java
    • Java 并发
      • Java 并发 - 公平锁和非公平锁
  • Java
    • Java 并发
      • Java 并发 - 内存模型
  • Java
    • Java 并发
      • Java 并发 - 原子类
  • Java
    • Java 并发
      • Java 并发 - 如何确保三个线程顺序执行?
  • Java
    • Java 并发
      • Java 并发 - 锁
  • Java
    • Java 的新特性
      • Java 10 新特性概述
  • Java
    • Java 的新特性
      • Java 11 新特性概述
  • Java
    • Java 的新特性
      • Java 12 新特性概述
  • Java
    • Java 的新特性
      • Java 13 新特性概述
  • Java
    • Java 的新特性
      • Java 14 新特性概述
  • Java
    • Java 的新特性
      • Java 15 新特性概述
  • Java
    • Java 的新特性
      • Java 8的新特性
  • Java
    • Java 的新特性
      • Java 9 新特性概述
  • Java
    • Java 调试排错
      • 调试排错 - Java Debug Interface(JDI)详解
  • Java
    • Java 调试排错
      • 调试排错 - CPU 100% 排查优化实践
  • Java
    • Java 调试排错
      • 调试排错 - Java Heap Dump分析
  • Java
    • Java 调试排错
      • 调试排错 - Java Thread Dump分析
  • Java
    • Java 调试排错
      • 调试排错 - Java动态调试技术原理
  • Java
    • Java 调试排错
      • 调试排错 - Java应用在线调试Arthas
  • Java
    • Java 调试排错
      • 调试排错 - Java问题排查:工具单
  • Java
    • Java 调试排错
      • 调试排错 - 内存溢出与内存泄漏
  • Java
    • Java 调试排错
      • 调试排错 - 在线分析GC日志的网站GCeasy
  • Java
    • Java 调试排错
      • 调试排错 - 常见的GC问题分析与解决
  • Java
    • Java 集合
      • Java 集合 - ArrayList
  • Java
    • Java 集合
      • Java 集合 - HashMap 和 ConcurrentHashMap
  • Java
    • Java 集合
      • Java 集合 - HashMap的死循环问题
  • Java
    • Java 集合
      • Java 集合 - LinkedHashSet&Map
  • Java
    • Java 集合
      • Java 集合 - LinkedList
  • Java
    • Java 集合
      • Java 集合 - PriorityQueue
  • Java
    • Java 集合
      • Java 集合 - Stack & Queue
  • Java
    • Java 集合
      • Java 集合 - TreeSet & TreeMap
  • Java
    • Java 集合
      • Java 集合 - WeakHashMap
  • Java
    • Java 集合
      • Java 集合 - 为什么HashMap的容量是2的幂次方
  • Java
    • Java 集合
      • Java 集合 - 概览
  • Java
    • Java 集合
      • Java 集合 - 高性能队列Disruptor详解
  • 分布式
    • RPC
      • ⭐️RPC - Dubbo&hsf&Spring cloud的区别
  • 分布式
    • RPC
      • ⭐️RPC - Dubbo的架构原理
  • 分布式
    • RPC
      • ⭐️RPC - HSF的原理分析
  • 分布式
    • RPC
      • ⭐️RPC - 你应该知道的RPC原理
  • 分布式
    • RPC
      • ⭐️RPC - 动态代理
  • 分布式
    • RPC
      • 深入理解 RPC 之协议篇
  • 分布式
    • RPC
      • RPC - 序列化和反序列化
  • 分布式
    • RPC
      • ⭐️RPC - 服务注册与发现
  • 分布式
    • RPC
      • RPC - 核心原理
  • 分布式
    • RPC
      • ⭐️RPC - 框架对比
  • 分布式
    • RPC
      • ⭐️RPC - 网络通信
  • 分布式
    • 分布式事务
      • 分布式事务 Seata TCC 模式深度解析
  • 分布式
    • 分布式事务
      • 分布式事务的实现原理
  • 分布式
    • 分布式事务
      • 常用的分布式事务解决方案
  • 分布式
    • 分布式事务
      • 手写实现基于消息队列的分布式事务框架
  • 分布式
    • 分布式算法
      • CAP 定理的含义
  • 分布式
    • 分布式算法
      • Paxos和Raft比较
  • 分布式
    • 分布式算法
      • 分布式一致性与共识算法
  • 分布式
    • 分布式锁
      • ⭐️分布式锁的原理及实现方式
  • 分布式
    • 搜索引擎
      • ElasticSearch与SpringBoot的集成与JPA方法的使用
  • 分布式
    • 搜索引擎
      • 全文搜索引擎 Elasticsearch 入门教程
  • 分布式
    • 搜索引擎
      • 十分钟学会使用 Elasticsearch 优雅搭建自己的搜索系统
  • 分布式
    • 搜索引擎
      • 腾讯万亿级 Elasticsearch 技术解密
  • 分布式
    • 日志系统
      • Grafana Loki 简明教程
  • 分布式
    • 日志系统
      • 分布式系统中如何优雅地追踪日志
  • 分布式
    • 日志系统
      • 如何优雅地记录操作日志?
  • 分布式
    • 日志系统
      • 日志收集组件—Flume、Logstash、Filebeat对比
  • 分布式
    • 日志系统
      • 集中式日志系统 ELK 协议栈详解
  • 分布式
    • 消息队列
      • 消息队列 - Kafka
  • 分布式
    • 消息队列
      • 消息队列 - Kafka、RabbitMQ、RocketMQ等消息中间件的对比
  • 分布式
    • 消息队列
      • 消息队列之 RabbitMQ
  • 分布式
    • 消息队列
      • 消息队列 - 使用docker-compose构建kafka集群
  • 分布式
    • 消息队列
      • 消息队列 - 分布式系统与消息的投递
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息的可靠性传输
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息的顺序性
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息队列的高可用
  • 分布式
    • 消息队列
      • 消息队列 - 消息队列设计精要
  • 分布式
    • 监控系统
      • 深度剖析开源分布式监控CAT
  • 大数据
    • Flink
      • Flink架构与核心组件
  • 微服务
    • Dubbo
      • 基于dubbo的分布式应用中的统一异常处理
  • 微服务
    • Dubbo
      • Vim快捷键
  • 微服务
    • Service Mesh
      • Istio 是什么?
  • 微服务
    • Service Mesh
      • OCTO 2.0:美团基于Service Mesh的服务治理系统详解
  • 微服务
    • Service Mesh
      • Service Mesh是什么?
  • 微服务
    • Service Mesh
      • Spring Cloud向Service Mesh迁移
  • 微服务
    • Service Mesh
      • 数据挖掘算法
  • 微服务
    • Service Mesh
      • Seata Saga 模式
  • 微服务
    • Spring Cloud
      • Seata TCC 模式
  • 微服务
    • Spring Cloud
      • Spring Cloud Config
  • 微服务
    • Spring Cloud
      • Seata AT 模式
  • 微服务
    • Spring Cloud
      • Spring Cloud Gateway
  • 微服务
    • Spring Cloud
      • Spring Cloud OpenFeign 的核心原理
  • 微服务
    • Spring Cloud
      • Seata XA 模式
  • 数据库
    • Database Version Control
      • Liquibase vs. Flyway
  • 数据库
    • Database Version Control
      • Six reasons to version control your database
  • 数据库
    • MySQL
      • How Sharding Works
  • 数据库
    • MySQL
      • MySQL InnoDB中各种SQL语句加锁分析
  • 数据库
    • MySQL
      • MySQL 事务隔离级别和锁
  • 数据库
    • MySQL
      • MySQL 索引性能分析概要
  • 数据库
    • MySQL
      • MySQL 索引设计概要
  • 数据库
    • MySQL
      • MySQL出现Waiting for table metadata lock的原因以及解决方法
  • 数据库
    • MySQL
      • MySQL的Limit性能问题
  • 数据库
    • MySQL
      • MySQL索引优化explain
  • 数据库
    • MySQL
      • MySQL索引背后的数据结构及算法原理
  • 数据库
    • MySQL
      • MySQL行转列、列转行问题
  • 数据库
    • MySQL
      • 一条SQL更新语句是如何执行的?
  • 数据库
    • MySQL
      • 一条SQL查询语句是如何执行的?
  • 数据库
    • MySQL
      • 为什么 MySQL 使用 B+ 树
  • 数据库
    • MySQL
      • 为什么 MySQL 的自增主键不单调也不连续
  • 数据库
    • MySQL
      • 为什么我的MySQL会“抖”一下?
  • 数据库
    • MySQL
      • 为什么数据库不应该使用外键
  • 数据库
    • MySQL
      • 为什么数据库会丢失数据
  • 数据库
    • MySQL
      • 事务的可重复读的能力是怎么实现的?
  • 数据库
    • MySQL
      • 大众点评订单系统分库分表实践
  • 数据库
    • MySQL
      • 如何保证缓存与数据库双写时的数据一致性?
  • 数据库
    • MySQL
      • 浅谈数据库并发控制 - 锁和 MVCC
  • 数据库
    • MySQL
      • 深入浅出MySQL 中事务的实现
  • 数据库
    • MySQL
      • 浅入浅出MySQL 和 InnoDB
  • 数据库
    • PostgreSQL
      • PostgreSQL upsert功能(insert on conflict do)的用法
  • 数据库
    • Redis
      • Redis GEO & 实现原理深度分析
  • 数据库
    • Redis
      • Redis 和 I/O 多路复用
  • 数据库
    • Redis
      • Redis分布式锁
  • 数据库
    • Redis
      • Redis实现分布式锁中的“坑”
  • 数据库
    • Redis
      • Redis总结
  • 数据库
    • Redis
      • 史上最全Redis高可用技术解决方案大全
  • 数据库
    • Redis
      • Redlock:Redis分布式锁最牛逼的实现
  • 数据库
    • Redis
      • 为什么 Redis 选择单线程模型
  • 数据库
    • TiDB
      • 新一代数据库TiDB在美团的实践
  • 数据库
    • 数据仓库
      • 实时数仓在有赞的实践
  • 数据库
    • 数据库原理
      • OLTP与OLAP的关系是什么?
  • 数据库
    • 数据库原理
      • 为什么 OLAP 需要列式存储
  • 系统设计
    • DDD
      • Domain Primitive
  • 系统设计
    • DDD
      • Repository模式
  • 系统设计
    • DDD
      • 应用架构
  • 系统设计
    • DDD
      • 聊聊如何避免写流水账代码
  • 系统设计
    • DDD
      • 领域层设计规范
  • 系统设计
    • DDD
      • 从三明治到六边形
  • 系统设计
    • DDD
      • 阿里盒马领域驱动设计实践
  • 系统设计
    • DDD
      • 领域驱动设计(DDD)编码实践
  • 系统设计
    • DDD
      • 领域驱动设计在互联网业务开发中的实践
  • 系统设计
    • 基础架构
      • 容错,高可用和灾备
  • 系统设计
    • 数据聚合
      • GraphQL及元数据驱动架构在后端BFF中的实践
  • 系统设计
    • 数据聚合
      • 高效研发-闲鱼在数据聚合上的探索与实践
  • 系统设计
    • 服务安全
      • JSON Web Token 入门教程
  • 系统设计
    • 服务安全
      • 你还在用JWT做身份认证嘛?
  • 系统设计
    • 服务安全
      • 凭证(Credentials)
  • 系统设计
    • 服务安全
      • 授权(Authorization)
  • 系统设计
    • 服务安全
      • 理解OAuth2.0
  • 系统设计
    • 服务安全
      • 认证(Authentication)
  • 系统设计
    • 架构案例
      • 微信 Android 客户端架构演进之路
  • 系统设计
    • 高可用架构
      • 业务高可用的保障:异地多活架构
  • 计算机基础
    • 字符编码
      • Base64原理解析
  • 计算机基础
    • 字符编码
      • 字符编码笔记:ASCII,Unicode 和 UTF-8
  • 计算机基础
    • 操作系统
      • 为什么 CPU 访问硬盘很慢
  • 计算机基础
    • 操作系统
      • 为什么 HTTPS 需要 7 次握手以及 9 倍时延
  • 计算机基础
    • 操作系统
      • 为什么 Linux 默认页大小是 4KB
  • 计算机基础
    • 操作系统
      • 磁盘IO那些事
  • 计算机基础
    • 操作系统
      • 虚拟机的3种网络模式
  • 计算机基础
    • 服务器
      • mac终端bash、zsh、oh-my-zsh最实用教程
  • 计算机基础
    • 服务器
      • Nginx强制跳转Https
  • 计算机基础
    • 服务器
      • curl 的用法指南
  • 计算机基础
    • 网络安全
      • 如何设计一个安全的对外接口?
  • 计算机基础
    • 网络安全
      • 浅谈常见的七种加密算法及实现
  • 计算机基础
    • 网络编程
      • MQTT - The Standard for IoT Messaging
  • 计算机基础
    • 网络编程
      • 两万字长文 50+ 张趣图带你领悟网络编程的内功心法
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有 TIME_WAIT 状态
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有性能问题
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有粘包问题
  • 计算机基础
    • 网络编程
      • 为什么 TCP 建立连接需要三次握手
  • 计算机基础
    • 网络编程
      • 为什么 TCP/IP 协议会拆分数据
  • 计算机基础
    • 网络编程
      • 使用 OAuth 2 和 JWT 为微服务提供安全保障
  • 计算机基础
    • 网络编程
      • 四种常见的 POST 提交数据方式
  • 计算机基础
    • 网络编程
      • 有赞TCP网络编程最佳实践
  • 计算机基础
    • 网络编程
      • 看完这篇HTTP,跟面试官扯皮就没问题了
  • 计算机基础
    • 网络编程
      • 详细解析 HTTP 与 HTTPS 的区别
  • 质量&效率
    • 快捷键
      • Idea快捷键(Mac版)
  • 质量&效率
    • 快捷键
      • Shell快捷键
  • 质量&效率
    • 快捷键
      • conduit
  • 质量&效率
    • 敏捷开发
      • Scrum的3种角色
  • 质量&效率
    • 敏捷开发
      • Scrum的4种会议
  • 质量&效率
    • 敏捷开发
      • ThoughtWorks的敏捷开发
  • 质量&效率
    • 敏捷开发
      • 敏捷开发入门教程
  • 运维&测试
    • Docker
      • Docker (容器) 的原理
  • 运维&测试
    • Docker
      • Docker Compose:链接外部容器的几种方式
  • 运维&测试
    • Docker
      • Docker 入门教程
  • 运维&测试
    • Docker
      • Docker 核心技术与实现原理
  • 运维&测试
    • Docker
      • Dockerfile 最佳实践
  • 运维&测试
    • Docker
      • Docker开启Remote API 访问 2375端口
  • 运维&测试
    • Docker
      • Watchtower - 自动更新 Docker 镜像与容器
  • 运维&测试
    • Kubernetes
      • Kubernetes 介绍
  • 运维&测试
    • Kubernetes
      • Kubernetes 在有赞的实践
  • 运维&测试
    • Kubernetes
      • Kubernetes 学习路径
  • 运维&测试
    • Kubernetes
      • Kubernetes如何改变美团的云基础设施?
  • 运维&测试
    • Kubernetes
      • Kubernetes的三种外部访问方式:NodePort、LoadBalancer 和 Ingress
  • 运维&测试
    • Kubernetes
      • 谈 Kubernetes 的架构设计与实现原理
  • 运维&测试
    • 压测
      • 全链路压测平台(Quake)在美团中的实践
  • 运维&测试
    • 测试
      • Cpress - JavaScript End to End Testing Framework
  • 运维&测试
    • 测试
      • 代码覆盖率-JaCoCo
  • 运维&测试
    • 测试
      • 浅谈代码覆盖率
  • 运维&测试
    • 测试
      • 测试中 Fakes、Mocks 以及 Stubs 概念明晰
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP中的Bean是如何被AOP代理的
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP原生动态代理和Cglib动态代理
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP实现方式(xml&注解)
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP是如何收集切面类并封装的
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP概述
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP的底层核心后置处理器
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP的延伸知识
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(一)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(三)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(二)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(五)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(四) - 循环依赖与解决方案
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - 启动引导
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot JarLauncher
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot Web Mvc 自动装配
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 使用ApplicationListener监听器
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 声明式事务
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 嵌入式容器
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot引起的“堆外内存泄漏”排查及经验总结
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot的启动流程
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot自动化配置源码分析
  • Java FrameWorks
    • Spring
      • Spring Boot
        • 如何自定义Spring Boot Starter?
  • Java FrameWorks
    • Spring
      • Spring IOC
        • IOC - 模块装配和条件装配
  • Java FrameWorks
    • Spring
      • Spring IOC
        • IOC - 配置源(xml,注解)
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Environment
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring ApplicationContext
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanDefinition
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanFactory
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanFactoryPostProcessor
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanPostProcessor
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(一) - 概述
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(三) - 实例化阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(二) - BeanDefinition
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(五) - 销毁阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(四) - 初始化阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring ComponentScan
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Events
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 基础篇
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 总结
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 进阶篇
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC容器的生命周期
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Resource
  • Java FrameWorks
    • Spring
      • Spring MVC
        • DispatcherServlet的初始化原理
  • Java FrameWorks
    • Spring
      • Spring MVC
        • DispatcherServlet的核心工作原理
  • Java FrameWorks
    • Spring
      • Spring MVC
        • WebMvc的架构设计与组件功能解析
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Boot 2 + Spring Security 5 + JWT 的单页应用 Restful 解决方案
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Security Oauth
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Security
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • DispatcherHandler的工作原理(传统方式)
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • DispatcherHandler的工作原理(函数式端点)
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • WebFlux的自动装配
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • 快速了解响应式编程与Reactive
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • 快速使用WebFlux
  • 分布式
    • 协调服务
      • Zookeeper
        • Zookeeper - 客户端之 Curator
  • 分布式
    • 协调服务
      • Zookeeper
        • 详解分布式协调服务 ZooKeeper
  • 分布式
    • 协调服务
      • etcd
        • 高可用分布式存储 etcd 的实现原理
  • 数据库
    • Database Version Control
      • Flyway
        • Database Migrations with Flyway
  • 数据库
    • Database Version Control
      • Flyway
        • How Flyway works
  • 数据库
    • Database Version Control
      • Flyway
        • Rolling Back Migrations with Flyway
  • 数据库
    • Database Version Control
      • Flyway
        • The meaning of the concept of checksums
  • 数据库
    • Database Version Control
      • Liquibase
        • Introduction to Liquibase Rollback
  • 数据库
    • Database Version Control
      • Liquibase
        • LiquiBase中文学习指南
  • 数据库
    • Database Version Control
      • Liquibase
        • Use Liquibase to Safely Evolve Your Database Schema
  • 系统设计
    • 流量控制
      • RateLimiter
        • Guava Rate Limiter实现分析
  • 系统设计
    • 流量控制
      • Sentinel
        • Sentinel 与 Hystrix 的对比
  • 系统设计
    • 流量控制
      • Sentinel
        • Sentinel工作主流程
  • 系统设计
    • 流量控制
      • 算法
        • 分布式服务限流实战
  • 系统设计
    • 解决方案
      • 秒杀系统
        • 如何设计一个秒杀系统
  • 系统设计
    • 解决方案
      • 红包系统
        • 微信高并发资金交易系统设计方案--百亿红包背后的技术支撑
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 什么是预排序遍历树算法(MPTT,Modified Preorder Tree Traversal)
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 加密算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 推荐系统算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • linkerd
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 查找算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 缓存淘汰算法中的LRU和LFU
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 负载均衡算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Paxos算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Raft算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Snowflake算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - ZAB算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - 一致性Hash算法
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Bitmap & Bloom Filter
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Map & Reduce
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Trie树/数据库/倒排索引
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 分治/hash/排序
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 双层桶划分
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 外(磁盘文件)排序
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 布隆过滤器
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理算法
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 文本预处理:后缀树(Suffix Tree)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:BM 算法 (Boyer-Moore)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:KMP 算法(Knuth-Morris-Pratt)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:朴素算法(Naive)(暴力破解)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 分支限界算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 分治算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 动态规划算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 回溯算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 贪心算法
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 十大排序算法
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(一)之3种简单排序(选择,冒泡,直接插入)
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(三)之堆排序
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(二)之希尔排序
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(四)之归并排序
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 树的高度和深度
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 红黑树深入剖析及Java实现
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 线性结构 - Hash
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 线性结构 - 数组、链表、栈、队列
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 逻辑结构 - 树
  • 运维&测试
    • 测试
      • Spock
        • Groovy 简明教程
  • 运维&测试
    • 测试
      • Spock
        • Spock 官方文档
  • 运维&测试
    • 测试
      • Spock
        • Spock单元测试框架介绍以及在美团优选的实践
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(一)
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(三)
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(二)
  • 运维&测试
    • 测试
      • TDD
        • 测试驱动开发(TDD)- 原理篇
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Nacos
          • Nacos 服务注册的原理
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Nacos
          • Nacos 配置中心原理分析
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • 服务调用过程
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Bus
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Consul
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Stream
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Sentinel
          • Sentinel 与 Hystrix 的对比
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Sentinel
          • Sentinel
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • How Hystrix Works
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Hystrix
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Hystrix原理与实战
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Spring Cloud Hystrix基本原理
由 GitBook 提供支持
在本页
  • 1. 什么是后缀树
  • 2. 参考

这有帮助吗?

  1. 计算机基础
  2. 数据结构与算法
  3. 字符串匹配算法

字符串匹配 - 文本预处理:后缀树(Suffix Tree)

上一页字符串匹配算法下一页计算机基础

最后更新于2年前

这有帮助吗?

[TOC]

1. 什么是后缀树

上述字符串匹配算法(朴素的字符串匹配算法, KMP 算法, Boyer-Moore算法)均是通过对模式(Pattern)字符串进行预处理的方式来加快搜索速度。对 Pattern 进行预处理的最优复杂度为 O(m),其中 m 为 Pattern 字符串的长度。那么,有没有对文本(Text)进行预处理的算法呢?本文即将介绍一种对 Text 进行预处理的字符串匹配算法:后缀树(Suffix Tree)。

后缀树的性质:

  • 存储所有 n(n-1)/2 个后缀需要 O(n) 的空间,n 为的文本(Text)的长度;

  • 构建后缀树需要 O(dn) 的时间,d 为字符集的长度(alphabet);

  • 对模式(Pattern)的查询需要 O(dm) 时间,m 为 Pattern 的长度;

2021-02-19-ixeLak

下面是根据集合 {bear, bell, bid, bull, buy, sell, stock, stop} 所构建的 Trie 树。

我们观察上面这颗 Trie,对于关键词 "bear",字符 "a" 和 "r" 所在的节点没有其他子节点,所以可以考虑将这两个节点合并,如下图所示。

这样,我们就得到了一棵压缩过的 Trie,称为压缩字典树(Compressed Trie)。

而后缀树(Suffix Tree)则首先是一棵 Compressed Trie,其次,后缀树中存储的关键词为所有的后缀。这样,实际上我们也就得到了构建后缀树的抽象过程:

  • 根据文本 Text 生成所有后缀的集合;

  • 将每个后缀作为一个单独的关键词,构建一棵 Compressed Trie。

比如,对于文本 "banana\0",其中 "\0" 作为文本结束符号。下面是该文本所对应的所有后缀。

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

将每个后缀作为一个关键词,构建一棵 Trie。

然后,将独立的节点合并,形成 Compressed Trie。

则上面这棵树就是文本 "banana\0" 所对应的后缀树。

现在我们先熟悉两个概念:显式后缀树(Explicit Suffix Tree)和隐式后缀树(Implicit Suffix Tree)。

下面用字符串 "xabxa" 举例说明两者的区别,其包括后缀列表如下。

xabxa
abxa
bxa
xa
a

我们发现,后缀 "xa" 和 "a" 已经分别包含在后缀 "xabxa" 和 "abxa" 的前缀中,这样构造出来的后缀树称为隐式后缀树(Implicit Suffix Tree)。

而如果不希望这样的情形发生,可以在每个后缀的结尾加上一个特殊字符,比如 "$" 或 "#" 等,这样我们就可以使得后缀保持唯一性。

xabxa$
abxa$
bxa$
xa$
a$
$

Suffix Tree 与 Trie 的不同在于,边(Edge)不再只代表单个字符,而是通过一对整数 [from, to] 来表示。其中 from 和 to 所指向的是 Text 中的位置,这样每个边可以表示任意的长度,而且仅需两个指针,耗费 O(1) 的空间。

首先,我们从一个最简单的字符串 Text = "abc" 开始实践构建后缀树,"abc" 中没有重复字符,使得构建过程更简单些。构建过程的步骤是:从左到右,对逐个字符进行操作。

abc

第 1 个字符是 "a",创建一条边从根节点(root)到叶节点,以 [0, #] 作为标签代表其在 Text 中的位置从 0 开始。使用 "#" 表示末尾,可以认为 "#" 在 "a" 的右侧,位置从 0 开始,则当前位置 "#" 在 1 位。

其代表的后缀意义如下。

第 1 个字符 "a" 处理完毕,开始处理第 2 个字符 "b"。涉及的操作包括:

  • 扩展已经存在的边 "a" 至 "ab";

  • 插入一条新边以表示 "b";

其代表的后缀意义如下。

这里,我们观察到了两点:

  • "ab" 边的表示 [0, #] 与之前是相同的,当 "#" 位置由 1 挪至 2 时,[0, #] 所代表的意义自动地发生了改变。

  • 每条边的空间复杂度为 O(1),即只消耗两个指针,而与边所代表的字符数量无关;

接着再处理第 3 个字符 "c",重复同样的操作,"#" 位置向后挪至第 3 位:

其代表的后缀意义如下。

此时,我们观察到:

  • 经过上面的步骤后,我们得到了一棵正确的后缀树;

  • 操作步骤的数量与 Text 中的字符的数量一样多;

  • 每个步骤的工作量是 O(1),因为已存在的边都是依据 "#" 的挪动而自动更改的,仅需为最后一个字符添加一条新边,所以时间复杂度为 O(1)。则,对于一个长度为 n 的 Text,共需要 O(n) 的时间构建后缀树。

当然,我们进展的这么顺利,完全是因为所操作的字符串 Text = "abc" 太简单,没有任何重复的字符。那么现在我们来处理一个更复杂一些的字符串 Text = "abcabxabcd"。

abcabxabcd

同上面的例子类似的是,这个新的 Text 同样以 "abc" 开头,但其后接着 "ab","x","abc","d" 等,并且出现了重复的字符。

前 3 个字符 "abc" 的操作步骤与上面介绍的相同,所以我们会得到下面这颗树:

当 "#" 继续向后挪动一位,即第 4 位时,隐含地意味着已有的边会自动的扩展为:

即 [0, #], [1, #], [2, #] 都进行了自动的扩展。按照上面的逻辑,此时应该为剩余后缀 "a" 创建一条单独的边。但,在做这件事之前,我们先引入两个概念。

  • 活动点(active point),是一个三元组,包括(active_node, active_edge, active_length);

  • 剩余后缀数(remainder),是一个整数,代表着还需要插入多少个新的后缀;

如何使用这两个概念将在下面逐步地说明。不过,现在我们可以先确定两件事:

  • 在 Text = "abc" 的例子中,活动点(active point)总是 (root, '\0x', 0)。也就是说,活动节点(active_node)总是根节点(root),活动边(active_edge)是空字符 '\0x' 所指定的边,活动长度(active_length)是 0。

  • 在每个步骤开始时,剩余后缀数(remainder)总是 1。意味着,每次我们要插入的新的后缀数目为 1,即最后一个字符。

# = 3, active_point = (root, '\0x', 1), remainder = 1

当处理第 4 字符 "a" 时,我们注意到,事实上已经存在一条边 "abca" 的前缀包含了后缀 "a"。在这种情况下:

  • 我们不再向 root 插入一条全新的边,也就是 [3, #]。相反,既然后缀 "a" 已经被包含在树中的一条边上 "abca",我们保留它们原来的样子。

  • 设置 active point 为 (root, 'a', 1),也就是说,active_node 仍为 root,active_edge 为 'a',active_length 为 1。这就意味着,活动点现在是从根节点开始,活动边是以 'a' 开头的某个边,而位置就是在这个边的第 1 位。这个活动边的首字符为 'a',实际上,仅会有一个边是以一个特定字符开头的。

  • remainder 的值需要 +1,也就是 2。

# = 4, active_point = (root, 'a', 1), remainder = 2

此时,我们还观察到:当我们要插入的后缀已经存在于树中时,这颗树实际上根本就没有改变,我们仅修改了 active point 和 remainder。那么,这颗树也就不再能准确地描述当前位置了,不过它却正确地包含了所有的后缀,即使是通过隐式的方式(Implicitly)。因此,处理修改变量,这一步没有其他工作,而修改变量的时间复杂度为 O(1)。

继续处理下一个字符 "b","#" 继续向后挪动一位,即第 5 位时,树被自动的更新为:

由于剩余后缀数(remainder)的值为 2,所以在当前位置,我们需要插入两个最终后缀 "ab" 和 "b"。这是因为:

  • 前一步的 "a" 实际上没有被真正的插入到树中,所以它被遗留了下来(remained),然而我们又向前迈了一步,所以它现在由 "a" 延长到 "ab";

  • 还有就是我们需要插入新的最终后缀 "b";

实际操作时,我们就是修改 active point,指向 "a" 后面的位置,并且要插入新的最终后缀 "b"。但是,同样的事情又发生了,"b" 事实上已经存在于树中一条边 "bcab" 的前缀上。那么,操作可以归纳为:

  • 修改活动点为 (root, 'a', 2),实际还是与之前相同的边,只是将指向的位置向后挪到 "b",修改了 active_length,即 "ab"。

  • 增加剩余后缀数(remainder)为 3,因为我们又没有为 "b" 插入全新的边。

# = 5, active_point = (root, 'a', 2), remainder = 3

再具体一点,我们本来准备插入两个最终后缀 "ab" 和 "b",但因为 "ab" 已经存在于其他的边的前缀中,所以我们只修改了活动点。对于 "b",我们甚至都没有考虑要插入,为什么呢?因为如果 "ab" 存在于树中,那么他的每个后缀都一定存在于树中。虽然仅仅是隐含性的,但却一定存在,因为我们一直以来就是按照这样的方式来构建这颗树的。

继续处理下一个字符 "x","#" 继续向后挪动一位,即第 6 位时,树被自动的更新为:

由于剩余后缀数(Remainder)的值为 3,所以在当前位置,我们需要插入 3 个最终后缀 "abx", "bx" 和 "x"。

活动点告诉了我们之前 "ab" 结束的位置,所以仅需跳过这一位置,插入新的 "x" 后缀。"x" 在树中还不存在,因此我们分裂 "abcabx" 边,插入一个内部节点:

分裂和插入新的内部节点耗费 O(1) 时间。

现在,我们已经处理了 "abx",并且把 remainder 减为 2。然后继续插入下一个后缀 "bx",但做这个操作之前需要先更新活动点,这里我们先做下部分总结。

对于上面对边的分裂和插入新的边的操作,可以总结为 Rule 1,其应用于当 active_node 为 root 节点时。

Rule 1

当向根节点插入时遵循:

  • active_node 保持为 root;

  • active_edge 被设置为即将被插入的新后缀的首字符;

  • active_length 减 1;

因此,新的活动点为 (root, 'b', 1),表明下一个插入一定会发生在边 "bcabx" 上,在 1 个字符之后,即 "b" 的后面。

# = 6, active_point = (root, 'b', 1), remainder = 2

我们需要检查 "x" 是否在 "b" 后面出现,如果出现了,就是我们上面见到过的样子,可以什么都不做,只更新活动点。如果未出现,则需要分裂边并插入新的边。

同样,这次操作也花费了 O(1) 时间。然后将 remainder 更新为 1,依据 Rule 1 活动点更新为 (root, 'x', 0)。

# = 6, active_point = (root, 'x', 0), remainder = 1

此时,我们将归纳出 Rule 2。

Rule 2

  • 如果我们分裂(Split)一条边并且插入(Insert)一个新的节点,并且如果该新节点不是当前步骤中创建的第一个节点,则将先前插入的节点与该新节点通过一个特殊的指针连接,称为后缀连接(Suffix Link)。后缀连接通过一条虚线来表示。

继续上面的操作,插入最终后缀 "x"。因为活动点中的 active_length 已经降到 0,所以插入操作将发生在 root 上。由于没有以 "x" 为前缀的边,所以插入一条新的边:

这样,这一步骤中的所有操作就完成了。

# = 6, active_point = (root, '\0x', 0), remainder = 1

继续处理下一个字符 "a","#" 继续向后挪动一位。发现后缀 "a" 已经存在于数中的边中,所以仅更新 active point 和 remainder。

# = 7, active_point = (root, 'a', 1), remainder = 2

继续处理下一个字符 "b","#" 继续向后挪动一位。发现后缀 "ab" 和 "b" 都已经存在于树中,所以仅更新 active point 和 remainder。这里我们先称 "ab" 所在的边的节点为 node1。

# = 8, active_point = (root, 'a', 2), remainder = 3

继续处理下一个字符 "c","#" 继续向后挪动一位。此时由于 remainder = 3,所以需要插入 "abc","bc","c" 三个后缀。"c" 实际上已经存在于 node1 后的边上。

# = 9, active_point = (node1, 'c', 1), remainder = 4

继续处理下一个字符 "d","#" 继续向后挪动一位。此时由于 remainder = 4,所以需要插入 "abcd","bcd","cd","d" 四个后缀。

上图中的 active_node,当节点准备分裂时,被标记了红色。则归纳出了 Rule 3。

Rule 3

  • 当从 active_node 不为 root 的节点分裂边时,我们沿着后缀连接(Suffix Link)的方向寻找节点,如果存在一个节点,则设置该节点为 active_noe;如果不存在,则设置 active_node 为 root。active_edge 和 active_length 保持不变。

所以,现在活动点为 (node2, 'c', 1),其中 node2 为下图中的红色节点:

# = 10, active_point = (node2, 'c', 1), remainder = 3

由于对 "abcd" 的插入已经完成,所以将 remainder 的值减至 3,并且开始处理下一个剩余后缀 "bcd"。此时需要将边 "cabxabcd" 分裂,然后插入新的边 "d"。根据 Rule 2,我们需要在之前插入的节点与当前插入的节点间创建一条新的后缀连接。

此时,我们观察到,后缀连接(Suffix Link)让我们能够重置活动点,使得对下一个后缀的插入操作仅需 O(1) 时间。从上图也确认了,"ab" 连接的是其后缀 "b",而 "abc" 连接的是其后缀 "bc"。

当前操作还没有完成,因为 remainder 是 2,根绝 Rule 3 我们需要重新设置活动点。因为上图中的红色 active_node 没有后缀连接(Suffix Link),所以活动点被设置为 root,也就是 (root, 'c', 1)。

# = 10, active_point = (root, 'c', 1), remainder = 2

因此,下一个插入操作 "cd" 将从 Root 开始,寻找以 "c" 为前缀的边 "cabxabcd",这也引起又一次分裂:

由于此处又创建了一个新的内部节点,依据 Rule 2,我们需要建立一条与前一个被创建内节点的后缀连接。

然后,remainder 减为 1,active_node 为 root,根据 Rule 1 则活动点为 (root, 'd', 0)。也就是说,仅需在根节点上插入一条 "d" 新边。

# = 10, active_point = (root, 'd', 0), remainder = 1

整个步骤完成。

总体上看,我们有一系列的观察结果:

  • 在每一步中将 "#" 向右移动 1 位时,所有叶节点自动更新的时间为 O(1);

  • 但实际上并没有处理这两种情况:

    • 从前一步中遗留的后缀;

    • 当前步骤中的最终字符;

  • remainder 告诉了我们还余下多少后缀需要插入。这些插入操作将逐个的与当前位置 "#" 之前的后缀进行对应,我们需要一个接着一个的处理。更重要的是,每次插入需要 O(1) 时间,活动点准确地告诉了我们改如何进行,并且也仅需在活动点中增加一个单独的字符。为什么?因为其他字符都隐式地被包含了,要不也就不需要 active point 了。

  • 每次插入之后,remainder 都需要减少,如果存在后缀连接(Suffix Link)的话就续接至下一个节点,如果不存在则返回值 root 节点(Rule 3)。如果已经是在 root 节点了,则依据 Rule 1 来修改活动点。无论哪种情况,仅需 O(1) 时间。

  • 如果这些插入操作中,如果发现要被插入的字符已经存在于树中,则什么也不做,即使 remainder > 0。原因是要被插入的字符实际上已经隐式地被包含在了当前的树中。而 remainder > 0 则确保了在后续的操作中会进行处理。

  • 那么如果在算法结束时 remainder > 0 该怎么办?这种情况说明了文本的尾部字符串在之前某处已经出现过。此时我们需要在尾部添加一个额外的从未出现过的字符,通常使用 "$" 符号。为什么要这么做呢?如果后续我们用已经完成的后缀树来查找后缀,匹配结果一定要出现在叶子节点,否则就会出现很多假匹配,因为很多字符串已经被隐式地包含在了树中,但实际并不是真正的后缀。同时,最后也强制 remainder = 0,以此来保证所有的后缀都形成了叶子节点。尽管如此,如果想用后缀树搜索常规的子字符串,而不仅是搜索后缀,这么做就不是必要的了。

  • 那么整个算法的复杂度是多少呢?如果 Text 的长度为 n,则有 n 步需要执行,算上 "$" 则有 n+1 步。在每一步中,我们要么什么也不做,要么执行 remainder 插入操作并消耗 O(1) 时间。因为 remainder 指示了在前一步中我们有多少无操作次数,在当前步骤中每次插入都会递减,所以总体的数量还是 n。因此总体的复杂度为 O(n)。

  • 然而,还有一小件事我还没有进行适当的解释。那就是,当我们续接后缀连接时,更新 active point,会发现 active_length 可能与 active_node 协作的并不好。例如下面这种情况:

假设 active point 是红色节点 (red, 'd', 3),因此它指向 "def" 边中 "f" 之后的位置。现在假设我们做了必要的更新,而且依据 Rule 3 续接了后缀连接并修改了活动点,新的 active point 是 (green, 'd', 3)。然而从绿色节点出发的 "d" 边是 "de",这条边只有 2 个字符。为了找到合适的活动点,看起来我们需要添加一个到蓝色节点的边,然后重置活动点为 (blue, 'f', 1)。

在最坏的情况下,active_length 可以与 remainder 一样大,甚至可以与 n 一样大。而恰巧这种情况可能刚好在找活动点时发生,那么我们不仅需要跳过一个内部节点,可能是多个节点,最坏的情况是 n 个。由于每步里 remainder 是 O(n),续接了后缀连接之后的对活动点的后续调整也是 O(n),那么是否意味着整个算法潜在需要 O(n2) 时间呢?

我认为不是。理由是如果我们确实需要调整活动点(例如,上图中从绿色节点调整到蓝色节点),那么这就引入了一个拥有自己的后缀连接的新节点,而且 active_length 将减少。当我们沿着后缀连接向下走,就要插入剩余的后缀,且只是减少 active_length,使用这种方法可调整的活动点的数量不可能超过任何给定时刻的 active_length。由于 active_length 从来不会超过 remainder,而 remainder 不仅在每个单一步骤里是 O(n),而且对整个处理过程进行的 remainder 递增的总数也是 O(n),因此调整活动点的数目也就限制在了 O(n)。

2. 参考

  • https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

  • https://www.cnblogs.com/gaochundong/p/suffix_tree.html

  • https://blog.csdn.net/v_july_v/article/details/6897097

  • https://www.pdai.tech/md/algorithm/alg-domain-char-match-st.html

在《》一文中,介绍了一种特殊的树状信息检索数据结构:字典树(Trie)。Trie 将关键词中的字符按顺序添加到树中的节点上,这样从根节点开始遍历,就可以确定指定的关键词是否存在于 Trie 中。

2021-02-19-LXpIqi
2021-02-19-uICZSz
2021-02-19-J6a2oz
2021-02-19-jIwHsI
2021-02-19-gJmpuH

在 1995 年,Esko Ukkonen 发表了论文《》,描述了在线性时间内构建后缀树的方法。下面尝试描述 Ukkonen 算法的基本实现原理,从简单的字符串开始描述,然后扩展到更复杂的情形。

2021-02-19-Wk1vTF
2021-02-19-aEeqkB
2021-02-19-BxSWIV
2021-02-19-uZ11Mu
2021-02-19-peHnd5
2021-02-19-5e7p3B
2021-02-19-zTP3Od
2021-02-19-zHS35e
2021-02-19-BBxBoL
2021-02-19-88wKrf
2021-02-19-TCZDm3
2021-02-19-JM6Lmi
2021-02-19-EpCZQE
2021-02-19-mRF3gh
2021-02-19-lJHTBN
2021-02-19-EyJNhJ
2021-02-19-YiWjuU
2021-02-19-OJdioh
2021-02-19-pQJcbl
2021-02-19-ySTbgR
2021-02-19-JRKf8d
字典树(前缀树)
On-line construction of suffix trees (opens new window)