提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

PTA 数据结构与算法题目集（中文）7-44 基于词频的文件相似度 (30分)

文件 数据结构
2023-03-07 09:08:29 时间

我的GIS/CS学习笔记：https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes <一个浙江大学本科生的计算机、地理信息科学知识库 > 还有不少数据结构和算法相关的笔记以及pta题解哦x

思路

倒排索引的结构如下： “关键词1”：“文档1”的ID，“文档2”的ID，…………。 “关键词2”：带有此关键词的文档ID列表。 从词的关键字，去找文档。

题目

实现一种简单原始的文件相似度计算，即以两文件的公共词汇占总词汇的比例来定义相似度。为简化问题，这里不考虑中文（因为分词太难了），只考虑长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。

输入格式:

输入首先给出正整数N（≤100），为文件总数。随后按以下格式给出每个文件的内容：首先给出文件正文，最后在一行中只给出一个字符#，表示文件结束。在N个文件内容结束之后，给出查询总数M（≤10​4​​），随后M行，每行给出一对文件编号，其间以空格分隔。这里假设文件按给出的顺序从1到N编号。

输出格式:

针对每一条查询，在一行中输出两文件的相似度，即两文件的公共词汇量占两文件总词汇量的百分比，精确到小数点后1位。注意这里的一个“单词”只包括仅由英文字母组成的、长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。单词间以任何非英文字母隔开。另外，大小写不同的同一单词被认为是相同的单词，例如“You”和“you”是同一个单词。

输入样例:

3 Aaa Bbb Ccc # Bbb Ccc Ddd # Aaa2 ccc Eee is at Ddd@Fff # 2 1 2 1 3

输出样例:

50.0% 33.3% 

#include <iostream>
#include<map>
#include<list>
#include<ctype.h>
#include<string>
#include<cctype>
#include<algorithm>
//倒排索引；
//(inverted index)
using namespace std;
//link[i][i]: words in a file;
//link[j][j]: public words;
int link[105][105];

//index:
map<string, list<int> > words;

int main(int argc, const char * argv[]) {
	int n, i, j, k;
	cin >> n;
	string line, aword;
	map<string, list<int> >::iterator word;
//input
	for (i = 1; i <= n; ++i) {
		int count = 0;
		getline(cin, line);
		while (line[0] != '#') {
			j = 0;
			while (j < line.length()) {
				k = 0;
				aword.clear();
        //create word;
				while (k < 10 && isalpha(line[j])) {
					aword += line[j];
					++j;
					++k;
				}
				while (isalpha(line[j]))
					++j;
          //deal with a word;
				if (aword.length()>=3) {
					transform(aword.begin(), aword.end(), aword.begin(), ::tolower);
					word = words.find(aword);
					if (word==words.end()||word->second.back() != i) {
          //if not in this file but exist: 
						if (word != words.end()) {
							list<int>::iterator f;
							f = word->second.begin();
              //update public words;
							while (f != word->second.end()) {
								link[i][*f]++;
								link[*f][i]++;
								++f;
							}
						}
            //if not exist:
						words[aword].push_back(i);
						++count;
					}
				}
				else
					++j;
			}
			getline(cin, line);
		}
		link[i][i]= count;
	}
//output:
	int m, f1, f2;
	cin >> m;
	double per;
	for (i = 0; i < m; ++i) {
		cin >> f1 >> f2;
		per = 1.0*link[f1][f2] / (link[f1][f1] + link[f2][f2] - link[f1][f2])*100;
		printf("%.1f%%\n", per);
	}
	return 0;
}

相关文章