如何java讀取海量中文文本

使用Boyer-Moore算法

科爾沁網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),科爾沁網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為科爾沁上千余家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢，請找那個售后服務(wù)好的科爾沁做網(wǎng)站的公司定做！

或者使用KMP算法

建議使用后者

KMP算法（java）

public class KMP {

/**

* @param args

*/

//計(jì)算模式串的next值

public static void getNext(String strModel, int dNext[]){

int i = 0,j = 1;

dNext[1] = 0;

while(j strModel.length()){

while(i 0 strModel.charAt(i) != strModel.charAt(j))//遞推

i = dNext[i];

i++;

j++;

if(j == strModel.length())

break;

if(strModel.charAt(j) == strModel.charAt(i))//得出next值

dNext[j] = dNext[i] + 1;

else

dNext[j] = i;

}

}

//利用next值查詢子串

public static int getSubString(String strMain, String strModel, int dStart){

int dPos = -1;

int i = dStart;

int j = 1;

int dNext[] = new int[200];

getNext(strModel, dNext);

while(istrMain.length()){

if(strMain.charAt(i) == strModel.charAt(j)){//當(dāng)前字符匹配

if(j == (strModel.length()-1)){//查找成功

dPos = i - j + 1;

break;

}

i++;

j++;

}

else{//當(dāng)前字符不匹配

if(dNext[j] == 0){

i++;

j = 1;

}

else{

j = dNext[j];

}

}

}

return dPos;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

String strModel = " jlsdjflskjdm";

int[] dNext = new int[20];

getNext(strModel, dNext);

for(int i = 1; istrModel.length(); i++)

System.out.print(dNext[i] + " ");

String strMain = " aaaaaaaaaaabbbcdabbksfjlsdjflskjd";

System.out.println();

System.out.println(getSubString(strMain, strModel, 1));

}

}

數(shù)據(jù)結(jié)構(gòu)里實(shí)現(xiàn)KMP算法

KMP算法的C語言實(shí)現(xiàn)2007-12-10 23:33

基本思想：

這種算法是D.E.Knuth 與V.R.Pratt和J.H.Morris同時發(fā)現(xiàn)的，因此人們稱為KMP算法。此算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配操作。

其基本思想是：每當(dāng)匹配過程中出現(xiàn)字符串比較不等時，不需回溯i指針，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右“滑動”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。

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

}

}

java kmp算法中的 kmp 是什么意思？

kmp算法

一種改進(jìn)的字符串匹配算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發(fā)現(xiàn)，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP算法）。

完全掌握KMP算法思想

學(xué)過數(shù)據(jù)結(jié)構(gòu)的人，都對KMP算法印象頗深。尤其是新手，更是難以理解其涵義，搞得一頭霧水。今天我們就來面對它，不將它徹底搞懂，誓不罷休。

如今，大伙基本上都用嚴(yán)蔚敏老師的書，那我就以此來講解KMP算法。(小弟正在備戰(zhàn)考研，為了節(jié)省時間，很多課本上的話我都在此省略了，以后一定補(bǔ)上。)

嚴(yán)老的《數(shù)據(jù)結(jié)構(gòu)》79頁講了基本的匹配方法，這是基礎(chǔ)。先把這個搞懂了。

80頁在講KMP算法的開始先舉了個例子，讓我們對KMP的基本思想有了最初的認(rèn)識。目的在于指出“由此，在整個匹配的過程中，i指針沒有回溯，”。

我們繼續(xù)往下看：

現(xiàn)在討論一般情況。

假設(shè) 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’

把課本上的這一段看完后，繼續(xù)

現(xiàn)在我們假設(shè) 主串第i個字符與模式串的第j(j=m)個字符‘失配’后，主串第i個字符與模式串的第k(kj)個字符繼續(xù)比較

此時，s(i)≠p(j), 有

主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….

|| (相配) || ≠(失配)

匹配串： P(1) ……. p(j-1) p(j)

由此，我們得到關(guān)系式

‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’

由于s(i)≠p(j)，接下來s(i)將與p(k)繼續(xù)比較，則模式串中的前(k-1)個字符的子串必須滿足下列關(guān)系式，并且不可能存在 k’k 滿足下列關(guān)系式：(kj),

‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’

即：

主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….

|| (相配) || || ?(有待比較)

匹配串： P(1) p(2) …… p(k-1) p(k)

現(xiàn)在我們把前面總結(jié)的關(guān)系綜合一下

有：

S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……

|| (相配) || || || ≠(失配)

P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)

|| (相配) || || ?(有待比較)

P(1) p(2) ……. p(k-1) p(k)

由上，我們得到關(guān)系：

‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’

接下來看“反之，若模式串中存在滿足式(4-4)。。。。。。?！边@一段?？赐赀@一段，如果下面的看不懂就不要看了。直接去看那個next函數(shù)的源程序。(偽代碼)

K 是和next有關(guān)系的，不過在最初看的時候，你不要太追究k到底是多少，至于next值是怎么求出來的，我教你怎么學(xué)會。

課本83頁不是有個例子嗎？就是 圖4.6

你照著源程序，看著那個例子慢慢的推出它來?？纯茨阕龅氖遣皇呛驼n本上正確的next值一樣。

