13
回答
如何最高效的标识出文章中的关键字
终于搞明白,存储TCO原来是这样算的>>>   

条件:

1. 有一个关键字库,数量在上万级别
2. 有几万篇文章,平均下来大约每篇500字

需求:

想给文章中出现关键字的地方加粗显示

常规做法一篇篇文章逐一检查每个关键字,还有没有更高效的方法,或者有现成的开源项目可实现这个吗?

<无标签>
举报
鉴客
发帖于5年前 13回/637阅
共有13个答案 最后回答: 5年前

这不是我碰到的面试题么?

总体的思想是MapReduce.我大体说一下个人的思路,抛砖引玉.

首先你的文章每篇500字,看做一个独立的个体了.没必要再分,要分的是你的关键字库,比如说有10亿个关键字(每个1字节).那么文件大小就是1G.再假设你的机器内存限制在1M.你可以大概算一下总共要分多少个文件.假设分成5000个文件.

1.分而治之/hash映射:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,...x4999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M,这样保证了每个文件里面的关键字不重复.
2.对每篇文章遍历这5000个小文件,加粗.(其实这里不符合MapReduce的思想,因为没做merge sort.除了遍历我还没想到什么好的办法)这里我推荐用Hadoop来搞,这玩意就是为这而生的.

(3,4可选做,如果你关键字库里面不会重复的话,跳过.)一箭双雕,这样一来可以完成关键字库中出现最多的关键字统计:
3.hash统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
4.堆/归并排序:取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100个词及相应的频率存入文件,这样又得到了5000个文件。最后就是把这5000个文件进行归并(类似于归并排序)的过程了。(这里是MapReduce的思想)

5.(选做).同样的方法,可以统计出上万文章中出现最多关键字的统计.方法同3,4.只不过是

文章已经分好了.只需要MapReduce文章即可.
参考: http://blog.csdn.net/v_july_v/article/details/7382693

--- 共有 4 条评论 ---
鉴客回复 @Grrrr : 嗯,非常感谢:) 5年前 回复
Grrrr回复 @鉴客 : 既然遍历跑不掉,也不想用MapReduce模式的话. 我建议把关键字库的结构调选好(trie树,后缀树.xx树),这样一来可以大大减少字库容量.比如act,action.attention 还有模式匹配算法.你可以做一个测试比较下KMP和传统的比照.. 5年前 回复
Grrrr回复 @鉴客 : 就如我说的,这个需求就不是一个MapReduce模式. 我有点强硬套上去的. 不过你可以看见当你做了3,4,5以后.会有另外2个成果.而这2个是统计,这才是MapReduce模式. 5年前 回复
鉴客MapReduce 会不会有点杀鸡用牛刀呢? 5年前 回复

当添加新的关键字,取hash(x)%5000,存到对应的文件即可.

其实我的回答算不上MapReduce模式. 只是把一篇篇文章逐一检查每个关键字, 化简成了一篇篇文章逐一检查5000个文件(开多线程不知道会不会提高效率). 因为楼主的需求没有统计,只是遍历.

坐等更牛B的回答.

哈。不好意思,昨天没看到这个帖子,没立刻水。我谈下我的建议吧。

1、首先,明确了,你是对集合A中,寻找集合B的子集。A是文件,B是关键词库。因此,遍历A,B都是不可缺少的。

2、但是遍历A和遍历B是不一样的。更本原因在于,B是静态的,A是动态的。或者严格上说,A是执行态的,B即便是动态的,也是非运行状态下的调整。除非你的命题变成,当对于本批A集合内,频率出现N次以上的元素,则会作为新元素落入B集合。

3、由于2的原因,导致集合A始终可以区分到足够小的范围,使得其子集之间无想关性。一个非最小无相关性的区分就是文件本身。毕竟你这个不是个带反馈的滤波器类型的目标。例如对A集合的元素的频率结论会影响A集合的操作本身。如2后面举的例子。而集合B则相反,总存在一个规模N,当B集合的子集达到规模N以上,一定存在相关性。一个非最大相关性的联系就是通过字母。例如 book和bed。存在共同的B。

这里比较抽象,我不想用单词作为你的操作对象的具体描述对象,因为可能你的关键字库是如下”中华人民共和国“本身就是个关键词。而中华又是个关键词。你也不可能用标点符号进行分割。

