《数据结构实验报告高维检索》由会员分享,可在线阅读,更多相关《数据结构实验报告高维检索(2页珍藏版)》请在金锄头文库上搜索。
1、高维数据检索方法的实现及评价高维数据检索方法的实现及评价实验报告实验报告班级:10020801 姓名:吴亮 学号:2008302651 电话:15191416617 日期:2010.1.8 ( (一一) ) 需求分析需求分析 1、实验要求及其功能:给定一组高维(n=128 维)特征数据 A,建立一种高效的检索结构。 在建立好检索结构后,给定几组同样规模大小的高维(128 维)特征数据集 Bi, i=1,2,.m,请实现一种快速的检索方法,针对每个数据集 Bi 中的特征数据,寻找其在 数据集 A 中的最近邻元素(最近邻元素定义为两者之间的欧式距离最小),然后根据全 搜索得到的最近邻结果,统计自己
2、实现方法的正确率。 2、输入输出:实验输入一文件名,然后再输入检索的检索的文件名,然后程序将显示全搜索和进行快 速搜索所需要的时间,以及实现快速搜索的正确率。 ( (二二) ) 概要设计概要设计 1 基本结构: typedef struct /存储 128 维空间中点的坐标double descr128; feature; typedef struct /表示 128 维空间中点的集合feature *f; double *sum; /表空间中每一点的坐标之和List; 2. 基本操作: int read(List &L) 为 L 分配空间,并读取文件中的数据,并返回文件中表示 128 维空间
3、 中点的个数 void distance(List &L,int n1,List &M,int n2,int *DS) 全搜索求 M 中每一个点在 128 维空间中和 L 中的点的最短欧式距离的平方,并将 L 中对应的点的下标存储到 DS中 int Partition(List &L,long low,long high) 交换顺序表 L 中字表 L.rlow.high的 记录,使枢轴记录 d 到位,并返回其所在位置 void Qsort(List &L,long low,long high) 对顺序表 L 中的子序列 L.rlow.high做 快速排序 void speedsearch(Li
4、st &L,int n1,List &M,int n2,int *DS) 快速搜索求 M 中的每一个 点在 128 维空间中和 L 中的点的最短欧式距离的平方,并将 L 中对应的点的下标存储到 DS中( (三三) ) 函数调用模块函数调用模块main()main()int read(List &L)void distance(List &L,int n1,List &M,int n2,int *DS)int Partition(List &L,long low,long high)void Qsort(List &L,long low,long high)void speedsearch(Li
5、st &L,int n1,List &M,int n2,int *DS)( (四四) ) 程序使用说明及测试结果程序使用说明及测试结果 1 程序使用说明 (1) 本程序的运行环境为 VC6.0。 (2) 进入演示程序后即显示提示信息:请输入需要建立高效检索结构的数据的 文件名,输入文件名后,再输入需要检索的数据的文件名,回车等待后将显示程序进行全 搜索所需要的时间以及进行快速搜索所需要的时间和实现快速搜索的正确率。运行界面(五)、实验总结(五)、实验总结( (实验心得实验心得) ) 我有看过其他人所做的,运用的思想大多数一致,也有半面取值法,就是说排好序求出相 应的点的下标后,取下标左边的数据或者是右边的数据。而我所做的正确率相对来说却比 较低,同样的思路,在相同的取值范围内有些人的比我的高很多,我的正确率最高达到百 分之七十多,一般情况是在百分之六十多左右。在同一个检索结构中,不同的数据快速检 索的正确率也不相同。在我所试的第一组数据中,随着所检索数据的减少,正确率也会相 应减小,但是 2000 多数据却比 1000 多数据的正确率高。其他组的数据也大概符合这个规 律。教师评语:教师评语:实验成绩:实验成绩:指导教师签名: 批阅日期: