匹配檢索演算法

❶ 匹配演算法依據是什麼

其主要原理都是切分出單字串，然後和詞庫進行比對，如果是一個詞就記錄下來， 否則通過增加或者減少一個單字，繼續比較，一直還剩下一個單字則終止，如果該單字串無法切分，則作為未登錄處理。

❷ 通訊錄拼音搜索模糊匹配的演算法問題

我用java寫了個簡單的，你可以多測試下：

publicstaticvoidmain(String[]args){

		String[]name={"wang","hai","bao"};

		String[]tests={"whb","WaHB","wangHB","HB","wh","whbo","whba"};

		for(Stringstring:tests){
			System.out.println(string+":"+match(name,string));
		}

	}

	publicstaticbooleanmatch(String[]source,Stringinput){

		if(source==null||source.length==0||input==null||input.length()==0){
			returnfalse;
		}

		Stringtemp;

		//統一轉小寫
		input=input.toLowerCase();

		for(inti=0;i<source.length;i++){

			temp=source[i].toLowerCase();

			if(temp==null||temp.length()==0){
				returnfalse;
			}
			
						//最後一步特殊處理
			if(i==source.length-1){
				if(temp.startsWith(input)){
					returntrue;
				}
			}

			//輸入的字元完全匹配到
			if(input.startsWith(temp)){
				//匹配到後生成新的字元串
				input=input.substring(0,input.indexOf(temp));
				//System.out.println("temp:"+temp+"	匹配到後input："+input);
			}

			//首字母匹配到
			elseif(temp.startsWith(input.substring(0,1))){

				input=input.substring(1);
				//System.out.println("temp:"+temp+"	匹配到後input："+input);
			}else{
				returnfalse;
			}

			//表示匹配結束
			if(input.length()==0){
				returntrue;
			}

		}

		returnfalse;
	}

❸ 串模式匹配演算法

# include <string.h> # include <stdio.h> # include <stdlib.h> # define OK 1 # define ERROR 0 typedef int Status; //串的定長順序存儲結構 # define MAX_STR_LEN 40 typedef char SString[MAX_STR_LEN + 1];//0號單元存放串的長度 Status StrAssign(SString T,char * chars)//生成一個其值等於chars的串T { int i; if (strlen(chars) > MAX_STR_LEN) { return ERROR; } else { T[0] = strlen(chars); for (i=1; i<=T[0]; ++i) { T[i] = * (chars + i - 1); } return OK; } } //返回串S的元素的個數 int StrLength(SString S) { return S[0]; } //用Sub返回串S的自第pos個字元起長度為len的子串 Status SubString(SString Sub,SString S,int pos,int len) { int i; if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1) { return ERROR; } for (i=1; i<=len; ++i) { Sub[i] = S[pos+i-1]; } Sub[0] = len; return OK; } //輸出字元串T void StrPrint(SString T) { int i; for (i=1; i<=T[0]; ++i) { printf("%c ",T[i]); } printf("\n"); } //求模式串T的next函數值並存入數組next void get_next(SString T,int next[]) { int i = 1,j = 0; next[1] = 0; while (i < T[0]) { if (j==0 || T[i]==T[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } } //求模式串T的next函數修正值並存入數組nextval void get_nextval(SString T,int nextval[]) { int i = 1,j = 0; nextval[1] = 0; while (i < T[0]) { if (j==0 || T[i]==T[j]) { ++i; ++j; if (T[i] != T[j]) { nextval[i] = j; } else { nextval[i] = nextval[j]; } } else { j = nextval[j]; } } } //利用模式串T的next函數求T在主串S中第pos字元之後的位置的KMP演算法 //1=<pos=<StrLength(S) int Index_KMP(SString S,SString T,int pos,int next[]) { int i = pos,j = 1; while (i<=S[0] && j<=T[0]) { if (j==0 || S[i]==T[j]) { ++i; ++j; } else { j = next[j]; } } if (j > T[0]) { return i - T[0]; } else { return 0; } } int main(void) { int i,* p; SString s1,s2; StrAssign(s1,"aaabaaaab"); printf("主串為："); StrPrint(s1); StrAssign(s2,"aaaab"); printf("子串為："); StrPrint(s2); p = (int *)malloc((StrLength(s2) + 1) * sizeof(int)); get_next(s2,p); printf("子串的next的數組為："); for (i=1; i<=StrLength(s2); ++i) { printf("%d ",* (p+i)); } printf("\n"); i = Index_KMP(s1,s2,1,p); if (i) { printf("主串和子串在第%d個字元處首次匹配\n",i); } else { printf("主串和子串匹配不成功\n"); } get_nextval(s2,p); printf("子串的nextval數組為："); for (i=1; i<=StrLength(s2); ++i) { printf("%d ",* (p+i)); } printf("\n"); printf("主串和子串在第%d個字元處首次匹配\n",Index_KMP(s1,s2,1,p)); printf("求串s1的從第5個字元起長度為5的子串s2:\n"); SubString(s2,s1,5,5); printf("串s2為:"); StrPrint(s2); return 0; } /* 在vc++6.0中的輸出結果： ------------------------ 主串為：a a a b a a a a b 子串為：a a a a b 子串的next的數組為：0 1 2 3 4 主串和子串在第5個字元處首次匹配 子串的nextval數組為：0 0 0 0 4 主串和子串在第5個字元處首次匹配 求串s1的從第5個字元起長度為5的子串s2: 串s2為:a a a a b Press any key to continue ------------------------------ */

