产品经理需要了解的搜索算法

《产品经理需要了解的搜索算法》由会员分享，可在线阅读，更多相关《产品经理需要了解的搜索算法（7页珍藏版）》请在金锄头文库上搜索。

1、产经产经品理需要了解的搜索算法品理需要了解的搜索算法 1简倒排索引介 倒排索引（英文：InvertedIndex种检统种），是一索引方法，常被用于全文索系中的一 单词结文档映射构。 现绝进这实际应代搜索引擎大多数的索引都是基于倒排索引来行构建的，源于在用当中， 户查时输关键户记用在使用搜索引擎找信息往往只入信息中的某个属性字，如一些用不得 输词查输节查该节歌名，会入歌来找歌名；入某个目内容片段来找目等等。 对为满户顺应时获趋势聪开发面海量的信息数据，足用需求，信息代快速取信息的，明的 们进开发时对这进发者在行搜索引擎些信息数据行逆向运算，研了“关键词文档”形式 种结实现过对进户的一映射构，了通

2、了物品属性信息物品行映射，可以帮助用快速定位到 标获难种维目信息，极大地降低了信息取度。倒排索引又叫反向索引，它是一逆向思运算， 现检领种结是代信息索域里面最有效的一索引构。 2倒排索引&FAQ 户请结许对检统过产从用求到果返回，多朋友会倒排索引在索系中的工作程生好奇，本小 节规认识问题就倒排索引的一些常，有如下： Q1为么：何索引？倒排索引又是什？ 为查过标预创种储结索引，是了加快信息找程，基于目信息内容先建的一存构。例如：一 书录论读读时开书本，没有目，理上也是可的，只是当你合上当前在的内容，下次再翻本 查较费时间页录们书去找，就比耗了。如果增加几目，我可以快速地了解本的大体内容分 每节页

3、这样们查询书布，以及一个章面位置的分布情况，我内容的效率自然就会提高。的 录书种简单目，就是本内容一索引。 术种关键值进图倒排索引，是索引技中的一，它是基于信息主体的属性行构建的。如下1： 图1图倒排索引概念示例 设检统假索系中只有一个商品衣服 A该结产，基于商品构建其倒排索引构之后，会生 图结这样户过上右表中的索引构，用可以通搜“AAA”，“蓝色”，“M码”，“猴子”，均可找到 该检扩检围商品，加快了索速度，大了索范。 Q2户查询请时发么：当接受到用求，倒排索引中生了什？ 户查询请时进进检时结过一般地，当接受到用求，入到倒排索引行索，在返回果的程中， 步骤主要有以下几个： Step1词统对户

4、请：在分系用求等原始 Query进产对应行分析，生的 terms； Step2：terms词项查对应在倒排索引中的列表中找的 terms结的果列表； Step3对结进计态关：果列表数据行微运算，如：算文档静分，文档相性等； Step4对进综结给户：基于上述运算得分文档行合排序，最后返回果用。 该过较为简洁检过实产环为业务环杂上述程是的一个索程。事上，在生境中因境的繁，会 设计变复杂过图绍使得索引的模式得且繁多。前文主要通概念来介倒排索引的架构体系， 检统拥较为稳处产环每处细一个成熟的索系往往有一套定的算法体系，用于理生境中的一 节术步骤涉关技需求。上述中及了大量相的数据储术查处存技、找算法、排

5、序算法、文本 术理技甚至 I/O术技等等。 3术倒排索引技剖析 关步骤术层对构建倒排索引是搜索引擎里面至重要的一个，从技面去分析，于构造一个倒 为排索引，主要分两部分： Doc2term词项构造； 记录倒排表的构建。 3.1term词项构造 词项过步骤词项构造是在构建索引程中必不可或缺的一个，构造效果的好坏往往会直接影 户验结该过词统项响到用的搜索体，以及搜索果的召回。程主要是利用分系将文档中的各 较强词汇户查图属性的文本信息拆分成一些表意且重要的，便于用找，如下2： 图2词项图构造概念 词项过词统对进处时涉问题在构造的程中，利用分系文本行理往往及到很多方面的，而且 对语种处绍处时涉问题于不同

