首页 技术 正文
技术 2022年11月8日
0 收藏 899 点赞 1,769 浏览 670 个字

双数组Trie树索引的可操作性研究.pdf

提示:任一状态点的移动,会影响其Trie树中父节
点的base值的选择以及兄弟结点位置的变动,而兄
弟结点的移动又须变更相应的子节点的check值。

设待插入的词或其子串为‘c1c2c3…’。由双数
组的结构可以看出,当索引中已经存在以单个字符G
为状态的状态点时,所需的操作与建立双数组时的相
同,不影响双数组的整体结构,我们把符合这种情况
的词或其子串统称为“稳定词”。

(1)字符c1不在序列码表中,把c1加入序列码表中,设定其码值为数组大小。

(2) 索引中存在以字符c1,以及(c1,….ci-2)ci-1
为状态的状态点,但字符Ci不在序列码表中。这时要把ci加入序列码表。

比如:青年,青菜,已经在索引中,但青壮年中的‘壮‘不在序列码中,这时需要调整’壮‘的兄弟结点‘年’‘菜’,的插入位置,并修改兄弟结点孩子的check值。青年,青菜,没有孩子结点。

(3) 索引中存在以字符c1以及c1…ci-2ci-1’
为状态的状态点,字符Ci也在序列码表中,但状态点
c1…ci-2ci-1ci不存在索引中。

如: 白菜,白金在索引中,白伯不在索引中,需要修改白的base值,及白菜,白金的插入位置。并修改白菜心(白菜的孩子结点)的check值。

原先索引中已经存在:阿伯,现在新插入结点白伯,类似于: 青菜,白菜。

(4) ci 在序列码中,但ci不是首字状态点。把ci对应位置空出来,存放ci。ci位置原先结点及其兄弟结点插入其他位置,并修改其父节点的base值,孩子结点的check值,类似于relocate。

下一篇: linux笔记1
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,104
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,580
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,428
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,200
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,835
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,918