kmp演算法及python實現的簡單介紹

本文目錄一覽：

• 1、KMP演算法詳細代碼
• 2、kmeans演算法用Python怎麼實現
• 3、python 怎麼用kmp演算法實現兩個字元串的匹配問題
• 4、KMP模式匹配演算法是什麼？
• 5、數據結構里實現KMP演算法

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];

}

}