❹ 字元串匹配的傳統演算法

傳統的匹配演算法
串匹配演算法雖然發展了幾十年，然而非常實用的演算法是近年才出現。串匹配問題的研究存在理論研究和實際應用的脫節。那些專門從事演算法研究的學者關心的只是理論上看起來很美妙的演算法——具有很好的時間復雜度。而開發人員只追求實際應用中盡可能快的演算法。兩者之間從不注意對方在干什麼。將理論研究和實際應用結合的演算法(如BNDM演算法)只是近年才出現。在實際應用中常常很難找到適合需求的演算法——這樣的演算法實際上是存在的，但是只有資深專家才比較了解。考慮如下情況，一位軟體開發人員，或者一位計算生物學家，或者一位研究人員，又或者一位學生，對字元串匹配領域並沒有深入了解，可是現在需要處理一個文本搜索問題。那些汗牛充棟的書籍使得閱讀者淹沒在各種匹配演算法的海洋中，卻沒有足夠的知識選擇最適用的演算法。最後，常常導致這樣的局面：選擇一種最簡單的演算法加以實現。這往往導致很差的性能，從而影響整個開發系統的質量。更糟糕的是，選擇了一個理論上看起來很漂亮的演算法，並且花費了大量精力去實現。結果，卻發現實際效果和一個簡單演算法差不多，甚至還不如簡單演算法。因此，應該選用一種「實用」演算法，即在實際應用中性能較好，並且一個普通程序員能在幾小時內完成演算法的實現代碼。另外，在字元串匹配研究領域中，一個人所共知的事實是「演算法的思想越簡單，實際應用的效果越好」。
傳統的串匹配演算法可以概括為前綴搜索、後綴搜索、子串搜索。代表演算法有KMP，Shift-And，Shift-Or，BM，Horspool，BNDM，BOM等。所用到的技術包括滑動窗口、位並行、自動機、後綴樹等。

❺ bm是什麼意思

BM是一種匹配演算法。

BM演算法被認為是亞線性串匹配演算法，它在最壞情況下找到模式所有出現的時間復雜度為O(mn)，在最好情況下執行匹配找到模式所有出現的時間復雜度為O(n/m)。

BM演算法主要思想描述如下：

模式字元串的匹配順序是從右向左:

1、首先將P和T對齊，即p和t對齊；

2、然後匹配從模式字元串P的最右端字元開始，即判斷p[m]和t[m]是否匹配：

如果匹配成功，則向左移動判斷p[m-1]和t[m-1]是否匹配，如此循環下去；如果匹配不成功，則進行字元串滑移。

BM演算法的原理：

