昨天拿到的一个任务->设计一个文章查重算法。于是用了一下午尝试去了解了下,最后算是解决了吧。然而仍有许多实现未去了解,这里先留个坑。(真的会填么?)现在这里整理下昨天尝试过的。

相似度统计算法,大概还是算是使用频率很高的。比如十分常见的IR领域(信息检索系统),或者说论文查重。

”分不分开”

思路分为两种:

  • 把一篇文章分割/取出变成若干字符串,然后对结果集合进行相似度匹配,即向量统计法
  • 求两篇文章的最大公共子序列(LCS算法)

我是这样看的:
LCS算法需要根据length(str1)*length(str2)生成矩阵,并进行动态规划计算,空间复杂度和时间复杂度并不理想,得出的最有用结果是两个字符串的最大公共序列(完全相同的最大区域),一小部分对于总体并不是太有价值,所以主流解决方案并未采用,另外一个问题就是不好进行优化,无论如何都要对一篇文章全部分析不能只取出有价值的部分。

LCS实现:
昨天犯懒没有写,留坑(某种意义上的挖坑王)

”取字还是取特征词”

既然选择了向量空间模型统计法,那么就需要文本->向量的这个过程,流程是:

长文本->向量集合->向量频度分析

向量怎么选就遇到问题了,如果是要分析两本书,不可能逐字比对吧。况且一句话里面其实无意义的语气词等很多,(语文学的不好,这个就不深入了)对于google这种每天百万级别的来讲更是不可能。于是大部分解决方案会把内容取出特征词汇。英语的话比较简单(词都是空格区分的),中文显然比较蛋疼(身为中国人不得不承受的卵疼。。),主流语言有很多开源分词库可用,大致原理是基于语料库分词后过滤掉无用词再统计词频筛选出前n个。再往下说又是玄学领域了。

我的选择么,因为要求大概还是在百字左右,我认为调库分词大概会比逐字分析更为费时,采用了后者。

附上PHP分字的代码(两句话你敢信):

function wordDivide($str) { 
    preg_match_all("/.{1}/u", $str, $splitStr);//正则分割,str=>array 
    return array_count_values($splitStr[0]);//统计数组元素频度,array=>dict 
}

”怎么分析向量集合”

这里选择就相当多了,常见的有LD(编辑距离)算法,JaccardSimilarity算法,计算余弦法。

LD算法:

Levenshtein Distance,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。根据length(str1)*length(str2)生成矩阵并将之中的元素生成矩阵。

缺点太明显啦,“生成矩阵”,“生成矩阵”这两个词大概就明白了,空间时间复杂度太高。而且由一个转换为另一个,也就代表着改变了顺序即为完全不同,”AABB“!=”BBAA”,一开始采用的这个,发现更优解果断舍弃。

PHP实现:

function dummyLevenshtein($str0, $str1)
{
    //用矩阵纪录操作数
    $vec = array(); //初始化
    for ($i = 0; $i <= sizeof($str0); $i++) $vec[0][$i] = $vec[$i][0] = $i;
    for ($x = 1; $x <= sizeof($str0); $x++) {
        $src_i = $str0[$x - 1];
        for ($y = 1; $y <= sizeof($str1); $y++) {
            $dst_j = $str1[$y - 1];
            if ($src_i == $dst_j) $cost = 0; else $cost = 1; //取左上+当前操作数,左侧+1,上侧+1三个数值中的最小
            /
            $vec[$x][$y] = min($vec[$x - 1][$y] + 1, $vec[$x][$y - 1] + 1, $vec[$x - 1][$y - 1] + $cost);
        }
    }
    return $vec[sizeof($str0)][sizeof($str0)];
}

function handleStr($str0, $str1)
{
    if (!is_string($str0) || !is_string($str1)) throw new Exception("Input Error");
    if (strlen($str0) == 0 || strlen($str1) == 0) throw new Exception("Input Error"); //字符串分割
    /
    preg_match_all("/.{1}/u", $str0, $str0);
    preg_match_all("/.{1}/u", $str1, $str1);
    $str0 = $str0[0];
    $str1 = $str1[0];
    return 1 - (dummyLevenshtein($str0, $str1) * 2 / (sizeof($str0) + sizeof($str1)));//相似度计算
}

