《媒体数据库技术》实验指导与报告书

1、常熟理工学院多媒体数据库技术实验指导与报告书_2011_学年第 _二_学期专业： _计算机科学与技术 _学号： _姓名： _ _实验地点： _ _指导教师： _ _计算机科学与工程学院2011.02实验目录实验 1文本媒体的压缩与解压2实验 2签名文件的仿真实现9实验 3音频信号的时频转换12实验 4基于直方图的图像检索17实验 1文本媒体的压缩与解压实验目的1）给定一段ASCII 文本，采用变长编码进行压缩，生成压缩码流；2）解压生成的压缩码流，还原成原始ASCII 文本；3）掌握变长编码的基本原理和方法。预习内容Huffman 编码实验内容1）采用 C/C+ 实现压缩算法；2）采用 C/C

2、+ 实现解压算法；3）统计和分析生成的码流，计算压缩比；4）分析 Huffman 编码的性能，什么情况下其性能最好？什么情况下性能最差？实验结果 （可续页）#include <stdio.h>#include <stdlib.h>#include <string.h>#include <conio.h>#define MAX_SINGLECODE_LEN 10 / 单个字符最大码长 #define MAX_STRING_LEN 1000 / 要编码的字符串的最大长度 #define MAX_CODESTRING_LEN 10000 / 产生的二进

3、制码的最大长度 #define MAX_WORDS 1000 / 要编码的字符串中字符种数最大值 #define END_TREE 30000 / 树部分存储的结束符#define PATH_LEN 50 / 路径串最大长度/*哈夫曼树结构定义*/typedef struct Huffmantreechar ch; / 字符部分int weight; / 结点权值int mark; / 标记是否加入树中struct Huffmantree *parent,*lchild,*rchild,*next;HTNode,*LinkTree;/*编码字典结构定义*/typedef structchar

4、ch; / 字符部分char codeMAX_SINGLECODE_LEN; /编码部分CodeDictionary;LinkTree setWeight(char *);LinkTree sortNode(LinkTree);LinkTree createHTree(LinkTree);void codeHTree(LinkTree,CodeDictionary *);void decodeHTree(LinkTree,char *,char *);void deleteNode(LinkTree);void compressString(char *s,CodeDictionary *,c

5、har *);void readFile(char *);void writeFile(char *);void readCode(LinkTree,char *);void writeCode(LinkTree,char *);void menu();/* 主函数* 输入：空* 返回：空*/void main(void)char choice; / 菜单选择变量char stringMAX_STRING_LEN; / 保存从文件中读取的内容 LinkTree temp; / 保存赋了权值的表LinkTree ht; / 保存排序后的表LinkTree htcopy,tempcopy; / 表

