您的位置:

kmp算法及python实现的简单介绍

本文目录一览:

KMP算法详细代码

KMP.java

源代码为:

package algorithm.kmp;

/**

* KMP算法的Java实现例子与测试、分析

* @author 崔卫兵

* @date 2009-3-25

*/

public class KMP {

/**

* 对子串加以预处理,从而找到匹配失败时子串回退的位置

* 找到匹配失败时的最合适的回退位置,而不是回退到子串的第一个字符,即可提高查找的效率

* 因此为了找到这个合适的位置,先对子串预处理,从而得到一个回退位置的数组

* @param B,待查找子串的char数组

* @return

*/

public static int[] preProcess(char [] B) {

int size = B.length;

int[] P = new int[size];

P[0]=0;

int j=0;

//每循环一次,就会找到一个回退位置

for(int i=1;isize;i++){

//当找到第一个匹配的字符时,即j0时才会执行这个循环

//或者说p2中的j++会在p1之前执行(限于第一次执行的条件下)

//p1

while(j0 B[j]!=B[i]){

j=P[j];

}

//p2,由此可以看出,只有当子串中含有重复字符时,回退的位置才会被优化

if(B[j]==B[i]){

j++;

}

//找到一个回退位置j,把其放入P[i]中

P[i]=j;

}

return P;

}

/**

* KMP实现

* @param parStr

* @param subStr

* @return

*/

public static void kmp(String parStr, String subStr) {

int subSize = subStr.length();

int parSize = parStr.length();

char[] B = subStr.toCharArray();

char[] A = parStr.toCharArray();

int[] P = preProcess(B);

int j=0;

int k =0;

for(int i=0;iparSize;i++){

//当找到第一个匹配的字符时,即j0时才会执行这个循环

//或者说p2中的j++会在p1之前执行(限于第一次执行的条件下)

//p1

while(j0 B[j]!=A[i]){

//找到合适的回退位置

j=P[j-1];

}

//p2 找到一个匹配的字符

if(B[j]==A[i]){

j++;

}

//输出匹配结果,并且让比较继续下去

if(j==subSize){

j=P[j-1];

k++;

System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);

}

}

System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);

}

public static void main(String[] args) {

//回退位置数组为P[0, 0, 0, 0, 0, 0]

kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");

//回退位置数组为P[0, 0, 1, 2, 3, 4]

kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");

//回退位置数组为P[0, 0, 0]

kmp("测试汉字的匹配,崔卫兵。这个会匹配1次","崔卫兵");

//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]

kmp("这个会匹配0次","it1it1it1");

}

}

kmeans算法用Python怎么实现

1、从Kmeans说起

Kmeans是一个非常基础的聚类算法,使用了迭代的思想,关于其原理这里不说了。下面说一下如何在matlab中使用kmeans算法。

创建7个二维的数据点:

复制代码 代码如下:

x=[randn(3,2)*.4;randn(4,2)*.5+ones(4,1)*[4 4]];

使用kmeans函数:

复制代码 代码如下:

class = kmeans(x, 2);

x是数据点,x的每一行代表一个数据;2指定要有2个中心点,也就是聚类结果要有2个簇。 class将是一个具有70个元素的列向量,这些元素依次对应70个数据点,元素值代表着其对应的数据点所处的分类号。某次运行后,class的值是:

复制代码 代码如下:

2

2

2

1

1

1

1

这说明x的前三个数据点属于簇2,而后四个数据点属于簇1。 kmeans函数也可以像下面这样使用:

复制代码 代码如下:

[class, C, sumd, D] = kmeans(x, 2)

class =

2

2

2

1

1

1

1

C =

4.0629 4.0845

-0.1341 0.1201

sumd =

1.2017

0.2939

D =

34.3727 0.0184

29.5644 0.1858

36.3511 0.0898

0.1247 37.4801

0.7537 24.0659

0.1979 36.7666

0.1256 36.2149

class依旧代表着每个数据点的分类;C包含最终的中心点,一行代表一个中心点;sumd代表着每个中心点与所属簇内各个数据点的距离之和;D的

每一行也对应一个数据点,行中的数值依次是该数据点与各个中心点之间的距离,Kmeans默认使用的距离是欧几里得距离(参考资料[3])的平方值。

kmeans函数使用的距离,也可以是曼哈顿距离(L1-距离),以及其他类型的距离,可以通过添加参数指定。

kmeans有几个缺点(这在很多资料上都有说明):

1、最终簇的类别数目(即中心点或者说种子点的数目)k并不一定能事先知道,所以如何选一个合适的k的值是一个问题。

2、最开始的种子点的选择的好坏会影响到聚类结果。

3、对噪声和离群点敏感。

4、等等。

2、kmeans++算法的基本思路

kmeans++算法的主要工作体现在种子点的选择上,基本原则是使得各个种子点之间的距离尽可能的大,但是又得排除噪声的影响。 以下为基本思路:

