压缩索引理论、技术及其应用
发布时间: 2021-09-13
来源: 科技服务团
基本信息
建立了并开发了熵压缩的文本自索引理论与技术,同时支持在压缩索引上的快速检 索。理论空间占用为 nHk + 2nlog(Hk+2) + n + o(n) 位。定位给定模式 P 在输入文本 T 中 的所有出现时间复杂度为 O(m log n + occ log n(loglog n)2)。字串提取时间复杂度为 O(len (log σ + loglog n) + log n(loglog n)2) , 其中 n 是文本 T 的输入规模, σ 是 T 的字符表大小, Hk 是 T 的高阶经验熵, occ 是模式 P 在文本 T 中的出现次数。
提出并开发了首个图数据库相似性搜索的简明索引, 支持图的快速相似性搜索。理 论空间占用逼近图数据库大小的线性对数函数。在实现上,该索引是首个能在内存中在 2 千 500 万个化学分子结构图数据库中进行快速图的相似性搜索的简明索引。已有索引都是 传统索引,据我们所知,只能在少于 500 万个图数据库上进行搜索。
已完成算法理论和技术的软件开发。针对各种输入数据分布的优化一直在进行中。
主要技术指标:
普通文本数据上自索引空间占用为输入文本大小的 30%,高度重复数据上自索引空 间占用为输入文本大小的 5%。在压缩索引上进行模式搜索,包括定位和提取查询平均时 间在毫秒或微秒级。图数据库简明索引空间占用为输入大小的 5%-15%, 图的相似性查询 在秒级。