6、备份LinkTree htree; / 保存哈夫曼树LinkTree ptr=NULL;CodeDictionary codedictionaryMAX_WORDS;/char codestringMAX_CODESTRING_LEN; /char codestring2MAX_CODESTRING_LEN;/LinkTree ht2; / 保存读取的树LinkTree htree2; / 保存排序后的表编码字典保存 0-1 形的代码串保存 0-1 形的代码串char filestringMAX_STRING_LEN; /解码后要写入文件中的内容if(ht2=(LinkTree)malloc(

7、sizeof(HTNode)=NULL)/创建链表的头结点printf(" 内存不足！ ");getch();exit(0);ht2->next=NULL;while(1)menu(); / 调入主菜单choice=getch(); / 读入用户选项switch(choice) / 判断用户选择case 'c':case 'C':printf("n您选择了压缩文件模式:nn");readFile(string); / 读取要编码的文件（字符串）temp=setWeight(string); / 得到有权值的表temp

8、copy=setWeight(string);ht=sortNode(temp); / 按权值排序后的表htcopy=sortNode(tempcopy); / 用于记录解码树htree=createHTree(ht); / 得到哈夫曼树codeHTree(htree,codedictionary);/ 哈夫曼编码compressString(string,codedictionary,codestring);/ 压缩为 0-1 码 writeCode(htcopy,codestring); / 将解码树和 0-1 码保存deleteNode(htree); / 释放空间 */break;ca

9、se 'u':case 'U':printf(" 您选择了解压缩文件模式 :nn");readCode(ht2,codestring2); / 读取要解码的0-1 码htree2=createHTree(ht2); / 得到哈夫曼树codeHTree(htree2,codedictionary);/ 哈夫曼编码decodeHTree(htree2,codestring2,filestring); / 解码writeFile(filestring); /将解码文件保存deleteNode(htree2); / 释放空间break;case &#

10、39;e':case 'E':exit(0); / 退出程序/* 整理输入的字符串，求出每个字符在数组中出现的次数，作为权值* 输入：（字符型指针）字符串的地址* 返回：（哈夫曼结点指针）含权链表的首地址*/LinkTree setWeight(char *string)int i=0; / 文件字符串下标LinkTree tree; / 头指针LinkTree ptr,beforeptr; / 创建指针与其前驱HTNode *node;if(tree=(LinkTree)malloc(sizeof(HTNode)=NULL)/ 创建链表的头结点 return NULL

11、;tree->next=NULL;for(i=0;stringi!='0'i+)ptr=tree;beforeptr=tree;if(node=(HTNode *)malloc(sizeof(HTNode)=NULL)return NULL;node->next=NULL;node->parent=NULL;node->lchild=NULL;node->rchild=NULL;node->mark=0;node->ch=stringi;node->weight=1;if(tree->next=NULL) /如果是第一个非头

12、结点tree->next=node;elseptr=tree->next;while(ptr&&ptr->ch!=node->ch) /查找相同字符ptr=ptr->next;beforeptr=beforeptr->next;if(ptr&&ptr->ch=node->ch) /如果链表中某结点的字符与新结点的字符相同ptr->weight+; / 将该结点的权加一free(node);else /将新结点插入链表后node->next=beforeptr->next;beforeptr->

13、;next=node;return tree; / 返回头指针/* 将整理完的字符串（带权链表）按出现次数从小到大的顺序排列* 输入：（哈夫曼结点指针）要排序的表头地址* 返回：（哈夫曼结点指针）排序后的表头地址*/LinkTree sortNode(LinkTree tree)LinkTree head; / 头指针LinkTree ph,beforeph; / 创建指针及其前驱LinkTree pt;if(head=(LinkTree)malloc(sizeof(HTNode)=NULL)/创建新链表的头结点return NULL;head->next=NULL;ph=head;be

14、foreph=head;while(tree->next)pt=tree->next; / 取被 * 作链表的头结点tree->next=pt->next;pt->next=NULL;ph=head->next;beforeph=head;if(head->next=NULL)head->next=pt; / 创建当前 *作链表头结点elsewhile(ph&&ph->weight<pt->weight) /将被 * 作结点插入相应位置ph=ph->next;beforeph=beforeph->ne

15、xt;pt->next=beforeph->next;beforeph->next=pt;free(tree);return head; / 返回排序后的头指针/* 用排完序的字符串建立哈夫曼树* 输入：（哈夫曼结点指针）要建立哈夫曼树的地址* 返回：（哈夫曼结点指针）建立后的哈夫曼树地址*/LinkTree createHTree(LinkTree tree)LinkTree p,q,beforep;HTNode *newnode;for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->nex

16、t,q=p->next)/p、 q 初值为头结点后的两个结点，即最小权结点tree->next=q->next;q->next=NULL;p->next=NULL;if(newnode=(HTNode *)malloc(sizeof(HTNode)=NULL)/ 申请新结点作为哈夫曼树的中间结点return NULL;newnode->next=NULL;newnode->mark=0;newnode->lchild=p; / 取链表头结点后的两个结点作为新结点的左、右孩子 newnode->rchild=q;p->parent=ne

17、wnode;q->parent=newnode;newnode->weight=p->weight+q->weight; /权值相加p=tree->next;beforep=tree;if(p!=NULL&&p->weight>=newnode->weight)newnode->next=beforep->next; / 将新结点插入原链表的相应位置 beforep->next=newnode;elsewhile(p!=NULL&&p->weight<newnode->weigh

18、t)p=p->next;beforep=beforep->next;newnode->next=beforep->next;beforep->next=newnode;return (tree->next);/* 对哈夫曼树进行编码* 输入：（哈夫曼结点指针）要编码的哈夫曼树地址* （编码字典类型指针）存放字典的首地址* 返回：空*/void codeHTree(LinkTree tree,CodeDictionary *codedictionary)int index=0,k=0;char codeMAX_SINGLECODE_LEN; / 用于统计每个字

19、符的哈夫曼编码 LinkTree ptr=tree; / 从树的根结点开始if(ptr=NULL)printf(" 要压缩的文件是空的!n");exit(0);教师评分实验 2签名文件的仿真实现实验目的1）给定一段文本以及一组关键词，实现文本索引的签名文件技术；2）设计一种哈希函数，把各关键词映射为比特串（签名）；3）将文本分块，采用“位或”操作实现文本块的签名文件；4）输入任意查询关键词，采用“位与”操作实现文本检索。预习内容P79：3.4.3签名文件实验内容1）采用 C/C+ 仿真签名文件技术的整个流程；2）分析产生文本块“误选”的原因，以及避免误选的关键要素。实验结果

20、 （可续页）#include <stdio.h>#include <stdlib.h>#include<string.h>#define B 100#define W 20#define INPUT_FILE "name.txt"enum yn yes, no ;struct cell char nameW + 1;struct cell *next;int h(char *x)int i = 0, hash = 0;while(xi != 0 && i < W) hash += (int)xi;+i;hash %=

21、 B;return hash;void insertcell(char *x, struct cell *A)int k = h(x);struct cell *p = (struct cell *)malloc(sizeof(struct cell);struct cell *q = Ak;struct cell *r = NULL;if(q = NULL) Ak = p; else while(q != NULL) if(strcmp(q->name, x) = 0)free(p);return;elser = q;q = q->next;r->next = p;strc

22、py(p->name, x);p->next = NULL;return;enum yn member(char *x, struct cell *A)struct cell *q = Ah(x);while(q != NULL)if(strcmp(q->name, x) = 0)return (yes);q = q->next;return (no);int main(void)struct cell *AB = 0 ;char xW + 1;FILE *p;if(p = fopen(INPUT_FILE, "r") while(!feof(p)

23、fscanf(p, "%20s", x);xW = '0'insertcell(x, A);fclose(p);while(1) printf("Input a name: ");scanf("%20s", x);xW = '0'printf("%s %sn", x,member(x, A) ? "not found" : "found"); elseprintf("Cannot open %sn", INPUT_FILE)

24、;return 0;教师评分实验 3音频信号的时频转换实验目的给定一段音频信号的时域采样序列x(n), n=0,1,2,N-1，采用离散Fourier变换计算其频域采样序列X (k ), k0,1,2,. N1 。（ 注：实际中N 一般取2 的自然数次幂。 ）预习内容N11）离散 Fourier 变换： X ( k)x(n)WNknk0,1,2,.,N 1n02）离散 Fourier 反变换： x(n)1 N 1X (k)WN knn0,1,2,., N1N k 0j (2 / N )knj (2 / N )kn；其中 WN e, WNe根据欧拉公式 e jtcos(t)j(sin t ) ，

25、离散 Fourier 变换可重写为：N 1N 1X (k) Re X (k)j Im X (k)x( n)cos(2kn/ N )jx(n)sin(2 kn/ N) k 0,1,2,., N 1n 0n 0X (k )Re2 X ( k)1/ 2k 0,1,2,., N 1从而，音频信号的频谱表示为：Im 2 X (k )相位角为： ( k)arctanIm X (k)/ ReX (k)k0,1,2,., N1实验内容1）对给定的音频信号，进行时域离散采样，得到采样序列x(n), n=0,1,2,N-1；2）对采样序列作离散Fourier 变换，得到频域采样序列X (k),k0,1,2,. N

26、1 ；3）计算音频信号的频谱和相位角；4）查阅资料，了解加快离散Fourier 变换速度的方法。实验结果 （可续页）#include<stdio.h>#include<math.h>#include<stdlib.h>#defineN1000typedefstructdoublereal;doubleimg;complex;voidfft(); /*快速傅里叶变换 */voidifft(); /*快速傅里叶逆变换 */voidinitW();voidchange();voidadd(complex,complex,complex*);/* 复数加法 */vo

27、idmul(complex,complex,complex*);/* 复数乘法 */voidsub(complex,complex,complex*);/* 复数减法 */voiddivi(complex,complex,complex*);/* 复数除法 */voidoutput(); /* 输出结果 */complexxN,*W;/* 输出序列的值 */intsize_x=0;/* 输入序列的长度，只限2的 N次方*/doublePI;intmain()inti,method;system("cls");PI=atan(1)*4;printf("Pleasei

28、nputthesizeofx:n");/* 输入序列的长度*/scanf("%d",&size_x);printf("PleaseinputthedatainxN:(such as:5 6)n");/* 输入序列对应的值*/for(i=0;i<size_x;i+)scanf("%lf %lf",&xi.real,&xi.img);initW();/* 选择 FFT 或逆 FFT 运算 */printf("UseFFT(0)orIFFT(1)?n");scanf("%

29、d",&method);if(method=0)fft();elseifft();output();return0;/* 进行基 -2 FFT 运算 */voidfft()inti=0,j=0,k=0,l=0;complexup,down,product;change();for(i=0;i<log(size_x)/log(2);i+)l=1<<i;for(j=0;j<size_x;j+=2*l)for(k=0;k<l;k+)mul(xj+k+l,Wsize_x*k/2/l,&product);add(xj+k,product,&

30、up);sub(xj+k,product,&down);xj+k=up;xj+k+l=down;voidifft()inti=0,j=0,k=0,l=size_x;complexup,down;for(i=0;i<(int)(log(size_x)/log(2);i+) /*蝶形运算*/l/=2;for(j=0;j<size_x;j+=2*l)for(k=0;k<l;k+)add(xj+k,xj+k+l,&up);up.real/=2;up.img/=2;sub(xj+k,xj+k+l,&down);down.real/=2;down.img/=2;d

31、ivi(down,Wsize_x*k/2/l,&down);xj+k=up;xj+k+l=down;change();voidinitW()inti;W=(complex*)malloc(sizeof(complex)*size_x);for(i=0;i<size_x;i+)Wi.real=cos(2*PI/size_x*i);Wi.img=-1*sin(2*PI/size_x*i);voidchange()complextemp;unsignedshorti=0,j=0,k=0;doublet;for(i=0;i<size_x;i+)k=i;j=0;t=(log(size

32、_x)/log(2);while(t-)>0)j=j<<1;j|=(k&1);k=k>>1;if(j>i)temp=xi;xi=xj;xj=temp;voidoutput()/* 输出结果inti;printf("Theresultarefor(i=0;i<size_x;i+)printf("%.4f",xi.real);if(xi.img>=0.0001)*/asfollowsn");printf("+%.4fjn",xi.img);elseif(fabs(xi.img)<

33、;0.0001)printf("n");elseprintf("%.4fjn",xi.img);voidadd(complexa,complexb,complex*c)c->real=a.real+b.real;c->img=a.img+b.img;voidmul(complexa,complexb,complex*c)c->real=a.real*b.real-a.img*b.img;c->img=a.real*b.img+a.img*b.real;voidsub(complexa,complexb,complex*c)c-&g

34、t;real=a.real-b.real;c->img=a.img-b.img;voiddivi(complexa,complexb,complex*c)c->real=(a.real*b.real+a.img*b.img)/(b.real*b.real+b.img*b.img);c->img=(a.img*b.real-a.real*b.img)/(b.real*b.real+b.img*b.img);教师评分实验 4基于直方图的图像检索实验目的1）给定一组灰度图像，计算每帧图像的灰度直方图；2）把每帧图像的灰度直方图表示成向量的形式，建立检索系统的直方图特征数据库；3）定

35、义直方图特征向量的距离公式，以计算两帧图像的相似度；4）给定一个查询要求（草图），计算其直方图特征，根据相似度公式从特征数据库中找到最接近的特征向量，返回特征向量对应的图像作为检索结果。预习内容P145： 6.3.2颜色直方图DIB（设备无关位图）文件格式（BMP）实验内容1）采用 C/C+ 实现实验目的4 步骤；2）直方图特征向量距离可采用L-1 度量法，公式（6.3），更好的方法是累加直方图；3）可对图像先分块，把空间区域信息考虑进去；4）上网查找资料，了解改进直方图图像检索的有效策略。实验结果 （可续页）#include<stdio.h>#include<stdlib.

36、h>typedefchar UC;typedef structint p;int sx;int sy;int vmax;char *v;IMG;void ReadPPM(char *filename,IMG *img)/打开PPM文件FILE *fp;long len;char c1,c2;if(fp=fopen(filename,"rb")=NULL)printf("Can not open the file.n"); /若打不开，则停止程序exit(1);fscanf(fp,"%c%d%d%d%d%c",&c1,&a

37、mp;img->p,&img->sx,&img->sy,&img->vmax,&c2);/读取各参数/第一个 %c 是读取 PPM 文件格式当中的P，若其不是P，则不是 PPM 文件/最后一个 %c 为图像格式后面的空格，防止将其被误认为是像素的大小被读入if(c1!='P'|(img->p!=5&&img->p!=6)/ 判断图像是否为PPM 文件printf("It's wrong to open the file.n");exit(1);len=img->

38、sx*img->sy;if(img->p=5)/ 当图像为黑白时，只分配一个len大小的空间img->v=(UC*)calloc(len,1);fread(img->v,len,1,fp);/将图像的像素信息写入新分配的空间当中if(img->p=6)/为彩色时，则分配3 个 len 大小的空间img->v=(UC*)calloc(len,3);fread(img->v,len,3,fp);fclose(fp);/ 关闭文件void WritePPM(char *filename,IMG img) /写 PPM 文件FILE *fp;long len=

39、img.sx*img.sy;if(fp=fopen(filename,"wb")=NULL)printf("Can not open the file.n");exit(0);if(img.p=5)/ 判断黑白，将其写入一个len 大小的空间当中fprintf(fp,"P%d %d %d %d ",img.p,img.sx,img.sy,img.vmax); fwrite(img.v,len,1,fp);if(img.p=6)fprintf(fp,"P%d %d %d %d ",img.p,img.sx,img.sy,img.vmax);fwrite(img.v,len,3,fp);fclose(fp);void Histogram(UC *v,long sz,int vmax,long *h) /统计图像直方图int i;int pv;for(i=0;i<=vmax;i+)/ 直方图中的像素大小不会超过255*(h+i)=0