1、从输入的数据点集合(要求有k个聚类)中随机选择一个点作为第一个聚类中心

2、对于数据集中的每一个点x,计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)

3、选择一个新的数据点作为新的聚类中心,选择的原则是:D(x)较大的点,被选取作为聚类中心的概率较大

4、重复2和3直到k个聚类中心被选出来

5、利用这k个初始的聚类中心来运行标准的k-means算法

假定数据点集合X有n个数据点,依次用X(1)、X(2)、……、X(n)表示,那么,在第2步中依次计算每个数据点与最近的种子点(聚类中心)的

距离,依次得到D(1)、D(2)、……、D(n)构成的集合D。在D中,为了避免噪声,不能直接选取值最大的元素,应该选择值较大的元素,然后将其对应

的数据点作为种子点。

如何选择值较大的元素呢,下面是一种思路(暂未找到最初的来源,在资料[2]等地方均有提及,笔者换了一种让自己更好理解的说法):

把集合D中的每个元素D(x)想象为一根线L(x),线的长度就是元素的值。将这些线依次按照L(1)、L(2)、……、L(n)的顺序连接起来,组成长

线L。L(1)、L(2)、……、L(n)称为L的子线。根据概率的相关知识,如果我们在L上随机选择一个点,那么这个点所在的子线很有可能是比较长的子

线,而这个子线对应的数据点就可以作为种子点。下文中kmeans++的两种实现均是这个原理。

3、python版本的kmeans++

在 中能找到多种编程语言版本的Kmeans++实现。下面的内容是基于python的实现(中文注释是笔者添加的):

复制代码 代码如下:

from math import pi, sin, cos

from collections import namedtuple

from random import random, choice

from copy import copy

try:

import psyco

psyco.full()

except ImportError:

pass

FLOAT_MAX = 1e100

class Point:

__slots__ = ["x", "y", "group"]

def __init__(self, x=0.0, y=0.0, group=0):

self.x, self.y, self.group = x, y, group

def generate_points(npoints, radius):

points = [Point() for _ in xrange(npoints)]

# note: this is not a uniform 2-d distribution

for p in points:

r = random() * radius

ang = random() * 2 * pi

p.x = r * cos(ang)

p.y = r * sin(ang)

return points

def nearest_cluster_center(point, cluster_centers):

"""Distance and index of the closest cluster center"""

def sqr_distance_2D(a, b):

return (a.x - b.x) ** 2 + (a.y - b.y) ** 2

min_index = point.group

min_dist = FLOAT_MAX

for i, cc in enumerate(cluster_centers):

d = sqr_distance_2D(cc, point)

if min_dist d:

min_dist = d

min_index = i

return (min_index, min_dist)

'''

points是数据点,nclusters是给定的簇类数目

cluster_centers包含初始化的nclusters个中心点,开始都是对象-(0,0,0)

'''

def kpp(points, cluster_centers):

cluster_centers[0] = copy(choice(points)) #随机选取第一个中心点

d = [0.0 for _ in xrange(len(points))] #列表,长度为len(points),保存每个点离最近的中心点的距离

for i in xrange(1, len(cluster_centers)): # i=1...len(c_c)-1

sum = 0

for j, p in enumerate(points):

d[j] = nearest_cluster_center(p, cluster_centers[:i])[1] #第j个数据点p与各个中心点距离的最小值

sum += d[j]

sum *= random()

for j, di in enumerate(d):

sum -= di

if sum 0:

continue

cluster_centers[i] = copy(points[j])

break

for p in points:

p.group = nearest_cluster_center(p, cluster_centers)[0]

'''

points是数据点,nclusters是给定的簇类数目

'''

def lloyd(points, nclusters):

cluster_centers = [Point() for _ in xrange(nclusters)] #根据指定的中心点个数,初始化中心点,均为(0,0,0)

# call k++ init

kpp(points, cluster_centers) #选择初始种子点

# 下面是kmeans

lenpts10 = len(points) 10

changed = 0

while True:

# group element for centroids are used as counters

for cc in cluster_centers:

cc.x = 0

cc.y = 0

cc.group = 0

for p in points:

cluster_centers[p.group].group += 1 #与该种子点在同一簇的数据点的个数

cluster_centers[p.group].x += p.x

cluster_centers[p.group].y += p.y

for cc in cluster_centers: #生成新的中心点

cc.x /= cc.group

cc.y /= cc.group

# find closest centroid of each PointPtr

changed = 0 #记录所属簇发生变化的数据点的个数

for p in points:

min_i = nearest_cluster_center(p, cluster_centers)[0]

if min_i != p.group:

changed += 1

p.group = min_i

# stop when 99.9% of points are good

if changed = lenpts10:

break

for i, cc in enumerate(cluster_centers):

cc.group = i

return cluster_centers

def print_eps(points, cluster_centers, W=400, H=400):

Color = namedtuple("Color", "r g b");

colors = []

for i in xrange(len(cluster_centers)):

