中文文本匹配演算法

Ⅰ 全文檢索演算法，請問誰能給我點頭緒落，不懂啊。。

全文檢索技術
全文檢索是指索引程序掃描文章中的每個詞並建立對應索引，記錄該詞出現的位置和次數。當通過搜索引擎查詢時，檢索程序就在記錄的索引進行查找並返回給用戶。全文檢索又分為基於字的全文索引和基於詞的全文索引。基於字的全文索引會對內容中的每個字建立索引並記錄，此方法查全率高，但查准率低，特別是對於中文，有時搜索馬克，會列出馬克思的結果。基於詞的全文索引是把一個詞語作為一個單位進行索引記錄，並能處理同義詞。搜索引擎有自己的詞庫，當用戶搜索時，搜索引擎會從詞庫中抽取關鍵詞作為索引項，這樣可以大大提高檢索的准確率。
中文分詞技術
一直以來大家都比較熟悉網路，網路有自己的中文分詞技術。一般採用的包括正向最大匹配，反向最大匹配，最佳匹配法，專家系統方法等。其中最大正向匹配是最常用的分詞解決方案，它採用機械式演算法，通過建立詞典並進行正向最大匹配對中文進行分詞。舉個簡單的例子比如搜索「北京大學在哪裡」，則返回結果很多都是包含北京大學，北大等詞語的網頁，搜索引擎就是採用正向最大匹配去判斷，把北京大學當做一個詞語來索引記錄並返回。當然，正向最大匹配也有不完整性，比如長度過長的詞語，搜索引擎有時無法准確的分詞，或者對前後都相互關聯的詞無法准確分詞。例如「結合成分子時」，會被返回結合、成分、子時，而有時我們想要的關鍵詞是「分子」。
很多時候網路都會根據自己詞庫中詞語的權重進行拆分，權重的計算基於生活各個方面，比較復雜，搜索引擎要做的就是返回用戶最想要的結果，有時站長們做網站要站在用戶的角度去考慮問題，其實這也是站在搜索引擎的角度考慮問題，不論在確定目標關鍵詞或者是長尾關鍵詞時，都可以根據中文分詞的原理來選擇，這樣可以最大化的減少無用功。
分詞原理不斷在變化，不斷在更新，我們應該繼續學習，只有掌握了本質才能抓住實質。

Ⅱ 字元串匹配演算法的使用（未完待整理）

字元串的匹配在Java中都知道使用indexOf函數來實現，那麼其匹配演算法是怎麼樣的呢？

單模式和多模式的區別就是一次遍歷主串能否將多個模式的字元串都查找出來。

英文全稱為Brute Force，暴力匹配演算法，匹配字元串的方法比較暴力，也比較簡單易懂。其大概的思路就是：

我們可以看到，在極端情況下，在主串 aaaa...aab 中尋找模式串 aab ，那麼總共需要尋找(n-m+1)次，且每次都需要比對m次，那麼時間復雜度將是 (n-m+1)*m ，即 O(n*m) ；但實際上並不會這么低效，因為我們的使用場景中主串和模式串都不會太長，而且在每個子串和模式串進行比對時，只要中途有一個不匹配，那麼當前比對就會提前結束，因此大部分情況下，時間復雜度都會比 O(n*m) 要好。

我們在BF演算法的基礎上引入哈希演算法，我們不需要將每個子串與模式串逐個字元地進行比較，而是計算得出每個子串的hash值，然後和模式串的hash值進行比較，如果有相等的，那就說明有子串和模式串匹配上了。

雖然我們只需要比對模式串和子串的hash值就能得到匹配結果，次數為(n-m+1)，但是對每個子串進行hash計算的時候，是要遍歷每個字元的，因此次數也是m，那麼總的時間復雜度還是 O(n*m) ，並沒有明顯地提升。

那麼我們該如何想出一個辦法，使得每個子串hash值的計算時間得到提升呢？這就是RK演算法的精髓，假設子串包含的字元集中元素個數為k，那麼就用k進制數來代表這個子串，然後hash的過程就是將這個k進制的數轉換為十進制的數，這個十進制的數就是該子串的hash值。

相鄰子串的hash值計算是有規律的，我們只需要遍歷一次主串就能得到所有子串的hash值，演算法復雜度為O(n)，而不是像原先一樣，每個子串都需要O(m)的時間復雜度。

然後將模式串的hash值和所有子串的hash值進行比較，每次比較的時間復雜度是 O(1) ，總共比較(n-m+1)次，所以RK演算法的總的時間開銷為 O(n)+O(1)*O(n-m+1) ，即為 O(n) ，時間復雜度比BF演算法更加高效。

當然，有hash的地方就有可能會存在hash沖突，有可能子串和hash值和模式串的hash值是一樣的，但內容就是不一樣，此時怎麼辦呢？其實很簡單，對於hash值一樣的子串，我們增加雙保險，再比較一下這m個字元是否都一樣即可，總的時間開銷為 O(n)+O(1)*O(n-m+1)+O(m) ，即為 O(n) 。

如果極端情況下出現了很多hash沖突呢？我們對於每個和模式串相同hash值的子串都需要逐一再進行比較，那麼總的時間開銷就會為 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即為 O(n*m) ，不過這種概率太小了，大部分情況下都不會這樣。

在真正的文本編輯器中查找和替換某個字元串時，使用的演算法既不是上述的BF演算法，也不是RK演算法；BF演算法只適合不是很長的主串，RK演算法則要設計一個沖突概率很低的hash演算法，這個比較困難，所以實際使用的是BM演算法，它是工程中非常常用的一種字元串匹配演算法，效率也是最高的。

演算法的思想和過程有些復雜，待以後整理。

