????????本文寫(xiě)的內(nèi)容可能在很多巨佬看來(lái)屬實(shí)是一些簡(jiǎn)單的廢話，但我的底子比較薄，很多東西都是想了好久，這篇文章的主要目的實(shí)際上也只不過(guò)是把我的一些改進(jìn)的地方記錄下來(lái)，防止以后忘記。。。
題目描述：
百度、谷歌等互聯(lián)網(wǎng)搜索引擎提供高效的網(wǎng)頁(yè)、文檔搜索功能，用戶可以通過(guò)一個(gè)和多個(gè)關(guān)鍵詞查詢感興趣的網(wǎng)頁(yè)信息。要實(shí)現(xiàn)超大規(guī)模的文本文檔搜索，通常需要借助高效的索引和查詢算法。編程實(shí)現(xiàn)一個(gè)基于關(guān)鍵詞的文檔搜索程序，實(shí)現(xiàn)對(duì)大規(guī)模文本文檔的快速搜索和排序。具體方法如下：
??1、對(duì)給定的文檔（網(wǎng)頁(yè)）集合（含N個(gè)文檔）中每個(gè)文檔進(jìn)行單詞（英文）提取，并統(tǒng)計(jì)每個(gè)單詞k在每個(gè)文檔d出現(xiàn)的頻次（即出現(xiàn)次數(shù)）TNkd（該文檔總詞數(shù)為
），由此可以計(jì)算其詞頻TFkd
?
為了提高算法的準(zhǔn)確性，在此只統(tǒng)計(jì)字典中出現(xiàn)且不為停用詞（stop-word）的單詞。單詞為僅由字母組成的字符序列，包含大寫(xiě)字母的單詞應(yīng)將大寫(xiě)字母轉(zhuǎn)換為小寫(xiě)字母后進(jìn)行詞頻統(tǒng)計(jì)。
在課程網(wǎng)站下載區(qū)提供了字典“dictionary.txt”文件和英文停用詞表“stopwords.txt”文件(文件中只包含單詞，不含其解釋，且已按字典序排序）。
說(shuō)明：在自然語(yǔ)言處理中，停用詞（stop-word）指的是文本分析時(shí)不會(huì)提供額外語(yǔ)義信息的詞的列表，如英文單詞a，an，he，you等就是停用詞。
2、統(tǒng)計(jì)每個(gè)單詞k在文檔集合中出現(xiàn)的次數(shù)（DNk，即出現(xiàn)該單詞的文檔數(shù)），并計(jì)算其逆文檔頻率IDFk（log以10為底）。定義如下：
3、針對(duì)輸入的關(guān)鍵詞K1,K2,..,Km，按照TF-IDF對(duì)文檔集合中的文檔進(jìn)行相關(guān)度打分。對(duì)任意一個(gè)文檔d，針對(duì)所輸入的關(guān)鍵詞，其相關(guān)度計(jì)算公式如下：
??
? 若某個(gè)關(guān)鍵詞未在文檔集合中出現(xiàn)，則不用計(jì)算其IDFk，其對(duì)所有文檔的相關(guān)度都為0。
??4、依據(jù)相關(guān)度給出檢索結(jié)果按由高至低進(jìn)行排序，返回Top-N的結(jié)果。
為了簡(jiǎn)化搜索引擎的實(shí)現(xiàn)，從互聯(lián)網(wǎng)上爬取（Web Crawling）相關(guān)網(wǎng)頁(yè)(文檔)的工作已經(jīng)完成，并將爬取的網(wǎng)頁(yè)文檔數(shù)據(jù)已存入一個(gè)文本文件（aritcle.txt）中，其中每個(gè)網(wǎng)頁(yè)第一行為網(wǎng)頁(yè)標(biāo)識(shí)號(hào)（如XX-XXXX，可按字符串來(lái)輸入），然后為網(wǎng)頁(yè)內(nèi)容，網(wǎng)頁(yè)文檔間以換頁(yè)符\f分隔。在課程網(wǎng)站下載區(qū)提供了一個(gè)用于測(cè)試的article.txt文件。
【輸入形式】
從命令行輸入作為需要返回的檢索結(jié)果數(shù)量NUM和作為檢索的關(guān)鍵詞串K1,K2,..,Km
具體形式如下：
search NUM K1?K2?.. Km
其中search為搜索引擎運(yùn)行程序，NUM與關(guān)鍵詞之間以一個(gè)空格分隔。根據(jù)當(dāng)前目錄下的“dictionary.txt”文件、停用詞文件“stopwords.txt”以及網(wǎng)頁(yè)數(shù)據(jù)文件“article.txt”，按上面要求對(duì)網(wǎng)頁(yè)文檔進(jìn)行相關(guān)度計(jì)算和排序。
注意：
1．輸入串K1?K2?.. Km中的停用詞及非字典中單詞將不進(jìn)行相關(guān)度分析。
2．由于Windows系統(tǒng)下文本文件中的’\n’回車符在（評(píng)測(cè)環(huán)境）Linux系統(tǒng)下會(huì)變?yōu)椤痋r’和’\n’2個(gè)字符，建議用fscanf(fp,”%s”,…)來(lái)處理字典文件和停用詞文件中英文單詞。
【輸出形式】
先將Sim值排名前5（TOP 5）的網(wǎng)頁(yè)信息輸出到屏幕上，輸出時(shí)先輸出相關(guān)度Sim值（小數(shù)點(diǎn)后保留六位）、相應(yīng)網(wǎng)頁(yè)序號(hào)（從article.txt文件中讀入網(wǎng)頁(yè)文檔時(shí)按序從1開(kāi)始編號(hào)）及在文件article.txt中的標(biāo)識(shí)號(hào)，三者之間由一個(gè)空格分隔，最后有一個(gè)回車。
同時(shí)將Sim值排名前NUM（TOP N）的網(wǎng)頁(yè)信息輸出到results.txt文件中，輸出時(shí)先輸出相關(guān)度Sim值（小數(shù)點(diǎn)后保留六位）、相應(yīng)網(wǎng)頁(yè)序號(hào)（從article.txt文件中讀入網(wǎng)頁(yè)文檔時(shí)按序從1開(kāi)始編號(hào)）及在文件article.txt中的標(biāo)識(shí)號(hào)，三者之間由一個(gè)空格分隔，每個(gè)網(wǎng)頁(yè)信息后有一個(gè)回車；若找到的網(wǎng)頁(yè)文檔數(shù)（即Sim值大于0的文檔數(shù)，即包含所給關(guān)鍵詞的文檔數(shù)）少于NUM，則按實(shí)際數(shù)目輸出（屏幕輸出也如此）。
注意：如果相關(guān)度Sim值相同，則按照網(wǎng)頁(yè)序號(hào)由小到大的順序輸出！
【樣例輸入】
假設(shè)search.exe為搜索引擎程序，以下面方式運(yùn)行該程序：
search 100 edu news article
（運(yùn)行程序前，從課程網(wǎng)站下載區(qū)下載文件：article.txt, dictionary.txt, stopwords.txt, results(樣例).txt到本地）
說(shuō)明：若本地編程環(huán)境為dev-C++，可點(diǎn)擊菜單Execute\Parameters…，在下面對(duì)話框中輸入相應(yīng)命令行參數(shù)。
【樣例輸出】
程序運(yùn)行后，屏幕上輸出Top-5的結(jié)果為：
0.581744 24 1-24
0.466224 230 1-230
0.447891 543 1-543
0.446951 54 1-54
0.440138 87 1-87
所生成的結(jié)果文件“results.txt”內(nèi)容應(yīng)與下載區(qū)文件“results(樣例).txt”完全相同。
【樣例說(shuō)明】
樣例屏幕輸出為按相關(guān)度排序由高到低排名前5的結(jié)果。其中每一行第一部分為網(wǎng)頁(yè)文檔的相關(guān)度（Sim）值，第二部分為相應(yīng)文檔在文件中的序號(hào)，第三部分為文檔在文件中的標(biāo)識(shí)號(hào)。文件results.txt中為按相關(guān)度排序由高到低排名前100的結(jié)果。
【評(píng)分標(biāo)準(zhǔn)】
本綜合功能測(cè)試題，其評(píng)分標(biāo)準(zhǔn)為通過(guò)測(cè)試數(shù)據(jù)即可得滿分。程序運(yùn)行無(wú)結(jié)果或結(jié)果錯(cuò)誤將不得分。
思路分析
??????? 最開(kāi)始的時(shí)候沒(méi)有多思考，因?yàn)閷?duì)于一個(gè).c文件到底能開(kāi)多大的數(shù)組不太確定（），索性放棄了思考，按照最簡(jiǎn)單的想法，開(kāi)一個(gè)巨大的數(shù)組將dictionary中所有詞存入數(shù)組，設(shè)置這樣一個(gè)結(jié)構(gòu)體，flag標(biāo)記是否為stopword，之后對(duì)應(yīng)的DNk，DNkd。。。各種量全部?jī)?chǔ)存下來(lái)（好家伙，做完一看真是什么牛馬都存下來(lái)了），結(jié)果費(fèi)了半天勁，終于將代碼寫(xiě)完，結(jié)果一編譯，編譯器直接報(bào)錯(cuò)為
????????這還是我第一次見(jiàn)這種錯(cuò)誤，急忙上了百度搜了搜，不出所料是數(shù)組開(kāi)大了，之后就卡住了，原有的思路根本沒(méi)法應(yīng)對(duì)這個(gè)，之后再群里討教大佬，大佬為我仙人指路，告訴我Trie樹(shù)是一條名路，從此我便踏上了Trie樹(shù)的道路。
??????? 最開(kāi)始對(duì)于Trie樹(shù)的印象是完全由鏈?zhǔn)浇Y(jié)構(gòu)組成，結(jié)果上網(wǎng)一看大佬的操作才知道數(shù)組也能玩的這么花，但是當(dāng)時(shí)總感覺(jué)時(shí)間緊任務(wù)重，沒(méi)有時(shí)間來(lái)理解這個(gè)方法了，于是直接照著網(wǎng)上的模板copy了插入與查找操作，最開(kāi)始不理解，用的都沒(méi)自信，寫(xiě)了一段時(shí)間便沒(méi)勇氣寫(xiě)下去了。
??????? 但ddl是第一生產(chǎn)力，不得已又開(kāi)始去寫(xiě)，后來(lái)逐漸意識(shí)到了統(tǒng)計(jì)的單詞只需要關(guān)鍵詞的數(shù)據(jù)，完全沒(méi)必要將所有單詞存下來(lái)（實(shí)際上是舍友問(wèn)我的時(shí)候我才看到的，屬實(shí)是審題失誤了），之后我將Words的組成縮減了，但是后來(lái)審視自己的代碼時(shí)又發(fā)現(xiàn)完全沒(méi)必要將Trie樹(shù)變成結(jié)構(gòu)體，這樣[][26]中將會(huì)有大部分的空間是被浪費(fèi)的，這時(shí)才反應(yīng)過(guò)來(lái)可以變成[][28]，前0~25號(hào)表示下一級(jí)的位置，26號(hào)表示關(guān)鍵詞的位置，27號(hào)表示這是要統(tǒng)計(jì)的關(guān)鍵詞，之后的操作就絲滑起來(lái)了。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-496189.html
??????? 可是，本地終于過(guò)了，交上去發(fā)現(xiàn)還是不對(duì)，我TM改了若干處才發(fā)現(xiàn)是命令行參數(shù)用錯(cuò)了，這才修成正果（淚目了，蒟蒻的眼淚從嘴角滑了出來(lái)）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-496189.html
代碼部分：（請(qǐng)求巨佬批評(píng)指正）
// pro1:Trie樹(shù)確定索引位置； 用stopWord除去不該計(jì)算的詞
// pro2:以文檔為單位(N)記錄每個(gè)單詞的頻次;
//##data:以結(jié)構(gòu)體{TNkd,DNk,TFkd[pages],IDFk}來(lái)記錄##ki的TNkd++,DNk++
// pro3:一篇文檔結(jié)束后，計(jì)算TFkd,TNkd清0,讀入文檔時(shí)記錄對(duì)應(yīng)的文檔數(shù)以及其網(wǎng)頁(yè)序號(hào);
// pro4:讀完所有文檔,
// pro5:計(jì)算IDFk,計(jì)算完計(jì)算Sim
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#define PageSize 16000
#define WordSize 10000
struct node {
int TNkd, DNk;
double TFkd[PageSize];
double IDFk;
} Words[WordSize*10];
struct ednode {
char eno[10];
double sim;
int id;
} Pages[PageSize];
int Trie[4200000][28]; // flag為1說(shuō)明
int num_word = 0, pos, num_page = 0;
int TNd[PageSize],NUM;
char arr[1024], s[35000000];
int search(char word[]) { //查找操作，在Trie樹(shù)中找尋單詞
int p = 0;
for (int i = 0; word[i]; i++) {
int ch = word[i] - 'a';
if (!Trie[p][ch]) {
return 0;
}
p = Trie[p][ch];
}
return p;
}
int cmp(const void *a, const void* b)
{
struct ednode *tmpa = (struct ednode*)a,*tmpb = (struct ednode*)b;
if(tmpa->sim < tmpb->sim) return 1;
else if(tmpa->sim > tmpb->sim) return -1;
else
{
return tmpa->id -tmpb->id;
}
}
int main(int argc, char *argv[]) {
//這一部分是將詞典里的詞錄入到Trie樹(shù)里，涉及插入操作，但這塊的pos值特別大
FILE *dictionary = fopen("dictionary.txt", "r");
while (fscanf(dictionary, "%s", arr) != EOF) {
int p = 0, i;
for (i = 0; arr[i] != '\0'; i++) {
int ch = arr[i] - 'a';
if (!Trie[p][ch]) {
Trie[p][ch] = ++pos;
}
p = Trie[p][ch];
}
Trie[p][27] = 1; //用flag標(biāo)記這個(gè)單詞是詞典中的詞
}
fclose(dictionary);
//用stopwords里的單詞在Trie樹(shù)中尋找，找到的將flag變?yōu)?，以后就只統(tǒng)計(jì)flag為1的單詞，涉及查找，用函數(shù)search
FILE *stopwords = fopen("stopwords.txt", "r");
while (fscanf(stopwords, "%s", arr) != EOF) {
int index = search(arr);
if (Trie[index][27])
Trie[index][27]= 0;
}
fclose(stopwords);
//讀入ki部分
NUM = atoi(argv[1]);
for (int i = 2; i < argc; i++) {
int index = search(argv[i]);
if(Trie[index][27] == 1)
Trie[index][27] = 2;
}
//將所有內(nèi)容讀入到一個(gè)大樹(shù)組中
FILE *article = fopen("article.txt", "r");
int c = fread(s, sizeof(char), 35000000, article);
fclose(article);
//讀取article
char word[85]; //word是用來(lái)存儲(chǔ)文檔中的單詞
for (int i = 0; i<c; i++) {
if (i == 0) { //將第一頁(yè)的頁(yè)碼錄入，存在數(shù)組Pages中，從0開(kāi)始
int j;
for (j = i; s[j] != '\n'; j++) {
Pages[num_page].eno[j-i] = s[j];
}
Pages[num_page].id = num_page+1; //將第幾頁(yè)錄入，方便以后排序后能確定正確的順序
} else if ((s[i] <= 'z' && s[i] >= 'a') || (s[i] <= 'Z' && s[i] >= 'A')) {
int j;
for (j = i;(s[j] <= 'z' && s[j] >= 'a') || (s[j] <= 'Z' && s[j] >= 'A'); j++) {
word[j - i] = tolower(s[j]); //將單詞都轉(zhuǎn)換為小寫(xiě)單詞
}
word[j-i]='\0';
i = j - 1;
int index = search(word); //找到Trie樹(shù)中單詞對(duì)應(yīng)的位置index
if(Trie[index][27] == 1)
{
TNd[num_page]++;
}
else if (Trie[index][27] == 2) { //如果是這個(gè)單詞是Ki，則在Words中輸入該單詞，actual對(duì)應(yīng)的是實(shí)際單詞在Words中的位置
Trie[index][27] = 3; //表示該單詞不是第一次出現(xiàn)了
Trie[index][26] = num_word++; //actual對(duì)應(yīng)的位置正是最后一位
if(Words[Trie[index][26]].TNkd == 0)
Words[Trie[index][26]].DNk++; // DNk++
Words[Trie[index][26]].TNkd++;//單詞的TNkd++
TNd[num_page]++;
} else if (Trie[index][27] == 3) { //flag為3表示該單詞不是第一次出現(xiàn)了，actual是單詞在Words中的位置
if(Words[Trie[index][26]].TNkd == 0)
Words[Trie[index][26]].DNk++;
Words[Trie[index][26]].TNkd++;
TNd[num_page]++;
}
} else if (s[i] == '\f') { //一頁(yè)結(jié)束，處理如下
int j;
for(j = 0; j < num_word;j++) //清算本頁(yè)的TFkd，并將TNkd歸0
{
Words[j].TFkd[num_page] = 100.0*Words[j].TNkd/TNd[num_page];
Words[j].TNkd = 0;
}
num_page++; //頁(yè)碼增加
for(j = i+1; !isdigit(s[j]);j++); //找到頁(yè)碼表示的位置
i = j;
for(j = i; s[j] != '\n';j++) //讀入新頁(yè)碼
{
Pages[num_page].eno[j-i] = s[j];
}
Pages[num_page].id = num_page+1;
}
}
num_page++;
//計(jì)算部分
for(int i = 0; i < num_word;i++)
{
if(Words[i].DNk!=0)
Words[i].IDFk = log10(1.0*num_page/Words[i].DNk); //計(jì)算IDFk
}
for(int i=0;i< num_page;i++){
for(int j = 0; j< num_word;j++)
{
Pages[i].sim += 1.0*Words[j].TFkd[i]*Words[j].IDFk;//計(jì)算Sim
}
}
//輸出部分
FILE *results = fopen("results.txt","w");
qsort(Pages,num_page,sizeof(Pages[0]),cmp);
for(int i = 0 ; i <NUM && i < num_page;i++)
{
fprintf(results,"%.6lf %d %s\n",Pages[i].sim,Pages[i].id,Pages[i].eno);
}
for(int i = 0; i < 5 && i <num_page;i++)
{
printf("%.6lf %d %s\n",Pages[i].sim,Pages[i].id,Pages[i].eno);
}
fclose(results);
return 0;
}到了這里，關(guān)于2022BUAA數(shù)據(jù)結(jié)構(gòu)期末大作業(yè)的一些想法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
