2. 新疆师范高等专科学校 新疆教育学院, 乌鲁木齐 830043
为了揭示SWF文件格式的隐含属性,基于对象交换模型(OEM)的构建方式,提出了一种增强半结构化模型E-OEM,可对SWF文件格式进行描述和存储.采用OEM进行SWF文件格式的描述;对OEM描述模型进行改进,采用头尾分类、文件体聚类的思想将相同类别标签作为一类;通过引入Huffman编码,实现E-OEM具有描述和存储的功能.随机选择百例不同源文件进行E-OEM建模,仿真实验结果表明,所提模型不仅可以将隐含属性显性表示,同时提高了具有高标签重复率的文件存储效率,证实了模型的有效性.
2. Xinjiang Education Institude, Xinjiang Teacher's College, Urumchi 830043, China
It's difficult to reveal hidden relationships of the shockwave flash (SWF). The article proposed an enhancement object exchange model (E-OEM) based on object exchange model (OEM). This model can describe and store SWF file format. First, SWF file format is described though OEM. Then, OEM descriptive model is improved with classifying the head and the end, clustering the body. E-OEM could realize the function of description and storage through Huffman coding. Also, 100 different source files are used to build semi-structure model. It is shown that E-OEM has a good impact on the relationship dominance, and can implement effective retrieval of high tag repetitive rate, and the storage rate is improved. It is shown that the model is valid.
SWF(shockwave flash)是动画设计软件Flash的专属格式,支持点阵图形与矢量,具有缩放不失真、文件体积小等特点,广泛应用于网页制作、动画设计等领域中.非结构化的SWF文件,结构简单,无法找到各个属性的对应关系,需要依据SWF文件说明先进行数据分析,大大降低了处理效率.
半结构化数据代指那些结构隐含或不严谨的数据类型,全世界超过80%的数据类型都是以半结构化形式存储的[1].它可以很好地解决结构化数据的严格约束与非结构化结构混乱的问题.
笔者基于对象交换模型(OEM, object exchange model)的优点与不足,提出了增强OEM(E-OEM, enhancement OEM)并进行相关研究.
1 相关工作Zhu[2]对Flash动画进行文件结构与上下文结构挖掘,构建了3种分类模型实现Flash动画的语义特征信息分析. Fouche等[3]采用数据插入技术,将隐含数据替换为不规则的二进制数,保证了数据的隐秘性. Zhang等[4]将传统的地理信息系统数据通过Flash软件的组建分离,转化为SWF文件,具有更高的传输速度.王岳平[5]采用SWFmill对电影文件的内部存储结构进行分析,用于电影的场景中.
迄今为止,常用的半结构化描述方式有OEM描述模型与XML描述模型. OEM是斯坦福大学Serge Abiteboul教授所提出的一种自描述的数据模型,可以很好地对半结构化数据进行描述与设计[6].曹文仙等[7]将整个数据库构建为一个OEM,采取半结构化数据查询重写桶算法的思想,降低了算法代价.黄洪等[8]在分析出传统图形用户开发存在的问题后,提出了一种基于XML的图形用户界面描述方法,实现了图形用户界面定义与具体程序设计语言和开发平台的无关性.张富等[9]提出了一个模糊XML模型,实现了模糊XML模型到知识库间的转化.孙宏伟[10]提出了XML与关系数据库的三层双向集成技术,实现了XML与关系数据库之间的数据转换. XML相比于OEM而言,更为灵活,但容易造成大量冗余,在SWF格式分析中,采取OEM的改进方式更适合SWF短小精悍的特点.
在动画及视频的存储方面,张敏[11]利用数字图像处理技术与视频分割技术,为用户提供更精确、生动、全面的教育Flash资源,推动教育数字化的发展;Deng等[12]在SWF文件内部读取的字节数组部分加入水印标签来保护版权,防止反编译等有效攻击;陈爱东[13]结合XML文件格式特点,实现了SWF向XML文件的转换,并构建了Flash动画检索系统;廖建平[14]根据SWF解析规则设计解析框架,实现了文件头与文件体的解析,并采用XML描述方式进行形式化描述;倪应华等[15]详细地分析了SWF的文件头与标签,并设计解析程序实现了SWF动画环境信息、动画元素信息以及控制信息的获取.
2 可描述可存储的半结构化模型 2.1 基于OEM的描述模型SWF文件格式分为3个部分:文件头、文件体,文件尾.文件头用于确定文件基本信息;文件体描述了文件的细节内容;文件尾仅用作简单的停止.在SWF半结构化模型建立中,引入OEM进行描述. OEM以对象作为实体,每个对象可由一个四元组(oid, label, type, value)进行表示[6].笔者选择较为常用的属性进行半结构化描述,构建基于OEM的半结构化SWF描述模型. 图 1是源文件abc.swf的OEM模型.在建立模型后,需要引入一些OEM的相关概念对SWF文件格式进行相关描述.
定义1 一个简单的路径表达式是以点为间隔的标签描述(label)序列,记作se=l1, l2, l3, …, ln.
定义2 频繁简单路径表达式fpe:pe出现在OEM中的次数称为pe的支持度计数sup(pe),来去掉出现频度较低的简单路径表达式.当sup(pe)≥min_sup(用户自己设立的最低支持度)时,pe称为频繁pe,记作fpe.
由定义可见,fpe与dp相比可以更好地反映SWF的一般结构,采用模式抽取的方式[16-18],对图 1的OEM进行深度优先遍历,找到所有频繁的最大简单路径表达式,用mpe表示.
在构建OEM描述模型时,对遍历得到的最大简单路径表达式mpe添加层次标记,从而生成最大简单路径表达式集合,记作M. M中包含了OEM图中所有存在的路径,其他任何一个路径集均为它的子集.在图 1中,经过OEM的优先遍历后,可以生成层次结构的最大简单路径表达式集M={head1-1.sign2-1.compress3-1.first4-1, head1-1.sign2-1.compress3-1.second4-2…}. OEM构建方式可以构建出完备的M集合,但需要较多的存储空间,同时检索效率较低,因此提出一种基于OEM改进的增强半结构化模型——E-OEM,该模型可以实现描述与存储的功能.
2.2 E-OEM半结构化模型建立对上述建模所遇到的问题,采取改进措施.
首先,对整个SWF文件进行遍历,标记出各个标签的位置信息作为聚类的类内标识(location)并获得每个标签的ID号.在SWF文件中,文件头、文件尾属性固定,采用决策树方式对其进行分类.文件体部分长度不固定,采用K-means算法进行聚类.聚类个数参照SWF7.0说明的标签数量,ID号相同的标签为一类.将同类标签压入堆栈进行存储,按照location进行编号,避免查询时的混乱.对相似标签内容,根据需要进行压缩、整合,该方法极大程度上解决了存储过程中冗余量较大的问题,但导致最大简单路径表达式扩大,检索效率降低.
采用Huffman编码方式进行存储,对存入堆栈标签的数量进行统计,出现频度最高的标签具有最短的编码位数,逐级递增.对于一个SWF文件而言,一般4~5位编码即可满足视频播放的要求.采用此种编码方式有效地压缩了存储空间,具有实际意义.为方便描述,对E-OEM进行如下定义.
定义3 一个SWF文件可以构建为一棵以SWF文件标签ID为节点的Huffman树T,用三元组表示T=(ID,R,W). ID代表SWF文件标签的ID号;R(relation)是一个属性集,在其中包含了相同ID下所有的不同属性、位置以及属性值;W(weigh)代表Huffman的权重.
定义4 R属性值较多,根据ID的不同,将其构建成单独的一系列子树P={P1, P2, P3, …, Pn},可以看出P⊆T.
定义5 ∀Pi∈P,{L, A, C}⊆Pi,L(location)代表在SWF文件中,该标签所在的位置信息;A(attribute)代表该标签所含的属性信息;C(correlation)代表一个关联关系,包含3种属性(U, V),(U, V)∈R.当U, V∈ N时,下列结果可以成立:①U为父对象,V为子对象;②U为父属性,V为子属性;③U为原子属性,V为属性值.
定义6 (相似度判定)Pi是一个R的子树,对其用三元组进行表示.不同标签间不具备可比性,因此针对同一个R内的所有子树进行分析,RA={A1, A2, …, An},子权重按照均匀分布设置为
$ S = \frac{{\sum\limits_{i = 1}^{k - 1} {{{W'}_i}} }}{{\sum\limits_{p = 1}^{\mathit{n} - 1} {{W_i}} }} = \frac{{k - 1}}{{n - 1}}, S \in \left[{0, 1} \right] $ | (1) |
当S趋向于0时,相似度较高;S趋向于1时,相似度较低.当(n-1)(k-1)=0时,代表该类中仅存在一个标签,将S置为ONLY. Ni等[19]对SWF文件进行分析,得出同一ID的相似度S较高,做聚类操作是有意义的.
3 仿真结果根据E-OEM描述存储的双特性,将E-OEM结构模型应用于SWF解析中,做出了SWF的解析器,实现SWF文件属性显性化.该解析器的技术路线包括以下几步:①借助E-OEM对SWF的各项数据进行信息重构,分类列出相关信息;②根据找寻最大简单路径表达式的方法,确定对象、属性、属性值之间的相互关系,并确认其中的隐含属性;③采用Huffman树状存储方式对相同ID进行存储,节约存储空间,并提高检索效率;④构建可视化的SWF解析器来对模型进行验证.
对SWF文件采用E-OEM进行描述,构建可视化的SWF解析器可以明确其内部的结构关系,如图 2所示.
由图 2可以看出,半结构化解析的SWF文件具备显示隐含属性的能力.此框架可以通过标签分类完成SWF文件的分析,在文件头部分进行具体阐释,文件体的标签数量众多,采用数值统计的方法,将其代表的主属性表示出来,对整体影响较小的属性进行了适当忽略.可以看出,半结构化模型相比于非结构化模型具有更清晰的层次性、逻辑性与描述性.
同时,根据SWF的编码规则,对图 1的源文件进行半结构化描述,构建E-OEM描述存储结构示意图,如图 3所示.
如图 3所示,通过对图 1源文件标签的遍历、统计构建SWF文件标签分布图(图 3(a)),利用式(1)计算源文件各标签的相似度S(图 3(b)),进而构建图 1源文件的E-OEM(图 3(c)).相比图 1的OEM,图 3(c)所示的E-OEM模型更加短小精炼.
相比图 3源文件,图 4是一个较为复杂的SWF动画源文件motion.swf的模型构建过程.采用相同方式进行模型构建.
标签出现的频率称为标签重复率. Huffman编码将标签重复率高的标签赋予短的编码长度,减少存储空间的浪费.实验中,使用最高的标签重复率(最大标签重复率)判定压缩率与标签频度的关系.
在检索方面,通过增加最大简单路径表达式权重,尽可能缩小检索范围,在高频ID中表现明显.引入相似度S,将相似程度很高的标签归类,有效减少冗余量.采用子树的方式对复杂属性进行二度分类,具有更好的适应性.与OEM描述模型相比,E-OEM拥有更快的检索效率,更优的存储空间.
在实际的数据解析中,文件涵盖的信息会比实验中列举的更多.在标签类别多的情况下,更能体现出E-OEM的优越性. 图 5选取了100例SWF文件进行测试,采用SWF协议的压缩解压方法与模型方法的理论值进行对比.
由图 5可以直观看出,同在ID层进行压缩率对比,E-OEM压缩率在最大标签重复率较高时,具有更好的压缩性能,如表 1所示.
因此,在模型存储方面,文件的最大标签重复率将会影响模型的存储效率.在检索方面,经过全局遍历后,对于特定的检索要求,E-OEM可以达到处理的快速性.总体而言,E-OEM在存储方面可以基本实现模型功能,具有普适性和广泛性.
4 结束语笔者提出一种可描述可存储的半结构化模型E-OEM,该模型可用于提高存储效率;同时,引入Huffman编码与相似度S,提高检索效率.在SWF文件解析中,实现了标签隐含属性显性化,一定程度上提高了存储率与检索率,对非结构化数据具有推广意义,仿真结果证明了模型的有效性.
致谢: 感谢移动媒体与文化计算北京市重点实验室的支持[1] | 孙涛. 面向半结构化数据的数据模型和数据挖掘方法研究[D]. 吉林: 吉林大学, 2010. http://cdmd.cnki.com.cn/Article/CDMD-10183-2010107378.htm |
[2] | Zhu Xiaowei. Research on automatic classification technology of flash animations based on content analysis[J]. Journal of Multimedia, 2013, 8(6): 693–698. |
[3] | Fouche M A, Olivier M. Steganographic techniques for hiding data in swf files[C]//IFIP International Conference on Digital Forensics. Berlin Heidelberg:Springer, 2011:245-255. |
[4] | Zhang Jinqun, Zhu Yunqiang, Wang Juanle, et al. Flash based WebGIS system and its application in monitoring and evaluating China's regional development[J]. International Journal of Digital Content Technology and Its Applications, 2011, 5: 285–295. |
[5] | 王岳平. Flash电影的视觉场景和图形图像特征研究[D]. 济南: 山东师范大学, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10445-1013215496.htm |
[6] | 杨学伟. 基于OEM模型的半结构化数据模式抽取算法研究[D]. 北京: 中国石油大学, 2011. http://cdmd.cnki.com.cn/Article/CDMD-10425-1011287578.htm |
[7] |
曹文仙, 赵雪岩, 李建成, 等. 半结构化数据OEM图应用[J]. 西安工程科技学院学报, 2007, 01: 92–95.
Cao Wenxian, Zhao Xueyan, Li Jiancheng, et al. Application of the semi structured data OEM diagram[J]. Journal of Xi'an University of Engineering Science and Technology, 2007, 01: 92–95. doi: 10.3969/j.issn.1674-649X.2007.01.020 |
[8] |
黄洪, 林辉, 王奔. 一种图形用户界面的XML描述方法与工具开发[J]. 计算机应用与软件, 2011, 10: 198–202.
Huang Hong, Lin Hui, Wang Ben. A GUI XML description method and tool development[J]. Computer Applications and Software, 2011, 10: 198–202. |
[9] |
张富, 严丽, 马宗民, 等. 基于模糊描述逻辑的模糊XML模型的表示与推理[J]. 计算机学报, 2011, 08(8): 1437–1451.
Zhang Fu, Yan Li, Ma Zongmin, et al. Representation and reasonng of fuzzy XML model with fuzzy description logic[J]. Chinese Journal of Computers, 2011, 08(8): 1437–1451. |
[10] | 孙宏伟. XML与RDB的多层次双向数据集成技术研究[D]. 西安: 西北工业大学, 2003. http://cdmd.cnki.com.cn/article/cdmd-10699-2004021973.htm |
[11] | 张敏. Flash组成元素的视觉特征研究[D]. 济南: 山东师范大学, 2011. http://cdmd.cnki.com.cn/article/cdmd-10445-1011079407.htm |
[12] | Deng Hua, Zhang Jifu, Chai Xiaoli. The design and implementation of flash animation watermarking[C]//2014 IEEE Workshop on Electronics, Computer and Applications.[S.l.]:IEEE, 2014:489-491. |
[13] | 陈爱东. Flash动画的内容提取与描述模型研究[D]. 济南: 山东师范大学, 2010. http://cdmd.cnki.com.cn/Article/CDMD-10445-2010230601.htm |
[14] | 廖建平. SWF动画内容解析与XML表达自动阅卷研究[D]. 上海: 华东师范大学, 2009. http://cdmd.cnki.com.cn/Article/CDMD-10269-2010028883.htm |
[15] |
倪应华, 金炳尧. SWF矢量动画解析框架设计[J]. 计算机系统应用, 2010, 19(3): 202–205.
Ni Yinghua, Jin Bingyao. Design of an analytical framework with SWF vector graphics[J]. Computer Systems & Applications, 2010, 19(3): 202–205. |
[16] |
鲁明羽, 陆玉昌. 基于OEM模型的半结构化数据的模式抽取[J]. 清华大学学报(自然科学版), 2004(9): 1264–1267.
Lu Mingyu, Lu Yuchang. OEM-based schema extraction of semi-structured data[J]. Journal of Tsinghua University (Science and Technology), 2004(9): 1264–1267. |
[17] | 杨学伟. 基于OEM模型的半结构化数据模式抽取算法研究[D]. 北京: 中国石油大学, 2011. http://cdmd.cnki.com.cn/Article/CDMD-10425-1011287578.htm |
[18] |
李颖, 张晓贤, 孙佳慧. 基于频繁模式半结构化数据的模式抽取[J]. 吉林大学学报(信息科学版), 2012(5): 540–543.
Li Ying, Zhang Xiaoxian, Sun Jiahui. Semi-structured data model extraction based on frequent patterns[J]. Journal of Jilin University (Information Science Edition), 2012(5): 540–543. |
[19] | Ni Yinghua, Yuan Liyong, Ma Yongjin, et al. Research on content retrieval of flash animation based on XML[C]//20103rd IEEE International Conference on Ubi-media Computing (U-Media).[S.l.]:IEEE, 2010:64-67. |