著录项信息
专利名称 | 一种基于频域特征的子序列检索方法和系统 |
申请号 | CN201711319350.4 | 申请日期 | 2017-12-12 |
法律状态 | 授权 | 申报国家 | 中国 |
公开/公告日 | 2018-04-13 | 公开/公告号 | CN107908593A |
优先权 | 暂无 | 优先权号 | 暂无 |
主分类号 | G06F17/14 | IPC分类号 | G06F17/14;G06F17/30查看分类表>
|
申请人 | 清华大学 | 申请人地址 | 北京市海淀区清华园北京-8***
变更
专利地址、主体等相关变化,请及时变更,防止失效 |
权利人 | 清华大学 | 当前权利人 | 清华大学 |
发明人 | 王建民;黄向东;芮蕾;康荣;王晨 |
代理机构 | 北京路浩知识产权代理有限公司 | 代理人 | 王莹;吴欢燕 |
摘要
本发明提供一种基于频域特征的子序列检索方法和系统,检索方法包括:将滑动窗口在数据库的所有序列上依次滑动,滑动窗口任一次滑动获取一个与滑动窗口长度相等的子序列;对每一子序列进行离散傅里叶变换,获取每一子序列对应的频域特征序列,所有子序列对应的频域特征序列构成频域特征序列集合;遍历频域特征序列集合,基于降维规则对频域特征序列集合进行降维,获取基于频域特征的降维表示的序列;通过空间索引方法对降维表示的序列进行检索。本发明能够有效减少虚假匹配结果的数量,使得降维表示后的序列之间的距离更加接近原序列之间的实际距离,进而减小子序列近似查询的响应时间。本发明具备应对大数据的能力,且具有更好的实用价值。
1.一种基于频域特征的子序列检索方法,其特征在于,包括:
将滑动窗口在数据库的所有序列上依次滑动,所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列;
对每一子序列进行离散傅里叶变换,获取每一子序列对应的频域特征序列,所有子序列对应的频域特征序列构成频域特征序列集合;
遍历所述频域特征序列集合,基于降维规则对所述频域特征序列集合进行降维,获取基于频域特征的降维表示的序列;
通过空间索引方法对所述降维表示的序列进行检索;
所述遍历所述频域特征序列集合,基于降维规则对所述频域特征序列集合进行降维,获取基于频域特征的降维表示的序列之前还包括:
获取所述频域特征序列集合的平均序列,所述平均序列包括与所述滑动窗口长度相等个数维度的分量;
获取所述平均序列前指定维度的分量的幅值,并对所述前指定维度的分量的幅值按照数值大小进行排序,获取第一幅值集合;
将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。
2.根据权利要求1所述的检索方法,其特征在于,所述基于降维规则对所述频域特征序列集合进行降维进一步包括:
通过如下降维规则对所述频域特征序列集合进行降维:
其中,RFi,j为降维表示后的序列值,RFi,j包括R个,Fi,0为所述频域特征序列集合所包括的第i条频域特征序列中位置下标为0的元素,Pos[j]为所述幅值位置集合的第j个元素,1≤i≤R,0≤j≤f-1,f为所述预设个数,R为所述频域特征序列集合包括的频域特征序列的个数,Fi,Pos[j]为所述频域特征序列集合包括的第i条频域特征序列中位置下标为Pos[j]的元素,w为滑动窗口的长度,RFi,j的长度与f的值相等。
3.根据权利要求1所述的检索方法,其特征在于,所述指定维度通过下式获取:
其中,L为指定维度,w为滑动窗口的长度, 是下取整符号。
4.根据权利要求1所述的检索方法,其特征在于,通过下式获取所述频域特征序列集合的平均序列:
其中,为所述频域特征序列集合的平均序列,R为所述频域特征序列集合包括的频域特征序列的个数,Fi=[Fi,0,Fi,1,…,Fi,w-1],1≤i≤R,w为滑动窗口的长度,Fi为所述频域特征序列集合中的第i个频域特征序列,Fi的长度与滑动窗口的长度相等。
5.根据权利要求1所述的检索方法,其特征在于,所述一个与所述滑动窗口长度相等的子序列通过下式表示:
Si[offset:offset+w-1],1≤i≤N,0≤offset≤Len(Si)-w;
其中,Si为一个与所述滑动窗口长度相等的子序列,offset为滑动窗口的移动偏置,w为滑动窗口的长度,N为数据库的序列个数,Len(Si)为一个与所述滑动窗口长度相等的子序列的长度,S[i:j]为序列S从第i维到第j维的子序列。
6.根据权利要求1所述的检索方法,其特征在于,所述数据库的每一序列的任一维度的值为实数。
7.一种基于频域特征的子序列检索系统,其特征在于,包括:
获取子序列模块,用于将滑动窗口在数据库的所有序列上依次滑动,所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列;
获取频域特征序列模块,用于对每一子序列进行离散傅里叶变换,获取每一子序列对应的频域特征序列,所有子序列对应的频域特征序列构成频域特征序列集合;
降维模块,用于遍历所述频域特征序列集合,基于降维规则对所述频域特征序列集合进行降维,获取基于频域特征的降维表示的序列;
检索模块,用于通过空间索引方法对所述降维表示的序列进行检索;
所述检索系统还包括:
获取平均序列模块,用于获取所述频域特征序列集合的平均序列,所述平均序列包括与所述滑动窗口长度相等个数维度的分量;
获取第一幅值集合模块,用于获取所述平均序列前指定维度的分量的幅值,并对所述前指定维度的分量的幅值按照数值大小进行排序,获取第一幅值集合;
记录模块,用于将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。
法律信息
- 2018-10-30
- 2018-05-08
实质审查的生效
IPC(主分类): G06F 17/14
专利申请号: 201711319350.4
申请日: 2017.12.12
- 2018-04-13
引用专利(该专利引用了哪些专利)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有引用任何外部专利数据! |
被引用专利(该专利被哪些专利引用)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有被任何外部专利所引用! |