文档章节

什么是Shingling算法

mickelfeng
 mickelfeng
发布于 2017/06/15 14:48
字数 375
阅读 31
收藏 0

shingling算法用于计算两个文档的相似度,例如,用于网页去重。维基百科对w-shingling的定义如下:

In natural language processing a w-shingling is a set of unique "shingles"—contiguous subsequences of tokens in a document —that can be used to gauge the similarity of two documents. The w denotes the number of tokens in each shingle in the set.

维基百科用一个浅显的例子讲解了shingling算法的原理。比如,一个文档

"a rose is a rose is a rose"

分词后的词汇(token,语汇单元)集合是

(a,rose,is,a,rose,is, a, rose)

那么w=4的4-shingling就是集合:

{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) }

去掉重复的子集合:

{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }

给定shingle的大小,两个文档A和B的相似度 r 定义为:

r(A,B)=|S(A)∩S(B)| / |S(A)∪S(B)|

其中|A|表示集合A的大小。

因此,相似度是介于0和1之间的一个数值,且r(A,A)=1,即一个文档和它自身 100%相似。

 

扩展阅读

  • Shingling算法的更详细说明参见博客网页去重——Shingling算法,该文作者使用的类库是com.planetj.math.rabinhash.RabinHashFunction32
  • 距离和相似度度量
    • 范数和欧拉距离
    • cosine similarity
    • Jacard index
    • Pearson correlation coefficient
    • 编辑距离或者Levenshtein distance
    • SimRank 相似
  • 网页去重-算法篇
    • I-Match
    • Shingling
    • SimHashing( locality sensitive hash)
    • Random Projection
    • SpotSig
    • combined
  • 一个对算法进行解释的外文资料sketching

本文转载自:http://www.gooseeker.com/cn/node/knowledgebase/shingling

mickelfeng

mickelfeng

粉丝 237
博文 2785
码字总数 604219
作品 0
成都
高级程序员
私信 提问
shingling算法——提取特征,m个hash函数做指纹计算,针对特征hash后变成m维向量,最后利用union-find算法计算相似性

shingling算法用于计算两个文档的相似度,例如,用于网页去重。维基百科对w-shingling的定义如下: In natural language processing a w-shingling is a set of unique "shingles"—contigu......

桃子红了呐
2017/11/16
0
0
从文档相似度计算看LSH(Locality Sensitive Hashing)

经常使用的哈希函数,冲突总是不招人喜欢。LSH却依赖于冲突,在解决NNS(Nearest neighbor search )时,我们期望: 离得越近的对象,发生冲突的概率越高 离得越远的对象,发生冲突的概率越低 ...

开源中国驻成都办事处
2012/09/16
5.9K
4
List of Python Tutorials

Python Home Introduction Running Python Programs (os, sys, import) Modules and IDLE (Import, Reload, exec) Object Types - Numbers, Strings, and None Strings - Escape Sequence, R......

好铁
2016/04/01
25
0
【转】海量数据相似度计算之simhash和海明距离

 通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式...

一只死笨死笨的猪
2014/09/30
1K
0
海量数据相似度计算实例 simhash和海明距离

simHash是用来网页去重最常用的hash方法,速度很快。海明距离是在信息编码中,两个合法代码对应位上编码不同的位数称为码距。 通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数...

一曲
2015/12/24
112
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
378
7
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
11
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部