colors.append(Color((3 * (i + 1) % 11) / 11.0,

(7 * i % 11) / 11.0,

(9 * i % 11) / 11.0))

max_x = max_y = -FLOAT_MAX

min_x = min_y = FLOAT_MAX

for p in points:

if max_x p.x: max_x = p.x

if min_x p.x: min_x = p.x

if max_y p.y: max_y = p.y

if min_y p.y: min_y = p.y

scale = min(W / (max_x - min_x),

H / (max_y - min_y))

cx = (max_x + min_x) / 2

cy = (max_y + min_y) / 2

print "%%!PS-Adobe-3.0\n%%%%BoundingBox: -5 -5 %d %d" % (W + 10, H + 10)

print ("/l {rlineto} def /m {rmoveto} def\n" +

"/c { .25 sub exch .25 sub exch .5 0 360 arc fill } def\n" +

"/s { moveto -2 0 m 2 2 l 2 -2 l -2 -2 l closepath " +

" gsave 1 setgray fill grestore gsave 3 setlinewidth" +

" 1 setgray stroke grestore 0 setgray stroke }def")

for i, cc in enumerate(cluster_centers):

print ("%g %g %g setrgbcolor" %

(colors[i].r, colors[i].g, colors[i].b))

for p in points:

if p.group != i:

continue

print ("%.3f %.3f c" % ((p.x - cx) * scale + W / 2,

(p.y - cy) * scale + H / 2))

print ("\n0 setgray %g %g s" % ((cc.x - cx) * scale + W / 2,

(cc.y - cy) * scale + H / 2))

print "\n%%%%EOF"

def main():

npoints = 30000

k = 7 # # clusters

points = generate_points(npoints, 10)

cluster_centers = lloyd(points, k)

print_eps(points, cluster_centers)

main()

上述代码实现的算法是针对二维数据的,所以Point对象有三个属性,分别是在x轴上的值、在y轴上的值、以及所属的簇的标识。函数lloyd是

kmeans++算法的整体实现,其先是通过kpp函数选取合适的种子点,然后对数据集实行kmeans算法进行聚类。kpp函数的实现完全符合上述

kmeans++的基本思路的2、3、4步。

python 怎么用kmp算法实现两个字符串的匹配问题

也许可以试试抛开正则,使用split:

#!/bin/env python

fileH = open("test")

listSec1 = []

ret = []

fileContent = fileH.read()

for s in fileContent.split("test"):

listSec1.append(s)

for s in listSec1[1].split("O_4 #1"):

ret.append(s)

print ret[0]

fileH.close()

KMP模式匹配算法是什么?

KMP模式匹配算法是一种改进算法,是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的,因此人们称它为“克努特-莫里斯-普拉特操作”,简称KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于:每当一趟匹配过程出现字符不相等时,主串指针i不用回溯,而是利用已经得到的“部分匹配”结果,将模式串的指针j向右“滑动”尽可能远的一段距离后,继续进行比较。

1.KMP模式匹配算法分析回顾图4-5所示的匹配过程示例,在第三趟匹配中,当i=7、j=5字符比较不等时,又从i=4、j=1重新开始比较。然而,经仔细观察发现,i=4和j=1、i=5和j=1以及i=6和j=1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出,主串中的第4、5和6个字符必然是b、c和a(即模式串第2、第2和第4个字符)。因为模式中的第一个字符是a,因此它无须再和这三个字符进行比较,而仅需将模式向右滑动2个字符的位置进行i=7、j=2时的字符比较即可。同理,在第一趟匹配中出现字符不等时,仅需将模式串向右移动两个字符的位置继续进行i=2、j=1时的字符比较。由此,在整个匹配过程中,i指针没有回溯,如图1所示。

图1改进算法的模式匹配过程示意

数据结构里实现KMP算法

KMP算法的C语言实现2007-12-10 23:33

基本思想:

这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的,因此人们称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。

其基本思想是:每当匹配过程中出现字符串比较不等时,不需回溯i指针,而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。

#include stdio.h

#include string.h

int index_KMP(char *s,char *t,int pos);

void get_next(char *t,int *);

char s[10]="abcacbcba";

char t[4]="bca";

int next[4];

int pos=0;

int main()

{

int n;

get_next(t,next);

n=index_KMP(s,t,pos);

printf("%d",n);

return 0;

}

int index_KMP(char *s,char *t,int pos)

{

int i=pos,j=1;

while (i=(int)strlen(s)j=(int)strlen(t))

{

if (j==0||s[i]==t[j-1])

{

i++;

j++;

}

else j=next[j];

}

if (j(int)strlen(t))

return i-strlen(t)+1;

else

return 0;

}

void get_next(char *t,int *next)

{

int i=1,j=0;

next[0]=next[1]=0;

while (i(int)strlen(t))

{

if (j==0||t[i]==t[j])

{

i++;

j++;

next[i]=j;

}

else j=next[j];

}

}