6、，会有不同的理机制。下面主要介在理文本及到的几个： （1词）文本条化 语组项术务一段文本信息，它本身是一个由言成的字符串系列，本技点的主要任是将一段 连续语关对语处的文本序列信息拆分成多个子序列。它与言本身相，面不同的言，理文本 样对语义紧实际应的方式往往会不一。于中文，由于其言多歧且表意凑的特性，在用中， 一般需要借助 NLP关术对进标对应词的相技内容行特征抽取，甚至人工注等，生成的典， 词词进词较词随后再基于典利用分器行分，才能看到好的文本条效果。 对为单词间而于英文，普遍的英文句子，段落内容，它会以空格符作之的分隔符，所以一 对进经般情况下，以空格符英文内容行拆分，已可以取得比较过好的效

7、果，不英文中也会 带存在一些特殊模式，如上撇号的格式“Teachersoffice”连，字符格式“English speaking”,进对应处单词也需要行的理，把提取出来。 （2词过滤）停用 词现频较值词为停用是指在文档列表中出的数高且价不大的。以英文例，在英文文档中出 现较词次数多的停用如：”is”、”the”、”I”、“and”、”me”这类词语现等等；一在往往出在所 类词语为有文档中，若以此term进则产行索引构建，会生多个全量文档索引列表。停用 词过滤赖实际场的使用往往依于使用关键查询较为频场电景，字使用得繁的景如某一个商 词显为对品牌的垂直型搜索引擎，一个合适的停用表得尤重要；而于

8、Web 搜索引擎如百 度、Google该类查询场较较强词等，型的搜索引擎面向的景多，通用性，往往不需要停用 过滤。 （3词归）条一化 转换基于上述两点，将文档内容成一个或多个 term查询时户后，在，最理想的情况是用 输关键刚入的字好与 term实际时户输完全匹配，上，很多候用入的 query词间与条之往 户们还往不会完全匹配，而用是希望 query词进户查询能与条行匹配，比如用在“color”时， 户用肯定也希望关能看到于“colour”结词归务的返回果。条一化的任就是将一些看起来不 词为类单词完全一致的条划分一个等价，比如英式colour单词和美式color归为类一、 Airconditi

9、oner 和 airconditioner归为类这样户查询时对类一等等；，用在，只要等价中 单词进类单词的任意行搜索，都会返回包含等价中的任意一个的文档。 （4词词还）干提取、形原 这词规种扩检围词是条范化的两重要方式，用于展索范。干提取的主要思想是“缩减”，将 词转为词条化干，如：将“beaches”处理成“beach”,将“bananas”处理成“banana”词还等；形 原的主要思想是“转换”，如：将“doing”、“done”、“did”转化成原型“do”，将“given”、“gave” 转化成原型“give”词实现规则对词缀进缩词等；干提取的方法一般是基于条后行减，至于 还实现词进词

10、变结词归术对形原，其方法需要典来行形化的映射；基于在此合条一化技， 扩检围产展索范会生一定的正向作用。 3.2记录倒排表的构建 记录过规词项倒排表的构建程面向的是海量的文档数据集合，在大小模上它比集合要大得 多，无法完全存放在内存当中，需要写盘记录时们为入磁。因此，在构建倒排表我有必要 虑内存的使用作考。 图3图倒排索引概念 记录在无法全内存的情况下，倒排表的主要构建思想是“分割”处逻辑，亦即基于一定的理 对进处对业务记录全量文档集合行等份的批量理。于不同的需求，构建倒排表的方法往往 样会不一。基本的构建方法如下： S1:过处转为通一系列的理将文档集合化“词项ID文档 ID”对； S2:对词项