外要说的就是PHP标准库里面自带(传送门:http://php.net/manual/zh/function.levenshtein.php)
JaccardSimilarity算法:

嗯,名字很长。然而这个方法十分粗暴,原理就是:选出两个集合中相同的元素/两个集合的全部元素。即 |S ∩ T|/|S ∪ T|

总之就是:这样的方法需要你说啊喂

如此简单代码贴出来怕被喷就省了

然而这个方法准确度也理所当然的不高,可以说十分不靠谱,果断不采用。

计算余弦法:

真的是那个cos么?嗯,真的是你怕不怕。我们可以把它们想象成空间中的两条线段,都是从原点([0, 0, …])出发,指向不同的方向。两条线段之间形成一个夹角,如果夹角为0度,意味着方向相同、线段重合;如果夹角为90度,意味着形成直角,方向完全不相似;如果夹角为180度,意味着方向正好相反。因此,我们可以通过夹角的大小,来判断向量的相似程度。夹角越小,就代表越相似。

从结果来看,这个与LD算法有相似的准确度,并且完美的解决了匹配顺序的问题,效率相比之下也比较划算,所以是目前的主流方法,果断采用。

PHP实现:

//分字
function wordDivide($str)
{
if (!is_string($str) || strlen($str) == 0) {
throw new Exception("Input error!!! ");
}
preg_match_all("/.{1}/u", $str, $splitStr);
return array_count_values($splitStr[0]);
}

//余弦定理算法
function calcCos($wordGroup1, $wordGroup2)
{
$unionArray = $wordGroup1;
//计算并集
foreach ($wordGroup2 as $key => $value)
$unionArray[$key] += $value;
$denominator = 0;
$count1 = $count2 = 0;
//遍历并集
foreach ($unionArray as $key => $value) {
$denominator += $wordGroup1[$key] * $wordGroup2[$key];
$count1 += $wordGroup1[$key] * $wordGroup1[$key];
$count2 += $wordGroup2[$key] * $wordGroup2[$key];
}
//返回余弦结果
return $denominator / sqrt($count1 * $count2);
}

function testStr($str1, $str2)
{
try {
$str1 = wordDivide($str1);
$str2 = wordDivide($str2);
$back = calcCos($str1, $str2);
echo "OutPut : ", $back * 100, "%n";
} catch (Exception $e) {
echo "Error occurred :", $e;
}
}

贴上简单的测试结果:

余弦定理算法:doc1 与 doc2 相似度为:0.9954971, 耗时:22mm

距离编辑算法:doc1 与 doc2 相似度为:0.99425095, 耗时:322mm

可见效率有明显提高,复杂度大致为:O(length(str1) +length(str2)) 。

总之呢

那么这样也就算解决了呢。然而,上面只普通青年的解决方法,谷歌这种大佬级别的,早已经不用这些方法。

向量(VSM)计算方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理。想想像Google这种全网搜索引擎,收录了上百亿的网页,爬虫每天爬取的网页数都是百万千万级别的。为了防止重复收录网页,爬虫需要对网页进行判重处理。如果采用VSM方法,计算量是相当可观的。

机智地谷歌提出了SimHash算法。(貌似一开始是别人),写到这里感觉累觉不爱,先上张图,下篇博客里认真分析下。(又挖坑)

———OSC居然不让外链,好吧是在下输了———–

下面给出几个可以提供参考的文章:

基于标题相似度的系列博客归类 : http://segmentfault.com/a/119000000269438
3

自己实现文本相似度算法(余弦定理): http://my.oschina.net/BreathL/blog/42477

计算字符串相似度算法——Levenshtein : http://wdhdmx.iteye.com/blog/1343856

TF-IDF与余弦相似性的应用 : http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html

从11点写成了深夜档也是醉了,滚去睡了。。