鉴于不少地里的朋友问这题到底啥样子，其实这题很简单，不是什么算法题，就是把一个数学公式简单的用coding来实现而已。
首先他会问你知不知道tf_idf，我说基本了解（其实烂熟于胸了），他说不知道也没关系，然后他会把wiki上的tf_idf解释给你听，装着仔细听就行了，注意他的定义可能会稍微不一样，不过他会把公式写出来的。可以参考：https://zh.wikipedia.org/zh-hans/TF-IDF
他当时给的定义是输入要查询的几个关键字，每个文档的tf_idf的定义是：
要查询的几个关键字在该文档各自的tf_idf之和。
每个关键字的tf_idf的定义基本和wiki上的一样，稍微有点不同的是分母不是该文档中所有词出现的次数之和，而是频率最高的词出现的次数，其他一样：
tf_idf=keyCount/maxCount * log(n/docCount)，这里keyCount是要查询的词在该文档中出现的次数，maxCount是该文档中频率最高的词出现的次数，n是总文档数，docCount是要查询的词出现在几个文档中。
最后的要求就是输入要查询的几个关键字，输出最高tf_idf的几个文档的序号，自己随便输入一些文档的词（他要考察你给的例子好不好），然后和他一起计算结果对不对。反正onsite都写了代码，这里就顺便贴在下边：- #include <unordered_set>
- #include <unordered_map>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- /*
- input: vector<string> keys, vector<vector<string>> docs
- keys: a few key words to query
- docs: a list of docs, each doc is a list of strings
- return: highest ranking docs for query keys
- tf_idf definition:
- tf_idf=sum of each key's tf_idf
- key's tf_idf=keyCount/maxCount * log(n/docCount)
- */
- vector<int> tf_idf(vector<string> & keys, vector<vector<string>> & docs) {
- int n=docs.size(); // total number of the docs
- vector<unordered_map<string, int>> keyCount(n); //each word's count in each doc
- vector<int> maxCount(n); //the most freq word's count in each doc
- for(int i=0; i<n; ++i) {
- for(auto & word:docs[i]) {
- ++keyCount[i][word];
- maxCount[i]=max(maxCount[i],keyCount[i][word]);
- }
- }
- unordered_map<string, int> docCount; //each word appears in how many docs
- for (int i=0; i<n; ++i) {
- for(string & key:keys) {
- if(keyCount[i].count(key)) ++docCount[key];
- }
- }
- vector<pair<double, int>> tfidf(n); //each doc's tf_idf, pair.first: tf_idf, pair.second: file's index, pair is used for sorting
- for (int i=0; i<n; ++i) {
- for(string & key:keys) {
- tfidf[i].first+=(keyCount[i][key]+0.0)/maxCount[i]*log((n+0.0)/docCount[key]);
- }
- tfidf[i].second=i;
- }
- sort(tfidf.begin(),tfidf.end(),greater<pair<double,int>>());
- int m=2; //output first 2 highest tf_idf doc's index
- vector<int> ret(m);
- for(int i=0; i<m; ++i) {
- ret[i]=tfidf[i].second;
- }
- return ret;
- }
- int main() {
- vector<string> keys={"dog","cat"};
- vector<vector<string>> docs={ //testing case, given by myself
- {"dog", "dog", "cat", "a", "big"}, // 2/2*log(4/2)+1/2*log(4/2)
- {"cat", "dog", "a", "big"}, // 1/1*log(4/2)+1/1*log(4/2)
- {"cow", "a", "the"},
- {"the", "a"}
- };
- vector<int> ret;
- ret=tf_idf(keys,docs);
- for(auto & r:ret) cout << r << endl; //output doc's index
- }
|
匿名用户-YH8B9
2016-11-17 00:40:38