11、ID、文档 ID进词项对行排序，将具有相同文档 ID归该词项对应并到所的倒排 记录图表中，效果如3 所示； S3:步骤产盘间将上述生的倒排索引写入磁，生成中文件； S4:间终将上述所有的中文件合并成最的倒排索引。 业务应场发记录单扫扫从用景的角度出，倒排表的构建方法主要有：遍描和多遍描；从工 发记录动态程角度出，倒排表的构建方法主要有：分布式构建和构建。 3.2.1单扫遍描构建 顾义名思，单扫仅对进历遍描指的是文档集合行一次遍，即可完成倒排索引的构建。由于 开销问题进转换内存，会将全量文档集行分割，成几个内存大小相同的文档集合，然后依 执该简单次行前文中提及到的构建方法。方法能快速构建一个可行

12、的倒排索引户，帮助用 过关键标通字匹配快速找到目文档。 3.2.2扫多遍描构建 扫时获关关词项多遍描主要用于构建索引取于文档的更多相信息，如一些TFIDF标指、 词频关记录为进扩业、文档内容系等，以丰富倒排表的内容，搜索引擎行功能充；在工流 线单扫查询类够显经满户水上，遍描构建索引由于其型的丰富度不，然已不能足广大用的 户关键查询语查询查询筛选需求了。搜索用的需求并不止于字，像短、模糊、精确、模糊 筛选统计这们时获、排序、聚合等等需求。意味着我在构建倒排列表要尽可能取文档的更 查询时关术多信息，便于的微运算、重排序、相性分析等技需求。 3.2.3分布式构建 对于一些大型搜索引擎如 Web单搜索

13、引擎，台机器已无法支撑其索引构建，需要多台机 组对进处进每器成集群其行分布式理，将构建成的倒排索引行分割，分布在多台机器上， 结户发请时应户台机器各自形成独立的索引构，当用出求，会有多台机器响，并且根据用 结进查询关结结进的搜索需求在各自的索引构行，返回相果，再将所有果在内存中行集中 处处过优结给户实现过师们钟理，最后把理的最果返回用。在具体的程中，工程往往更情 规计于一些通用的面向大模机器算的分布式架构如 Hadoop 中的 MapReduce、Java 中的 Fork/join软开发架构等，极大地提高了件效率。 3.2.4动态构建 该变这对进时对进方法中的文档集合是化的，要求在文档集行索引

14、构建也要文档的更新行 应问题见电领发自适。此常于商域里，如商品的上下架、商品内容的更新等，都会引索引 动态问题们该类问题实的更新。于此，我常采取一些策略型方法来解决型的，提高索引的 时见种性。常的策略如下两： 对进周期性文档行全量重建索引； 辅储维护辅基于主索引的前提下，构建助索引，用于存新文档，于内存中，当助索引达到 时盘进一定的内存占用，写入磁与主索引行合并。 策略 1简单对级较是最直接、且有效的索引更新策略，于数量说处简单大的搜索引擎来理 动态计复杂难维护发严便捷，由于索引算的性，使用其它策略会使得索引，甚至引重的性 问题倾过这涉热换能。所以大型搜索引擎往往更向于周期性重建索引，不会及到

15、索引切的 问题经产续这对热换时，大量的文档常会生持性的文档更新情况，于索引切会造成一定的 难处导丢户查问题困，理不好会致数据失，用不到新文档等。 策略 2进辅时较储开销较这中在行主索引合并会遇到比大的存，由于文档量大，意味着在 进时涉读该过处该行合并操作会及到大量倒排文件的写操作，要想将程高效化，目前能理 问题统该产环的文件系极其稀少，所以策略在生境中往往可用性并不高。 4总结 实际产环业务杂术阐术复在生境中，由于的繁，倒排索引的技体系会比本文所述的技点要 杂讲户为应得多。本文主要解了倒排索引的作用、索引构建方法、用行分析以及索引的用 场发绍现术景，从整体出，向大家介代倒排索引大致的技体系，帮助大家了解倒排索引的 阐术概念，了解搜索引擎。可能本文述的技为点、架构体系会因笔者个人的理解偏差而存 在一些不足或欠缺丰富。