首页 > 经验 > 关键词 > 谷歌搜索引擎最新资讯 > 正文

谷歌搜索引擎背后的数学

2016-01-19 14:28 · 稿源:changhai.org

一. 引言

在如今这个互联网时代, 有一家公司家喻户晓——它自 1998 年问世以来, 在极短的时间内就声誉鹊起, 不仅超越了所有竞争对手, 而且彻底改观了整个互联网的生态。 这家公司就是当今互联网上的第一搜索引擎: 谷歌 (Google)。

在这样一家显赫的公司背后, 自然有许许多多商战故事, 也有许许多多成功因素。 但与普通商战故事不同的是, 在谷歌的成功背后起着最关键作用的却是一个数学因素。

本文要谈的就是这个数学因素。

谷歌作为一个搜索引擎, 它的核心功能顾名思义, 就是网页搜索。 说到搜索, 我们都不陌生, 因为那是凡地球人都会的技能。 我们在字典里查个生字, 在图书馆里找本图书, 甚至在商店里寻一种商品, 等等, 都是搜索。 只要稍稍推究一下, 我们就会发现那些搜索之所以可能, 并且人人都会, 在很大程度上得益于以下三条:

1、搜索对象的数量较小——比如一本字典收录的字通常只有一两万个, 一家图书馆收录的不重复图书通常不超过几十万种, 一家商店的商品通常不超过几万种, 等等。

2、搜索对象具有良好的分类或排序——比如字典里的字按拼音排序, 图书馆里的图书按主题分类, 商店里的商品按品种或用途分类, 等等。

3、搜索结果的重复度较低——比如字典里的同音字通常不超过几十个, 图书馆里的同名图书和商店里的同种商品通常也不超过几十种, 等等。

但互联网的鲜明特点却是以上三条无一满足。 事实上, 即便在谷歌问世之前, 互联网上的网页总数就已超过了诸如图书馆藏书数量之类传统搜索对象的数目。 而且这还只是冰山一角, 因为与搜索图书时单纯的书名搜索不同, 互联网上的搜索往往是对网页内容的直接搜索, 这相当于将图书里的每一个字都变成了搜索对象, 由此导致的数量才是真正惊人的, 它不仅直接破坏了上述第一条, 而且连带破坏了二、 三两条。 在互联网发展的早期, 象雅虎 (Yahoo) 那样的门户网站曾试图为网页建立分类系统, 但随着网页数量的激增, 这种做法很快就 “挂一漏万” 了。 而搜索结果的重复度更是以快得不能再快的速度走向失控。 这其实是可以预料的, 因为几乎所有网页都离不开几千个常用词, 因此除非搜索生僻词, 否则出现几十万、 几百万、 甚至几千万条搜索结果都是不足为奇的。

互联网的这些 “不良特点” 给搜索引擎的设计带来了极大的挑战。 而在这些挑战之中, 相对来说, 对一、 二两条的破坏是比较容易解决的, 因为那主要是对搜索引擎的存储空间和计算能力提出了较高要求, 只要有足够多的钱来买 “装备”, 这些都还能算是容易解决的——套用电视连续剧《蜗居》中某贪官的台词来说, “能用钱解决的问题就不是大问题”。 但对第三条的破坏却要了命了, 因为无论搜索引擎的硬件如何强大, 速度如何快捷, 要是搜索结果有几百万条, 那么任何用户想从其中 “海选” 出自己真正想要的东西都是几乎不可能的。 这一点对早期搜索引擎来说可谓是致命伤, 而且它不是用钱就能解决的问题。

