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 |
建议继续学习:
- 相似度计算常用方法综述 (阅读:9353)
- 字符串匹配那些事(一) (阅读:5736)
- 如何计算两个文档的相似度(一) (阅读:4743)
- 一个简单的中文分词程序 (阅读:4523)
- 漫话中文分词算法 (阅读:3979)
- URL相似度计算的思考 (阅读:3685)
- 如何计算两个文档的相似度(二) (阅读:3732)
- 漫话中文自动分词和语义识别(下):句法结构和语义结构 (阅读:3437)
- 腾讯php程序员面试题目答案――编程任务 (阅读:3224)
- 基于trie数据字典的php中文分词 (阅读:3026)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:排头兵 来源: 排头兵 @ Talk
- 标签: 分词 相似度
- 发布时间:2010-08-02 02:34:41
- [67] Go Reflect 性能
- [67] Oracle MTS模式下 进程地址与会话信
- [67] 如何拿下简短的域名
- [61] IOS安全–浅谈关于IOS加固的几种方法
- [60] 图书馆的世界纪录
- [59] 【社会化设计】自我(self)部分――欢迎区
- [58] android 开发入门
- [56] 视觉调整-设计师 vs. 逻辑
- [49] 给自己的字体课(一)——英文字体基础
- [47] 界面设计速成