算法设计与分析课程设计
quantumxiaol/NEU_Algorithm_coursedesign
1)(东北大学 计算机学院, 沈阳市 10000)
摘 要 随着计算机技术与互联网技术的飞速发展，越来越丰富的信息呈现在用户面前，但同时伴随的问题是用户越来越难以获得其最需要的信息。本次课程设计旨在设计与实现一个小型搜索引擎系统，主要分为四部分：首先需要利用爬虫爬取网页信息；其次进行分词，再应用字典树查重与统计词频并编号，生成临时索引；之后对单词编号进行希尔排序、归并排序与多路平衡归并排序并整合，生成倒排索引；最后根据倒排索引查询结果，并用堆排序对网页编号出现次序排序，最后用二分查找查询结果并输出。
关键词 搜集、分词、字典树、临时索引、希尔排序、归并排序、多路平衡归并排序、倒排索引、堆排序、二分查找
Implementation of a simple search engine
Liu XiaoLong1) Wang YiZheng2) Ji Ye3) Teng Peng4)
1)(Northeastern University, ShenYang 10000, China)
Abstract With the rapid development of computer technology and Internet technology, more and more abundant information is presented to users, but at the same time, it is more and more difficult for users to obtain the information they need most. This course is designed to design and implement a small search engine system, which is mainly divided into four parts: first, we need to use crawlers to crawl web page information; Secondly, word segmentation is carried out, and then dictionary tree duplicate checking and word frequency statistics are applied and numbered to generate temporary index; After that, the word numbers are sorted and integrated to generate an inverted index; Finally, according to the inverted index query results, and use heap sorting to sort the sequence of web page numbers, and finally use binary search query results and output.
Key words Collect; Word Segmentation; Dictionary Tree; Temporary index; Shell Sort; Merging sort; Multi-channel Balanced Merge Sort; Inverted index; Heap Sort; Binary Search
1 课题概述
1.1 课题任务
课题任务即不调用算法库的条件下，实现一个小型搜索引擎，分块完成搜集、分析、索引、查询四部分。其中：
搜集指利用爬虫爬取网页信息；
分析是对网页内容抽取、分词，构建临时索引；
索引是在临时索引的基础上，进行排序与整合，构建倒排索引；
查询是响应用户的请求，根据倒排索引获取相关网页，计算网页排名，返回查询结果给用户。
1.2 课题原理
首先在互联网中发现、搜集网页信息；同时对信息进行提取和组织建立索引库；再由检索器根据用户输入的查询关键字，在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户。
1.3 相关知识
主要算法：
- 字典树
- 希尔排序
- 归并排序
- 多路平衡归并排序
- 堆排序
- 二分查找
2 算法设计
2.1 类函数列表
| 类型 | 内容 |
| 结构
体 |
struct TrieNode{
vector<TrieNode *> child; bool isEnd; int wordid; TrieNode() {this->child=vector<TrieNode *> (67,nullptr); this->isEnd=false; wordid=-114514;}}; |
| 类（
public为部 分函 数） |
class WordDictionary {
public: WordDictionary() {} ~WordDictionary(){} void release(TrieNode* r){} void addWord(string word,int id) {} void printWordDictionary(){} void readWordDictionary(){} void inputWordDictionary(){} intsearchwordid(stringword){} bool search(string word) {} bool dfsid(const string & word,int index,TrieNode * node,int &id) {} bool dfs(const string & word,int index,TrieNode * node) {} private: TrieNode *trie;} |
| 结构体 | struct trie {
int n; bool isRecord; trie* son[67]; trie (): n(0) { isRecord=false; for (int i = 0; i < 67; ++i) { son[i] = nullptr; }}}; |
| 类 | class WordsFrequency {
private: trie* root; public: WordsFrequency(vector<string>& book) {}} |
| 函数 | void debugWordDictionary(){}
bool isletter(char str) bool isdigit(char str) int mainTPfunction(){} int readsitestory_TP(long long int id,vector<string> &input){} inttempindex(longlongintid,vector<string>htmlword, vector<string>&wordlist,WordDictionary &WD,vector<pair<int,int>>&index1){} int tempindexwithfrequency(longlongintid, vector<string>htmlword,WordDictionary &WD,vector<pair<int,pair<int,int>>>&index1){} int analyseHtml(int num=HTMLNUM){} int generate_temp_index(vector<pair<int,int>> input){} voidPrintVector(vector<string>v,string information){}；int runsearch(); int keyword_search(std::vector<std::string> &inputlist); int isContinue();int preProcess(); int debugtest();int test(int num); int inputwordlist(std::vector<std::pair< std::string,int>> &input); int readwordlist(std::vector<std::pair< std::string,int>> &input); int inputtempindex(std::vector< std::pair<int,int>> &input); int readtempindex(std::vector< std::pair<int,int>> &input); int inputindex(std::vector<std::pair<int, std::vector<int>>> &input); int readindex(std::vector<std::pair<int, std::vector<int>>> &input); intinputtempindexfrequency(std::vector< std::pair<int, std::pair<int,int>>> &input); int readtempindexfrequency(std::vector< std::pair<int,std::pair<int,int>>> &input); void Readcsv();bool isHttp(std::string str); void inputsitestory(long long int htmlnum,std::string str); void readstory();void debugtest_read(); int readsitestory(long long int id, std::vector<std::string> &input); intreadsitestory_state(longlongint id,std::vector<std::string> &input); void debugtext_readhtml(int num); int analyseHtml(); void debugtext_analyseHtml(); |
2.1 文件格式定义
网页数据从new.csv文件中读取出来放入代码根目录的SearchEngine\1\html doc_id的txt文件中（doc_id为网页编号）
读取html doc_id中的网页文件，分词查重之后存入单词编号文件wordlist.txt,生成临时索引tempindex.txt,生成带词频的临时索引文件tempindexfrequency.txt
读取tempindex.txt中的文件，通过归并排序、希尔排序生成倒排索引文件index.txt
2.2 输入输出
输入：csv文件
输出：网页查询结果
Figure 1 程序整体流程
3 方案实现
3.1 关键算法
英文分词、利用字典树查重、希尔排序、归并排序、外部排序、堆排序
3.1 个人程序设计
- 网页的提取，单词的编号，生成临时索引，生成倒排索引：刘小龙[1]
伪代码：
TEMINDEX=READTEMPINDEXFILE();
FOR(AUTO IT=TEMINDEX.BEGIN();IT!=TEMINDEX.END();){
IF(IT==TEMINDEX.BEGIN()){IT++;CONTINUE;}
INT WORDID=(*(IT-1)).FIRST;
IF((*IT).FIRST==(*(IT-1)).FIRST){
SMALL.PUSH_BACK( (*(IT-1)).SECOND );
TEMINDEX.DELETE(IT-1);
IT++;
CONTINUE;
}
ELSE{
SMALL.PUSH_BACK((*(IT-1)).SECOND);
INDEXTEST.PUSH_BACK(MAKE_PAIR(WORDID,SMALL));
SMALL.CLEAR();
VECTOR<INT>().SWAP(SMALL);
IT++;
}
}
流程设计：
算法复杂度分析：
字典树
时间复杂度：初始化为 O(1)，其余操作为 O(|S|)，其中 |S| 是每次插入或查询的字符串的长度。
空间复杂度：O(|T|·Σ)，其中 |T| 为所有插入字符串的长度之和，Σ 为字符集的大小，Σ=67。
个人感悟：这一部分使用向量容器，对排好序的向量容器前后两个比较，对单词编号相同的记录出现的网页编号（和单词在该网页出现的频率），插入到一个记录网页编号的向量容器，然后删除一行记录，继续比较；出现不同则一个单词记录完成，将一行记录写入文件，重新比较。
这一部分我遇到了性能瓶颈，写入文件的时间要75min（带频率信息的文件是95min），现在想来，是STLvector的删除所致，应该直接读写文件。我的测试样例vector的大小有815321行，牵一发而动全身，拖慢了节奏。
- 英文分词：滕鹏[2]
伪代码：
WHILE (TEST>>STR)
IF STR[I]==标点符号/空格
DELETE STR[I]
ELSE
COUTINUE
流程设计：
Figure 2 英文分词流程
算法复杂度分析：
时间复杂度：O(n)，n是文件中的行数
空间复杂度：取决于文件大小
个人感悟：在这次课程设计当中，我了解到了我的不足，如算法的不完善、不细心和耐心不是很好等等。不细心的我在调试程序时，老是因为某个书写错误导致错误；对这些错误，我不得不花大量的时间去更正，并且还要重复检查是否出现雷同的错误而导致程序不能运行。但是通过这次课程设计，我的这些缺点有些改善。我在写新的程序时，首先要考虑的深入一点、仔细一点，这样要修改程序的时间就会少很多。并且也不会因为自己不细心而导致的浪费时间的情况出现。在进行程序设计时，要注意想好思路。即要有恰当模块名、变量名、常量名、子程序名等。将每个功能的模块，即函数名要清晰的表述出来，使用户能够一目了然此程序的功能。当然适当的给写注释，也是方便用户的理解。还有在编写程序时要注意对程序的适当分配，便于用户看懂程序，也便于自己检查城市。但是完成任何一个较大的程序，都需要掌握一定的编程基础，需要不断的探索和求知过程，这样对自己编程能力的提高有较大的帮助。
- 希尔排序、归并排序：季晔[3]
伪代码：
VOID MERGE_SORT(VECTOR<PAIR<INT,INT>>&Q, INT L, INT R){
IF (L >= R) RETURN;
INT MID = (L + R) >> 1;
MERGE_SORT(Q, L, MID);
MERGE_SORT(Q, MID + 1, R);
INT K = 0, I = L, J = MID + 1;
VECTOR<PAIR<INT,INT>> TMP(Q.SIZE());
WHILE (I <= MID && J <= R){
IF (Q[I].FIRST <= Q[J].FIRST) {
TMP[K++] = Q[I++];
}
ELSE TMP[K++] = Q[J++];
}
WHILE (I <= MID) TMP[K++] = Q[I++];
WHILE (J <= R) TMP[K++] = Q[J++];
FOR (INT I = L, J = 0; I <= R; I++, J++) Q[I] = TMP[J];}
多路平衡归并排序伪代码
INT ADJUST(LOSERTREE &LS,INT S,EXTERNAL &B){//调整败者树
INT T=(S+5)/2;
WHILE(T>0){
IF(CMPEXNODEG(B[S],B[LS[T]])){//S指向新的胜者，而LS[T]指向败者
INT TEM=S;
S=LS[T];
LS[T]=TEM;}
T/=2;//向上继续比较}
LS[0]=S;}
VOID CREATE_LOSERTREE(LOSERTREE &LS,EXTERNAL &B){
FOR(INT I=0;I!=5;++I){//设置LS败者的初值都为5， K位置的关键字已经设置为了-1，
LS[I]=5;}
FOR(INT I=0;I!=5;++I){//一次从存储点第一个关键词开始进行调整
ADJUST(LS,I,B);}}
VOID K_MERGE(LOSERTREE &LS,EXTERNAL &B,VECTOR<VECTOR<PAIR<INT,INT>>> R){
FOR(INT I=0;I!=K;++I){//先将个归并段的第一个关键字，放入存储数组
B[I].KEY=R[I][0];
}
B[K].KEY=-1;//设置一个最小值，作为建立败者树时用，
CREATE_LOSERTREE(LS,B);
INT NEXT0=1,NEXT1=1,NEXT2=1,NEXT3=1,NEXT4=1,NEXT5=1,NEXT6=1,NEXT7=1;
WHILE(B[LS[0]].KEY!=1000){//当1000出来的时候，说明归并已经完成
INT Q=LS[0];
COUT<<B[Q].KEY<<” “;//输出一个被选出来的关键字
ADJUST(LS,Q,B);//再进行调整，
}
}
流程设计：
Figure 3外部排序
算法复杂度分析：
希尔排序：
时间复杂度：最好情况是序列是正序排列，每一趟只需比较(n-1)次，即O(n)，而因为直接插入排序对有序的序列效率很高，因此最坏情况要优于直接插入排序的O(n^2)，渐进时间复杂度为O(nlog2n)
空间复杂度：希尔排序每一趟都只需要常量级空间，空间复杂度为O(1)
归并排序：
时间复杂度：归并排序分为数组划分和有序数组归并两个步骤，其中有序数组归并的时间复杂度为O（n），因为代码中有两个长度为n的循环。所以得到公式T（n）=2T（n/2）+O（n）得到归并排序的时间复杂度T（n）=O（nlogn）
空间复杂度：归并过程中临时的数组和递归压栈的数据占用空间为n+logn，因此空间复杂度为O(n)
多路平衡归并排序：
时间复杂度：由于是外部排序，涉及文件读写，所以很大一部分是文件读写时间，其余部分 内部排序时间复杂度是O(nlogn)，内部归并排序时间复杂度是O(logn)
个人感悟：
本次课程设计
1.让我认识到了算法的选择对一个程序影响之大。我负责索引部分的排序算法，内部排序中，希尔排序与归并排序各有其时空方面的利弊，但针对本次任务，需要排序的数据量过大，显然避免内存不足，外部排序是更好的选择。
2.巩固了我课内的知识，也锻炼了我的思维与代码编写能力。归并排序用到了递归分治的思想，希尔排序本质则是分段进行多次插入排序。而外部排序是我第一次尝试学习并实现，尽管最终未能整合进总程序，但利用外存储器与利用败者树这一特殊结构实现还是让我感叹算法之精妙。
3.培养了我的团队协作能力。我在整个课程设计中，尤其是文件读写和多路平衡归并排序的实现中遇到了许多困难，但得益于团队的帮助，我最终克服了这些困难。一起编写程序、一起准备汇报、一起写报告，这些都让我认识到团队的力量与合作精神。
4.让我认识到了自己存在的不足。显然我编写代码的能力存在不足，不仅写起代码很是生疏，而且许多我负责的部分也没能独立完成，这让我认识到自身存在的不足，我会在未来磨练自己的能力。
- 网页查询：王怡正[4]
伪代码：
堆排序：//建堆,
N= LENGTH(A)
FOR I= N/2 DOWNTO 1 DOLL从非叶子节点开始，自底往上，使A变成最大堆
MAX HEAPIFY(A, I,N)
END
/调整为最大堆,T(N)= O(LGN)
MAX_HEAPIFY(A,IDX,MAX) //IDX:数组开始的下标, MAX:最大的数组下标LEFT = 2*IDX
RIGHT = 2*IDX
IF(LEFT<MAX AND A[LEFT]-A[IDX]) THENLARGEST = LEFT
ELSE
LARGEST = IDX
IF(RIGHT < MAX AND A[RIGHT]>A[LARGEST]) THENLARGEST = RITHT
IF(LARGEST != IDX) THEN
EXCHANGE A[LARGEST] WITH A[IDX]
MAX_HEAPIFY(A,LARGEST,MAX)//交换位置后，还需要调整它的子树END
HEAPSORT(A)
BUILDHEAP(A)
FOR I = LENGTH(A) DOWNTO 2 DO
EXCHANGE A[1] WITH A[n]//把最大堆根节点与最后一个互换
MAX_HEAPIFY(A,1, I-1)//把交互后的排除在堆之外，重新从1到I-1,调整堆
END
流程设计：
Figure 4二分查找实现流程
Figure 5堆排序流程
算法复杂度分析：
堆排序
时间O(nlogn),
空间复杂度O(1)
二分查找
时间复杂度O(logn),
空间复杂度O(1)
个人感悟：在做这次算法的课程设计的过程中，我充分意识到不同算法对一个程序的处理数据的能力会造成多大的影响，这种影响在数据不大的情况下可能不会太过于明显，而一旦数据变得比较大那么这种影响就会很大程度上的显现出来，比如这次在设计查询的过程中，因为需要排序和查询两部分，我认真比较了不同算法之间的复杂度区别，最终选择了我认为时间复杂度和空间复杂度都适合的堆排序和二分查找，在编写的过程中，我仔细学习了两个算法的思路和本质，最后用递归程序将两个算法实现.在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。
如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。
3.2 程序优化
查单词编码：遍历查找->字典树查找
顺序查找：最好情况（查找第一个就是）时间复杂度为O(1)，最坏情况（查找最后一个是）时间复杂度为O(n)，平均情况即为(n+1)/2。而字典树有额外空间换时间，一般而言认为建树的额外空间是常数级，时间复杂度为O(1)。
参 考 文 献
[1] Li Dan-Yang, Zhao Ya-Hui, Luo Meng-Jiang, Cui Rong-yi. Query text proofreading method of professional courses based on trie tree language model, Journal of Yanbian University(Natural Science) 2020, 1004-4353（2020）03-0260-05(in Chinese)
（李丹阳，赵亚慧，罗梦江，崔荣一.基于字典树语言模型的专业课查询文本校对方法，延边大学学报（自然科学版），2020，1004-4353（2020）03-0260-05）
[2] Chen Zhi-Feng. Design of Automatic Word Segmentation System for Network Retrieval Based on Data Mining, Journal of Hubei University of Science and Technology, 2022, 2095-4654 (2022) 03-0117-05(in Chinese)
（陈志锋. 基于数据挖掘的网络检索自动分词系统设计,湖北科技学院学报，2022，2095-4654（2022）03-0117-05）
[3] （解学武. 数据结构与算法， data.biancheng.net）
[4] Wang Xiao-Di. Research on Query Recommendation Algorithm Based on Search Engine, Software Guide, 1672-7800(2020)010-0076-04(in Chinese)
（王晓迪，基于搜索引擎的查询推荐算法研究，软件导刊，2020,1672-7800（2020）010-0076-04）