子query统计和重要子query识别

Ronnyo

谁会做？？？？？


问题定义：
当query A切词后的term集是query B切词后的term集的真子集是，成query A为query B的子query，例如：
“刘德华”的切词结果为“刘德华”；
“刘德华电影”的切词结果为“刘德华 电影”；
“刘德华最新电影”的切词结果为“刘德华 最新 电影”；
“刘德华电影下载”的切词结果为“刘德华 电影 下载”；
根据以上切词结果，刘德华”是“刘德华电影”，“刘德华最新电影”, “刘德华电影下载”的子query；
“刘德华电影”是“刘德华最新电影”, “刘德华电影下载”的子query；
但是“刘德华电影下载”和“刘德华最新电影”不想不是对方的子query。
现有亿级的用户query，并且知道每个query的查询次数，要求：
（1） 列出一个query的全部子query，写出C语言实现。（15分）
（2） query中的不同term对这个query的重要形式不同的，例如“刘德华 电影 下载”中“刘德华”和“电影”的重要性比“下载”重要，因为：“刘德华 电影“所表达的查询需求，与”刘德华 下载“或者”电影 下载“相比，更接近原query的需求。根据(1)中的统计的子query数据，请给出一种思路，来计算也给query中的所有子query的重要性排序。如果认为子query数据的信息不够充分，请给出还需要哪些信息，以及获得这些信息的途径，给出算法思路描述，必要的符号和推理公式即可。

Ronnyo

统计方法
假设检验是常用的统计推断方法，在大数据时代，人们可以更加容易地得到更多特征。在ab-test时，常常需要使用假设检验方法研究特征在两者样本间是否有差异。一个常见的现象是，当特征数目较多时，在同样的显著性水平下，往往更加“容易”得到“显著差异”结果。
(1). 如何看待特征数目假设检验结果的影响？
(2). 假设独立特征数目是n，如何调整各个特征的p-value，调整后的p-value真实反映特征在两组间存在差异的显著性。
(3).假设特征间分布不独立，(2)的解决方案是否需要调整，如何调整？

Ronnyo

这些是百度笔试题


3. 相似度计算用于衡量对象之间的相似程度，在数据挖据，自然语言处理中使一个基础性计算，在广告检索服务中往往也会判断网民检索Query和广告Adword 的主题相似度。假设Query 或者Adword 的主题属性定义为一个长度为10000 的浮点数据Pr[10000](称之为主题概率数组)，其中Pr[i]表示Query 或者Adword 属于主题Id 为i 的概率，而Query和Adword 的相似度简化定义为两者主题概率数组的内积，即sim(Query,Adword)=sum(QueryPr[i]*AdwordPr[i])(0<==i<10000).在实际应用场景中，由于大多数主题的概率都为0，所以主题概率数组往往比较稀疏，在实现时会以一个紧凑型数组topic_info_t[]的方式保存，其中100<=数组大小<=1000，并按照topic_id 递增排列，
0<=topic_id<10000,0< topic_pr<1,
Struct topic_info_t {
int topic_id;
float topic_pr;
} ;
现在给出Query 的topic_info_t 数组和N(N>=5000)个Adwords 的topic_info_t 数组，现要求出Query 与Adwords 的相似度最大值，即
max(sim(Query,Adword[i])(0<=i<N).
float max_sim(const vector<topic_info_t>& query_topic_info,
const vector<topic_info_t> adwords_topic_info[],
int adwords_number);
编写代码求时间复杂度最低的算法，并给出时间复杂度分析。