这致命伤该如何治疗呢? 药方其实很简单, 那就是对搜索结果进行排序, 把用户最有可能需要的网页排在最前面, 以确保用户能很方便地找到它们。 但问题是: 网页的水平千差万别, 用户的喜好更是万别千差, 互联网上有一句流行语叫做: “在互联网上, 没人知道你是一条狗” (On the Internet, nobody knows you're a dog)。 连用户是人是狗都 “没人知道”, 搜索引擎又怎能知道哪些搜索结果是用户最有可能需要的, 并对它们进行排序呢?

在谷歌主导互联网搜索之前, 多数搜索引擎采用的排序方法, 是以被搜索词语在网页中的出现次数来决定排序——出现次数越多的网页排在越前面。 这个判据不能说毫无道理, 因为用户搜索一个词语, 通常表明对该词语感兴趣。 既然如此, 那该词语在网页中的出现次数越多, 就越有可能表示该网页是用户所需要的。 可惜的是, 这个貌似合理的方法实际上却行不大通。 因为按照这种方法, 任何一个象祥林嫂一样翻来复去倒腾某些关键词的网页, 无论水平多烂, 一旦被搜索到, 都立刻会 “金榜题名”, 这简直就是广告及垃圾网页制造者的天堂。 事实上, 当时几乎没有一个搜索引擎不被 “祥林嫂” 们所困扰, 其中最具讽刺意味的是: 在谷歌诞生之前的 1997 年 11 月, 堪称早期互联网巨子的当时四大搜索引擎在搜索自己公司的名字时, 居然只有一个能使之出现在搜索结果的前十名内, 其余全被 “祥林嫂” 们挤跑了。

二. 基本思路

正是在这种情况下, 1996 年初, 谷歌公司的创始人, 当时还是美国斯坦福大学 (Stanford University) 研究生的佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。 这两位小伙子之所以研究网页排序问题, 一来是导师的建议 (佩奇后来称该建议为 “我有生以来得到过的最好建议”), 二来则是因为他们对这一问题背后的数学产生了兴趣。

网页排序问题的背后有什么样的数学呢? 这得从佩奇和布林看待这一问题的思路说起。

在佩奇和布林看来, 网页的排序是不能靠每个网页自己来标榜的, 无论把关键词重复多少次, 垃圾网页依然是垃圾网页。 那么, 究竟什么才是网页排序的可靠依据呢? 出生于书香门第的佩奇和布林 (两人的父亲都是大学教授) 想到了学术界评判学术论文重要性的通用方法, 那就是看论文的引用次数。 在互联网上, 与论文的引用相类似的是显然是网页的链接。 因此, 佩奇和布林萌生了一个网页排序的思路, 那就是通过研究网页间的相互链接来确定排序。 具体地说, 一个网页被其它网页链接得越多, 它的排序就应该越靠前。 不仅如此, 佩奇和布林还进一步提出, 一个网页越是被排序靠前的网页所链接, 它的排序就也应该越靠前。 这一条的意义也是不言而喻的, 就好比一篇论文被诺贝尔奖得主所引用, 显然要比被普通研究者所引用更说明其价值。 依照这个思路, 网页排序问题就跟整个互联网的链接结构产生了关系, 正是这一关系使它成为了一个不折不扣的数学问题。

思路虽然有了, 具体计算却并非易事, 因为按照这种思路, 想要知道一个网页 Wi 的排序, 不仅要知道有多少网页链接了它, 而且还得知道那些网页各自的排序——因为来自排序靠前网页的链接更有分量。 但作为互联网大家庭的一员, Wi 本身对其它网页的排序也是有贡献的, 而且基于来自排序靠前网页的链接更有分量的原则, 这种贡献与 Wi 本身的排序也有关。 这样一来, 我们就陷入了一个 “先有鸡还是先有蛋” 的循环: 要想知道 Wi 的排序, 就得知道与它链接的其它网页的排序, 而要想知道那些网页的排序, 却又首先得知道 Wi 的排序。

为了打破这个循环, 佩奇和布林采用了一个很巧妙的思路, 即分析一个虚拟用户在互联网上的漫游过程。 他们假定: 虚拟用户一旦访问了一个网页后, 下一步将有相同的几率访问被该网页所链接的任何一个其它网页。 换句话说, 如果网页 Wi 有 Ni 个对外链接, 则虚拟用户在访问了 Wi 之后, 下一步点击那些链接当中的任何一个的几率均为 1/Ni。 初看起来, 这一假设并不合理, 因为任何用户都有偏好, 怎么可能以相同的几率访问一个网页的所有链接呢? 但如果我们考虑到佩奇和布林的虚拟用户实际上是对互联网上全体用户的一种平均意义上的代表, 这条假设就不象初看起来那么不合理了。 那么网页的排序由什么来决定呢? 是由该用户在漫游了很长时间——理论上为无穷长时间——后访问各网页的几率分布来决定, 访问几率越大的网页排序就越靠前。

为了将这一分析数学化, 我们用 pi(n) 表示虚拟用户在进行第 n 次浏览时访问网页 Wi 的几率。 显然, 上述假设可以表述为 (请读者自行证明):

pi(n+1) = Σj pj(n)pj→i/Nj

这里 pj→i 是一个描述互联网链接结构的指标函数 (indicator function), 其定义是: 如果网页 Wj 有链接指向网页 Wi, 则 pj→i 取值为 1, 反之则为 0。 显然, 这条假设所体现的正是前面提到的佩奇和布林的排序原则, 因为右端求和式的存在表明与 Wi 有链接的所有网页 Wj 都对 Wi 的排名有贡献, 而求和式中的每一项都正比于 pj, 则表明来自那些网页的贡献与它们的自身排序有关, 自身排序越靠前 (即 pj 越大), 贡献就越大。

为符号简洁起见, 我们将虚拟用户第 n 次浏览时访问各网页的几率合并为一个列向量 pn, 它的第 i 个分量为 pi(n), 并引进一个只与互联网结构有关的矩阵 H, 它的第 i 行 j 列的矩阵元为 Hij = pj→i/Nj, 则上述公式可以改写为:

pn+1 = Hpn

这就是计算网页排序的公式。

熟悉随机过程理论的读者想必看出来了, 上述公式描述的是一种马尔可夫过程 (Markov process), 而且是其中最简单的一类, 即所谓的平稳马尔可夫过程 (stationary Markov process), 而 H 则是描述马尔可夫过程中的转移概率分布的所谓转移矩阵 (transition matrix)。 不过普通马尔可夫过程中的转移矩阵通常是随机矩阵 (stochastic matrix), 即每一列的矩阵元之和都为 1 的矩阵 (请读者想一想, 这一特点的 “物理意义” 是什么?)。 而我们的矩阵 H 却可能有一些列是零向量, 从而矩阵元之和为 0, 它们对应于那些没有对外链接的网页, 即所谓的 “悬挂网页” (dangling page)。

上述公式的求解是简单得不能再简单的事情, 即:

pn = Hnp0

其中 p0 为虚拟读者初次浏览时访问各网页的几率分布 (在佩奇和布林的原始论文中, 这一几率分布被假定为是均匀分布)。

  • 相关推荐
  • 大家在看
  • 分析师认为苹果应该收购DuckDuckGo搜索引擎 以向谷歌施压

    伯恩斯坦公司(Bernstein)分析师Toni Sacconaghi在分享的一份研究报告中表示,苹果应该收购一家搜索引擎公司,向谷歌施加压力。

  • 谷歌前广告主管正在打造一款无广告的搜索引擎

    据外媒报道,Sridhar Ramaswamy于 2013 年成为谷歌广告和商务高级副总裁。他领导着这个价值 1150 亿美元的分支机构达五年之久,该机构负责通过AdSense在搜索、YouTube和网站上出现的广告。但因受够了谷歌的暴利和客户与广告商之间的利益冲突,Ramaswamy选择离开谷歌并创建了自己的搜索引擎。

  • 谷歌向苹果支付数十亿美元,使其成为Safari的默认搜索引擎

    英国监管机构周三发布了有关苹果Safari浏览器和谷歌搜索引擎交易的调查报告。英国竞争和市场管理局(CMA)最新报告显示, 2019 年,谷歌共向英国支付了 12 亿英镑(约合 15 亿美元)的费用,成为英国各种移动设备上的默认搜索引擎,其中,绝大部分付给了苹果公司。

  • 百度回应腾讯告老干妈涉某搜索引擎:手里的瓜突然不香了

    7月1日,随着贵阳警方发布了腾讯与老干妈千万广告费纠纷案是因为3人伪造印章与腾讯签合同,也让这件事情真相大白。但网上传闻“腾讯状告老干妈拖欠广告费提及某搜索引擎”,对此百度官方回应称“手里的瓜突然就不香了”。

  • 谷歌英国向苹果交了15亿美元“保护费” 成Safari默认搜索引擎

    据路透社报道,英国监管机构正在审查苹果和谷歌之间的一项长期协议,该协议涉及苹果设备将谷歌设置为默认搜索引擎。

  • Android版YouTube客户端尝试引入谷歌搜索引擎的结果

    ​继近日在 Android 版 YouTube 客户端中引入避免熬夜的“就寝提醒”功能之后,Google 现又尝试为其引入来自谷歌搜索引擎的推荐内容。Reddit 网友 u / TheMrIggs 爆料称,其近日试图在 YouTube App 中搜索“小刀开啤酒”,结果意外地发现了正在测试的这项功能。如下方截图所示,Android 版 YouTube 客户端已能够显示除站内视频之外的谷歌搜索引擎结果。

  • 替代谷歌 华为自研搜索引擎“花瓣”悄然上线

    鸿蒙系统、HMS、App Gallery等是华为取代安卓+谷歌服务的备胎方案,经挖掘,在海外市场,华为自研的搜索引擎服务Petal Search(花瓣搜索)也已经悄然上线。

  • 搜索引擎优化的三个诀窍,送你的网站“C位出道”

    面对搜索引擎上数不胜数的URL,确保你的网站稳固在搜索结果首页顶部非常重要。搜索引擎优化(SEO)可以助你一臂之力。

  • 字节跳动推出企业技术服务平台“火山引擎 ”

    6月22日消息,字节跳动企业技术服务平台“火山引擎”官网上线,字节跳动在企业服务领域的布局开始慢慢地揭开其神秘的面纱。据介绍,“火山引擎”是字节跳动旗下企业级智能技术服务平台,依托字节跳动的大数据、人工智能等技术能力,以及增长理念与方法论,为客户提供技术产品与解决方案。字节跳动火山引擎负责人肖默表示:字节跳动作为一家全球化互联网公司,在过去8年中迅速成长,在这一过程中,不断积累的技术能力、

  • 信息流优化策略与SEO搜索排名,有关联吗?

    最近,在和SEO你问我答群里小伙伴,私下交流的时候,总是在说一些流量获取的问题,而最为常讨论的情况就是SEO流量与信息流平台的流量。

  • 官抖直播,真能成为销售增长新引擎?

    当携程CEO梁建章、网易丁磊、格力董明珠纷纷走进直播间,并频传销量捷报;当寺库、妃鱼、唯品会为代表的电商平台选择扎根在抖音并开启高频直播,以寻求新流量渠道的获客和变现机会;

  • 百度搜索将严格控制搜索结果中的APP调起行为

    2020 年 3 月,百度搜索资源平台发布了《百度APP移动搜索落地页体验白皮书5.0》。近期百度搜索发现部分站点频繁出现强制用户调起APP的行为,严重影响了用户的搜索体验。

  • 记录“向往的小米生活”,巨量引擎如何让综艺IP效应最大化?

    当代年轻人的生活节奏越来越快,对娴静自得的生活状态总是持以特别的向往和期待。 5 月 8 日,《向往的生活》第四季正式上线,这个号召大家回归自然,放慢生活节奏的综艺节目自上线起即倡导不一样的生活方式,激起广大用户关注。作为此季的首席合作伙伴,小米 10 期望与“蘑菇屋”一起记录各种美好过往,更希望在拍摄场景中传递产品本身的优势功能。为了将IP效应最大化,小米联合巨量引擎,借助抖音和今日头条强大的内容传播影响力

  • 支付宝宣布搜索板块新增数十万金融类搜索关键词

    今日,支付宝宣布搜索板块新增数十万金融类搜索关键词,搜索股票名称、基金名称等关键词,可直接获取股票及理财信息查询、模拟交易、股票分析、研报资讯、理财交流、基金购买等金融服务。

  • 论道汽车效果广告,巨量引擎×金投赏炉边会开启“增效”密钥

    2020 年,汽车行业面临全新变局。存量市场竞争加剧,有效线索成本高企,投放预算进一步压缩,重重压力下,车企将营销关注点转向“效果”这个关键词上。效果广告在汽车行业仍是一个新概念,对比教育、快消等成熟行业还有着非常大的增长空间。“巨量引擎现在做效果广告营销是生意驱动型,希望真正帮助企业生意有成长,效能有增加。在汽车领域,不仅仅是帮助主机厂,也帮助主机厂的渠道、经销商们一起去提升生意能力。”在 6 月 12 日

  • VE视频引擎推出跨平台的视频剪辑解决方案

    据艾瑞、极数等咨询公司发布的中国短视频行业报告显示。国内的短视频用户数已达 8 亿之多,并且用户数还处在一个持续增长的过程中。在如此庞大的市场规模下,必然会产生海量的PGC(专家生产内容),UGC(用户生产内容)视频内容。PGC生产内容的方式需要专业的视频拍摄团队按照剧本拍摄,然后拍摄后的视频交付视频后期团队进行视频剪辑、视频包装。UGC生产内容是方式主要是用户拍摄一段生活场景视频。然后通过视频剪辑的APP去完成二次编

  • 支付宝搜索板块升级:新增数十万金融类搜索关键词

    6月16日消息,支付宝今日宣布,搜索板块迎来重要升级——新增数十万金融类搜索关键词,以往用户获取金融服务需进入到理财页面才可以。据介绍,现在用户上支付宝搜索股票名称、基金名称等关键词,即可一步直达获取股票及理财信息查询、模拟交易、股票分析、研报资讯、理财交流、基金购买等金融服务。据支付宝搜索产品运营负责人袁怀宾透露,目前50%通过支付宝搜索框获取服务的用户,搜索的都是金融类服务。“金融服务是

  • 快手磁力引擎再发力 欲助力商业伙伴获百亿营收

    2019 年 10 月,快手在北京举行2019 Fe+新商业峰会,正式宣布将快手营销平台全面升级为“磁力引擎”,全力冲刺社交新商业。 2018 年是快手商业化元年,快手在首届“Fe+商业峰会”上正式发布了快手营销平台。依托快手的大数据和技术优势,快手生态中的老铁们就像一块巨大的磁铁,让技术和商业产生了化学反应。 时隔一年,快手营销平台正式升级为“磁力引擎”。从字面上看,它是链接万物、具有高黏性和强定力的巨大力场。实际上,这

  • 华为开源数据虚拟化引擎openLooKeng:统一SQL接口

    华为在开源软件上又迈出了坚定一步,正式宣布开源数据虚拟化引擎openLooKeng,开源社区官网(https://openlookeng.io)同步上线。openLooKeng致力于为大数据用户提供极简的数据分析体验,让用户

  • 斑马仓携手数字化改革,成为家装行业贴地起飞的强引擎

    互联网家装发展至今,早已褪去过去的狂热和追捧,进入到客观和理性的阶段。但是不论如何,互联网家装仅仅是一种获客的工具和手段,没有了用户和流量,互联网家装模式必然会遭遇困境,一切都是零。因此,我们必须要思考一种有别于互联网家装的进化新模式。其实,模式很简单,还是回归到家装行业本身,通过解决家装行业本身的痛点和难题,达到供给端的升级和改造,从而找到满足用户新需求的方式和方法。痛点可以总结为:1、准入门槛低,竞争白热化2

  • 参与评论
文明上网理性发言,请遵守新闻评论服务协议