技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> Levenshtein distance相似度算法

Levenshtein distance相似度算法

浏览:3103次  出处信息

Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名。
主要用途:

Spell checking(拼写检查)
Speech recognition(语句识别)
DNA analysis(DNA分析)
Plagiarism detection(抄袭检测)
Spam email (垃圾邮件检测)
Duplicate content (重复内容)

计划用php写一个内容相似度引擎,这篇博客是其核心思想之一,主要这个DPS需要掌握,当然php有一个相似度函数similar_text可以参考,我为了体现算法思路,就用php实现了.

随便提一下,内容相似度引擎的思路:

内容DNA识别技术思路

1、对一篇文章进行分词,根据分词的结果排序,得出初级DNA

内容相似度引擎不只是简单的通过算法来判断内容是否相似,分词的目的是为了体现 语义,任何一篇文章都会有主题语句,可以通过算法大概的分析一篇文章的关键词出来,然后按照既定的规律进行排序,结合第2,3点可以判断一篇文章是否抄袭

2、对一篇文章进行整句切分, 算出句子的DNA,

在符合第1点的同时,如果一篇文章语句很多类似,那么也是可以判定一本文章是否有抄袭的嫌疑,当然,某些人会去改一些词,使得机器不好判断,结合第3点可以在一定程度防止通过篡改某些词来蒙混过关

3、对一篇文章进行分词,统计每个词的数量,并根据分词结果排序,获得高级DNA

对第3点的分词结果做一个简单描述
比如一篇文章介绍 中国人民解放军的,假如,中国这个词出现了67词,人民出现了12词,解放军出现了10词,后面陆续。。。。。。。。
根据 汉字首字符 chr,获得ascii编码,进行一个常规数组排序,比如从大到小。。。。。。。。。可以获得一个词的有序列表,记住包括出现次数。
截取有序列表的80%词汇量,次数*词/总数=80%,如果另外一篇文章符合前面2点,也符合第3点,那么这篇文章可以判断是篡改抄袭的.

思路就这些,准备明后天写写代码,计划用PHP来实现,C语言不是很熟悉,为了体现思路,效率估计不会很高。

Levenshtein distance or 相似度 or 最短距离 算法 代码

以下是代码片段:

<?php
@author shjuto@gmail.com
@blog http://www.paitoubing.cn
@date 2010-------2012 地球
class similarity
{
    function ld($str1,$str2)
    {
        $str1len = strlen($str1);
        $str2len = strlen($str2);
 
        if($str1len == 0)
        {
            return $str2len;
        }
 
        if($str2len == 0)
        {
            return $str1len;
        }
 
 
        $distance = array();
 
        for($i = 0; $i <= $str1len;$i++)
        {
            $distance[$i][0] = $i;
        }
 
        for($j = 0; $j <= $str2len;$j++)
        {
            $distance[0][$j] = $j;
        }
 
        for($i = 1; $i <= $str1len;$i++)
        {
            $char1 = $str1[$i-1];
 
            for($j = 1;$j <= $str2len;$j++)
            {
                $char2 = $str2[$j-1];
                if($char1 == $char2)
             {
                 $temp = 0;
             }
             else
             {
                 $temp = 1;
             }
 
             $distance[$i][$j] = min($distance[$i-1][$j]+1,$distance[$i][$j-1]+1,$distance[$i-1][$j-1]+$temp);
            }
 
        }
        //print_r($distance);
        // 可以注释掉,下面table的内容,为了测试思路,直观显示数组内容,添加上去的
        echo '<table border=1>';
        foreach ($distance as $key=>$value)
        {
         echo '<tr>';
         foreach ($value as $h)
         {
          echo '<td>'.$h.'</td>';
         }
         echo '</tr>';
        }
        echo '';
 
        return $distance[$str1len][$str2len];
    }
 
    function sim($str1,$str2)
    {
        $ld = $this->ld($str1,$str2);
 
        return 1 - ($ld / max(strlen($str1),strlen($str2)));
    }
 
}
 
$similarity = new similarity();
$str1 = 'kitten';
$str2 = 'sitting';
print_r($similarity->ld($str1,$str2));
echo $similarity->sim($str1,$str2);

建议继续学习:

  1. 相似度计算常用方法综述    (阅读:9353)
  2. 字符串匹配那些事(一)    (阅读:5736)
  3. 如何计算两个文档的相似度(一)    (阅读:4743)
  4. 一个简单的中文分词程序    (阅读:4523)
  5. 漫话中文分词算法    (阅读:3979)
  6. URL相似度计算的思考    (阅读:3685)
  7. 如何计算两个文档的相似度(二)    (阅读:3732)
  8. 漫话中文自动分词和语义识别(下):句法结构和语义结构    (阅读:3437)
  9. 腾讯php程序员面试题目答案――编程任务    (阅读:3224)
  10. 基于trie数据字典的php中文分词    (阅读:3026)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1