BT 如何利用碎片时间提升技术认知与能力？ 点击获取答案 * 投稿 * 活动大本营 * InfoQ手机客户端 * 关于我们 * 合作伙伴 * 欢迎关注我们的： * * * InfoQ - 促进软件开发领域知识与创新的传播 搜索关键词_____ Submit 登录 * En * 中文 * 日本 * Fr * Br 966,690 十二月 独立访问用户 * 语言 & 开发 + Java + Clojure + Scala + .Net + 移动 + Android + iOS + HTML 5 + JavaScript + 函数式编程 + Web API 特别专题 语言 & 开发 AI筑巢：机器学习在百度凤巢的深度应用 凤巢作为国内最大的搜索广告平台，机器学习在其中扮演什么样的角色呢？百度从09年开始就将机器学习应用到广告CTR模型中来，到目前为止，商 业广告的触发、点击预估、内容生态建设等几乎每个环节都深度使用机器学习算法。 浏览所有 语言 & 开发 * 架构 & 设计 + 架构 + 企业架构 + 性能和可伸缩性 + 设计 + 案例分析 + 设计模式 + 安全 特别专题 架构 & 设计 AI筑巢：机器学习在百度凤巢的深度应用 凤巢作为国内最大的搜索广告平台，机器学习在其中扮演什么样的角色呢？百度从09年开始就将机器学习应用到广告CTR模型中来，到目前为止，商 业广告的触发、点击预估、内容生态建设等几乎每个环节都深度使用机器学习算法。 浏览所有 架构 & 设计 * 数据科学 + 大数据 + NoSQL + 数据库 特别专题 数据科学 榨取最后一滴油水 Lovethesales要对来自700多个不同网站的两百多万个产品的数据进行分类，他们决定使用一种基于SVM的结构化分类器。他们通过优 化SVM的链接方式和重用标签训练数据获得各种改进。 浏览所有 数据科学 * 文化 & 方法 + Agile + 领导能力 + 团队协作 + 测试 + 用户体验 + Scrum + 精益 特别专题 文化 & 方法 大规模敏捷之总体规划 本系列文章的第一篇是关于如何让大规模敏捷工作共享同一个真实的大规模敏捷故事；第二篇文章描述了如何将需求切分成也许可以发布的史诗以及这样 做的重要性。因此，我们现在已经准备好基于那些切片及达成的共识进行构建；我们现在可以一起做总体规划了。 浏览所有 文化 & 方法 * DevOps + 持续交付 + 自动化操作 + 云计算 特别专题 DevOps 使用SpringBoot开启微服务之 虽然企业已经使用敏捷流程来开发软件，但是我们还在构建大型的整体耦合在一起的软件。如果你还没有准备好使用微服务，那你肯定落后于学习曲线中 的早期接受者阶段了。本文将帮助你创建、发现、调用微服务，开启微服务之旅。 浏览所有 DevOps * InfoQ手机客户端 * 架构 * 移动 * 运维 * 云计算 * AI前线 * 大数据 * 前端 * QCon合集 * AWS * PTC 全部话题 您目前处于： InfoQ首页 文章 网站文章如何能自动判定是抄袭？一种算法和实践架构剖析 网站文章如何能自动判定是抄袭？一种算法和实践架构剖析 喜欢 | 作者 文辉 文辉 关注 0 他的粉丝 发布于 2016年8月19日. 估计阅读时间: 15 分钟 | QCon北京2018全面起航：开启与Netflix、微软、ThoughtWorks等公司的技术创新之路！ * 分享到： 微博 微信 Facebook Twitter 有道云笔记 邮件分享 * "稍后阅读" * "我的阅读清单" Close [icon-notifications.svg] 亲爱的读者：我们最近添加了一些个人消息定制功能，您只需选择感兴趣的技术主题，即可获取重要资讯的邮件和网页通知。 1. 文本指纹介绍 互联网网页存在大量的重复内容网页，无论对于搜索引擎的网页去重和过滤、新闻小说等内容网站的内容反盗版和追踪、还是社交媒体等文本去重和聚类，都需要 对网页或者文本进行去重和过滤。 最简单的文本相似性计算方法可以利用空间向量模型，计算分词后的文本的特征向量的相似性，这种方法存在效率的严重弊端，无法针对海量的文本进行两两的相 似性判断。模仿生物学指纹的特点，对每个文本构造一个指纹，来作为该文本的标识，从形式上来看指纹一般为固定长度较短的字符串，相同指纹的文本可以认为 是相同文本。 最简单的指纹构造方式就是计算文本的md5或者sha哈希值，除非输入相同的文本，否则会发生“雪崩效应”，极小的文本差异通过md5或者sha计算出 来的指纹就会不同（发生冲撞的概率极低），那么对于稍加改动的文本，计算出来的指纹也是不一样。 因此，一个好的指纹应该具备如下特点： 1. 指纹是确定性的，相同的文本的指纹是相同的； 2. 指纹越相似，文本相似性就越高； 3. 指纹生成和匹配效率高。 业界关于文本指纹去重的算法众多，如k-shingle算法、google提出的simhash算法、Minhash算法、top k最长句子签名算法等等，本文接下来将简单介绍各个算法以及达观指纹系统的基本架构和思路。 2. 常用的指纹算法 2.1 k-shingle算法 shingle在英文中表示相互覆盖的瓦片。对于一段文本，分词向量为[w1, w2, w3, w4, … wn]， 设k=3，那么该文本的shingle向量表示为[(w1,w2,w3), (w2,w3,w4), (w3,w4,w5), …… (wn-2,wn-1,wn)]，计算两个文本的shingle向量的相似度（jarccard系数）来判断文本是否重复。由于k-shingle算法 的shingle向量空间巨大（特别是k特别大时），相比vsm更加耗费资源，一般业界很少采用这类算法。 2.2 Simhash算法 相关厂商内容 Simhash是google用来处理海量文本去重的算法，同时也是一种基于LSH(locality sensitive hashing)的算法。简单来说，和md5和sha哈希算法所不同，局部敏感哈希可以将相似的字符串hash得到相似的hash值，使得相似项会比不 相似项更可能的hash到一个桶中，hash到同一个桶中的文档间成为候选对。这样就可以以接近线性的时间去解决相似性判断和去重问题。 simhash算法通过计算每个特征（关键词）的哈希值，并最终合并成一个特征值即指纹。 simhash算法流程 1. 首先基于传统的IR方法，将文章转换为一组加权的特征值构成的向量。 2. 初始化一个f维的向量V，其中每一个元素初始值为0。 3. 对于文章的特征向量集中的每一个特征，做如下计算： a) 利用传统的hash算法映射到一个f-bit（一般设成32位或者64位）的签名。对于这个f- bit的签名，如果签名的第i位上为1，则对向量V中第i维加上这个特征的权值，否则对向量的第i维减去该特征的权值； b) 整个特征向量集合迭代上述运算后，根据V中每一维向量的符号来确定生成的f-bit指纹的值，如果V的第i维为正数，则生成f-bit指纹的第 i维为1，否则为0。 [30.jpg] 图1 simhash算法示意图 Simhash指纹匹配过程经过simhash指纹生成算法生成的指纹是一个f位的二进制字符串，如一个32位的指纹，‘10100111110001 1010100011011011’。对于两个文本的f位0-1字符串，simhash算法采用hamming distance来计算两个指纹之间的相似度，但是对于海量文本，如何从千万级别（甚至更多）的指纹集合中，找出最多只有k位不同的指纹呢？ 一个简单的思想就是以空间换时间，对于一个32位的指纹来说，将该指纹划分成4段，即4个区间，每个区间8位，如果两个指纹至多存在3（设k=3）位差 异，那么至少有一段的8位是完全相同的，因此可以考虑利用分段来建立索引，来减少需要匹配的候选指纹数量。 Simhash指纹匹配算法 1. 首先对于指纹集合Q构建多个表T1，T2…Tt，每一个表都是采用对应的置换函数π(i)将32-bit的fingerprint中的某p(i )位序列置换换到整个序列的最前面。即每个表存储都是整个Q的fingerprint的复制置换； 2. 对于给定的F，在每个Ti中进行匹配，寻找所有前pi位与F经过π(i)置换后的前pi位相同的fingerprint。 3. 对于所有在上一步中匹配到的置换后的fingerprint，计算其是否与π(i)(F)至多有k-bit不同。 Simhash算法比较高效，比较适用于对于长文本。 2.3 Minhash算法 Minhash也是一种LSH算法，同时也是一种降维的方法。Minhash算法的基本思想是使用一个随机的hash函数h(x)对集合A和B中的每个 元素进行hash，hmin(A)、hmin(B)分别表示hash后集合A和集合B的最小值，那么P(hmin(A) == hmin(B)) = Jaccard(A, B)。这是minhash算法的核心，其中hmin(A)为哈希函数h(x)对集合A的最小哈希值。 [31.jpg] 图2： 最小签名矩阵生成示意图 Minhash算法采用最小哈希函数族（一组随机的最小哈希函数）来构建文档的最小哈希签名。文档的最小哈希签名矩阵是对原始特征矩阵降维的结果。应用 过程中，可以使用k个最小函数分别计算出集合的哈希最小值。设hi表示第i个最小hash函数，最小签名矩阵中列向量为样本si的最小签名向量，其中w ij表示第j个最小hash函数对样本i的最小哈希值。 当k小于原始集合的长度（k << n）时，就相当于对数据降维，类比PCA等降维方法，minhash避免了复杂的矩阵运算。由于最小签名矩阵中，样本i，j的某一行或某几行的子向量的 相似度于样本i，j的jarcarrd距离相等，因此可以对最小签名矩阵运行行条化策略，经矩阵平均分为b个行条，每个行条由r条组成，当两个样本在任 意一个行条中的向量相等，即是一个相似性候选对，并检查文档是否真正相似或者相等。 关于minhash的原理和推导，以及在大量文本及高维特征下如何快速进行最小签名矩阵的构建操作可以参考https://en.wikipedia. org/wiki/MinHash及《大数据 互联网大规模数据挖掘与分布式处理》，数学的奥妙就在于此。 经过minhash降维后的文本向量，从概率上保证了两个向量的相似度和降维前是一样的，结合LSH技术构建候选对可以大大减少空间规模，加快查找速度 。 3.内容型网页文本指纹算法 [34.jpg] 本节将给出我们在对内容型网页（小说、新闻等）去重任务中总结出来的算法和实践经验，特别在当前内容版权日益受到重视和保护的背景下，对于内容版权方来 说，如何从网络上发现和追踪侵权和盗版行为日益重要。 从前文可以看出，指纹识别算法是实现指纹识别的关键，它直接决定了识别率的高低，是指纹识别技术的核心。特别是类似新闻类、小说类网页在转载或者盗版过 程中，文字的个数、顺序上一般都保持一致，当然不排除个别字错误或者少一个字的情况。 指纹生成的过程主要包括将文本全部转换成拼音、截取每个字拼音的首字母、统计该粒度内字母的频率分布、通过和参考系比较，将结果进行归一化、按字母序， 将数字表征转换成数字。 [32.jpg] 图3 指纹生成算法 算法描述： 1. 转拼音：可以解决字符集编码不一致的问题，可以利用成熟的英文指纹算法，减小分布空间，同时可以解决同音字替代问题； 2. 截取拼音首字：减小存储长度和分布空间（26个字母）； 3. 提取首字母频率：选择多少字来计算指纹，统计频率分布。需要设置颗粒度的大小（分段大小）以及重叠率。 大粒度容错性高，但是匹配率低；小粒度容错性低，但是误报率高且敏感度高。 重叠率是设置指纹计算片段移动的窗口大小： 假设拼音内容长为2n，颗粒长度为n，重叠率为50%，则需要计算的指纹片段分别为[1-n]，[n/2,3*n/2]，[n,2n] 4. 减去参考系：频率减去参考系 5. 归一化：将每个字母的数字特征归一化到一个闭区间内，如[0,9],按照字母顺序连接数字特征，变成一个数字，即指纹。 + 若空间为[0,9],即一个20位的整数，2^64，需要 8 byte + 若空间为[0,7],可用一个20位的8进制数，8^20,需要 8 byte + 若空间为[0,3],只需要 4^20, 共40 bit, 5 byte + 若空间为[0,1],需要2^20,20 bit,3 byte 归一化过程的算法步骤如下，假设颗粒长度为m： 输入：片段频率集合S:[s1,s2,s3,…sn] 参数：指纹集合dnas:[] 计算基数radix:=pow(2, log(m)/log(2) ) FOR 片段频率s IN S 修正频率,每个频率值:=max(频率，基数) 指纹dna:=空串 FOR tmp IN s[m-5:m] 将tmp转换成整数，基数为radix 将tmp转换成字符串，基数为radix dna:=dna连接tmp dnas:=dnas添加dna END 输出：指纹集合dnas 4. 达观指纹系统结构 4.1 基本架构 达观指纹追踪系统主要由爬虫系统、指纹生成系统、指纹存储、指纹查询和比对、数据分析、后台管理系统等几个主要模块构成，如图4所示。其中存储层包括匹 配结果信息库、网页库以及指纹库。 [33.jpg] 图4 指纹追踪系统模块图 A. 爬虫系统 爬虫系统从目的上看主要在于抓取互联网上的特定领域的网页（如新闻类网页），爬虫系统是原始数据的唯一来源，只有通过爬虫系统才能从浩瀚的互联网中抓取 相似的网页内容。爬虫系统需要拥有较高的抓取能力和反爬取能力，为整个系统提供大量的待检测页面。 B. 指纹存储模块 指纹存储模块计算母体（海量文本）的指纹，指纹可以理解为一行文本的向量表示，本系统的指纹存储系统采用mongo DB进行存储。 C. 指纹生成模块 指纹生成模块的输入是一行文本，其输出为该文本的指纹表示，为了达到较高的对比准确率，一个好的指纹生成系统至关重要。 D. 指纹查询和比对模块 指纹库中存储着大量的母体指纹，对于某一文本，指纹查询和比对模块要快速的判断该文本是否在母体库中存在重复。 E. 数据分析 数据分析系统需要对大量的文本及其对比结果进行统计数据分析。 F. 后台管理平台 提供数据分析的展示，并提供用户使用查询和输出分析报告等。 数据存储模块 A. 网页库 主要存放爬虫系统抓取的网页信息、站点信息，本系统网页库采用mongo DB。 B. 指纹库 主要存放母体指纹，本系统采用mongo DB存放指纹。为了加快指纹的查询和比对，本系统采用redis来对指纹建立索引，加快匹配速度。 C. 匹配信息库 存储指纹匹配结果， 包括待匹配的两个指纹， 原始网页id， 匹配相似度等。 4.2 系统架构 [34.jpg] 图5 系统架构图 4.3 系统处理流程 本系统的处理流程如图6所示，系统支持每天自动化从母体库中调度新的任务进行去重操作。 [35.jpg] 图6 系统流程图 5 总结 对于网页去重、内容盗版追踪、内容聚类等应用来说，指纹模块都是极其重要的模块。本文介绍了一些比较常用的指纹算法，包括k-shingle、simh ash、minhash；同时介绍了达观数据自主开发的指纹追踪系统及其关键算法，没有最好的算法，只有合适的算法，在实际的使用过程中，需要根据具体 业务场景，确定架构和算法。 作者介绍 文辉，同济大学计算机应用技术专业硕士，现任达观数据联合创始人，主要负责据推荐系统、数据采集系统、大数据平台架构等主要系统的研究和开发。曾就职于 盛大文学数据中心部门，负责推荐系统、爬虫系统、数据挖掘和分析等大数据系统的研发工作，在数据挖掘和采集、Hadoop/Hive、Spark等方面 具备充足的研发和实践经验。 __________________________________________________________________ 感谢杜小芳对本文的审校。 给InfoQ中文站投稿或者参与内容翻译工作，请邮件至editors@cn.infoq.com。也欢迎大家通过新浪微博（@InfoQ，@丁晓昀） ，微信（微信号：InfoQChina）关注我们。 评价本文 专业度 (*) ( ) ( ) ( ) ( ) 风格 (*) ( ) ( ) ( ) ( ) * 编辑观点 * 主编观点 ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ 提交 ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ 提[ ] [_] Author Contacted 相关主题: * 语言 & 开发 语言 & 开发 关注 183 他的粉丝 * 架构 & 设计 架构 & 设计 关注 484 他的粉丝 * 企业实践 企业实践 关注 1 他的粉丝 * 算法 算法 关注 1 他的粉丝 相关内容 您好，朋友！ 您需要 注册一个InfoQ账号 或者 登录 才能进行评论。在您完成注册后还需要进行一些设置。 获得来自InfoQ的更多体验。 告诉我们您的想法 ____________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ 允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p [ ] 当有人回复此评论时请E-mail通知我 [BUTTON Input] (not implemented)____________ 社区评论 关闭 by 发布于 * 查看 * 回复 * 回到顶部 关闭____________________________ 您的回复 引用原消息 ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ 允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p [ ] 当有人回复此评论时请E-mail通知我 [BUTTON Input] (not implemented)____________ 取消 关闭____________________________ 您的回复 ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ 允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p [ ] 当有人回复此评论时请E-mail通知我 [BUTTON Input] (not implemented)_____ 取消 关闭 OK 讨论 赞助商链接 InfoQ每周精要 订阅InfoQ每周精要，加入拥有25万多名资深开发者的庞大技术社区。 您的邮箱________ 订 语言 & 开发 AI筑巢：机器学习在百度凤巢的深度应用 美丽联合集团VP顶天：总结这一年，我们在技术上的变与不变 关于Parcel你需要知道的所有内容：超快的Web应用打包器 架构 & 设计 AI筑巢：机器学习在百度凤巢的深度应用 万亿级大数据平台的架构设计与演进实践 美丽联合集团VP顶天：总结这一年，我们在技术上的变与不变 文化 & 方法 大规模敏捷之总体规划 美丽联合集团VP顶天：总结这一年，我们在技术上的变与不变 荷兰铁路在采纳敏捷和精益中的做法 数据科学 Hazelcast加入Eclipse基金会 基于Kubernetes构建现代大数据管道 使用TensorFlow和Kubernetes构建GPU加速工作流 DevOps Meltdown和Spectre是什么以及如何应对 Hazelcast加入Eclipse基金会 深入了解Spectre和Meltdown * 首页 * 全部话题 * QCon全球软件开发大会 * 关于我们 * 投稿 * 创建账号 * 登录 * 全球QCon * [javascript] 伦敦 Mar 6-10, 2017 * [javascript] 北京 Apr 16-18, 2017 * [javascript] 圣保罗 Apr 24-26, 2017 * [javascript] 纽约 Jun 26-30, 2017 * [javascript] 上海 Oct 19-21, 2017 * [javascript] 东京，2017 秋 * [javascript] 旧金山 Nov 13-17, 2017 InfoQ每周精要 订阅InfoQ每周精要，加入拥有25万多名资深开发者的庞大技术社区。 您的邮箱________ ____________________ 订 * RSS订 * InfoQ官方微博 * InfoQ官方微信 * 社区新闻和热点 特别专题 * 活动大本营 * 月刊：《架构师》 * AWS专区 * 百度技术沙龙专区 * 信息无障碍参考文档 提供反馈 feedback@cn.infoq.com 错误报告 bugs@cn.infoq.com 商务合作 hezuo@geekbang.org 内容合作 editors@cn.infoq.com 市场合作 hezuo@geekbang.org InfoQ.com及所有内容，版权所有 © 2006-2017 C4Media Inc. InfoQ.com 服务器由 Contegix提供, 我们最信赖的ISP伙伴。 北京创新网媒广告有限公司 京ICP备09022563号-7 隐私政策 (BUTTON) 关闭 登陆InfoQ，与你最关心的话题互动。 E-mail ____________________ 密________________________ 登录 __________________________________________________________________ (BUTTON) 使用Google账号登录 (BUTTON) 使用Microsoft账号登录 (BUTTON) 使用Weibo账号登录 忘记密码？ 没有帐号？立即注册 找回密码.... InfoQ账号使用______________________________ 发送邮件 重新登录 没有帐号？立即注册 InfoQ Logo Follow 关注你最喜爱的话题和作 快速浏览网站内你所感兴趣话题的精选内容。 Like 内容自由定制 选择想要阅读的主题和喜爱的作者定制自己的新闻源。 Notifications 获取更新 设置通知机制以获取内容更新对您而言是否重要 BT Close E-mail ____________________ 密________________________ Submit 使用Google账号登录 使用Microsoft账号登录 使用Weibo账号登录 忘记密码？ InfoQ账号使用______________________________ (BUTTON) 发送邮件 重新登录 重新发____________________________________ (BUTTON) 重新发送 重新登录 没有用户名？ 点击注册 您的个人介绍是最新的么？请确认并更新。 E-mail ____________________ 注意：如果要修改您的邮箱，我们将会发送确认邮件到您原来的邮箱。 公司[ ]称: [_] 使用现有的公司名称 修改公____________________________________ 公司[ ]质： [_] 使用现有的公司性质 修改公____________________________________________________..............] 公司[ ]模: [_] 使用现有的公司规模 修改公司规模为： [___________] 国[ ] [_] 使用现在的国家 更新--- 选择您的国家 ---__________________........] 省[ ] [_] 使用现在的省份 更新省份: [ ] Subscribe to our newsletter? [ ] Subscribe to our industry email notices? 提交 请根据验证邮件确认新的邮件地址。 我们发现您在使用ad blocker。 我们理解您使用ad blocker的初衷，但为了保证InfoQ能够继续以免费方式为您服务，我们需要您的支持。InfoQ绝不会在未经您许可的情况下将您的数据提供给第 三方。我们仅将其用于向读者发送相关广告内容。请您将InfoQ添加至白名单，感谢您的理解与支持。