一、引言

假设我们想要开发一个邮件系统,那么如何实现垃圾邮件的过滤呢。

垃圾邮件过滤

最简单的办法就是把确定为是垃圾邮件的地址都保存起来,存入黑名单中。当用户接收到黑名单地址的邮件时,直接将邮件归类到垃圾箱中。

垃圾邮件的地址数量可能是巨大的,因此除了被存储在数据库中,程序实际使用的时候一定是需要借助缓存的。不论是使用本地缓存还是内存缓存,当数据量达到一定数量级时,都是不太合适的。

今日头条的走红带动了“个性化推荐”的概念,自此之后,内容型的产品,个性化算法就逐渐从卖点变为标配。伴随着“机器学习”,“大数据”之类的热词和概念,产品的档次瞬间提高了很多。而各种推荐算法绝不仅仅是研发自己的任务,作为产品经理,必须深入到算法内部,参与算法的设计,以及结合内容对算法不断“调教”,才能让产品的推荐算法不断完善,最终与自己的内容双剑合璧。

本文以新闻产品为例,结合了我之前产品从零积累用户的经验,整理了作为PM需要了解的基本算法知识和实操。

一、背景

给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题

Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。

在继续下面的内容之前,有必要在这里介绍下两个概念:真前缀真后缀

一、算法功能

给定一个出发点(单源点)和一个有向网G=(V, E), 求出源点到其它各顶点之间的最短路径。

二、算法思想

(1)把图中顶点集合分成两组,第一组为集合S,存放已求出其最短路径的顶点,第二组为尚未确定最短路径的顶点集合是V-S(令W=V-S),其中V为网中所有顶点集合。

(2)按最短路径长度递增的顺序逐个把W中的顶点加到S中,直到S中包含全部顶点,而W为空。

(3)在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到W中任何顶点的最短路径长度。

(4)此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,W中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

9.1 基本概念

(1)列表
同一类型的数据元素(或记录)构成的集合,可利用任意数据结构实现。

(2)关键字
数据元素的某个数据项的值,用它可以标识列表中的一个或一组数据元素。

如果一个关键字可以唯一标识列表中的一个数据元素,则称其为主关键字,否则为次关键字。 当数据元素仅有一个数据项时,数据元素的值就是关键字。

8.1 基本概念

有n个记录的序列{R1,R2,…,Rn},其相应关键字的序列是{K1,K2, …,Kn },相应的下标序列为1,2,…,n

通过排序,要求找出当前下标序列1,2,…, n的一种排列p1,p2, …,pn,使得相应关键字满足如下的**非递减(或非递增)**关系,即:Kp1≤ Kp2≤…≤ Kpn ,这样就得到一个按关键字有序的记录序列:{Rp1,Rp2, …, Rpn}