|||
前面已经说到,论坛的抽取目标是楼主帖、回复帖,然后在从楼主帖和回复贴中提取发布时间等详细信息。回帖符合以前提到的最大连续重复子串的特点。所以这里先谈下回帖的提取。然后再讨论剩下的提取目标。
字符串中提取最大连续重复子串是个传统的算法问题。其实最大和重复两个条件在很多中情况下相互矛盾,当要求重复的子串长度最大时,重复次数可能会小,而当重复次数达到一定程度时,就会出现长度较短。当然如果两个参数同时达到最大,当然是最好了。理论上来讲,我们只能设定阈值来限定一个值,达到要求的模式都提取出来,然后再通过通过公式计算出权重最大的,就是我们所需要的模式了。
因为所有的回帖都是后台代码循环生成的,所以他们会属于一个父节点。我们所需要做的工作就是遍历网页中的每个结点,分析其所有的子节点,找出当前节点下的最大连续重复出现的模式。这里我们设置重复次数的最低阈值为5,那么只有连续出现5次的节点才是我们所需要的模式。第二个问题,如果把该父节点下的所有子节点的标签名表示成一字符串,那么我们所需要做的就是在这个字符串中找到最大连续重复的子串,这里大家可能会想到后缀树可以用来发现字符串中的连续重复出现的字符串,虽然说后缀树的查找效率很高,但是其构造成本很大。所以这里,我们是不是可以想一个好的算法来解决这个问题呢。
首先我们先谈谈最大连续重复出现这个概念,最大代表重复出现的子串的长度最长,当然,如果想以前的论文中用后缀树解决这个问题,把节点的路径当成字符串处理,确实最长代表内容最多,最可能是包含内容的回帖。但是这个先不谈是否可行,因为很多回帖虽然是程序循环生成,但是在目前的论坛中, 内容中也是可以包含很多的标签包括div,style,font,tr等等,这就大大破坏了结构相等的特性,也就是说把论坛回帖提取问题转化成字符串中发现连续重复子串的问题是不切实际的。因此,基于后缀树的论文基本上都不能适用于现今的论坛。因此我们只有采用结构相似来定义“重复”这个概念。那么重复就是节点之间的相似,这时对于节点的长度就没有要求了,因为节点是嵌套的,也许它本身可能只有一个节点,但是其子节点中包含了很多信息。因此我们只要求连续重复出现,并且重复次数达到阈值,就可以当作候选模式提取出来。
通过上面的分析,我们只需要解决以下三个问题就可以最终解决回帖提取问题:1、研究出算法提取每个父节点下所有连续重复出现的子节点序列为候选模式;2、研究算法计算两个节点的结构相似度3、在提取的候选模式中,用一个公式选出最符合条件的模式,就是我们的回帖节点序列。在以后的博文中我们会分别讨论这个三个问题。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 21:25
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社