一种基于频域特征的子序列检索方法和系统

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.一种基于频域特征的子序列检索系统，其特征在于，包括：
获取子序列模块，用于将滑动窗口在数据库的所有序列上依次滑动，所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列；
获取频域特征序列模块，用于对每一子序列进行离散傅里叶变换，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；
降维模块，用于遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；
检索模块，用于通过空间索引方法对所述降维表示的序列进行检索；
所述检索系统还包括：
获取平均序列模块，用于获取所述频域特征序列集合的平均序列，所述平均序列包括与所述滑动窗口长度相等个数维度的分量；
获取第一幅值集合模块，用于获取所述平均序列前指定维度的分量的幅值，并对所述前指定维度的分量的幅值按照数值大小进行排序，获取第一幅值集合；
记录模块，用于将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。

一种基于频域特征的子序列检索方法和系统\n技术领域\n[0001] 本发明涉及计算机数据管理技术领域，更具体地，涉及一种基于频域特征的子序列检索方法和系统。\n背景技术\n[0002] 子序列近似查询的一般做法是：输入一个查询序列Q和不相似度阈值ε，输出数据库中所有满足匹配条件的子序列。匹配条件是指匹配序列和查询序列之间的不相似度不超过阈值ε。度量两条序列之间的不相似度的一种常见做法是使用序列距离函数，一种典型的序列距离函数是欧式距离，即给定两个等长序列 和 它们之间基于欧式距离的不相似度为\n[0003] 子序列近似查询的一种暴力解法是直接检索数据库中的所有子序列，计算并判断每个子序列是否满足匹配条件，找出所有满足匹配条件的子序列后输出结果。这种解法在实际应用中往往是不可行的，因为序列本质上是高维数据，直接处理这些高维数据会带来昂贵的计算和存储成本，并且使得查询响应时间过长而难以接受。\n[0004] 一种常见的替代方法是基于序列降维表示的子序列检索方法：(1)先对查询序列和数据库中序列的所有子序列进行降维表示；(2)然后对降维表示后的子序列进行检索，得到与降维表示后的查询序列相匹配的降维表示后的子序列集合A；(3)最后将集合A还原成原空间对应的子序列集合B，并通过一定的后处理，从子序列集合B中过滤出真正满足匹配条件的子序列集合C。记数据库中实际所有满足匹配条件的子序列集合为D，保证上述方法正确性的关键是要保证集合B是集合D的超集，即集合D中的每一个元素都在集合B中，而集合B中可能包含集合D中没有的元素，从而保证了从集合B中过滤出来的集合C等于集合D，即保证子序列近似查询结果没有遗漏。\n[0005] 一种序列降维表示方法是基于频域特征，其一般思路是首先通过某种方法提取序列的频域特征，构成频域特征序列，然后利用频域特征的性质进行降维表示。提取序列的频域特征的常见做法之一是使用离散傅里叶变换(Discrete Fourier Transform，DFT)，例如，一个长度为n的序列 的离散傅里叶变换为一个长度为n的\n频域特征序列 其中\n[0006] 离散傅里叶变换具有一些良好的性质，使得当离散傅里叶变换被用在基于频域特征的序列降维表示方法中时，能够最终保证基于序列降维表示的子序列检索方法的正确性。下面进行说明：首先离散傅里叶变换满足帕萨瓦尔定理，即如果 是序列 的离散傅里叶变换，那么有 其次，离散傅里叶变换是一种线性变换，因此如\n果序列 的离散傅里叶变换为 序列 的离散傅里叶变换为 那么序列 的离散傅里叶变换为 上述两条性质可以推出公式：\n该公式的意义是：如果将两个等长序列 之间的距离定义为欧式距离，那么离散傅里叶变换就具有保距性，即变换前后两个序列之间的距离保持不变。因此，如果对频域特征序列进行降维，选择其中的f维(f