4、动手前,肯定是对静态对象做分析方法的确定,然后根据静态对象的分析方法,决定动态处理的数据的分析方法。因此首先是针对B集合进行处理。处理的目标是尽可能的降低查询成本。说白了就是遍历的成本。这里有两种策略,一个是,假设大概率是击中,只是不知道哪被击中,一种是假设大概率是击不中。对于后者,实际上是对前者的补集做处理。处理方式本质一样的。类似冒泡排序修正为快速排序或堆排序。O(log2N)是跑不掉的。不过这个也是等概率下,实际工程中可以通过两个方面的权重进行调整。一个是被A击中的频率,一个是B自身的相关性涵盖的内容。有点哈夫曼编码的味道。例如你存在b开头的单词是3个,a开头的单词是2个。那么b的访问一定是优先进行的。而之后在对其互斥的集合进行访问。 @Grrrr 谈的hash 是个良好的设计方法,但是 hash解决的是匹配验证本身的计算费用问题。不是我上面谈的问题。以上都是B集合的处理方案。说的空,是因为具体库得根据性质进行具体分析,理论和工程差异就在这。

5、对于A集合的操作。B集合已经确定了。则A就是个快速扫描的工作。而前面说过。A总能存在无相关性,此时可以使用并发操作。但是这里的并发操作并不是说多线程计算。而是说,假设 ”中华人民共和国的发展“,此处的”的“ 导致 ”中华人民共和国“和后续的”发展“是无相关性的,由此,”发展“在B集合内的匹配查找和”中华人民共和国”是异步的。准确说,两者可并发的东西,他们之间的内容是不需要组合再处理的。此时你不需要在 ”中华人民共和国“未击中时,查找 ”共和国的发展“ 这个内容的匹配。可以直接跳过 ”中华人民共和国的”。

6、综合4,5,则你需要对所有文件的内容,进行双次扫描。第一次是切割A集合的内容。第二次是根据第一次的切割,将相互非相关的集合,每个集合作为整体,落入B进行匹配。而实际上此处又反过来,对第4部分需要进行二次分析,实际上是从前面的分析中,寻找到,更小的能将A集合进行继续非想关性切割的判断内容。但这种判断内容,可能是符号,例如标点,或“的”这个本身的单词,属于B集合内没有的元素。但是也可能就是B集合内本身的元素,但是有点需要注意,这个元素一定的独立的。例如B集合中,存在对 “TMD”的作为关键词,任何包含 TMD的连续单词,都不在B集合内,则我们可以把 “TMD”作为 B集合里的独立元素。 也就是,该元素作为一个集合整体时,非其他元素的子集。由于关键词,本身包含有序,所以是有序集。只要不包含 “TMD”,那么别的单词为“TMBD”,那也不会影响’TMD“作为独立元素的特性,这个是可以证明出来的。当然”NTMD“,就会导致”TMD“不是独立元素。

由此这些独立元素本身也可以作为第一边扫描的非相关性边界检测。同时在检测到时,你可以立刻增加下划线。

 

基本思想就是上述的方式。那边不是北京招算法lead吗?开价还比较高,30W 到 60W。但说实话,看不懂我上面的内容的,也敢去拿这个钱的,只能说是骗钱的。

 

--- 共有 4 条评论 ---
宏哥见宏哥的答案. 5年前 回复
asdfsx勉强看的懂~~~算法苦手 5年前 回复
中山野鬼回复 @Grrrr : 哈。那写都是名词而已。关键面向具体任务实际操作。 5年前 回复
Grrrr野鬼说的更注重细节问题. 隐隐约约感觉到了trie树(键值树)结构. 还有KMP字符匹配算法. 5年前 回复

分词建->索引->标注

分词软件进行文章分词(关键词库为词库)建立报文摘要-->进真正的数据库,建立分词索引->根据索引段进行词标注-->0

不管是oracle 还是postgresql,mssql,sybase,DB2都有极强的针对"分词"类型进行索引能力,相当于在两个二叉树上进行索引.

参见宏哥针对300万产品进行分词索引的帖子,所用词库是20万.文中提到的规模, pieces of Cake

逐个检查最好,使用分词会有遗漏
--- 共有 2 条评论 ---
jingshishengxuMapReduce 只是把一个人的活多个人干了,并没有减少计算时间(我对MapReduce没实践过,估计是这样) 5年前 回复
jingshishengxu如果不要求百分百标注出来,允许极小遗漏的话,可以把关键词放在bloom里,这样就不用逐个比较了 5年前 回复

引用来自“jingshishengxu”的答案

逐个检查最好,使用分词会有遗漏
看数学模型是否正确了。数学的价值就是高度严谨的逻辑映射。不然我现在痛苦的证明数学问题做什么。哈。
--- 共有 1 条评论 ---
jingshishengxu对搞数学的只有膜拜了 5年前 回复
顶部