不同於樸素模式（brute-force search）的逐個字元對比，Boyer-Moore充分使用預處理 P的信息來盡可能跳過更多的字元。通常，我們比較一個字元串都是從首字母開始，逐個比較下去。一旦發現有不同的字元，就需要從頭開始進行下一次比較。

這樣，就需要將字串中的所有字元一一比較。Boyer-Moore演算法的關鍵在於，當 P的最後一個字元被比較完成後，我們可以決定跳過一個或更多個字元。如果最後一個字元不匹配，那麼就沒必要繼續比較前一個字元。

如果最後一個字元未在 P中出現，那麼我們可以直接跳過 T的n個字元，比較接下來的n個字元，n為 P的長度（見定義）。

如果最後一個字元出現在 P中，那麼跳過的字元數需要進行計算（也就是將 P整體往後移），然後繼續前面的步驟來比較。通過這種字元的移動方式來代替逐個比較是這個演算法如此高效的關鍵所在。

❻ 字元串匹配演算法

boyermoore演算法的sample程序

TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind)
{
//
// 聲明：
// 該段代碼只是BoyerMoore(名字也許不準確)的基本思想，當
// 然不是最優的，具體完善工作就留給你自己樂！嘻嘻。
// 該演算法的本質就是從字元串的右端而不是左端開始比較，這
// 樣，當查詢不匹配時才有可能直接躍過多個字元（最多可以躍過
// strlen(sFind)個字元），如果最右邊的字元匹配則回溯。比如：
//
// pain
// ^ 這是第一次比較n和空格比
// The rain in SpainThe rain in Spain
//
// pain
// ^ 這是第二次比較，好爽呀！
// The rain in SpainThe rain in Spain
//
// 當然，這樣比較會產生一些問題，比如：
//
// pain
// ^ （圖1）
// The rain in SpainThe rain in Spain
//
// 如果比較到這兒，大家都會看到，只需再向後移到兩個字元
// 就匹配成功了，但如果接下去還按上面的方法跳strlen(sFind)的
// 話，就會錯過一次匹配！！！！！
//
// pain
// ^
// The rain in SpainThe rain in Spain
//
// 怎麼辦？當然可以解決！大家回頭看圖1，當時a是pain的子
// 串，說明有可能在不移動strlen(sFind)的跨度就匹配成功，那就
// 人為地給它匹配成功的機會嘛！串一下pain串，直接讓兩個a對齊
// 再做比較！呵呵，如果要比較的字元不是pain的子串，當然就可
// 以直接跨過strlen(sFind)個字元了！不知我說明白沒？
//
//

// 查詢串的長度
int nLenOfFind = lstrlen(sFind);
// 被查詢串的長度
int nLenOfSrc = lstrlen(sSrc);
// 指向查詢串最後一個字元的指針
TCHAR * pEndOfFind = sFind + nLenOfFind -1;
// 指向被查詢串最後一個字元的指針
TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1;

// 在比較過程中要用到的兩個指針
TCHAR * pSrc = sSrc;
TCHAR * pFind;

// 總不能一直讓它比較到win.com文件的地址去吧？嘻嘻！
while ( pSrc <= pEndOfSrc ) {

// 每次匹配都是從右向左，這是本演算法的核心。
pFind = pEndOfFind;

// 如果比較不成功，被查詢串指針將向右串的字元數
int nMoveRightSrc;

// 比較被查詢串的當前字元是否和查詢串的最右邊字
// 符匹配，如果匹配則回溯比較，如果全匹配了，該
// 干什麼，我就不用說了吧？:-)
while ( pFind >= sFind ) {

// TNND，白廢功夫比了！看看需要向右移動幾個
// 字元吧（如果說從右到左是本演算法的核心，則
// 判斷向右移幾個字元則是本演算法的技巧）。
if ( *pSrc != *pFind ) {

// 被查詢串的當前字元是否在查詢串里？
TCHAR * p = strrchr( sFind, *pSrc );
// 沒在，直接移lstrlen(sFind)個字元
if ( NULL == p )
nMoveRightSrc = nLenOfFind;
else
// 哇塞！真的在，那就只需...
nMoveRightSrc = pEndOfFind - p;

break;
}

// 哈！又匹配成功了一個！接著向左回溯...
pFind --;
pSrc --;
}

// 如果在上面的while循環里每一次比較都匹配了
// 那就對了唄！告訴用戶找到了
if ( pFind < sFind )
return ( pSrc + 1 );

// 沒匹配成功，nMoveRightSrc上面已經算好了
// 直接用就可以了。
pSrc += nMoveRightSrc;
}

// 程序運行到這兒肯定是沒指望了！
return NULL;
}

