(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202210394936.1 (22)申请日 2022.04.15 (65)同一申请的已公布的文献号 申请公布号 CN 114756591 A (43)申请公布日 2022.07.15 (73)专利权人 成都卓讯智安科技有限公司 地址 610000 四川省成 都市成都高新区科 园二路10号3 栋1单元7层1号 (72)发明人 眭新光　关创创　 (74)专利代理 机构 北京万驰专利代理事务所 (普通合伙) 1610 6 专利代理师 郭永 (51)Int.Cl. G06F 16/2457(2019.01) G06F 16/2455(2019.01)G06F 16/22(2019.01) (56)对比文件 CN 111737263 A,2020.10.02 CN 108280 085 A,2018.07.13 CN 110929103 A,2020.0 3.27 CN 111177491 A,2020.0 5.19 CN 114020822 A,2022.02.08 WO 2021258 848 A1,2021.12.3 0 US 2004034656 A1,2004.02.19 审查员 翟一鸣 (54)发明名称 一种基于双向链 表的数据筛 选方法和系统 (57)摘要 本发明公开了一种基于双向链表的数据筛 选方法和系统， 预先按指定长度从全词规则集中 提取去重后的最少公共子串集合， 并建立各最少 公共子串与原始字符串的映射关系， 该方法包 括： 根据最少公共子串集合构造出采用连续内存 数组存放的数据集， 数据集中各数据成员为结构 体； 根据各计数值将各数据成员作为节点划分到 预设双向链表指针数组的各个分区； 从各分区中 依次取出第一目标节点， 并根据与第一目标节点 关联的第二目标节点的索引值更新预设双向链 表指针数组； 在各分区中不存在节点时， 确认完 成数据筛选， 从而避免了多次重新对 数据集的完 整排序， 提高了对最少公共子串集合的筛选效 率。 权利要求书3页 说明书8页 附图4页 CN 114756591 B 2022.10.14 CN 114756591 B 1.一种基于双向链表的数据筛选方法， 其特征在于， 预先按指定长度从全词规则集中 提取去重后的最少公共子串集合， 并建立各最少公共子串与原始字符串的映射关系， 所述 方法包括： 根据所述最少公共子串集合构造出采用连续内存数组存放的数据集， 所述数据集中各 数据成员为结构 体， 各所述数据成员中包括计数值、 与其他数据成员之间的关联信息、 双向 链表指针头节点和自身在数组中的索引值； 根据各所述计数值将各所述数据成员作为节点划分到预设双向链表指针数组的各个 分区； 从各所述分区中依次取出第 一目标节点， 并根据与所述第 一目标节点关联的第 二目标 节点的索引值更新所述预设双向链 表指针数组； 在各所述分区中不存在节点时， 确认完成数据筛 选； 其中， 所述第一目标节点为最大计数值所在分区的首个节点， 所述计数值表征了所述 数据成员映射的原 始字符串的条 数， 所述最少公共子串为划分次数最少的公共子串； 根据与所述第一目标节点关联的第二目标节点的索引值更新所述预设双向链表指针 数组， 具体为： 根据所述第二目标节点的索引值确定所述第二目标节点的计数值； 将所述计数值减一并确定所述第二目标节点的新计数值； 若所述新计数值 为零， 在所述预设双向链 表指针数组中删除所述第二目标节点； 若所述新计数值不为零， 根据 所述新计数值调 整所述第 二目标节点在所述预设双向链 表指针数组中的位置 。 2.如权利要求1所述的方法， 其特征在于， 各所述分区带有表征数组深度的下标， 根据 各所述计数值将各所述数据成员作为节点划分到预设双向链表指针数组的各个分区， 具体 为： 依次将各所述数据成员作为当前数据成员， 并将当前数据成员的当前计数值减一后确 定目标下标， 并基于目标 下标确定目标分区； 若所述目标分区是所述预设双向链表指针数组上最后 一个分区， 从头遍历所述预设双 向链表指针数组并确定第一个小于 当前计数值的第三目标节点， 将当前数据成员作为节点 插入所述第三目标节点之前； 若所述目标分区不是所述预设双向链表指针数组上最后一个分区， 基于尾部插入法将 当前数据成员作为节点插 入； 其中， 最后一个分区中各节点的计数值 不小于最后一个分区的下 标。 3.如权利要求1所述的方法， 其特征在于， 若所述新计数值不为零， 根据所述新计数值 调整所述第二目标节点在所述预设双向链 表指针数组中的位置， 具体为： 若所述第二目标节点处于最后 一个分区且存在所述第 二目标节点的后继节点， 将所述 新计数值和所述后继节点的计数值进 行比较， 并根据比较结果使 所述第二目标节点保持不 动或与所述后继节点交换位置； 若所述第二目标节点处于最后 一个分区且不存在所述后继节点， 将所述第 二目标节点 保持不动或将所述第二目标节点挪动到当前 所处分区的前一个分区； 若所述第二目标节点不处于最后 一个分区， 将所述第 二目标节点挪动到当前所处分区权　利　要　求　书 1/3 页 2 CN 114756591 B 2的前一个分区。 4.如权利要求1所述的方法， 其特 征在于， 在确认完成数据筛 选之后， 所述方法还 包括： 将取出的各所述第一目标节点用结果 集数组的形式存 储为筛选结果。 5.一种基于双向链表的数据筛选系统， 其特征在于， 预先按指定长度从全词规则集中 提取去重后的最少公共子串集合， 并建立各最少公共子串与原始字符串的映射关系， 所述 系统包括： 构造模块， 用于根据所述最少 公共子串集合构造出采用连续内存数组存放的数据集， 所述数据集中各数据成员为结构体， 各所述数据成员中包括计数值、 与其他数据成员之间 的关联信息、 双向链 表指针头节点和自身在数组中的索引值； 划分模块， 用于根据 各所述计数值将各所述数据成员作为节点划分到预设双向链表指 针数组的各个分区； 筛选模块， 用于从各所述分区中依次取出第一目标节点， 并根据与所述第一目标节点 关联的第二目标节点的索引值更新所述预设双向链 表指针数组； 确认模块， 用于在各 所述分区中不存在节点时， 确认完成数据筛 选； 其中， 所述第一目标节点为最大计数值所在分区的首个节点， 所述计数值表征了所述 数据成员映射的原 始字符串的条 数， 所述最少公共子串为划分次数最少的公共子串； 所述筛选模块， 具体用于： 根据所述第二目标节点的索引值确定所述第二目标节点的计数值； 将所述计数值减一并确定所述第二目标节点的新计数值； 若所述新计数值 为零， 在所述预设双向链 表指针数组中删除所述第二目标节点； 若所述新计数值不为零， 根据 所述新计数值调 整所述第 二目标节点在所述预设双向链 表指针数组中的位置 。 6.如权利要求5所述的系统， 其特征在于， 各所述分区带有表征数组深度的下标， 所述 划分模块， 具体用于： 依次将各所述数据成员作为当前数据成员， 并将当前数据成员的当前计数值减一后确 定目标下标， 并基于目标 下标确定目标分区； 若所述目标分区是所述预设双向链表指针数组上最后 一个分区， 从头遍历所述预设双 向链表指针数组并确定第一个小于 当前计数值的第三目标节点， 将当前数据成员作为节点 插入所述第三目标节点之前； 若所述目标分区不是所述预设双向链表指针数组上最后一个分区， 基于尾部插入法将 当前数据成员作为节点插 入； 其中， 最后一个分区中各节点的计数值 不小于最后一个分区的下 标。 7.如权利要求5所述的系统， 其特征在于， 若所述新计数值不为零， 所述筛选模块， 还具 体用于： 若所述第二目标节点处于最后 一个分区且存在所述第 二目标节点的后继节点， 将所述 新计数值和所述后继节点的计数值进 行比较， 并根据比较结果使 所述第二目标节点保持不 动或与所述后继节点交换位置； 若所述第二目标节点处于最后 一个分区且不存在所述后继节点， 将所述第 二目标节点 保持不动或将所述第二目标节点挪动到当前 所处分区的前一个分区；权　利　要　求　书 2/3 页 3 CN 114756591 B 3