KMP演算法在本質上是和BM演算法一樣的。演算法的思想和過程有些復雜，待以後整理。

瀏覽器輸入框中的智能輸入匹配是怎麼實現的，它是怎麼做動態字元串匹配查找的呢？這就用到了Trie樹。

又名字典樹，是一種專門用來快速查找字元串前綴匹配結果的樹形結構，其本質就是將所有字元串的重復的前綴合並在一起，構造一個多叉樹。

其中，根節點不包含任何信息，每個節點表示一個字元，從根節點到紅色節點的一條路徑表示存儲的一個字元串。當我們在如上Trie樹中查找"he"時，發現"he"並非是一個字元串，而是"hello"和"her"的公共前綴，那麼就會找到這兩個字元串返回。

Trie樹在內存中是如何存儲的呢？因為每一個節點都可能是包含所有字元的，所以每一個節點都是一個數組（或者散列表），用來存儲每個字元及其後綴節點的指針。

使用Trie樹，最開始構建的時候，時間復雜度為 O(n) ，其中n為所有字元串長度之和，但是一旦構建完成，頻繁地查詢某個字元串是非常高效的，時間復雜度為 O(k) ，其中k為查找字元串的長度。

Trie樹雖然查詢效率很高，但是比較浪費內存，每一個節點都必須維護一個數組存放所有可能的字元數據及其指向下一個節點的指針，因此在所有字元串公共前綴並不多的時候，內存空間浪費地就更多了。這種問題其實也有對應的解決辦法，我們可以不使用數組，而是使用有序數組、散列表、紅黑樹來存放，可以相應地降低性能來節省內存空間。

Trie樹除了可以實現瀏覽器動態輸入內容查找候選項的功能外，還可以實現多模式地敏感詞匹配功能。假設我們需要對用戶輸入的內容進行敏感詞檢查，將所有的敏感內容用***代替，那麼該如何實現呢？

首先我們可以維護一個敏感詞字典，使用上述四種單模式匹配演算法也可以實現，但是需要遍歷N次用戶輸入的內容，其中N是所有敏感詞的模式串，顯得非常低效。但是我們如果將敏感詞字典維護為一個Trie樹，然後將用戶輸入的內容從位置0開始在Trie樹中進行查詢，如果匹配到紅色節點，那麼說明有敏感詞；如果沒有匹配到紅色節點，就從用戶輸入內容的下一個位置開始繼續在Trie樹中查詢，直至將用戶輸入內容遍歷完，因此我們只是遍歷了一遍主串。

然而更高效的多模式字元串匹配使用地更多的是如下的AC自動機。

如果把Trie樹比作BF演算法，KMP演算法是BF演算法的改進，那麼AC自動機就是利用同樣的思想改進了Trie樹。

演算法的思想和過程有些復雜，待以後整理。

Ⅲ 文本相似度演算法-Jaro distance

給定兩個灶指衡文本串 , ,他們的Joro距離定義為：

求 match 的字元數：
分別來自 , 的字元，當他們相同或者距離小於 ,則被認為是 match 的。

比如： =「DIXON」, =「DICKSONX」

中的逗滑每一個字元都會與 中距離 內的字元進行比較。將所有 match 的字元隱做串，需要替調換順序才能匹配的總數除以二就是transpositions的大小 。這里兩個字元串中匹配的分別是："DION"，「DION",所以 。
另外 =4, =8,
則：

參考：
https://rosettacode.org/wiki/Jaro_distance#Java

Ⅳ 串模式匹配演算法

# 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 ------------------------------ */

Ⅳ 漢語分詞演算法如何實現

常用的分詞演算法有正向最大匹配、逆向最大匹配、雙向最大匹配、最佳匹配法、最少分詞法、詞網格演算法等等。
最大匹配法（Forward Maximum Matching method, FMM法）：選取包含6-8個漢字的符號串作為最大符號串，把最大符號串與詞典中的單詞條目相匹配，如果不能匹配，就削掉一個漢字繼續匹配，直到在詞典中找到相應的單詞為止。匹配的方向是從右向左。
逆向最大匹配法（Backward Maximum Matching method, BMM法）：匹配方向與MM法相反，是從左向右。實驗表明：對於漢語來說，逆向最大匹配法比最大匹配法更有效。
雙向匹配法（Bi-direction Matching method, BM法）：比較MM法與RMM法的切分結果，從而決定正確的切分。
最佳匹配法（Optimum Matching method, OM法）：將詞典中的單詞按它們在文本中的出現頻度的大小排列，高頻度的單詞排在前，頻度低的單詞排在後，從而提高匹配的速度。

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

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

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

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

Ⅶ 字元串的模式匹配演算法

#include<iostream>
using namespace std;
void Next(char T[],int next[])
{ next[0]=-1;
int j=0,k=-1;
while(T[j]!='\0')
if((k==-1)||(T[j]==T[k]))
{ j++;
k++;
next[j]=k;
}
else k=next[k];
}
int KMP(char S[],char T[])
{ int i=0,j=0;
int next[10];
Next(T,next);
while((S[i]!='\0')&&(T[j]!='\0'))
{ if(S[i]==T[j]) {i++;j++;}
else j=next[j];
if(j==-1)
{ i++;j++; }
}
if(T[j]=='\0') return(i-j+1);
else return 0;
}
int main()
{ char a[100],b[100];
cout<<"please enter primary string :";
cin.getline(a,100);
cout<<"please enter substring:";
cin.getline(b,100);
if(KMP(a,b)==0)
cout<<"not exist!\n";
else cout<<"location is:"<<KMP(a,b)<<endl;
return 0;
}
具體的你自己看吧。

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

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