行了，函數寫完了，我們可以試一下了！

void CTNNDDlg::OnButton1()
{
TCHAR sSrc[] = "The rain in Spain";
TCHAR sFind[]= "pain";

TCHAR * pFound = BoyerMooreSearch( sSrc, sFind );
if ( pFound )
MessageBox(pFound);
else
MessageBox("沒找到");
}

//另外一個
void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}

void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}

void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];

/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}

❼ 字元串查找匹配--kmp演算法

KMP的關鍵是部分匹配表。理解KMP的主要障礙是沒有完全掌握部分匹配表中的值到底意味著什麼。試著用最簡單的話來解釋它們。

這是「abababca」模式的部分匹配表：

現在，為了談論其含義，我們需要了解正確的前綴和正確的後綴。

字元串中的所有字元，其中一個或多個字元被截斷。
「S」，「Sn」，「Sna」和「Snap」都是「Snape」的正確前綴。
截取的范圍是從字元串的第一個字元到倒數第二個字元。

字元串中的所有字元，一個或多個字元在開頭處截斷。
「agrid」，「grid」，「rid」，「id」和「d」都是「Hagrid」的正確後綴。
截取的范圍是從字元串的第二個字元到倒數第一個字元。

考慮到這一點，我現在可以給出部分匹配表中值的一句話含義：

現在來分析「abababca」這個模式串：

對「a」分析，只有一個字元串，沒有前綴和後綴，故值為0。

對「ab」分析，有一個正確的前綴（「a」）和一個正確的後綴（「b」），前綴和後綴不匹配，故值為0。

對「aba」分析，有兩個正確的前綴（「a」和「ab」）和兩個正確的後綴（「a」和「ba」）。正確的前綴「ab」與兩個正確的後綴中的任何一個都不匹配。但是，正確的前綴「a」與正確的後綴「a」匹配。因此，在這種情況下，匹配正確後綴的最長正確前綴的長度是1。

對四個字元（「abab」）分析，有三個正確的前綴（「a」，「ab」和「aba」）和三個正確的後綴（「b」，「ab」和「bab」）。「ab」在兩者中，並且是兩個字元長，因此值為2。

對「ababa」分析，有四個正確的前綴（「a」，「ab」，「aba」和「abab」）和四個正確的後綴（「a」，「ba」，「aba」和「baba」）。現在，有兩個匹配：「a」和「aba」都是正確的前綴和正確的後綴。由於「aba」比「a」長，所以它獲勝，因此值為3。

對「abababc」分析。即使沒有列舉所有正確的前綴和後綴，顯然也不會有任何匹配; 所有後綴都以字母「c」結尾，並且沒有前綴與之匹配，因此值為0。

對「abababca」分析，由於它們都以「a」開頭和結尾，我們知道它的值至少為1.但是，它就是它的結束點; 在長度為2或更高時，所有後綴都包含ac，而只有最長的前綴（「abababc」）包含「c」。這個七個字元的前綴與七個字元的後綴（「bababca」）不匹配，因此值為1。

當我們找到部分匹配時，我們可以使用部分匹配表中的值來跳過（而不是重做不必要的舊比較）。該公式的工作方式如下：

如果找到長度為partial_match_length的部分匹配table[partial_match_length] > 1，我們可以跳過前面的partial_match_length - table[partial_match_length - 1]字元。

假設我們將「abababca」模式與「bacbababaabcbab」相匹配。這里是我們的部分匹配表，以便於參考：

我們第一次獲得部分匹配是在這里：

