P2P信息检索系统的查询结果排序与合并策略_凌波
第30卷 第3期2007年3月
计 算 机 学 报
C HIN ESE J OU RNAL OF COM PU TERS
Vol.30No.3
Mar.2007
收稿日期:2005201219;修改稿收到日期:2006209224.本课题得到国家自然科学基金(60373019,60573183和90612007)资助.凌 波,男,1974年生,博士,副教授,目前主要研究方向为P2P 环境下的数据管理、信息系统及区域竞争力等.E 2mail :lingbo @https://www.wendangku.net/doc/782639299.html,.周水庚,男,1966年生,博士,教授,博士生导师,研究兴趣包括信息检索与文本挖掘、空间数据库与地理信息系统以及对等计算等.周傲英,男,1965年生,博士,教授,博士生导师,研究兴趣包括Web 数据管理、数据挖掘、流数据分析与处理以及对等计算等.
① SETI @home Home Page.http ://setiat https://www.wendangku.net/doc/782639299.html, ② ICQ Home Page.http ://https://www.wendangku.net/doc/782639299.html, ③ Groove Home Page.http ://https://www.wendangku.net/doc/782639299.html,
P2P 信息检索系统的查询结果排序与合并策略
凌 波1) 周水庚2) 周傲英
2)
1)(中国浦东干部学院信息技术部 上海 201204)2)
(复旦大学计算机科学与工程系 上海 200433)
摘 要 基于P2P 信息检索系统的特性,提出了一种完全分布式的查询结果排序与合并策略.首先分析当前P2P 信息检索系统查询结果排序和合并问题的根源;接着提出一种完全分布式的查询结果排序与合并策略,包括元数据管理策略、查询结果的排序与合并的实现;然后用详细的实验证明了该策略的有效性.关键词 P2P ;信息检索;查询结果排序与合并中图法分类号TP18
A Strategy of Q uery R esult R anking and Merging for P2P Information R etrieval Systems
L IN G Bo 1) ZHOU Shui 2Geng 2) ZHOU Ao 2Y ing 2
)
1)
(Depart ment of I nf ormation Technology ,China Executive L eadershi p A cadem y ,S hanghai 201204)
2)
(Depart ment of Com puter Science and Engi neeri ng ,Fu dan Uni versit y ,S hanghai 200433)
Abstract This paper p ropo ses a f ully dist ributed strategy to rank and merge t he result s ret rieved from different peers in P2P information ret rieval systems.First ,t he challenges of query answer 2ing in P2P IR systems are investigated and t he issue of ret rieved result s ranking and merging is identified.Seco nd ,a f ully dist ributed strategy is developed and it s implementing issues are ad 2dressed.Finally ,an extensive experimental st udy is conducted and t he result s verify t he effec 2tiveness of t his propo sed st rategy.
K eyw ords P2P ;information ret rieval ;query result ranking and merging
1 引 言
自2000年起,对等计算(peer 2to 2peer ,简称
P2P )倍受计算机研究界的关注.在P2P 系统中,每个对等节点(peer ,简称节点,如用Internet 连接的PC )都拥有对等的功能与责任,既可充当服务器向其它节点提供数据与服务,又可作为客户机享用其
它节点提供的数据与服务、节点间的交互直接对等;此外,任何一个节点可随时加入或离开该系统,形成一个真正的动态网络环境.已经取得的研究成果表明,这类系统具有许多潜在优良特性,如系统可扩展性好、资源(种类与数量)丰富、性能高等,可应用于许多领域:如CPU 周期共享①、信息传输②、协同工作组件③和数据共享[125]等.其中,数据共享已经成为当前P2P 研究的热点.但已有的P2P 数据共享系
统大都仅限于缺乏语义的粗粒度(文件水平)共享,用户通过文件名进行查找.这种不能基于语义来共享数据的机制限制了P2P潜能的发挥.
信息检索(IR)技术已取得很大突破,能对多种数据(文本、图像等)进行语义丰富的检索.但传统的信息检索系统存在固有的局限性,如系统缺乏可扩展性及能力(包括处理能力和存储能力)有限等.这些局限性在当今信息爆炸的时代显得更为突出,限制了IR的广泛应用.
为应对上述两类技术面临的挑战,研究界提出了P2P信息检索的理念[4,627],把P2P与信息检索相集成,充分发掘各自的优点并相互克服对方的不足.由于P2P信息检索技术还处于研发的初始阶段,面临不少挑战.其中,如何排序和合并从多个节点检索出来的答案就是亟待解决的难题之一.本文基于P2P的特性,深入分析该问题的根源,并提出了一种完全分布的检索结果排序与合并策略,取得了如下成果:
(1)通过深入分析,明确了P2P信息检索系统在查询结果排序与合并上所面临的挑战的根源;
(2)提出了一种完全分布的查询结果排序与合并策略,包括元数据管理策略、排序与合并的实现;
(3)进行了详细的实验分析,用实验结果证明了该策略的有效性.
本文的其余部分组织如下:第2节讨论相关工作;第3节对研究问题的根源进行理论分析;第4节提出分布排序与合并策略;第5节进行实验分析;第6节总结全文.
2 相关工作
P2P信息检索系统是一种新型的分布式信息检索系统.传统的分布式信息检索系统通常根据某种划分标准(如文档语义)将整个系统的文档集划分为多个子集,并分配给不同的文件库服务器维护.虽然整个系统物理上有多个文档库,分别由不同节点(服务器)管理,但整个系统在逻辑上仍然只有一个统一的文档库[8].可见,P2P信息检索系统的核心理念和实现机制明显区别于传统的分布式信息检索系统: (1)节点数目不同.P2P信息检索系统可有成千上万个节点,且每个节点都是独立自治的信息检索系统.每个节点都有一个独立的文档库,系统在逻辑上有成千上万个独立的文档库.(2)文档和统计信息管理方式不同.在传统的分布式信息检索系统中,服务器之间相互备份统计信息,每个服务器节点都有全局统计信息;而在P2P环境中,每个节点主要管理本地文档及其统计信息,节点决策时只能借助于局部信息或全局信息近似值.(3)检索处理模式不同.传统信息检索系统有一个中心节点,维护所有文档服务器各自存储文件的特征描述文件,对于一个查询,基于该描述文件可以很好地定位查询答案所在的文档服务器,检索结果排序也由这个中心节点集中式地完成;而在P2P环境中存在中心节点的假设是不现实的.因此,在传统信息检索领域所取得的成果不能直接用于解决P2P环境面临的问题.
最近,P2P信息检索已经开始受到关注.在文献[4]中,我们介绍了在Best Peer[9]平台上开发的P2P 信息检索系统Peer IS,并论述了体系结构、节点内部的模块及工作流程等关键技术,但没有深入研究检索结果排序和合并问题.
Planet P[7]也是一个采用向量空间模型[10]表达文本数据的P2P信息检索系统.该系统采用基于Bloom filter[11]的资源定位和查询结果排序机制.每个节点都采用Bloom filter归纳本地文件的索引,并用go ssiping算法[12]将其在网络中散布.每个节点根据自己收集到的Bloom filter来查询共享文件:首先借助已收集到的Bloom filter来判断哪些节点可能维护查询答案;然后跟最可能提供答案的数个节点建立联系并下载答案;最后,查询提交节点排列这些被检索出的答案.可见,Planet P的排序机制存在以下局限性:(1)该机制是基于启发式规则的,因而不具备确定性.查询在哪些节点执行取决于提交节点所收集到的Bloom filter.由于一个节点不可能收集系统所有节点的Bloom filter,因而查询答案集具有随机性,即对于同一个查询和同一个在线节点集,查全率和查准率不确定.(2)查询排序计算的是集中式的,由查询提交节点完成,因而其计算负荷很重,进而影响系统的响应时间和可扩展性等性能.(3)尤其是它没有考虑各节点本地统计信息相异而导致的问题,这正是当前P2P信息检索系统排序问题的根源所在.本文正是要解决这个问题.
Psearch[6]是在CAN[16]上开发的结构化P2P 信息检索系统,它提出了一种具有确定性的排序策略.通过CAN提供的映射机制,包含特定关键词的索引项被发布到特定的节点.查找文档时,查询被转发给那些包含关键词的节点,后者把相关的索引项返回给查询节点,查询节点计算查询与文档的相似性并排序结果.本文提出的策略明显区别于Psearch
604计 算 机 学 报2007年
的机制,在查询排序计算方式上,Psearch的排序计算由查询提交节点独自完成;而本文提出的机制则把排序计算分散于所有被查询的节点,因而能更好地共享计算资源和平衡工作负荷.
3 检索结果排序与合并的
问题根源分析
不失一般性,可假设P2P信息检索系统的每个节点都采用向量空间模型[14215]表达数据,因为该模型是信息检索中最通用和最成熟的技术.接下来深入分析导致P2P信息检索系统检索结果排序问题的根源.
基于上述假设,P2P信息检索系统的每个文件及用户提交的查询都用向量表达,向量的维度就是系统中关键词的个数.向量的每个权重就是对应关键词表达文档或查询的语义重要程度[16].由此,对于任意一个文档d j,其向量定义如下:
d j=(w1,j,w2,j,…,w t,j)(1)并且,对于用户提交的任意一个查询q的向量为
q=(w1,q,w2,q,…,w t,q)(2) 那么,查询q和文档d j的语义相关程度可用它们向量之间夹角的余弦值来衡量,即
S R(d j,q)=
d?q
|d j|×|q|
=
∑t
i=1
w i,j×w i,q
∑t
i=1
w2i,j×∑
t
i=1
w2i,q
(3)
上式中,文档和查询的关键词的权重(w i)由t f/i d f 规则决定.其中,t f(term frequency)是词频,代表一个关键词在同一文档中出现的次数;i d f(Inverse Document Frequency)为反比文档频数,表示同一关键词在不同的文档中出现次数的倒数.根据该规则,如果一个关键词在同一文档中出现的频率越高,那么就越能表征该文档的语义,其重要程度越高;如果同一个词在不同的文档中出现的次数越多,那么它就越不能区分文档,其重要程度越低.
现在讨论如何计算一个索引项(关键词)的词频.如果用f req i,j表示关键词k i在文档d j中出现的原始次数,即原始词频;标准化词频用f i,j表示,那么可由以下公式计算:
f i,j=
f req i,j
max l f req i,j
(4)
上式中,max l f req i,j为本地最大原始词频.如果k i不在文档d j中出现,则f i,j=0.由式(4)可计算出索引项的词频.可见,任一索引项的词频仅决定于其所在的文档.
现在分析反比文档频数的情况.传统信息检索系统(包括分布式信息检索系统)中,可把整个系统看成一个逻辑节点(该推理在P2P中不成立).如果用N表示该逻辑节点的文档总数,n i表示含有索引词k i的文件总数,i d f i表示k i的反比文档频数;那么k i的反比文档频数可由以下公式计算而得:
i d f i=log
N
n i
(5)
至此,关键词k i的权重可由下列公式计算: w i,j=f i,j×i d f i=
f req i,j
max l f req i,j
×log N
n i
(6) 现在分析P2P环境中关键词权重计算的情况. P2P环境中,每个节点都是独立自治的信息检索系统,让我们在这种背景下分析式(6).由式(4)可知,文档d j的索引项k i的词频f i,j仅由文件本身决定,而跟节点无关,即同一文档d j的索引项k i的词频f i,j在不同节点的取值仍然相同.所以,元数据f i,j 并未给P2P信息检索系统的检索结果排序产生问题.
i d f i的情况却不同.假设x和y为P2P信息检
索系统中的两个不同节点.由于节点是自治的,各自本地文档库中文档总数不同,包含关键词k i的文档个数也不同,即
N x≠N y, n x i≠n y i(7) 现在分析索引项k i在这两个节点中的反比文档频数.在节点x中,k i的反比文档频数为
i d f x i=log
N x
n x i
(8) 在节点y中,索引项k i的反比文档频数为
i d f y i=log
N y
n y i
(9)
由式(7)可知:N x≠N y,n x
i≠n
y
i
,那么在大多数情况下:
i d f x i=log
N x
n x i
≠i d f y
i
=log N
y
n y i
(10) 由元数据N与n的特性可知,式(9)在大多数情况下是成立的.因此,对于同一文档d j的同一关键词k i,它在不同的节点的权重很可能不等.可见,由于P2P系统节点的自治性,同一索引项在不同节点中的反比文档频数不同.
类似地,对于同一个查询q中的关键词k i,它在不同节点解析出的反比文档频数也可能不同.即对
704
3期凌 波等:P2P信息检索系统的查询结果排序与合并策略
于两个不同的节点x 和y ,式(10)在大多数情况下
成立:
w x
i ,q =015+015f req i ,q max q
l (f req i ,q )
×log N x n x i ≠w
y
i ,q
=
015+
015f req i ,q
max q
l (f req i ,q )
×log N y
n y
i
(11)
由式(10)和(11)可得:由于P2P 系统的节点的自治性,单个节点没有全局信息且节点间的元数据不一致,使得节点仅按本地元数据计算得到的排序结果不可比.因此,传统信息检索系统的排序机制不能直接移植到P2P 信息检索系统.
4 检索结果排序与合并策略
本节首先提出一种分布式的元数据管理策略,以支持P2P 环境下检索结果的排序;然后讨论与该策略相关的问题并提出解决方案;最后论述排序与合并的实现过程.411 分布式元数据管理策略
如上所述,当前P2P 信息检索系统的结果排序与合并所面临的挑战根源在于计算环境的变化.解决该问题有三类可供选择的策略:(i )系统提供一个或数个服务器管理所有节点的元数据.检索时,查询请求首先被发送到服务器并由服务器进行检索结果排序计算,或者查询首先散发给可能提供答案的节点,再由这些节点从服务器下载元数据进行检索结果排序计算.采用前一种做法,所有的排序计算都由服务器承当,其必然不堪负重,系统存在可扩展性瓶颈.采用后一种方法,每当有节点处理检索时,都必须从服务器下载元数据,由于系统有大量的节点,且每时每刻都可能有检索处理.因而,服务器须不停响应下载请求,网络传输负荷非常大.并且,这两种方法都存在单点出错的缺点.显然,采用集中式机制的策略不适应于P2P 环境.(ii )所有节点都维护整个网络的相关元数据.该策略必然给所有节点带来极大的存储开销,可扩展性面临致命的挑战;另外,如何散布这些元数据以及维护它们的一致性又是一个问题.(iii )设计一种完全分布式的策略,让每个节点只为本地文件的索引项获得相关元数据的系统全局近似值.该方法有三个优点:(1)每个节点只分摊一小部分存储负荷,消除了(ii )的局限性;(2)索引项的元数据的全局近似值维护在本地,检索结果排序计算可在本地即时完成,可分摊计算负荷,提高查询响应速度;(3)由于检索结果排序只需元数据的全
局近似值①,元数据的更新频率不必很高,因而保证元数据的全局一致性和“新鲜性”不会引发高的传输负荷.显然,该类策略适合解决P2P 信息检索的问题.
接下来论述该策略的实现.假设P2P 信息检索系统的每个节点p 都有唯一的标识符,用P I D 表
示;k i 是该节点本地的任一索引项;n p
i 是节点p 中含有关键词k i 的文档数;N p 是该节点的本地文档总数.进而,定义一个映射方程(如分布式散列表D H T ),把索引项k i 映射到系统中对应的节点X ,X 被定义成关键词k i 的目标节点,用T ar get 表示.于是,节点p 可把本地任一索引项k i 的相关的元数据以元组〈P I D (p ),n p
i ,N p ,TimeS t am p 〉的形式映射到(k i 的)目标节点上.由于系统中所有节点都遵循同一P2P 协议,即每个节点都嵌有相同的映射方程，使得T ar get 能够“收集”齐系统中所有与k i 相关的元组〈P I D (p ),n p
i ,N p ,TimeS t am p 〉.然后,T arget 周期性地“归纳”这些统计信息,并把“归纳”好的统计信息返回给那些上传元组的节点,为方便后面的表述,用U ploaders 代表上传节点.实际上,这些“归纳”好的聚集信息就是关键词k i 的全局统计信息的近似值.基于这些全局近似值,任何节点一旦接到查询,就可在本地计算该查询与本地文档的相似度S R (d j ,q ),并即时排序本地检索结果.注意,T arget 与U ploaders 只是节点在承担不同角色时被赋予不同的称呼而已.索引项的元数据的上传、归纳和返回过程如算法1所述.
算法1. 索引项k i 的n i 和N 的全局近似值获取算法.
输入:，犘犐犇，狀p i ,N p 输出:n i ,N
For Peer P (Initial Peer ):While (true )
{
if (bEx it )//user want to exit exit (0);
if (Is I nitiated ()|FileModi f y ()|FileA d d ()|FileDe 2lete ())//节点刚初始化或其文件库更新{
GetS tatistics (n p i N p );//获取本地节点p 的n p
i N p PI D =（犽i );//根据映射机制确定目标节点
Send To Target (PI D ,〈PI D (P ),n p
i ,N p 〉
);//把统计信息发送到目标节点
Get From T arget (PI D ,n i ,N );
//从目标节点获取全局值n i ,N
}
if (R un Time ()>1day )
//持续运行时间超过更新周期
804计 算 机 学 报2007年
①Waterhouse S..J xta search :Distributed search for distrib 2
uted networks.http ://https://www.wendangku.net/doc/782639299.html,/J XTAsearch.pdf
{
Get From Target (PI D ,n i ,N );
//从目标节点获取全局值n i ,N
Set R un Time ToZero ();//运行时间归零}
slee p (I nternal Time );//等待}
For Peer X (Target Peer ):
While (true ){
if (bEx it )//节点可能离线exit (0);
if (!Queue Em pt y ())//数据队列非空{
ReceiveData (PI D ,n p i ,N p );
//从远程节点接受数据
n i =∑p
n p i +∑
p
(n p i t -n p
i t -1);//计算n i ,t 为当前更新周期,
N =
∑P
N
P
+
∑p
(N
p
t
-N p t -1);
//计算N ,t -1为上一更新周期S endB ackData (PI D ,n i ,N );//返回更新后的数据
}
sleep (I nternal Time );//等待}
412 节点动态性带来的挑战与对策
P2P 系统的显著特征之一就是节点的动态性,
即节点可随时加入或离开系统.节点的动态性必然影响节点元数据的“上载”、“归纳”和“返回”过程,进而影响系统元数据的一致性.回顾算法1,对于索引项k i ,其所在的文档的维护节点(U ploa ders )必须把相关元数据根据映射方程“上载”到对应的T ar get.由于节点的动态性,当U ploa ders 把这些元数据“上载”给T arget 时,如果T ar get 恰好离线或出错,则T ar get 就不能接收到相关的信息;同样,当T ar get 把归纳好的信息返回给U ploaders 节点时,如果U ploaders 刚好离线,那么U ploaders 也接收不到最新的统计信息.因而,节点的动态性给保持系统统计信息的一致性带来了挑战.解决该问题可采用代理机制.对于系统中的任一节点p ,可邀请一个或数个节点形成一个虚拟节点并互为代理,当自己离线时代替自己接收相关信息,并在自己在线时交还自己.这些节点的行为必须满足下列条件:
∪Onli ne proxy ΕO f f li ne p
且
∪Onli ne proxy ∪Onli ne p =7×24
(12)
上式中,∪Onli ne proxy ΕO f f li ne p 表示代理节点在线的时间大于等于节点的离线时间;而∪Onli ne proxy ∪
Onli ne p =7×24表示节点及其代理中,每周7天、每
天24小时的每时每刻都至少有一个节点在线,即节
点p 的代理节点的在线时间必须覆盖节点p 的离线时间.
413 索引更新时机与策略
对于P2P 信息检索系统而言,数据更新时机与更新策略的选择至关重要.由于系统的索引项的数量非常大,数据更新时必然增加节点的计算负荷;同时,节点间的数据传输必然消耗带宽.如果在查询处理时执行数据更新操作,必然影响系统的响应时间.为了消除该影响,系统可选择大部分节点比较空闲的时机(如午夜)更新数据.实验证明该机制是有效的.
当系统节点分布范围较小时,用户行为相对一致,数据更新时机(如午夜)的选择较为容易.当系统的节点分布于不同的时区时,用户的行为往往不一致,因而难以确定统一的节点空闲时机.此时,可以采用412节提出的代理机制来选择合理的数据更新时机,以缓解或消除数据更新对系统响应时间的影响.
数据更新策略是P2P 信息检索面临的另一个重要的问题.有效的更新策略必须能保证查询的正确程度(包括查全率、查准率和正确率,见第5节),又要能有效地利用系统资源(计算资源与带宽资源消耗少),涉及到更新周期、更新方式等多个方面.信息检索的成果(如增量式更新[17218]方式)很有借鉴价值.数据更新本身就是一个重要的研究问题,将专门论述.
414 检索结果分布式排序与合并实现过程
本文提出的分布排序策略在检索处理过程中即时实现.当一个查询通过某个节点提交给系统,这个查询首先在本地进行解析;然后,查询处理以并行的方式在P2P 系统中进行:如果高层元数据表明本地可能有答案,就对本地文档库进行查询,同时根据系统的资源定位机制及查询路由协议把该查询转发给其它可能提供合格答案的节点.其它节点一旦接到查询,便根据高层元数据判断本地是否可能提供合格答案,如果是,就根据式(3)计算查询与相关文档的语义相似度S R (d j ,q ),否则仅转发查询消息.由于相关的统计信息的全局近似值已维护在本地,所以被查询的节点的检索结果排序就可在本地即时完成(而不必进行元数据异地传输).最后,这些节点就把本地满足语义要求的所有答案(即S R (d j ,q )Ε
t hres hol d 的文档d j )或者排在最前面的k 个答
案(即S R (d j ,q )最大的k 个文档)的相关信息以〈Title ,S R ,S um m ary ,P I D ,Hops 〉形式返回给查询提交节点.这里,Title 是被检索出的文档名,S R 是
9
043期
凌 波等:P2P 信息检索系统的查询结果排序与合并策略
查询与该文档的语义相似性,S um m ary是被检索出的文章摘要,P I D是答案提供节点的标识符,而Hops则是答案提供节点到查询提交节点的逻辑距离.查询提交节点一旦接收到答案提供节点返回的这些元组,就根据S R的大小重新排列和合并这些元组列表并展现给用户选择;如果两元组的S R的大小相同,则基于Hops进行二次排序.如果所有这些答案仍然不能满足用户的需求,则查询提交节点再根据答案提供节点返回的信息从相关节点提取那些具有较大S R的元组,然后进行相同的排序合并操作.一旦用户选择了满意的答案,就可从答案提供节点直接下载.整个排序过程可用算法2表示.
算法2. 查询结果排序与合并算法.
For Peer P(querying Peer)://对于查询发起者
void InitiateQuery(query)
{
results+=Query I nL ocal Peer(query);
//在当前节点查询SendQuery ToN eibs(query);
//将查询发送到邻居节点进行查询results+=W ait ForResults(timeslot);
//等待查询结果,等待时间为timeS lot.
Ranking Results(results);//进行结果排序
Dis play Results ToUser(results);
//将结果返回给用户}
for Peer X(queried Peer)://对于被查询节点
void RecieveQuery(query)
{
if(is T hereA ny RelatedResults(query))
//本地有无相关答案{
results=Com puteS imilarit y(query);
//根据式(3)计算相似度}
ReSendQuery ToN eibs(query);
//将查询转发给其它邻居节点for(resultA in results)
//对于results中的任一结果result A {
if(S R(resultA,query)>threshol d)//如相似度大于
阈值
{
S endResult ToQuery I nitiator(resultA);//返回结
果给查询节点
}
}
}
5 实验分析
本节用实验证明本文提出的策略的有效性.首先描述实验环境;然后阐述实验方法论,包括数据分布、对比策略以及实验指标体系;最后依次基于这些指标比较不同的策略.
511 实验设置
实验由同一局域网内的12台PC机构成,配
置:CPU为Intel Pentium118GHz微处理器、128MB RAM、Windows2000操作系统.每台PC运行5～6个Peer IS[4]线程,每个线程代表一个P2P 信息检索节点,由其所在的PC的IP地址和端口标识,于是构造出由64个节点组成的P2P信息检索系统.接着,为每个节点嵌入一个分布式Hash方程来实现元数据的“上载”、
“归纳”和“返回”等操作,使节点获得统计信息的全局近似值并保持其一致性.另外,再产生一个文档集,每个文档的大小为10～100K B,由100个关键词索引;并为每个节点分配1000～2000个文档.再产生一个包含10个关键词的查询转发给相关节点进行S R(d j,q)计算,并根据检索结果评价相关的指标.
512 评价方法
定义三个指标来评价本文提出的策略:查全率(Recall)、查准率(Precision)和正确率(Correct2 ness).三个指标的内涵将在实验分析过程中详细论述.
P2P查询的答案取决于查询访问过的节点.在动态的P2P系统中,同一查询在不同的时间可能访问不同的节点.为了保证实验的可比性,实验环境必须可控,不同的比较方案必须基于同一个节点集评价.我们设计了3种比较方案:(1)Grank,系统的所有文档及与排序相关的元数据都由一个节点维护,这样获得的查全率、查准率和正确率是系统在理想状态下才能够获得的.在实验中,Grank所能获得的查全率、查准率和正确率均设为100%,用作评价基准;(2)Drank表征本文提出的分布式排序策略;
(3)Trank表示节点仅基于本地文档的元数据进行排序,用于反映把传统信息检索系统的排序策略直接用于P2P信息检索系统时出现的情形.
实验采用两种不同的数据分布来评价排序策略:均匀分布和80/20分布.采用均匀分布数据分布时,系统的整个文档集中的文档随机且均匀地分布
给每个节点,因而每个节点本地文档的n p
i
/N p与系统的全局值n i/N很相近,但这种数据分布在现实中是最不可能出现的.80/20分布能够很好地反映基于Internet的现实应用中信息消费的情形[9].
此外,实验机器均为专用;为消除实验误差,实验结果取5次实验的平均值.同时,当评价查全率与查准率时,由于阈值在0168～0177时,实验结果曲
014计 算 机 学 报2007年
线涵盖了所有的变化趋势,并且此时本文提出的策
略相对于传统策略的优势最小,最能说明问题,故513节与514节的实验结果图中仅展示该阈值区间的结果.513 查全率查全率(Recall )是检索处理完成时检索出的相关文档数占系统总的相关文档数的比例.由于节点的动态性,P2P 系统的查全率应该以查询提交至查询完成这段时间内所有在线节点为计算基础,即查询所获得的合格答案的数量与在查询执行过程中所有在线节点所能提供的合格答案之比,计算公式如下:
Recall =
∑Retrieved
A nsw er ∑CurrentAvailable
A nsw er
(13)
上述公式中,
∑Retrieved
A nsw er 是用户在规定时间内获
得的符合需求答案的总数,而∑CurrentAvailable
A nsw er 则为
整个系统范围内查询执行过程中所有在线节点所能提供的满足需求答案的总数目.显然,系统的查全率越高就越能满足用户的需求
,最理想的情况是用户检索出所有合格答案.
在实验中,查询执行5次,查全率的平均结果如图1和图2所示.
图1 均匀数据分布的查全率之比较
图2 80/20数据分布下的查全率之比较
图1所展示的均匀数据分布情形最有利于
Trank ,即仅采用节点本地文档的统计数据进行检索结果排序计算的情形.由上图可见,DRank 和TRank 均很接近于GRank ,这是因为采用均匀数据
分布,在TRank 场景中,每个节点本地文档的统计信息n p
i /N p 从整体而言与系统全局的统计信息n i /
N 比较接近;而采用本文提出的分布式元数据管理
策略,即DRank ,每个节点通过分布式算法能够获得本地所有索引项元数据的全局近似值.注意,即使在最有利TRank 的情形下(采用均匀数据分布),DRank 仍然可以获得更接近理想状态的查全率,这
说明本文提出的分布式策略在元数据管理方面确实有效.
图2展示了80/20数据分布的情形,它最能反映现实应用中信息共享的实际情况.在这种数据分布情况下,DRank 远远优于TRank .并且,随着查询与文档的相似度的阈值(t hreshol d )的增加,DRank 开始迅速增加后几乎保持不变,并非常接近GRank .相反,TRank 的查全率随着查询与文档的相似性的阈值的增加而减少.这是因为本文提出的分布式元数据管理策略能保证节点获取其索引项的元数据的全局近似值,因而可以保证很高的查全率.相反,TRank 策略仅根据本地文档的局部统计信息进行
排序计算,不可避免作出错误的决策;并且,随着查询与文档的相似性的阈值的增加,合格答案被不合格答案取代的机会增加,因而越来越多合格答案被遗漏,导致查全率不断下降.
从上面两个图可见,无论是采用均匀数据分布还是采用80/20数据分布,DRank 的查全率都比TRank 的查全率高,即本文提出的排序策略的查全
率在两种数据分布情况下都高于仅用节点局部统计数据进行检索结果排序的查全率.514 查准率
P2P 信息检索系统与传统信息检索系统的查准
率的计算机理相同,均可用下列公式:
Precision =
∑Qualified
A nsw er
∑Retrieved
A nsw er
.
上式中,
∑Retrieved
A nsw er 是在查询过程中从所有被查
询节点检索出的所有答案的总数目,
∑Qualifed
A nsw er 则
是检索出的结果中所有合格答案总数目,即满足不
等式S R (d j ,q )Εt hreshol d 的答案的总数.
在检验查全率的过程中,也记录了不同阈值时的
∑Retrieved
A nsw er ,∑Qualifed
A nsw er ,并根据式(14)计算出
对应的查准率,五次实验的平均结果如图3与图4所示.
1
143期凌 波等:P2P 信息检索系统的查询结果排序与合并策略
图3 均匀数据分布的查准率之比较
图4 80/20数据分布下的查准率之比
图3展示了采用均匀数据分布时,各种排序策略的查准率的平均值.
图4展示了采用80/20分布时不同排序策略的查准率的平均值.从图3和图4可以看到出现了分别类似于图1和图2的情形.实际上,导致这种结果的原因是一致的.
515 正确率
由于当前P2P数据共享系统的节点在返回检索结果时大多采用top2k协议.即如果被查询节点能够提供可能的合格答案,则返回本地最满足条件的M个答案给查询提交节点,查询提交节点重新排序和合并这些结果后,从中选出最能满足语义要求的K个答案给用户选择.
为了验证本文提出的分布式检索结果排序策略在top2k协议中的有效性,我们定义了一个新的评价指标:正确率(Correct ness).接下来论述正确率的内涵与计算方法.假设在P2P信息检系统中的一次查询处理中,任意一个查询处理节点返回M个最符合语义要求的答案给查询提交节点,该集合定义为{a1,a2,…,a M},那么所有查询处理节点提供的答案所构成的集合为∪
Queried_peer
{a1,a2,…,a M}.并且,假设所有的共享文档仅由一个节点维护(即GRank),那么对于同一查询,该节点提供与∪
Queried_peer
{a1,a2,…,a M}相同数目的最好答案构成的集合为{GlobalA nsw ers},而其中最满足语义的K个(top k)答案构成的子集为{Top K G lobalAnswers},那么P2P信息检索系统的正确率可由下列公式计算:
Correct ness=
∪
Quieried_peer
{a1,a2,…,a M}∩{Top K G lobalAnswers}
{Top K G lobalAnswers}
(15)
我们分别在均匀数据分布和80/20数据分布的情形下,用前面定义的查询来评价这三种排序策略的正确率.显然,基于上述定义,GRank策略的正确率为100%.在数据均匀分布时,查询执行5次所得的平均正确率如图
5所示.
图5 均匀数据分布的正确率之比较
从上图中可见,TRank和DRank的正确率都非常接近于GRank.这也是因为采用均匀数据分布
时,TRank中单个节点的n p
i
/N p接近于n i/N,而本文提出的排序策略(DRank)保证了查询处理节点获得(相关全局信息)n i/N的近似值,因而两者的正确率很高并且接近.即使在这种情形下,DRank的正确率仍然比TRank的正确率高.
图6 80/20数据分布下的正确率之比较图6展示了80/20数据分布时不同排序策略的正确率.该图表明,DRank的正确率远远高于TRank,尤其当K值较小时,两者的差异更加明显.这是因为本文提出的策略保证了节点获得非常接近
于系统的n p
i
/N p,而TRank中单个节点的n p i/N p远远偏离于系统的n i/N.此外,可以观察到,随着K 的增加,DRank与TRank的正确率都变差.这是因为,随着K的增加,M也增加,所有查询节点返回越来越多的答案,虽然这些答案在查询节点本地排列
214计 算 机 学 报2007年
较前,但从系统全局来看却很可能不是较前的.因而,随着K的增加,两者的正确率都下降.由于在P2P应用中,用户仅关注最前几个答案.所以,本文提出的分布式排序策略是有效的,而传统信息检索系统的排序策略难于满足需求.
总之,无论是在均匀数据分布还是在80/20数据分布情形下,本文所提出的分布式排序策略的查全率、查准率和正确率都比仅根据节点在本地文档的局部统计信息计算排序优先权对应的指标更好.
6 结 论
本文深入分析了导致P2P信息检索系统在查询结果排序与合并上产生问题的根源,提出了一种完全分布式的检索结果排序与合并策略、采用该策略的相关问题及其解决方案,并简要描述了这种检索结果排序和合并的实现过程.此外,用实验验证了该策略的有效性和实用性.实验结果表明,本文提出的策略远远优于仅根据节点在本地文档的局部统计信息进行检索结果排序的传统做法,并非常接近理想情况下所能取得的结果.
参考文献
[1]Druschel P,Rowstron A.PAST:A large2scale persistent
peer2to2peer storage utility//Elphinstone K ed.Proceedings
of t he8t h Workshop on Hot Topics in Operating Systems
(HotOS2VIII).Schoss Elmau,Germany:IEEE Press,
2001:65270
[2]Kalnis P,Ooi B,Papadias D,Tan K.An adaptive peer2to2
peer network for distributed caching of olap result s//Ra2
makrishnan R ed.Proceedings of ACM Conference on Man2
agement of Data(ACM SIGMOD).Madison,Wisconsin,
U SA:ACM Press,2002:25236
[3]Wee Siong Ng,Beng Chin Ooi,K ian2Lee Tan,Aoying
Zhou.PeerDB:A P2P based system for distributed data sha2
ring//Proceedings of ICDE,2003:6332644
[4]Ling Bo,Lu Zhi2Guo,Ng Wee Siong,Qian Wei2Ning,Zhou
Ao2Y ing.PeerIS:A Peer2to2Peer based Information retriev2
al System.Journal of Software,2004,15(9):137521384(in
Chinese)
(凌 波,陆治国,黄维雄,钱卫宁,周傲英.PeerIS:基于
Peer2to2Peer的信息检索系统.软件学报,2004,15(9):
137521384)
[5]Ling Bo,Wang Xiao2Yu,Zhou Ao2Y ing,Ng Wee Siong.A
collaborative Web caching system based on Peer2to2Peer ar2
chitecture.Chinese Journal of Computers,2005,28(2):
1702178(in Chinese)
(凌 波,王晓宇,周傲英,黄维雄.一种基于Peer2to2Peer技
术的Web缓存系统研究.计算机学报,2005,28(2):1702
178)
[6]Tang Chun2Qiang,Xu Zhi2Chen et al.pSearch:Information
retrieval in structured https://www.wendangku.net/doc/782639299.html,puter Communication
Review,2003,33(1):89294
[7]Cuenca2Acuna FM,Nguyen TD.Text2Based content search
and retrieval in ad hoc P2P communities.Depart ment of
Computer Science,Rutgers University:Technical Report
DCS2TR2483,2002
[8]Richardo Baeza2Yates,Bert hier Ribeiro2Neto.Modern Infor2
mation Retrieval.New Y ork:ACM Press,Addison2Wesley,
1999
[9]Ng W S,Ooi B C,Tan K L.Best Peer:A self2configurable
Peer2to2Peer system//Chrysant his P K ed.Proceedings of
t he18t h International Conference on Data Engineering.San
Jose,CA,USA:IEEE Computer Society Press,2002:272 [10]Anick P G.Adapting a full2text information retrieval system
to computer t he t roubleshooting domain//Proceedings of t he
ACM SIGIR′94,1994:3492358
[11]Bloom B H.Space/time trade2off s in hash coding.Journal of
t he ACM,1970
[12]Demers A,Greene D,Hauser C,Irish W,Larson J,Shenk2
er S,Sturgis H,Swinehart D,Terry D.Epidemic algorit hms
for replicated database maintenance//Proceedings of t he6t h
Annual ACM Symposium on Principles of Distributed Com2
puting,1987:1212
[13]Ratnasamy S,Francis P,Handley M,Karp R,Shenker S.
A scalable content2addressable network//G ovindan R ed.
Proceedings of t he ACM SIGCOMM.San Diego,CA:ACM
Press,2001:1612172
[14]Salton G,Lesk M https://www.wendangku.net/doc/782639299.html,puter evaluation of indexing and
text processing.Journal of t he ACM,1968,15(1):8236 [15]Raghavan V V,Wong S K M.A critical analysis of vector
space model for information retrieval.Journal of t he Ameri2
can Society for Information Science,1986,375(3):2792287 [16]Yu C T,Salton G.Precision weighting—An effective auto2
matic indexing met hod.Journal of t he ACM,1976,23(1):
76288
[17]Brown E W,Callan J P,Bruce Croft W.Fast incremental in2
dexing for full2text information retrieval//Proceedings of t he
20t h International Conference on Very Large Databases,
1994:1922202
[18]Ant hony Tomasic,Hector Garcia2Molina,Kurt Shoens.In2
cremental update of inverted list for text document ret riev2
al//Proceedings of t he1994ACM SIGMOD International
Conference on Management of Data,1994:2892300
314
3期凌 波等:P2P信息检索系统的查询结果排序与合并策略
L ING Bo,born on1974,Ph.D.,
associate professor.His main research
interests include data management and
information retrieval in peer2to2peer
computing,information systems,and
regional economics etc.
ZH OU Shui2G eng,born on1966,Ph.D.,professor,Ph.D.supervisor.His main research interests include infor2 mation retrieval and text mining,GIS and special database, and P2P computing etc.
ZH OU Ao2Ying,born on1965,Ph.D.,professor, Ph.D.supervisor.His main research interests include Web data management,data mining,data stream management and analysis,P2P computing,and financial data management and analysis etc.
B ackground
This paper is supported by projects funded by National Natural Science Foundation of China:"Query Processing in P2P Environment"(grant No160373019)and"Searching in P2P Networks"(grant No190612007)etc.These projects manage to address the challenges related to the data manage2 ment in P2P environment,so that the potential merits of P2P are exploited to effectively manage and process data in such an environment and propose new P2P2ased applications,in2 cluding relational data sharing and processing,data mining, and information retrieval.Specifically,the key techniques of information retrieval,such as result ranking and merging, are also the important topics of the projects.
Although great advances have been achieved in peer2to2 peer computing since2000,most of the other projects have following characters and limitations:(1)They are operating system or network oriented but not data2centered;(2)Most of them just support semantics2f ree file sharing of file granu2larity;(3)No comprehensive data operation and algorithms or strategies have been proposed.On the contrary,these projects manage to achieve semantic and effective data man2 agement in P2P environment and propose P2P2based informa2 tion retrieval as well.Specifically,this paper targets one of the key challenges of information retrieval in P2P environ2 ment,e.g.,how to rank and merge results retrieved f rom different peers,and successf ully proposed a f ully distributed strategy to rank and merge the results retrieved from differ2 ent peers in P2P information retrieval systems.First,the challenges of query answering in P2P IR systems have been investigated and the issue of retrieved results ranking and merging has been identified.Second,a f ully distributed strategy has been developed and its implementing issues have been addressed.Finally,an extensive experimental study has been conducted and its results have verified the effectiveness of this proposed strategy.
414计 算 机 学 报2007年
SQL语句从大到小排序
根据下面三个关系模式完成下面习题：答案已设为白色需要就全选设为黑色学生表student 第一章课件：编写基本的sql语句。 1．查询所有学生情况。 3．查询所有学生的姓名，性别以及年龄。 5．查询所有学生10年后的年龄。 7．查询所有课程（列名用中文显示）。 9．查看竟有那些学生选课（重复学号显示一次）。 11．显示课程表的边结构。第二章课件：约束和排序数据。 01．查询计算机系的所有学生的姓名和年龄。 02．查询体育课的学分。 03．查询年龄小于18的学生。 04．查询年龄大于20的学生。 05．查询年龄介于18和20之间的学生（包括18和20）。 06．查询年龄不在18和20之间的学生。 07．查询年龄为18，20，22的学生。 08．查询年龄不是18，20，22的学生。 09．查询所有姓张的学生。 10．查询所有没有先行课的课程。 11．查询有先行课的课程。 12．在计算机系中找，姓张的男生。 13．在计算机系中找，姓张的或者姓李的男生并且按照年龄从大到小排序。 14．查询所有学生信息，显示结果先按系从大到小排序，再按年龄排序。 第三章课件：多表查询 1．查询每个学生（学号）选了哪门课（课程）得了多少分 2．查询每个学生（姓名）选了哪门课（课程号）得了多少分 3．查询每个学生（姓名）选了哪门课（课程名）得了多少分 4．查询一下王林选可哪门课得了多少分。 5．查询每个学生的成绩类别（优、良还是及格）。 6．查询哪个学生没有选课（用外查询）。 7．查询哪门课没有人选（用外查询）。 第四章课件：组函数
1．查询一下所有课程的平均分，最高分，最低分和总分数。 2．查询一下有多少个学生参加选课。 3．查询一下计算机系有多少人过20岁。 4．统计一下计算机系的男生多少人。 5．查询一下每个学生考试的最高分和最低分。 6．查询每门课（课程号）的最高分和最底分。 7．查询每门课（课程名）的最高分和最底分。 8．查询计算机系中男生多少人，女生多少人。 9，查询人数在三百人以上的系。 10．查询选修人数在三人（包括三人）的课程（课程名）。 11．查询各科考试成绩最低的同学。 12．查询考试成绩小于所选课程平均分的人。（有能力的同学选做） 第五章课件：子查询 1．查询所有比王林大的同学信息。 2．查询和王林同在一个系的所有学生信息。 3．查询一下谁的成绩（所有成绩）最低。 4．查询一下每门课成绩最底的同学（要姓名，和成绩）。 5．查询一下哪个学生没有选课（用子查询）。 6．查询一下哪门课没有人选（用子查询）。 7．查询一下和王林一个系，但是比他年龄大的同学。 第六章课件：ddl语句 1．创建以上四个表，要求每个表必须有主键，表和表之间必须有外间关联。 3．写出insert语句，给表添加以上数据。 5．提交所有操作。 7．将王林的年龄设置为空。 9．将张大民调到计算机系。 11．将体育课的学分设置成和管理学学分一样（update 中带有子查询）。 13．回滚所有操作。 9．某公司印了一批充值卡，卡的密码是随机生成的，现在出现这个问题：卡里面的“o和0”（哦和零）“i和1”（哎和一），用户反映说看不清楚，公司决定，把存储在数据
排序操作实验报告
数据结构与算法设计 实验报告 （2016 — 2017 学年第1 学期） 实验名称： 年级： 专业： 班级： 学号： 姓名： 指导教师： 成都信息工程大学通信工程学院
一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 （1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。 （2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。 三、实验步骤 1、创建工程（附带截图说明） 2、根据算法编写程序（参见第六部分源代码） 3、编译 4、调试 四、实验结果图 图1-直接输入排序
图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡
排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。 六、源代码 要求：粘贴个人代码，以便检查。 #include 稳定排序和不稳定排序 这几天笔试了好几次了，连续碰到一个关于常见排序算法稳定性判别的问题，往往还是多选，对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目，当然如果你笔试之前已经记住了数据结构书上哪些是稳定的，哪些不是稳定的，做起来应该可以轻松搞定。本文是针对老是记不住这个或者想真正明白到底为什么是稳定或者不稳定的人准备的。 首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。 其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。 回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。 (1)冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。 (3)插入排序 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 (4)快速排序 快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时 Sql Server排序规则的简介、选择、应用 一、排序规则简介： 什么叫排序规则呢？MS是这样描述的："在Microsoft SQL Server 中， 字符串的物理存储由排序规则控制。排序规则指定表示每个字符的位模式以及存 储和比较字符所使用的规则。" 在查询分析器内执行下面语句，可以得到SQL SERVER支持的所有排序规则。 select * from ::fn_helpcollations() 排序规则名称由两部份构成，前半部份是指本排序规则所支持的字符集。 如： Chinese_PRC_CS_AI_WS 前半部份：指UNICODE字符集，Chinese_PRC_指针对大陆简体字UNICODE的排序规则，按拼音排序。 Chinese_PRC_Stroke 表示按汉字笔画排序； 排序规则的后半部份即后缀含义： _BIN 二进制排序 _CI(CS) 是否区分大小写，CI不区分，CS区分(case-insensitive/case-sensitive) _AI(AS) 是否区分重音，AI不区分，AS区分(accent-insensitive/accent-sensitive) _KI(KS) 是否区分假名类型,KI不区分，KS区分(kanatype-insensitive/kanatype-sensitive) _WI(WS) 是否区分宽度WI不区分，WS区分(width-insensitive/width-sensitive) 区分大小写:如果想让比较将大写字母和小写字母视为不等，请选择该选项。 区分重音:如果想让比较将重音和非重音字母视为不等，请选择该选项。如果选择该选项， 比较还将重音不同的字母视为不等。 区分假名:如果想让比较将片假名和平假名日语音节视为不等，请选择该选项。 区分宽度:如果想让比较将半角字符和全角字符视为不等，请选择该选项。 二、排序规则选择： 如果SQL Server 实例的所有用户都使用同一种语言，则应选取支持该语言的排序规则。例如，如果所有用户都讲法语，则选择法语排序规则。如果您的SQL Server 实例的用户讲多种语言，则应选择能最好地满足各种语言需要的排序规则。例如，如果用户一般都讲西欧语言，则选择Latin1_General 排序规则。 如果要支持讲多种语言的用户，则对于所有字符数据使用Unicode 数据类型nchar、nvarchar 和nvarchar(max) 是非常重要的。Unicode 可避免非Unicode 的char、varchar 和text 数据类型带来的代码页转换难题。因为排序规则定义用于比较操作的排序次序和Unicode 字符的排序，所以当用Unicode 数据类型实现所有列时，排序规则仍会产生不同。即使使用Unicode 数据类型存储字符数据时，也应选择支持大多数用户的排序规则，以防使用非Unicode 数据类型实现列或变量。 SQL Server 只支持由基础操作系统支持的代码页。在执行取决于排序规则的操作时，引用的对象所使用的SQL Server 排序规则必须使用计算机上运行的操作系统所支持的代码页。 如果指定的排序规则（或引用的对象所使用的排序规则）使用Windows 操作系统不支持的代码页，则SQL Server 将发出错误。对此错误的响应取决于计算机上安装的Windows 操作系统的版本。Windows 2000 及更新版本支持由SQL Server 排序规则使用的所有代码页。因此，不会出现该错误消息。 实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若key 信息学部算法分析 上机报告 学号0901******** 姓名陈龙 指导老师秦明 时间2011.11.1~11.23 一．上机实验题目 实验1 比较归并排序和快速排序的区别。 实验2 利用贪心算法对背包问题进行求解。 二．算法设计思路 归并排序： 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列，设定两个指针，最初位置分别为两个已经排序序列的起始位置，比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置，重复步骤直到某一指针达到序列尾，将另一序列剩下的所 有元素直接复制到合并序列尾。 快速排序： 设置两个变量I、J，排序开始的时候：I=0，J=N-1；以第一个数组元素作为关键数据，赋值给key，即key=A[0]；从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与key交换；从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与key交换；重复第3、4、5步，直到I=J；(3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i，j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。) 背包问题： 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]} 三. 源程序 归并排序 #include 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的，记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0] 小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 《数据结构》课程设计报告 专业 班级 姓名 学号 指导教师 起止时间 课程设计：排序综合 一、任务描述 利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 （2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 要求：根据以上任务说明，设计程序完成功能。 二、问题分析 1、功能分析 分析设计课题的要求，要求编程实现以下功能： （1）随机生成N个整数，存放到线性表中； （2）起泡排序并计算所需时间； （3）简单选择排序并计算时间； （4）希尔排序并计算时间； （5）直接插入排序并计算所需时间； （6）时间效率比较。 2、数据对象分析 存储数据的线性表应为顺序存储。 三、数据结构设计 使用顺序表实现，有关定义如下： typedef int Status; typedef int KeyType ; //设排序码为整型量 typedef int InfoType; typedef struct { //定义被排序记录结构类型 KeyType key ; //排序码 I nfoType otherinfo; //其它数据项 } RedType ; typedef struct { RedType * r; //存储带排序记录的顺序表 //r[0]作哨兵或缓冲区 int length ; //顺序表的长度 } SqList ; //定义顺序表类型 四、功能设计 （一）主控菜单设计 实验五 查找及排序 实验课程名： 数据结构与算法 一、实验目的及要求 1、掌握查找的不同方法，并能用高级语言实现查找算法。 2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法。 3、掌握常用的排序方法，并能用高级语言实现排序算法。 4、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。 5、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 二、实验内容 任务一：顺序表的顺序查找。 有序表的折半查找。 完成下列程序，该程序实现高考成绩表（如下表所示）的顺序查找，在输出结果中显示查找成功与查找不成功信息。 解答： （1）源代码：#include 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实作出来，且在大部分真实世界的资料，可以决定设计的选择，减少所需时间的二次方项之可能 递回关系式为： T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1) 这与插入排序和选择排序有相同的关系式，以及它被解为T(n) = O(n2)。 [编辑] 乱数快速排序的期望复杂度 乱数快速排序有一个值得注意的特性，在任意输入资料的状况下，它只需要O(n log n)的期望时间。是什么让随机的基准变成一个好的选择？假设我们排序一个数列，然后把它分为四个部份。在中央的两个部份将会包含最好的基准值；他们的每一个至少都会比25%的元素大，且至少比25%的元素小。如果我们可以一致地从这两个中央的部份选出一个元素，在到达大小为1的数列前，我们可能最多仅需要把数列分割2log2 n 次，产生一个 O(nlogn)算法。 不幸地，乱数选择只有一半的时间会从中间的部份选择。出人意外的事实是这样就已经足够好了。想像你正在翻转一枚硬币，一直翻转一直到有 k 次人头那面出现。尽管这需要很长的时间，平均来说只需要 2k 次翻动。且在 100k 次翻动中得不到 k 次人头那面的机会，是像天文数字一样的非常小。借由同样的论证，快速排序的递回平均只要 2(2log2 n)的呼叫深度就会终止。但是如果它的平均呼叫深度是O(log n)且每一阶的呼叫树状过程最多有 n 个元素，则全部完成的工作量平均上是乘积，也就是 O(n log n)。 [编辑] 平均复杂度 即使如果我们无法随机地选择基准数值，对于它的输入之所有可能排列，快速排序仍然只需要O(n log n)时间。因为这个平均是简单地将输入之所有可能排列的时间加总起来，除以n这个因子，相当于从输入之中选择一个随机的排列。当我们这样作，基准值本质上就是随机的，导致这个算法与乱数快速排序有一样的执行时间。 更精确地说，对于输入顺序之所有排列情形的平均比较次数，可以借由解出这个递回关系式可以精确地算出来。 在这里，n-1 是分割所使用的比较次数。因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。 这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。这意味着，它比最坏情况较接近最好情况。这个快 2010级数据结构实验报告 实验名称：排序 姓名：袁彬 班级： 2009211120 班内序号： 09 学号： 09210552 日期： 2010 年12 月19 日 1．实验要求 试验目的： 通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。 试验内容： 题目一： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②希尔排序 ③冒泡排序； ④快速排序； ⑤简单选择排序； ⑥堆排序 ⑦归并排序 ⑧基数排序 ⑨其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 题目二： 使用链表实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②冒泡排序； ③快速排序； ④简单选择排序； ⑤其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作） ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。 程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。 2.2 关键算法分析 ㈠、关键算法： 1、插入排序函数：Insert s ort(int n) ①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++) ②、如果后面的比前面的小，则进行前移：if(number[i] 沈阳化工大学实验报告 课程名称算法设计与分析 项目名称归并排序(分治)和插入排序的比较 学院应用技术学院 专业计中职1401 指导教师张雪 报告人张庭浩学号 1422030125 实验时间 2016.11.05 提交时间 2016.11.05 一、实验目的 1.理解和掌握分治算法的相关内容。 2.具体完成插入排序和归并排序性能的比较。 二、实验内容 编写一个真随机函数，随机产生大量数字。在产生相同的一组大量随机数字后，分别用归并排序和插入排序两种算法进行排序，并通过时间函数分别计算出运行的时间。 三、伪代码 1.归并排序 /*数组a[]是原始数组，数组b[]是目标数组*/ 归并排序（数组a[],数组b[]）{ `分割与归并（数组a[],0, a.length,数组b[]) } /*通过递归把要排序的子序列分的足够小*/ 分割与归并（数组a[],起始位置,结束位置,数组b[]){ if(结束位置- 起始位置< 2) 返回 中间位置= （起始位置+结束位置）/2 分割与归并（数组a[],起始位置,中间位置,数组b[]) 分割与归并（数组a[],中间位置,结束位置,数组b[]) 归并（数组a[],起始位置，中间位置，结束位置，数组b[]) 拷贝（数组a[],起始位置，结束位置，数组b[]) } 归并（数组a[],起始位置，中间位置，结束位置，数组b[]){ i0 = 起始位置，i1 = 中间位置 for j = 起始位置到结束位置 if(i0 < 中间位置且（i1 > 结束位置或a[i0] <= a[i1]){ //当i0没有超过中间位置时，有两种情况要将a[i0]复制到b[j]上： //1.i1已经超过结束位置，只要把剩下的复制过来就好； //2.a[i0]比a[i1]小 b[j]=a[i0] i0++ } else { b[j]=a[i1] i1++ } } 各种排序算法稳定性的探讨 首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。为了简便下面讨论的都是不降序排列的情形，对于不升序排列的情形讨论方法和结果完全相同。 其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。 回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。 (1)冒泡排序 冒泡排序是通过相邻比较、实时交换、缩小范围实现排序的。第1次操作n个元素，通过相邻比较将0~n-1中的最大元素交换到位置n-1上，第2次操作n-1个元素，通过相邻比较将0~n-2中的最大元素交换到位置n-2上……第n-1次操作2个元素，通过相邻比较将0~1上的最大元素交换到位置1上完成排序。在相邻比较时如果两个元素相等，一般不执行交换操作，因此冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是通过不断缩小排序序列长度来实现的。第1次操作n个元素，选择0~n-1中的最小者交换到位置0上，第2次操作n-1个元素，选择1~n-1中的最小者交换到位置1上……第n-1次操作2个元素，选择n-2~n-1上的最小者交换到位置n-2上完成排序。在每次选择最小元素进行交换时，可能破坏稳定性。这种情况可以描述为：约定要发生交换的位置称为当前位置，被交换的位置称为被交换位置，被交换位置上的元素为选中的最小元素。如果当前位置之后和被交换位置之前存在与当前位置相等的元素，执行交换后就破坏了稳定性。如序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。 (3)插入排序 插入排序是通过不断扩大排序序列的长度来实现的。第1次操作1个元素，直接放到位置0上即可；第2次操作2个元素，在0~1上为当前元素找到合适位置并插入；第3次操作3个元素，用在0~2上为当前元素找到合适位置并插入它……第n次操作n个元素，在0~n-1上为当前元素找到合适位置并插入完成排序。讨论元素的插入过程，假设当前是第n次操作，要在0~n-1上为当前元素寻找合适位置，设置一个工作指针初始化为n-1，向前移动工作指针直到遇到一个不大于当前元素的元素，就在这个元素的后面插入当前元素，仔细体会这个插入过程，不难理解插入排序是稳定的。 (4)快速排序 快速排序有两个方向，左边的i下标当a[i] <= a[center]时一直往右走，其中center是中枢元素的数组下标，一般取为当前排序段的第一个元素。而右边的j下标当a[j] > a[center]时一直往左走。如果i和j都走不动了，这时必有结论a[i] > a[center] >= a[j]，我们的目的是将a 分成不大于a[center]和大于a[center]的两个部分，其中前者位于左半部分后者位于右半部分。所以如果i>j(i不能等于j，为什么？)表明已经分好，否则需要交换两者。当左右分好时，j 指向了左侧的最后一个元素，这时需要将a[center]与a[j],交换，这个时侯可能会破坏稳定性。 sqlserver:整理一下SQLSERVER的排序规则疯狂代码 https://www.wendangku.net/doc/782639299.html,/ ?:http:/https://www.wendangku.net/doc/782639299.html,/DataBase/Article68892.html SQL SERVER排序规则平时使用不是很多也许不少初学者还比较陌生但有 个大家应是经常碰到: SQL SERVER数据库在跨库多表连接查询时若两数据 库默认集区别系统就会返回这样: “无法解决 equal to 操作排序规则冲突” .分析: 这个是排序规则不致造成我们做个测试比如: create table #t1( name varchar(20) collate Albanian_CI_AI_WS, value ) create table #t2( name varchar(20) collate Chinese_PRC_CI_AI_WS, value ) 表建好后执行连接查询: select * from #t1 A inner join #t2 B _disibledevent=>这样就出现了: 服务器: 消息 446级别 16状态 9行 1 无法解决 equal to 操作排序规则冲突 要排除这个最简单思路方法是表连接时指定它排序规则这样就 不再出现了语句这样写: select * from #t1 A inner join #t2 B on https://www.wendangku.net/doc/782639299.html,=https://www.wendangku.net/doc/782639299.html, collate Chinese_PRC_CI_AI_WS 2.排序规则介绍: 什么叫排序规则呢？MS是这样描述:"在 Microsoft SQL Server 2000 中 串物理存储由排序规则控制排序规则指定表示每个位模式以及存 储和比较所使用规则" 在查询分析器内执行下面语句可以得到SQL SERVER支持所有排序规则 select * from ::fn_helpcollations 排序规则名称由两部份构成前半部份是指本排序规则所支持集 如: Chinese_PRC_CS_AI_WS 前半部份:指UNICODE集Chinese_PRC_指针对大陆简体字UNICODE排序规则 排序规则后半部份即后缀 含义: _BIN 2进制排序 _CI(CS) 是否区分大小写CI不区分CS区分 _AI(AS) 是否区分重音AI不区分AS区分 数据结构实验报告 实验名称：实验四——排序 学生姓名：XX 班级： 班内序号： 学号： 日期： 1．实验要求 实验目的： 通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 题目1： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： 1、插入排序； 2、希尔排序； 3、冒泡排序； 4、快速排序； 5、简单选择排序； 6、堆排序； 7、归并排序； 8、基数排序（选作）； 9、其他。 具体要求如下： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关 键字交换记为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。 5、编写main（）函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 存储结构：数组 2.2 关键算法分析 一、关键算法： 1、插入排序 a、取排序的第二个数据与前一个比较 b、若比前一个小，则赋值给哨兵 c、从后向前比较，将其插入在比其小的元素后 d、循环排序 2、希尔排序 a、将数组分成两份 b、将第一份数组的元素与哨兵比较 c、若其大与哨兵，其值赋给哨兵 d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组 e、循环进行数组拆分 3、对数据进行编码 a、取数组元素与下一个元素比较 b、若比下一个元素大，则与其交换 c、后移，重复 d、改变总元素值，并重复上述代码 4、快速排序 a、选取标准值 b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后 指针前移，重新比较 c、否则后面元素赋给前面元素 d、若后指针元素小于标准值，前指针后移，重新比较 e、否则前面元素赋给后面元素 5、简单选择排序 a、从数组中选择出最小元素 b、若不为当前元素，则交换 c、后移将当前元素设为下一个元素 6、堆排序 a、生成小顶堆 b、将堆的根节点移至数组的最后 c、去掉已做过根节点的元素继续生成小顶堆 GDOU-B-11-112广东海洋大学学生实验报告书 实验名称实验二：使用分组，排序，汇 总 课程名称数据库原理与设计成绩 学院（系）软件学院专业计算机软件工程班级1093 学生姓名唐智羽学号200911701326 实验地点科技楼513 实验日期 一、实验目的： 1.掌握通配符的用法 2.掌握 GROUP BY 子句的使用 3.掌握 ORDER BY子句的使用 4.掌握 TOP和DISTINCT关键字的使用 5.掌握 COMPUTE和COMPUTE BY子句的使用 6.掌握聚集函数的使用 二、实验内容 完成在在Recruitment，GlobalToyz和Student数据库基础上的查询，按要求完成给出的下列题目，要求写出相应数据库的查询语句（SELECT语句） 1.显示以‘S’开头，并且玩具名称不少于7个字符的玩具名称vToyName。SELECT* FROM Toys WHERE vToyName LIKE'S______%' 2.显示名称里包含字母‘u’或‘x’的玩具ID和名称以及价格。 SELECT cToyId, vToyName, mToyRate FROM Toys WHERE vToyName LIKE'%[u]%'OR vToyName LIKE'%[x]%' 3.查询信用卡号（cCreditCardNo）中包含4个8的订购者（Shopper）的详细 信息。 SELECT* FROM Shopper WHERE cCreditCardNo LIKE'%8%8%8%8%' 4.统计订单号为‘000001’的订单订购的玩具的数量和玩具的总花费 （mToyCost）。 SELECT SUM(siQty),SUM(mToycost) FROM OrderDetail WHERE cOrderNo='000001'; 5.统计每份提单订购的玩具数量和玩具花费。 SELECT SUM(siQty),SUM(mToycost)稳定排序和不稳定排序
SqlServer排序规则简介.选择.应用
(完整word版)查找、排序的应用 实验报告
排序算法比较实验报告
算法排序问题实验报告
数据结构课程设计排序实验报告
实验五查找及排序讲解
快速排序
排序问题实验报告
算法设计实验一归并排序(分治)和插入排序的比较分析
排序算法稳定性
数据库汉字排序规则__按笔画排序
大数据结构实验四题目一排序实验报告材料
数据库实验2：使用分组,排序,汇总