然后找?guī)椎谰毩?xí)題好好練練，一定要做熟練了?，F(xiàn)在你的腦子里已經(jīng)有那個next算法的初步思想了，再回去看它是怎么推出來的，如果還看不懂，就繼續(xù)做練習(xí)，做完練習(xí)再看。相信自己?。?！

附：

KMP算法查找串S中含串P的個數(shù)count

#include iostream

#include stdlib.h

#include vector

using namespace std;

inline void NEXT(const string T,vectorint next)

{

//按模式串生成vector,next(T.size())

next[0]=-1;

for(int i=1;iT.size();i++ ){

int j=next[i-1];

while(T!=T[j+1] j=0 )

j=next[j] ; //遞推計(jì)算

if(T==T[j+1])next=j+1;

else next=0; //

}

}

inline string::size_type COUNT_KMP(const string S,

const string T)

{

//利用模式串T的next函數(shù)求T在主串S中的個數(shù)count的KMP算法

//其中T非空，

vectorint next(T.size());

NEXT(T,next);

string::size_type index,count=0;

for(index=0;indexS.size();++index){

int pos=0;

string::size_type iter=index;

while(posT.size() iterS.size()){

if(S[iter]==T[pos]){

++iter;++pos;

}

else{

if(pos==0)++iter;

else pos=next[pos-1]+1;

}

}//while end

if(pos==T.size()(iter-index)==T.size())++count;

} //for end

return count;

}

int main(int argc, char *argv[])

{

string S="abaabcacabaabcacabaabcacabaabcacabaabcac";

string T="ab";

string::size_type count=COUNT_KMP(S,T);

coutcountendl;

system("PAUSE");

return 0;

}

補(bǔ)上個Pascal的KMP算法源碼

PROGRAM Impl_KMP;

USES

CRT;

CONST

MAX_STRLEN = 255;

VAR

next : array [ 1 .. MAX_STRLEN ] of integer;

str_s, str_t : string;

int_i : integer;

Procedure get_nexst( t : string );

Var

j, k : integer;

Begin

j := 1; k := 0;

while j Length(t) do

begin

if ( k = 0 ) or ( t[j] = t[k] ) then

begin

j := j + 1; k := k + 1;

next[j] := k;

end

else k := next[k];

end;

End;

Function index( s : string; t : string ) : integer;

Var

i, j : integer;

Begin

get_next(t);

index := 0;

i := 1; j := 1;

while ( i = Length(s) ) and ( j = Length(t) ) do

begin

if ( j = 0 ) or ( s = t[j] ) then

begin

i := i + 1; j := j + 1;

end

else j := next[j];

if j Length(t) then index := i - Length(t);

end;

End;

BEGIN

ClrScr;

Write(s = );

Readln(str_s);

Write(t = );

Readln(str_t);

int_i := index( str_s, str_t );

if int_i 0 then

begin

Writeln( Found , str_t, in , str_s, at , int_i, . );

end

else

Writeln( Cannot find , str_t, in , str_s, . );

END.

index函數(shù)用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到則返回0

不再贅述算法原理，下面是兩個函數(shù)，已經(jīng)通過測試，可以直接用。

private int[] get_nextval(String t) {

int len = t.length();

int i = 0;

int j = -1;

int next[] = new int[len];

while (i len - 1) {

if (j == -1 || (t.charAt(i) == (t.charAt(j)))) {

i++;

j++;

if (t.charAt(i) != (t.charAt(j))) {

next[i] = (j + 1);

} else {

next[i] = next[j];

}

} else {

j = (next[j] - 1);

}

}

return next;

}

private int index_KMP(String s, String t, int[] next) {

int i = 0;

int j = 0;

while (i s.length() - 1 j t.length() - 1) {

if (j == 0 || (s.charAt(i) == t.charAt(j))) {

i++;

j++;

} else

j = (next[j] - 1);

}

if (j t.length() - 2) {

return (i - t.length() + 1);

} else

return -1;

}

急！kmp算法代碼

LZ的get_next函數(shù)和Index_KMP函數(shù)的代碼是復(fù)制粘貼的吧，那對應(yīng)的是字符數(shù)組下標(biāo)以1開始的代碼，此外也有少量錯誤，修改后的正確代碼如下。另外，LZ的代碼中找不到next數(shù)組的定義，并且元素類型應(yīng)該int才對頭，這點(diǎn)需要在適當(dāng)位置補(bǔ)充。

void?get_next(HString?T,?int?*next)

{

int?i=0,?j=-1;

next[0]?=?-1;?????/////?關(guān)鍵

while(i??T.length-1)?

{

if?(j==-1?||?T.ch[i]==T.ch[j])

{

++i;

++j;

//////////////?改進(jìn)版?KMP?增加此判斷?/////////

if?(T.ch[i]==T.ch[j])

next[i]==next[j];

else

////////////////////////////////////////////

next[i]==j;

}

else

j?=?next[j];

}

}

int?Index_KMP(HString?S,?HString?T,?int?pos)

{

int?i=pos,?j=0;

get_next(T,?next);

while(iS.length??jT.length)

{

if(j==-1?||?S.ch[i]==T.ch[j])

{

++i;

++j;

}

else

j?=?next[j];

}

if(j=T.length)

return?i-T.length;??//?返回的匹配位置從下標(biāo)?0?起算

else

return?-1;??????//?返回?-1?表示沒有找到

}