這是partial_match_length為1. table[partial_match_length - 1]（或table[0]）的值為0，因此我們不會先跳過任何一個。我們得到的下一個部分匹配是：

這是partial_match_length為5. table[partial_match_length - 1]（或table[4]）的值為3.這意味著我們可以跳過前面partial_match_length - table[partial_match_length - 1]（或5 - table[4]或5 - 3或2）字元：

這是partial_match_length 3. table[partial_match_length - 1]（或table[2]）的值是1.這意味著我們可以跳過前面partial_match_length - table[partial_match_length - 1]（或3 - table[2]或3 - 1或2）字元：

❽ 【演算法筆記】字元串匹配

BF 演算法中的 BF 是 Brute Force 的縮寫，中文叫作暴力匹配演算法，也叫樸素匹配演算法：

主串和模式串：
在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m

我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。

BF 演算法的時間復雜度是 O(n*m)

等價於

比如匹配Google 和Goo 是最好時間復雜度，匹配Google 和ble是匹配失敗的最好時間復雜度。

KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth與J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特—莫里斯—普拉特演算法。KMP演算法主要分為兩個步驟：字元串的自我匹配，目標串和模式串之間的匹配。

看來網上很多的文章，感覺很多的都沒有說清楚，這里直接復制阮一峰的內容，講的很清晰
內容來自 http://www.ruanyifeng.com/blog/

首先，字元串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜索詞"ABCDABD"的第一個字元，進行比較。因為B與A不匹配，所以搜索詞後移一位。

因為B與A不匹配，搜索詞再往後移。

就這樣，直到字元串有一個字元，與搜索詞的第一個字元相同為止。

接著比較字元串和搜索詞的下一個字元，還是相同。

直到字元串有一個字元，與搜索詞對應的字元不相同為止。

這時，最自然的反應是，將搜索詞整個後移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜索位置"移到已經比較過的位置，重比一遍。

一個基本事實是，當空格與D不匹配時，你其實知道前面六個字元是"ABCDAB"。KMP演算法的想法是，設法利用這個已知信息，不要把"搜索位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。

怎麼做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產生的，後面再介紹，這里只要會用就可以了。

已知空格與D不匹配時，前面六個字元"ABCDAB"是匹配的。查表可知，最後一個匹配字元B對應的"部分匹配值"為2，因此按照下面的公式算出向後移動的位數：

因為 6 - 2 等於4，所以將搜索詞向後移動4位。

因為空格與C不匹配，搜索詞還要繼續往後移。這時，已匹配的字元數為2（"AB"），對應的"部分匹配值"為0。所以，移動位數 = 2 - 0，結果為 2，於是將搜索詞向後移2位。

因為空格與A不匹配，繼續後移一位。

逐位比較，直到發現C與D不匹配。於是，移動位數 = 6 - 2，繼續將搜索詞向後移動4位。

逐位比較，直到搜索詞的最後一位，發現完全匹配，於是搜索完成。如果還要繼續搜索（即找出全部匹配），移動位數 = 7 - 0，再將搜索詞向後移動7位，這里就不再重復了。

下面介紹《部分匹配表》是如何產生的。

首先，要了解兩個概念："前綴"和"後綴"。 "前綴"指除了最後一個字元以外，一個字元串的全部頭部組合；"後綴"指除了第一個字元以外，一個字元串的全部尾部組合。

"部分匹配值"就是"前綴"和"後綴"的最長的共有元素的長度。以"ABCDABD"為例，

"部分匹配"的實質是，有時候，字元串頭部和尾部會有重復。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分匹配值），就可以來到第二個"AB"的位置。

BM（Boyer-Moore）演算法。它是一種非常高效的字元串匹配演算法，有實驗統計，它的性能是著名的KMP 演算法的 3 到 4 倍。

BM 演算法包含兩部分，分別是壞字元規則（bad character rule）和好後綴規則（good suffix shift）

未完待續

參考文章：
字元串匹配的Boyer-Moore演算法

❾ 什麼是演算法

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。
形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效計算性或者有效方法中成形。這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化演算法的情況。