Levenshtein distance相似度算法

Levenshtein distance相似度算法

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 [email protected]
@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);

建议继续学习：