字元串識別演算法

① 想找一個解決兩個字元串匹配程度的演算法。

假設string1="abcde",string2="bcd",則分析邏輯如下：
1. 如果string2長於string1，則不匹配
2. 在string1中順序查匹配string2中第一個字元的字元，
查到後，如果string1餘下的字元串長度小於string2的長度，則不匹配
3. 在上述條件滿足時，將string1的下一個字元和string2中的第二個字元匹配，以此類推，一旦有一個不匹配，則不匹配。回到第2步，查找下一個和string2首字元一致的字元。
4. 如果string2中的字元全都匹配上，則說明string2中string1中識別出來了。

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

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

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

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演算法

④ 字元串的模式匹配（BF演算法與KMF演算法）

Brute-Force演算法的實現：

測試程序以及運行結果：

雖然沒有任何丟失可能匹配字元的可能，但是每次的匹配沒有用到前一次匹配的比較結果，比較多次重復，降低了演算法效率。
時間復雜度：
m = pattern.length();
n = target.length();
最好的情況：O(m) (一次比較成功)
最壞的情況：O(n(n-m+1) m) 一般n>>m，所以O(n m) (比較到最後一次才成功）

先來一波kmp演算法的 網路 介紹：

無回溯的模式匹配演算法首先目標串的祛除了目標串的回溯，其次，通過getNext()演算法，匹配串也做到了部分不回溯。

無回溯演算法的核心是如何實現這個 next（） 演算法：

實際上next()演算法就是來 判斷pattern的子字元串與當pattern的0位置開始的字元串是否相同，第一個next[0]默認為1，接下來的如果不相同next[i]為0，如果第一個相同，為0,若連續開始相同，則依次++1
如:

如果pattern的首字元在pattern剩餘的字元串里沒有再出現過，那麼getNext()獲取的next[]必然是[-1,0,...,0]這樣的。

匹配方法如下：

kmp演算法的最壞的比較次數是m+n，next演算法的時間復雜度是0(m),kmp比較是O(n)，與BF演算法相比，已經大大縮小了比較的時間。

⑤ 字元串匹配演算法

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）字元：

⑦ OCR文字識別用的是什麼演算法

ocr文字識別的使用的演算法，下面就以迅捷辦公中的文字識別軟體為例：

1、打開ocr文字識別軟體，關閉提示窗；2、通過左上角的添加文件，將需要識別的圖片添加進去；3、點擊右下角的一鍵識別按鈕，開始識別。

上面便是ocr文字識別軟體的使用方法啦！