[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN108153907B - 通过16位Trie树实现空间优化的词典存储管理方法 - Google Patents

通过16位Trie树实现空间优化的词典存储管理方法 Download PDF

Info

Publication number
CN108153907B
CN108153907B CN201810046757.2A CN201810046757A CN108153907B CN 108153907 B CN108153907 B CN 108153907B CN 201810046757 A CN201810046757 A CN 201810046757A CN 108153907 B CN108153907 B CN 108153907B
Authority
CN
China
Prior art keywords
node
dictionary
trie tree
data
bit trie
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN201810046757.2A
Other languages
English (en)
Other versions
CN108153907A (zh
Inventor
肖英
屈晓芳
张宇
龚德浪
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Hangzhou Code Pigeon Intelligent Technology Co ltd
China Jiliang University
Original Assignee
Hangzhou Daimage Intelligent Technology Co ltd
China Jiliang University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Hangzhou Daimage Intelligent Technology Co ltd, China Jiliang University filed Critical Hangzhou Daimage Intelligent Technology Co ltd
Priority to CN201810046757.2A priority Critical patent/CN108153907B/zh
Publication of CN108153907A publication Critical patent/CN108153907A/zh
Application granted granted Critical
Publication of CN108153907B publication Critical patent/CN108153907B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22Indexing; Data structures therefor; Storage structures
    • G06F16/2228Indexing structures
    • G06F16/2246Trees, e.g. B+trees
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22Indexing; Data structures therefor; Storage structures
    • G06F16/2219Large Object storage; Management thereof

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明提供一种通过16位Trie树实现空间优化的词典存储管理方法,该方法包括以下步骤:获取完整的词典数据;创建管理链表,将词典数据与链表的根结点相关联;根据词典数据信息,从链表根结点构建16位Trie树实现对词典数据的存储管理。与现有的方法比较,本发明提出了通过16位Trie树实现空间优化的词典存储管理方法,利用映射表结构下构建16位Trie树的词典数据,使得Trie树在空间上更加紧凑的同时保证复杂度基本不变,提高了词典构建和索引以及修改删除的速度。本发明提出的算法与已有的Trie树比较,不仅可以随时对词典进行修改、遍历等存储管理操作,同时在16位Trie树构建时就能够进行排序,减少了词典更新时的开销,又保持了较高的索引效率。

Description

通过16位Trie树实现空间优化的词典存储管理方法
技术领域
本发明属于数据结构和信息管理领域,尤其涉及一种通过16位Trie树实现空间优化的词典存储管理方法。
背景技术
在现代社会,随着互联网的快速发展和智能移动设备的大量普及,尤其是大数据时代的到来,各种文化和知识不断充斥着我们的大脑,我们对各式信息的需求越来越多,可是有时候面对太过复杂而且繁多的信息量时,我们会感到无所适从,如何对这些大规模数据文件进行高效地存储管理成为一个新的挑战。其中Trie树作为一种数据结构经常被用在大规模数据文件存储管理领域,帮助我们处理各种数据。传统的Trie树是一种高效的索引树,可以建立有效的数据检索组织结构,其核心思想是以空间换时间,利用字符串的公共前缀来降低查询时间以提高效率,最大限度地减少无谓的字符串比较。
传统上,Trie树用一个矩阵形式的二维数组或是一个列表的形式的链表来表示。由于矩阵形式包含了许多空元素,是一个稀疏的数据结构,空间消耗会很大。而用列表形式来表示的Trie树虽然空间上更紧凑,但是它检索速度并没有那么快。之后,Aoe提出用双数组实现 Trie树,虽然双数组Trie树算法有效的降低了Trie树结构的空间浪费但是仍然存在着一些问题,首先就是与动态检索方法相比插入时间慢,不能处理频繁的更新。另外一个问题就是双数组的空间效率随着删除数量的增加而降低,因为它保留了删除产生的空元素。此外对于基于双数组结构实现的Trie树的词典存储管理方法还有另一个问题:每次进行修改、遍等操作都需要从根结点开始并且可能面临要移动大量已构建好的数据问题。
发明内容
为了解决上述技术问题,本发明提供一种通过16位Trie树实现空间优化的词典存储管理方法,该方法包括以下步骤:获取完整的词典数据;创建管理链表,将词典数据与链表的根结点相关联;根据词典数据信息,从链表根结点构建16位Trie树实现对词典数据的存储管理。与现有的方法比较,本发明提出了通过16位Trie树实现空间优化的词典存储管理方法,利用映射表结构下构建16位Trie树的词典数据,使得Trie树在空间上更加紧凑的同时保证复杂度基本不变,提高了词典构建和索引以及修改删除的速度。本发明提出的算法与已有的Trie 树比较,不仅可以随时对词典进行修改、遍历等存储管理操作,同时在16位Trie树构建时就能够进行排序,减少了词典更新时的开销,又保持了较高的索引效率。
为此,本发明实施例公开了一种通过16位Trie树实现空间优化的词典存储管理方法。该方法包括以下步骤:获取完整的词典数据;构建16位Trie树实现对词典数据的存储管理;构建16位Trie树节点(非根结点)信息leafsInfoMap映射表。
优选地,所述创建16位Trie树包括以下步骤:
a.获取词典数据信息的第一个字节,根据该字节的值寻找所对应的根节点,并与其关联;
b.在步骤a的基础上,以该节点作为父节点,并将其作为起始状态;
c.将词典数据信息的下一字节的高四位作为其子节点,将其与父节点相关联;
d.以高四位作为父节点,将该字节的低四位作为其子节点,将其与父节点相关联;
e.再次获取词典数据的下一字节,重复c,d步骤,直到获得词典数据最后一个字节,执行 d步骤;
f.获得词典数据最后一字节,将其低四位作为最终状态,完成树的构建。
优选地,所述的节点信息包括:
leafsInfo:子节点列表信息;
nodeValue:当前节点所代表的值;
endKey:当前节点是否为终端结点
leafs:子节点以及数据指针;
优选地,所述16位Trie树中的当前节点的子节点列表信息值用16位大小的leafsInfo表示。
优选地,所述16位Trie树中的节点值用nodeValue表示,该值从0到15,用于表示节点所代表的值。
优选地,所述16位Trie树中的节点当前存储的子节点指针以及数据指针的数组用leafs 表示,其中子节点指针指向当前节点所对应的子节点,数据指针指向当前节点所对应的数据,当子节点不存在并且数据指针也不存在时,leafs元素个数为0,当子节点存在时,leafs元素个数为子节点数量+1(其中数据指针占用一个元素)。
优选地,所述节点是否为终端结点用endKey表示,0表示为非终端结点,1表示为终端结点。
优选地,所述的leafsInfoMap映射表是词典数据中的节点(非根结点)信息的可能组合,用一65536×17大小的二维数组来表示。
本发明实例提供的一种通过16位Trie树实现空间优化的存储管理方法,利用映射表结构下构建16位Trie树的词典数据,使得Trie树在空间上更加紧凑的同时保证复杂度基本不变,提高了词典构建和索引以及修改删除的速度。本发明提出的算法与已有的Trie树比较,不仅可以随时对词典进行修改、遍历等存储管理操作,同时在16位Trie树构建时就能够进行排序, 减少了词典更新时的开销,又保持了较高的索引效率。
应当理解,以上总体说明和以下详细说明都是说明性和实例性的,旨在提供对所要求的本发明的进一步说明。
附图说明
图1是本发明实施例中通过16位Trie树实现空间优化的词典存储管理方法的流程图。
图2是本发明实施例中实现16位Trie树的词典数据存储的森林构造图。
图3是本发明实施例中实现16位Trie树的词典数据存储的流程示意图。
具体实施方式
为了使本发明的目的、技术方案及优点更加清楚明白,一下结合附图及实施例,对本发明进行进一步的详细说明。应当理解,此处所述描述的具体实施例仅仅用于解释本发明,并不用于限定本发明。
本发明实施例提供的通过16位Trie树实现空间优化的词典存储管理方法。
如图1所示,是本发明实施例通过16位Trie树实现空间优化的词典存储管理方法的流程图。
步骤S110,获取完整的词典数据。
例如,词典中要存放如下表1中的词条(key)数据:
安徽 清华
安徽省 清华大学
中国 清华园
中国歌 清华苑
中国舞曲 南山路
中国民歌 南京
中国戏曲 南京人
表1
步骤S120,构建16位Trie树实现对词典数据的存储管理。
如图2所示,根据表1的词典数据,这些词之间存在着一些共同的前缀(即相同的父节点),按照这些前缀可以组成一个森林树,各棵树的节点做如下说明:
虚线圆代表树的终端结点(即该节点endKey=1);
实线圆代表树的非终端结点(即该节点endKey=0);
从树的根部结点到当前终端结点构成的词是词典中的一条完整词条;
从树的根部结点某一非终端结点构成的词是词典中某些词条的公共前缀。
步骤S121,以上16位Trie树的构建包括以下步骤:
步骤S122,a.获取词典数据信息的第一个字节,根据该字节的值寻找所对应的根节点,并与其关联;
步骤S123,b.在步骤a的基础上,以该节点作为父节点,并将其作为起始状态;
步骤S124,c.将词典数据信息的下一字节的高四位作为其子节点,将其与父节点相关联;
步骤S125,d.以高四位作为父节点,将该字节的低四位作为其子节点,将其与父节点相关联;
步骤S126,e.再次获取词典数据的下一字节,重复c,d步骤,直到获得词典数据最后一个字节,执行d步骤;
步骤S127,f.获得词典数据最后一字节,将其低四位作为最终状态,完成树的构建。
由此可见构建的16位Trie树中,以词典数据的第一字节作为根结点,将其后续字节分别拆成高四位和低四位,构成高四位节点和低四位节点。从而节点(非根结点)的值为0-15,就可以通过leafsInfoMap映射表和当前节点的leafsInfo来对词典森林树进行词条管理。以下对节点信息进行详细介绍。
每个节点(非根结点)最多有16个子节点,节点中用16位大小的leafsInfo来表示其子节点的信息,如leafsInfo值为0x0009(二进制为000000000001001),代表该节点其下只有有值为0和值为3的节点。
节点中用nodeValue表示当前节点所代表的值,大小从0到15。
节点中用endKey表示当前节点是否为终端结点,0表示为非终端结点,1表示是终端结点。
节点中用leafs指针数组来表示其所存在的子节点及数据指针。相比于经典trie树的构建, Leafs指针数组采用动态构建,Leafs指针数组大小随着子节点数量改变而改变,最大元素为 17。从根本上杜绝了经典trie树构建中子节点指针数量固定不变而造成的空间上的浪费。
步骤S130,构建16位Trie树节点(非根结点)信息leafsInfoMap映射表。该表为一65536×17 大小的二维数组,其中65536个数是16位leafsInfo的所有情况(即2的16次方)所确定的,不同的leafsInfo情况下里面分别是该情况下对应的16个子节点信息(用leafsInfoMap[leafsInfo][0]-leafsInfoMap[leafsInfo][15]来表示),而用当前leafsInfo情况下的最后一位元素leafsInfoMap[leafsInfo][16]用来表示当前leafsInfo情况下的子节点数量。
例如:leafsInfoMap[leafsInfo][0],若leafsInfoMap[leafsInfo][0]值不为零(即当前节点存在值为0的子节点),那么当前节点的值为0的子节点位置为leafs[leafsInfoMap[leafsInfo][0]-1], 否则不存在。
该步骤伪代码如下:
Figure GDA0001706288870000041
Figure GDA0001706288870000051
由此可见leafsInfoMap映射表是词典数据中的节点(非根结点)信息的所有的可能组合,同过leafsInfoMap映射表和节点的leafsInfo信息可以查询到该节点下所有子节点是否存在和其相关联的数据信息。因此若在该节点下插入或删除子节点,仅需更新leafsInfo信息,并添加或删除相应节点中leafs所对应的子节点指针即可,因此加强了16位Trie树的存储管理。
根据上述对本发明的实施例的具体描述,可以清楚地理解根据本发明的通过16位Trie 树实现空间优化的存储管理方法利用映射表结构下构建16位Trie树的词典数据,使得Trie树在空间上更加紧凑的同时保证复杂度基本不变,提高了词典构建和索引以及修改删除的速度。本发明提出的算法与已有的Trie树比较,不仅可以随时对词典进行修改、遍历等存储管理操作,同时在16位Trie树构建时就能够进行排序,减少了词典更新时的开销,又保持了较高的索引效率。

Claims (4)

1.一种通过16位Trie树实现空间优化的词典存储管理方法,其特征在于,该方法包括以下步骤:
获取完整的词典数据;
构建16位Trie树实现对词典数据的存储管理;
构建16位Trie树节点信息leafsInfoMap映射表;
所述节点信息为非根结点信息,包括:leafsInfo、nodeValue、endKey、leafs;
所述leafsInfo为子节点列表信息;
所述leafsInfo的信息值为16位;
所述nodeValue为当前节点所代表的值;
所述nodeValue的值为0到15;
所述endKey为终端结点判断函数;
所述leafs为子节点指针以及数据指针;
所述子节点指针指向当前节点所对应的子节点;
所述数据指针指向当前节点所对应的数据;
通过所述leafsInfoMap和所述leafsInfo可以查询到所述节点下所有子节点的数据信息;
所述leafsInfoMap映射表是词典数据中的所述节点信息的可能组合,所述leafsInfoMap用65536×17的二维数组来表示。
2.根据权利要求1所述一种通过16位Trie树实现空间优化的词典存储管理的方法,其特征在于,所述构建16位Trie树包括以下步骤:
a.获取词典数据信息的第一个字节,根据该字节的值寻找所对应的根结点,并与其关联;
b.在步骤a的基础上,以该字节作为父节点,并将其作为起始状态;
c.将词典数据信息的下一字节的高四位作为其子节点,将其与父节点相关联;
d.以高四位作为父节点,将该字节的低四位作为其子节点,将其与父节点相关联;
e.再次获取词典数据的下一字节,重复c,d步骤,直到获得词典数据最后一个字节,执行d步骤;
f.获得词典数据最后一字节,将其低四位作为最终状态,完成树的构建。
3.根据权利要求1所述一种通过16位Trie树实现空间优化的词典存储管理的方法,其特征在于,所述子节点和所述数据指针不存在时,所述leafs元素个数为0,当所述子节点存在时,所述leafs元素个数为子节点数量+1,所述数据指针占用一个元素。
4.根据权利要求1所述一种通过16位Trie树实现空间优化的词典存储管理方法,其特征在于,所述endKey=0时,所述endKey表示为非终端结点,所述endKey=1时,所述endKey表示为终端结点。
CN201810046757.2A 2018-01-18 2018-01-18 通过16位Trie树实现空间优化的词典存储管理方法 Expired - Fee Related CN108153907B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201810046757.2A CN108153907B (zh) 2018-01-18 2018-01-18 通过16位Trie树实现空间优化的词典存储管理方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201810046757.2A CN108153907B (zh) 2018-01-18 2018-01-18 通过16位Trie树实现空间优化的词典存储管理方法

Publications (2)

Publication Number Publication Date
CN108153907A CN108153907A (zh) 2018-06-12
CN108153907B true CN108153907B (zh) 2021-01-22

Family

ID=62461799

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201810046757.2A Expired - Fee Related CN108153907B (zh) 2018-01-18 2018-01-18 通过16位Trie树实现空间优化的词典存储管理方法

Country Status (1)

Country Link
CN (1) CN108153907B (zh)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109902033B (zh) * 2019-02-13 2023-03-14 山东华芯半导体有限公司 应用于NVMe SSD控制器的namespace的LBA分配方法和映射方法
CN110489516B (zh) * 2019-08-15 2022-03-18 厦门铅笔头信息科技有限公司 一种快速为海量结构化数据建立前缀索引的方法
CN110602148B (zh) * 2019-10-10 2021-07-06 深圳前海微众银行股份有限公司 一种区块的状态树的生成和链上数据验证的方法及装置

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101499094A (zh) * 2009-03-10 2009-08-05 焦点科技股份有限公司 一种数据压缩存储并检索的方法及系统
CN101788990A (zh) * 2009-01-23 2010-07-28 北京金远见电脑技术有限公司 Trie树双数组的全局优化构造方法及系统
CN103365991A (zh) * 2013-07-03 2013-10-23 深圳市华傲数据技术有限公司 一种基于一维线性空间实现Trie树的词典存储管理方法
CN103365992A (zh) * 2013-07-03 2013-10-23 深圳市华傲数据技术有限公司 一种基于一维线性空间实现Trie树的词典检索方法
EP3145134A1 (en) * 2014-06-10 2017-03-22 Huawei Technologies Co., Ltd. Lookup device, lookup configuration method and lookup method

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101788990A (zh) * 2009-01-23 2010-07-28 北京金远见电脑技术有限公司 Trie树双数组的全局优化构造方法及系统
CN101499094A (zh) * 2009-03-10 2009-08-05 焦点科技股份有限公司 一种数据压缩存储并检索的方法及系统
CN103365991A (zh) * 2013-07-03 2013-10-23 深圳市华傲数据技术有限公司 一种基于一维线性空间实现Trie树的词典存储管理方法
CN103365992A (zh) * 2013-07-03 2013-10-23 深圳市华傲数据技术有限公司 一种基于一维线性空间实现Trie树的词典检索方法
EP3145134A1 (en) * 2014-06-10 2017-03-22 Huawei Technologies Co., Ltd. Lookup device, lookup configuration method and lookup method

Also Published As

Publication number Publication date
CN108153907A (zh) 2018-06-12

Similar Documents

Publication Publication Date Title
CN108197313B (zh) 通过16位Trie树实现空间优化的词典索引方法
CN102521334B (zh) 一种基于分类特性和平衡二叉树的数据存储、查询方法
CN103561133B (zh) 一种ip地址归属信息索引方法及快速查询方法
CN108153907B (zh) 通过16位Trie树实现空间优化的词典存储管理方法
CN103365991B (zh) 一种基于一维线性空间实现Trie树的词典存储管理方法
CN104462582B (zh) 一种基于结构和内容二级过滤的Web数据相似性检测方法
CN104199860B (zh) 一种基于二维地理位置信息的数据集分片方法
EP3435256B1 (en) Optimal sort key compression and index rebuilding
CN100444167C (zh) 完美双数组trie树词典管理与检索方法
CN101576929B (zh) 一种快速词条提示的实现方法
CN102955843B (zh) 一种键值数据库的多键查找实现方法
CN103092860B (zh) 搜索提示信息生成方法及装置
CN100498783C (zh) 一种支持全文检索系统同时检索数值类型数据域的方法
US9065469B2 (en) Compression match enumeration
CN113590894B (zh) 一种动态高效的遥感影像元数据入库检索方法
CN103902693B (zh) 一种读优化的内存数据库t树索引结构的方法
CN105447105A (zh) 基于NoSQL的分布式物联网数据的单字段区间索引查询方式
KR100999408B1 (ko) 해시트리를 이용한 url 검색방법
CN111339381A (zh) 一种字典序分区双数组的字符串批量查询方法及装置
CN106484865A (zh) 一种基于DNA k‑mer index问题四字链表字典树检索算法
CN114884877A (zh) 一种哈希表和HOT相结合的IPv6路由查找方法
CN104809170B (zh) 一种云环境下面向树型数据的存储方法
CN110995876B (zh) 一种ip存储与查找的方法及装置
KR101089722B1 (ko) 프리픽스 트리 기반 색인 방법 및 장치, 그 기록 매체
CN101299212B (zh) 一种基于比特映射的压缩键树的单词检索方法

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CP01 Change in the name or title of a patent holder

Address after: 310018, No. 258, source street, Xiasha Higher Education Park, Hangzhou, Zhejiang

Patentee after: China Jiliang University

Patentee after: Hangzhou code pigeon Intelligent Technology Co.,Ltd.

Address before: 310018, No. 258, source street, Xiasha Higher Education Park, Hangzhou, Zhejiang

Patentee before: China Jiliang University

Patentee before: HANGZHOU DAIMAGE INTELLIGENT TECHNOLOGY Co.,Ltd.

CP01 Change in the name or title of a patent holder
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20210122

CF01 Termination of patent right due to non-payment of annual fee