第3期 李应：基于局部搜索的音频数据检索方法 ·261· 门的声音片段，在含n个音频文件集中查询是否存 1)树中每个非叶结点最多有m棵子树：有n棵 在按动快门的音频文件.这个查询过程是：首先，把 子树的非叶结点有n对主关键码，每对主关键码指 待查的声音片段进行小波变换，产生该音频数据的 明其子树的主关键码的范围： 最佳树结构系数$和3个级别的离散小波逼近系 2)除根结点外，其他的非叶结点至少有 数cA6、cA5、44然后，计算该音频的cA6的过零 m21棵子树； 率Z,和平均幅度M,,即查询数据的参数对(Z, 3)所有的叶结点都处在同一层次上，它们包含 Mg人.根据参数对(Zg,Mg),在{(Za,Ma),… 了全部主关键码、次关键码和指向相应数据对象存 (Z.,M,)}中确定局部搜索范围{(，m)1 放地址的指针，且叶结点本身按主关键码从大到小、 DL≤≤DU&MDL≤m,≤MDU},其中， 从右到左顺序连接： ZDL =*Z,ZDU =*Z,MDL =m1 *M 4)每个叶结点中的子树棵数n可以多于m,可以 MDU=m2*M,,而、分别表示主关键码范围的 少于m.若设结点可容纳最大关键码数为m,则指向 下限系数和上限系数，m1、m2分别表示次关键码范 对象的地址指针也有m,个，因此，结点中的子树棵数 围的下限系数和上限系数.最后利用小波包最好 n应满足n∈「m12m,7在叶结点中，进行插入操 基小波塔型算法来确定最匹配的音频数据.例如， 作时，尽量使靠左的叶结点的子树棵数n=m 查询数据的参数(Z,M,)=(0.0500,0.1122),在 5)对LS-tree的搜索从根结点开始，首先用主关 图3中用“+表示，则搜索范围为图3中的矩形包。 键码范围进行搜索，当以主关键码范围的检索完成 围部分，即{(4，ma)100166≤≤00908≤ 时，再把检索结果从左到右用查询数据的次关键码 00394≤m:≤03245}，其中图3(b)是图3(a) 范围进行比较，取出符合次关键码范围的叶结点子 的局部放大.因此，希望用小波包最好基小波塔型 树，根据该子树“其他参数指针2”，进行小波包最好 算法来确定最匹配的音频数据只需在矩型范围内进 基小波塔型算法的检索 行，而不是整个平面 6)其中，叶结点结构、非叶结点结构以及待查 2.5r 询数据的结构分别如图4(a)、(b)和(c)所示 2.0 ·音频数据 主关键码 主关键码 主关键码 。查询范围 1.5 +查询数据 次关键码 次关键码 次关键码 1.0 选中标记 选中标记 选中标记 其他参数 其他参数 其他参数 05 指针1 指针1 指针1 0.·s 0.2 0.4 0.6 0.8 全选标记 左指针 右指针 过零率 (a)确定查询范围 (a)叶结点结构 范围(a,b) 范围(a,b) 主关键码范围 0. 子树指针 子树指针 次关键码范围 音频数据 全选标记 其他参数指针2 0.1 查询数据 (b)非叶结点结构 (c)查询数据的结构 图4LS-k tree的结点结构和查询数据的结构 Fig 4 The crunode structure of LS-tree and the 0.020.040.060.080.1 structure of query data 过零率 (6)放大查询范围 23LS-tree的应用举例 图3参数(Z,M,）=(00500,01122)时的查询范围 在图3中取出部分分布点，形成表1所示的一 Fig 3 The query range while the vector (Z.M)= 组过零率Zd和平均幅度M,的参数对.用这组数 (00500,01122) 据，根据LS-tee的定义，可以生成图5所示的LS 22定义LS-tree tree其中叶结点上的“*表示该结点上的其他部 分，即图4(a)中的次关键码、选中标记、其他参数指 为了实现局部搜索，定义LS-tree如下： 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net门的声音片段 ,在含 n个音频文件集中查询是否存 在按动快门的音频文件. 这个查询过程是 :首先 ,把 待查的声音片段进行小波变换 ,产生该音频数据的 最佳树结构系数 sI和 3个级别的离散小波逼近系 数 cA6、cA5、cA4. 然后 ,计算该音频的 cA6的过零 率 Zq 和平均幅度 M q ,即查询数据的参数对 ( Zq , M q ). 根据参数对 ( Zq , M q ) ,在 { ( Zd1 , …, M d1 ) , …, ( Zdn , M dn ) } 中 确 定 局 部 搜 索 范 围 { (zd , md ) | ZDL ≤ zd ≤ZDU&MDL ≤ md ≤ MDU} , 其 中 , ZDL = z1 3 Zq , ZDU = z2 3 Zq , MDL = m1 3 M q , MDU = m2 3 M q ,而 z1、z2 分别表示主关键码范围的 下限系数和上限系数 , m1、m2 分别表示次关键码范 围的下限系数和上限系数. 最后利用小波包最好 基 —小波塔型算法来确定最匹配的音频数据. 例如 , 查询数据的参数 ( Zq , M q ) = (0. 050 0, 0. 112 2) ,在 图 3中用“ + ”表示 ,则搜索范围为图 3中的矩形包 围部分 ,即 { (zd , md ) | 0. 016 6 ≤ zd ≤ 0. 090 8 ≤ 0. 039 4 ≤md ≤ 0. 324 5} ,其中图 3 ( b)是图 3 ( a) 的局部放大. 因此 ,希望用小波包最好基 —小波塔型 算法来确定最匹配的音频数据只需在矩型范围内进 行 ,而不是整个平面. 图 3 参数 ( Zq , M q ) = (0. 050 0, 0. 112 2)时的查询范围 Fig. 3 The query range while the vector ( Zq , M q ) = (0. 050 0, 0. 112 2) 2. 2 定义 LS2tree 为了实现局部搜索 ,定义 LS2tree如下 : 1) 树中每个非叶结点最多有 m 棵子树;有 n棵 子树的非叶结点有 n对主关键码 ,每对主关键码指 明其子树的主关键码的范围; 2 ) 除 根 结 点 外 , 其 他 的 非 叶 结 点 至 少 有 「m /2ô棵子树 ; 3)所有的叶结点都处在同一层次上 ,它们包含 了全部主关键码、次关键码和指向相应数据对象存 放地址的指针 ,且叶结点本身按主关键码从大到小、 从右到左顺序连接 ; 4) 每个叶结点中的子树棵数 n可以多于 m ,可以 少于 m. 若设结点可容纳最大关键码数为 m1 ,则指向 对象的地址指针也有 m1 个,因此 ,结点中的子树棵数 n应满足 n ∈「「m1 /2ô, m1 ô. 在叶结点中,进行插入操 作时,尽量使靠左的叶结点的子树棵数 n = m1 . 5)对 LS2tree的搜索从根结点开始 ,首先用主关 键码范围进行搜索 ,当以主关键码范围的检索完成 时 ,再把检索结果从左到右用查询数据的次关键码 范围进行比较 ,取出符合次关键码范围的叶结点子 树 ,根据该子树“其他参数指针 2”,进行小波包最好 基 —小波塔型算法的检索. 6)其中 ,叶结点结构、非叶结点结构以及待查 询数据的结构分别如图 4 ( a)、( b)和 ( c)所示. 图 4 LS2kd tree的结点结构和查询数据的结构 Fig. 4 The crunode structure of LS2tree and the structure of query data 2. 3 LS2tree的应用举例 在图 3中取出部分分布点 ,形成表 1所示的一 组过零率 Zd和平均幅度 M d 的参数对. 用这组数 据 ,根据 LS2tree的定义 ,可以生成图 5所示的 LS2 tree. 其中叶结点上的“3 ”表示该结点上的其他部 分 ,即图 4 ( a)中的次关键码、选中标记、其他参数指 第 3期 李 应 :基于局部搜索的音频数据检索方法 ·261·