中文文本匹配算法

Ⅰ 全文检索算法，请问谁能给我点头绪落，不懂啊。。

全文检索技术
全文检索是指索引程序扫描文章中的每个词并建立对应索引，记录该词出现的位置和次数。当通过搜索引擎查询时，检索程序就在记录的索引进行查找并返回给用户。全文检索又分为基于字的全文索引和基于词的全文索引。基于字的全文索引会对内容中的每个字建立索引并记录，此方法查全率高，但查准率低，特别是对于中文，有时搜索马克，会列出马克思的结果。基于词的全文索引是把一个词语作为一个单位进行索引记录，并能处理同义词。搜索引擎有自己的词库，当用户搜索时，搜索引擎会从词库中抽取关键词作为索引项，这样可以大大提高检索的准确率。
中文分词技术
一直以来大家都比较熟悉网络，网络有自己的中文分词技术。一般采用的包括正向最大匹配，反向最大匹配，最佳匹配法，专家系统方法等。其中最大正向匹配是最常用的分词解决方案，它采用机械式算法，通过建立词典并进行正向最大匹配对中文进行分词。举个简单的例子比如搜索“北京大学在哪里”，则返回结果很多都是包含北京大学，北大等词语的网页，搜索引擎就是采用正向最大匹配去判断，把北京大学当做一个词语来索引记录并返回。当然，正向最大匹配也有不完整性，比如长度过长的词语，搜索引擎有时无法准确的分词，或者对前后都相互关联的词无法准确分词。例如“结合成分子时”，会被返回结合、成分、子时，而有时我们想要的关键词是“分子”。
很多时候网络都会根据自己词库中词语的权重进行拆分，权重的计算基于生活各个方面，比较复杂，搜索引擎要做的就是返回用户最想要的结果，有时站长们做网站要站在用户的角度去考虑问题，其实这也是站在搜索引擎的角度考虑问题，不论在确定目标关键词或者是长尾关键词时，都可以根据中文分词的原理来选择，这样可以最大化的减少无用功。
分词原理不断在变化，不断在更新，我们应该继续学习，只有掌握了本质才能抓住实质。

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

字符串的匹配在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等。所用到的技术包括滑动窗口、位并行、自动机、后缀树等。