自然语言处理NPL 最大概率分词算法
NLP基于最大概率的汉语切分Ytinrete
要求：
基于最大概率的汉语切分
目标：采用最大概率法进行汉语切分。
其中：n-gram用bigram，平滑方法至少用Laplace平滑。
输入：接收一个文本，文本名称为：corpus_for_test.txt
输出：切分结果文本，
其中：切分表示：用一个字节的空格“”分隔，如：我们在学习。
每个标点符号都单算一个切分单元。
输出文件名为：学号.txt
Bigram参数训练语料：corpus_for_train.txt
注：请严格按此格式输出，以便得到正确评测结果
切分性能评价：
分
切分结果评测F*100, F=2P*R/(P+R)
特别注意:代码雷同问题
本次作业最后得分会综合考虑：切分性能、代码、文档等几个方面。
第三次作业上交的截止时间：2014 年1月7日24:00
1.关于最大概率分词
基本思想是：
一个待切分的汉字串可能包含多种分词结果，将其中概率最大的作为该字串的分词结果。
根据：
由于语言的规律性，句子中前面出现的词对后面可能出现的词有很强的预示作用。
公式1：
其中 w 表示词， s 表示待切分字符串。
公式2：
例如：
S ：有意见分歧
W1: 有/ 意见/ 分歧/
W2: 有意/ 见/ 分歧/
P(W1)=P(有)×P(意见)×P(分歧) ＝1.8*10-9
P(W2)=P(有意)×P(见)×P(分歧) ＝1*10-11
P(W1)> P(W2)
所以选择 W1
历史信息过长，计算存在困难
p(wi|w1w2…wi-1)
为了便于计算，通常考虑的历史不能太长，一般只考虑前面n-1个词构成的历史。 即： p(wi|wi-n+1…wi-1)
1212(|)*()(|)()()()(,,...,)()*()*...*()i i
P S W P W P W S P W P S P W P w w w P w P w P w =≈=≈n ()i
i w P w =在语料库中的出现次数语料库中的总词数N
n-gram
n 较大时：
提供了更多的语境信息，语境更具区别性。但是，参数个数多、计算代价大、训练语料需要多、参数估计不可靠。
n 较小时：
语境信息少，不具区别性。但是，参数个数少、计算代价小、训练语料，无需太多、参数估计可靠。
题目要求使用bigram，即考虑前一个词，即考虑左邻词。
左邻词
假设对字串从左到右进行扫描，可以得到w1 ,w2 ,…,wi-1 wi,…等若干候选词，如果wi-1 的尾字跟wi 的首字邻接，就称wi-1 为wi 的左邻词。比如上面例中，候选词“有”就是候选词“意见”的左邻词，“意见”和“见”都是“分歧”的左邻词。字串最左边的词没有左邻词。
最佳左邻词
如果某个候选词wi 有若干个左邻词wj ，wk ,…等等，其中累计概率最大的候选词称为wi 的最佳左邻词。比如候选词“意见”只有一个左邻词“有”，因此，“有”同时也就是“意见”的最佳左邻词；候选词“分歧”有两个左邻词“意见”和“见”，其中“意见”的累计概率大于“见”累计概率，因此“意见”是“分歧”的最佳左邻词。
数据稀疏问
若某n-gram在训练语料中没有出现,则该n-gram的概率必定是0。解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料，都不可能保证所有的词在训练语料中均出现。由于训练样本不足而导致所估计的分布不可靠的问题，称为数据稀疏问题。在NLP领域中，数据稀疏问题永远存在，不太可能有一个足够大的训练语料，因为语言中的大部分词都属于低频词。
解决办法: 平滑技术
把在训练样本中出现过的事件的概率适当减小。
把减小得到的概率密度分配给训练语料中没有出现过的事件。
这个过程有时也称为discounting(减值)。
目前已经提出了很多数据平滑技术，如：
Add-one 平滑
Add-delta 平滑
Witten-Bell平滑
Good-Turing平滑
Church-Gale平滑
Jelinek-Mercer平滑
Katz平滑
这里我使用laplace平滑
Add-one 平滑(Laplace’s law)
规定任何一个n-gram在训练语料至少出现一次（即规定没有出现过的n-gram在训练语料中出现了一次）。
没有出现过的n-gram的概率不再是0。
2.算法描述
1) 对一个待分词的字串S，按照从左到右的顺序取出全部候选词w1 ,w2 ,…,wi-1
wi,…wn；
2)到词典中查出每个候选词的概率值P(wi)，当候选词没有出现时，由laplace
平滑设其概率为1/(字典数+1)，记录每个候选词的全部左邻词；
3)按照公式1计算每个候选词的累计概率，同时比较得到每个候选词的最佳左
邻词；
4)如果当前wn是字串S的尾词，且累计概率P’(wn)最大，wn就是S的终
点词。
5)从wn开始，按照从右到左的顺序，依次将每个词的最佳左邻词输出，即为
S的分词结果。
3.程序设计
整个程序我分为两个阶段，字典生成阶段和分词阶段。
(make_dic.cpp)字典生成：
目标：
输入为训练语料(corpus_for_train.txt)，输出为字典(dic.txt)，字典内容为单词和单词出现在字典中的频率，首行为词典总词数。
实现步骤：
首先读入训练，通过空格和换行符作为判定，分出单个单词。若单词没有在字典中出现，则将其加入字典，单词自身频数加一，单词总数加一；若单词在字典中出现，则单词自身频数加一。将数据存入map中，然后再遍历map，创建一个输出流，输出为字典文件，数据为具体单词和他的出现概率（自身频数/单词总数）。
(zdgl_fenci.cpp)分词：
目标：
输入为字典和待切分语料（利用kill_space先将老师预先存好的待切分语料的空格和换行删去，成为为切分语料target.txt），输出为切分好的语料（2011211366.txt）。
实现步骤：
首先在主函数中，循环取出待切分语料的每个句子，将句子传给分词子程序，分词子程序处理后返回分好的句子，将句子输出到文件，再取下一句，依次循环，直到处理完为止。
分词子程序，处理过程分为三步：
1.将待切分的句子切成备选的切分词，并放在“单词池”中，切分标准参考一个假定的单词最大长度，程序里面我设置成20，也就是单词最长10个汉字（可以根据词典来决定），具体切分我考虑了两种，不同之处体现在对取到的单词（从一个汉字到10个汉字遍历地取），若不出现在词典中（出现在词典中的肯定会列入），第一种做法是只保留单个汉字形成的单词，另一种做法是保留全部的可能性。若采取第一种则效率会有很大的提高，但理论上会降低准确性，第二种虽然能够考虑到所有的情况，但是数据往往是前一种的几十倍，而且对于句子中很多单词都有在词典时，分词结果几乎和前一种相同，如果句子中的所有词都能在词典中时，分词结果就一样了（laplace平滑使得未出现的概率是最低的，乘积也会最低，所以不会选择未出现的词），但会多出几十倍的运算。两种的代码我都写出来了，考虑实际，我觉得第一种比较妥当，第二种我注释起来。
2.对“单词池”操作，通过循环的遍历，直到计算出所有的最佳左邻词。
3.在“单词池”中找出所有的句尾词，找到概率最大的，再通过左邻词，往回找，直到找到句头词，将这些词用空格分开，返回。
4.程序源码：
1.kill_space.cpp
将待切分文本corpus_for_test.txt变成不含空格和换行的待切分文本target.txt
#include
#include
#include
#include
/*
Name: 删除空格
Description: 删除空格
*/
using namespace std;
int main()
{
FILE *f_in, *f_out;//输入输出文件
char ch;
f_in=fopen("corpus_for_test.txt", "r");
f_out=fopen("target.txt", "w");
ch=getc(f_in);
while(EOF!=ch)
{
if(' '!=ch&&'\n'!=ch)
putc(ch, f_out);
ch=getc(f_in);
}
return 0;
}
2.make_dic.cpp
读入训练预料corpus_for_train.txt输出词典文件dic.txt
#include
#include
#include
#include
#include
using namespace std;
const char *train_text = "corpus_for_train.txt";//训练文件const char *dic_text = "dic.txt";//输出词典文件
map
map
//map
int main()
{
FILE *f_in;
f_in=fopen(train_text, "r");
ofstream f_out(dic_text);
double rate=0;
int count=0;
char ch;
string word;
ch=fgetc(f_in);
while(EOF!=ch)
{
if(' '!=ch&&'\n'!=ch)//词的一部分
{
word.append(1, ch);
if("。"==word)
word.clear();
}
else//单词结束
{
if(" "==word||0==word.size())
{
word.clear();
ch=fgetc(f_in);
continue;
}
dic_it=dic.find(word);
if(dic_it!=dic.end())
{
//找到
dic_it->second=dic_it->second+1;
word.clear();
}
else
{
//新单词
count++;
dic.insert(pair
word.clear();
}
}
ch=fgetc(f_in);
// if('\n'==ch)//吸收换行
// ch=fgetc(f_in);
}
f_out< dic_it=dic.begin(); while(dic_it!=dic.end()) { f_out< rate=(double)(dic_it->second)/count; f_out< dic_it++; } f_out.close(); fclose(f_in); /*测试用 ifstream file(dic_text); int count_text; file>>count_text; string word_text; double rate_text; for(int i=0; i { file>>word_text; file>>rate_text; dic_in_text.insert(pair } file.close(); */ return 0; } 3.zdgl_fenci.cpp 读入词典dic.txt和带切分文本target.txt输出分词结果2011211366.txt #include #include #include #include #include #include #include using namespace std; const char *target = "target.txt";//输入文件 const char *out_put= "2011211366.txt";//输出文件 const char *dic_text = "dic.txt";//输入词典文件 const int max_word=20;//假设一个词最长包括10个汉字double laplace ;//laplace平滑 map map typedef struct word_pre//单词池内元素 { int num;//标记 int p_begin;//起始位置 int p_end;//结束位置 double word_rate;//单词本身概率 double plus_rate;//单词累进概率 int best;//最佳左邻词 string this_word;//词本身 }word_pre; void dic_init_test(void)//测试用 { int count_text=10000000; laplace = (double)1/(count_text+1); dic.insert(pair dic.insert(pair dic.insert(pair dic.insert(pair dic.insert(pair void dic_init(void)//初始化词典 { ifstream file(dic_text); int count_text; file>>count_text; laplace = (double)1/(count_text+1); string word_text; double rate_text; for(int i=0; i { file>>word_text; file>>rate_text; dic.insert(pair } file.close(); } string zdgl_fenci(string sentance)//最大概率分词，输入为不带“。”的句子，输出为分好的句子 { if(sentance.size()<=2) return sentance;//单个字直接返回 int min=0, max=sentance.size()-1;//单词位置标记 //第一步建立单词池 vector int word_pre_num=0; //stack string temp_word; //第一种方法，对于未出现词，只保存单个字 for(int i=0; i<=max; i+=2) { temp_word.clear(); for(int j=i; j<=max&&j { temp_word.append(1, sentance.at(j)); temp_word.append(1, sentance.at(j+1)); dic_it=dic.find(temp_word); if(dic_it!=dic.end()||j==i)//有记录，或是第一个词 { word_pre w_pre; word_pre_num++; w_pre.num=word_pre_num; if(dic_it!=dic.end()) w_pre.word_rate=dic_it->second; else w_pre.word_rate=laplace; if(0==i)//句头词 { w_pre.plus_rate=w_pre.word_rate; w_pre.best=0; } else { w_pre.best=-1; w_pre.plus_rate=(double) -1; } w_pre.p_begin=i; w_pre.p_end=j+1; w_pre.this_word=temp_word; word_pool.push_back(w_pre);//入池} } } //第二种方法，记录所有可能情况 /* //严格全部入池 for(int i=0; i<=max; i+=2) { temp_word.clear(); for(int j=i; j<=max&&j { temp_word.append(1, sentance.at(j)); temp_word.append(1, sentance.at(j+1)); //入池 word_pre_num++; word_pre w_pre; w_pre.num=word_pre_num; dic_it=dic.find(temp_word); if(dic_it!=dic.end()) { w_pre.word_rate=dic_it->second; } else { w_pre.word_rate=laplace; } if(0==i) { w_pre.plus_rate=w_pre.word_rate; w_pre.best=0; } else { w_pre.best=-1; w_pre.plus_rate=double(-1); } w_pre.p_begin=i; w_pre.p_end=j+1; w_pre.this_word=temp_word; word_pool.push_back(w_pre);//入池 } } */ //第二步计算最佳左邻词 bool fail=true;//标记 while(fail) { fail=false; for(int i=0; i { if(-1==(word_pool.at(i)).best)//没有算出左邻词 { int p_begin_temp=(word_pool.at(i)).p_begin; vector for(int j=0; j { if(p_begin_temp==(word_pool.at(j)).p_end+1)//再考虑范围内 { if(-1==(word_pool.at(j)).best)//考虑的左邻词本身数据不全 { fail=true;//标记未完成 best_word_temp.clear(); break;//跳出循环 } else// { best_word_temp.push_back(j);//记录 } } } if(0!=best_word_temp.size())//所有备选项资料完备 { int max_p=0;//best_word_temp序号 for(int k=1; k { if((word_pool.at(best_word_temp.at(k))).plus_rate>(word_pool.at(best_word_temp.at(max_p ))).plus_rate) { max_p=k; } } //记录左邻词和概率 (word_pool.at(i)).best=best_word_temp.at(max_p); (word_pool.at(i)).plus_rate=((word_pool.at(i)).word_rate)*(word_pool.at(best_word_temp.at (max_p)).plus_rate); } } } } //第三步，选出最佳句尾词，并通过最佳左邻词，返回直到句头词。 vector for(int i =0; i { if(max==(word_pool.at(i)).p_end)//是结尾词 { end_word_temp.push_back(i); } } int best_end_word=0;//初始化 for(int i=1; i { if((word_pool.at(end_word_temp.at(i))).plus_rate>(word_pool.at(end_word_temp.at(best_en d_word))).plus_rate) { best_end_word=i; } } int position=end_word_temp.at(best_end_word); vector while(0!=(word_pool.at(position)).p_begin)//往回找 { word_complete.push_back((word_pool.at(position)).this_word); position=(word_pool.at(position)).best; } word_complete.push_back((word_pool.at(position)).this_word);//最后一个 //分词完成，每个词都放在word_complete里面 string complete; for(int i=word_complete.size()-1; i>=0; i--)//用空格分开，拼成成品 { complete+=word_complete.at(i); if(0!=i) complete+=" "; } return complete;//返回 } int main() { //dic_init_test();//测试用 dic_init(); FILE *f_in; ofstream f_out(out_put); f_in = fopen(target, "r"); char ch1=0, ch2=0; string word, sentance, s_complete; ch1=fgetc(f_in); if(EOF==ch1) cout<<"file id empty"; ch2=fgetc(f_in); while(EOF!=ch1&&EOF!=ch2) { word.append(1, ch1); word.append(1, ch2); if("。"==word)//一个句子 { s_complete.clear(); s_complete=zdgl_fenci(sentance); s_complete+=" 。";//加上“。” f_out< sentance.clear();//还原 } else//不是一个句子 { sentance+=word; } word.clear();//还原 ch1=fgetc(f_in); if(EOF==ch1) { if(sentance.size()>0)//防止漏掉最后一句话 { s_complete.clear(); s_complete=zdgl_fenci(sentance); s_complete+=" 。";//加上“。” f_out< } break; } ch2=fgetc(f_in); if(EOF==ch2) { if(sentance.size()>0)//防止漏掉最后一句话 { s_complete.clear(); s_complete=zdgl_fenci(sentance); s_complete+=" 。";//加上“。” f_out< } break; } } /*测试 s_complete=zdgl_fenci("有意见分歧"); s_complete+=" 。";//加上“。” f_out< */ fclose(f_in); f_out.close(); return 0; } 5.实验总结： 由于我的编程能力比较差，所以这个实验对我来说是个极大的挑战，最开始我甚至认为我绝对不能完成这项工作了，但是慢慢来一点一点的写，遇到问题上网查资料，实在不行换一种方法，一点一点的调试，最终还是能写出来了。 具体设计实现分次的时候，我完全没有头绪，想过用矩阵，但矩阵在确认最佳左邻词的时候不知道如何，遍历用链表，但是不知道切分点一致时不同的左邻词怎么连上去。网上查到了别人用有向图的做法(见附录)，当时对我来说是极具诱惑力的，但是特别注意里面有一项代码雷同问题，我能查得到的别人也一定查得到吧，我这么想着，所以就放弃了这个念头，还是自己想吧，最后想出了用vector容器并通过遍历来解决，真是不容易。 最后是大半夜写完的，程序跑出来我自己都要哭出来了，太不容易了。然后看看结果，第一句话和分词模板没有去掉空格前完全一样，又一次被感动了，看起来算圆满完成了。 附录： 网上别人做的用有向图最大概率分词 // word.cpp : Defines the entry point for the console application. // //#include "stdafx.h" // mympseg.cpp : 定义控制台应用程序的入口点。 #include #include #include #include using namespace std; const int NODENUM=100;//最大节点数 map const int MaxWordLength=8;//词的最大长度 const int MinWordLength=2;//词的最小长度 float prob[NODENUM];//每个节点的最大累计概率 int prevNode[NODENUM];//每个节点的最优前趋节点 const string strDelimiter=" ";//分词分割符 void LoadDict() { mapWord2Prob["有"]=0.018; mapWord2Prob["有意"]=0.0005; mapWord2Prob["意见"]=0.001; mapWord2Prob["见"]=0.0002; mapWord2Prob["分歧"]=0.0001; } //词作为边 struct edgeNode { string termText;//词 int start;//词的开始位置 int end;//词的结束位置 float prob;//词在语料库中出现的频率或者概率 }; //分割位置作为点 struct vexNode { int nSegNo; //分割节点编号 list }; //存储节点信息 vexNode adjlist[NODENUM]; //建立邻接表存储 void InitialGraph() { int i=0; for(i=0;i { adjlist[i].nSegNo=i; } } //插入一条边 void InsertEdge(edgeNode & newEdgeNode) { int v1=newEdgeNode.end; adjlist[v1].linkedlist.push_front(newEdgeNode); } //形成切分词图 void CreateWordSegGraph(string s) { short i=0; short j=0; short len=0; short restlen=0; short n=s.length(); float freq=0; string w; for(j=0;j { for(len=2;len<=MaxWordLength;len+=2) { restlen=n-j; if (len<=restlen) // 如果剩余词长度不够长，跳出循环 { w=s.substr(j,len); } else { break; } if (mapWord2Prob.find(w) != mapWord2Prob.end()) { freq=mapWord2Prob[w]; } else { freq=100; } if(freq != 100) { edgeNode stCandidateWord; stCandidateWord.termText=w; stCandidateWord.start=j/MinWordLength; stCandidateWord.end=(j+len)/MinWordLength; stCandidateWord.prob = freq; cout<<"插入一条边word "< InsertEdge(stCandidateWord); } } } } //寻找i的最佳前趋词 void getPrev(int i) { vexNode oVexNode=adjlist[i]; edgeNode oEdgeNode; list //得到前驱词的集合 float maxProb = 0; int maxNode = -1; //根据前驱词集合挑选最佳前趋节点 for(itList=oVexNode.linkedlist.begin(); itList!=oVexNode.linkedlist.end();itList++ ) { float nodeProb = prob[itList->start]+itList->prob;//候选节点概率 cout<<"搜索结点"< if (nodeProb > maxProb) { //候选节点概率最大的开始节点就是最佳前趋节点 maxNode = itList->start; maxProb = nodeProb; } } prob[i] = maxProb;//节点概率 prevNode[i] = maxNode;//最佳前驱节点 cout<<"节点"< } //回溯求最佳分割点 string BestSeg(string strSequence) { string strSeg=""; int nLeft=0; int nRight=0; for(int i=strSequence.length()/MinWordLength; i>0;i=prevNode[i]) { cout<<"最佳路径结点"< nRight=i; nLeft=prevNode[i]; cout<<"词"< strSeg=strSequence.substr(nLeft*MinWordLength,(nRight-nLeft)*MinWordLength)+strDeli miter+strSeg; } return strSeg; } int main(int argc, char * argv[]) //int _tmain(int argc, _TCHAR* argv[]) { LoadDict(); InitialGraph(); for (int i=0;i 数据挖掘分类算法比较 分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。通过对当前数据挖掘中具有代表性的优秀分类算法进行分析和比较，总结出了各种算法的特性，为使用者选择算法或研究者改进算法提供了依据。 一、决策树（Decision Trees） 决策树的优点： 1、决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。 2、对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。 3、能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。 4、决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。 5、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。 6、在相对短的时间内能够对大型数据源做出可行且效果良好的结果。 7、可以对有许多属性的数据集构造决策树。 8、决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。 决策树的缺点： 1、对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。 2、决策树处理缺失数据时的困难。 3、过度拟合问题的出现。 4、忽略数据集中属性之间的相关性。 二、人工神经网络 人工神经网络的优点：分类的准确度高,并行分布处理能力强,分布存储及学习能力强，对噪声神经有较强的鲁棒性和容错能力，能充分逼近复杂的非线性关系，具备联想记忆的功能等。 人工神经网络的缺点：神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值；不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度；学习时间过长,甚至可能达不到学习的目的。 https://www.wendangku.net/doc/bd16225482.html, 二元语法（2-gram）分词中的平滑算法_光环大数据培训 从一年前的计算语言学作业开始，我一直没明白，为什么我写的二元语法分词要比一元语法差。两天来我仔细分析了一下之前的实验细节，发现二元语法分词要超过一元语法，可以有两种方式：1.超大的语料；2.强大的平滑算法。 实验采用北大人民日报1-6月语料，大约700万字，选其中90%作为训练数据，另外10%作为测试数据。先看下实验结果： 分词方法准确率召回率 F值 最大正向匹配 0.9040 0.9189 0.9114 一元语法 0.9280 0.9502 0.9389 二元语法（+1平滑） 0.9093 0.9276 0.9184 二元语法（+eps平滑） 0.9102 0.9529 0.9311 二元语法（删除插值） 0.9317 0.9615 0.9463 一元语法引入了词频信息，效果对最大正相匹配有很大的提高。但是奇怪的是，二元语法（用前两种平滑算法）居然比一元语法的效果更差，问题在哪呢？ 经过测试，在测试语料中，二元语法的最短路径（参考《SharpICTCLAS分词系统简介(2)初步分词》的思路）上，平均每个段落有12处 p(wn|wn?1)=0。这就意味着700万字的训练数据还是不够大，平滑算法在这里需要起到非常重要的作用。 下面简单看看几种平滑算法的“含义”。 https://www.wendangku.net/doc/bd16225482.html, +1 平滑、+ε平滑 p(wn|wn?1)=f(wn?1wn)+1f(wn?1)+m 对于f(wn?1wn)=0的情况，式子会退化成 p(wn|wn?1)=1f(wn?1)+m。也就是说，如果前词频率越大，则认为后词出现的概率就越小。 删除插值法 p(wn|wn?1)=(1?λ)p′(wn|wn?1)+λp′(wn) 直观地说，这就是二元语法和一元语法的简单线性融合。 这种平滑算法在p′(wn|wn?1)=0时会退化成 p(wn|wn?1)=λp′(wn)。也就是说，后词词频越大，则认为后词出现的概率就越大。 实际上这也只是两种不同方法（一元、二元语法）的融合，因为 p′(wn|wn?1) 和p′(wn) 这一个条件概率、一个概率直接加权没有什么物理意义，只是单纯地“平滑”了一下。 总结 两种平滑方式很有意思。当出现数据稀疏时，一种只看前词的出现频率，一种只看后词的出现频率来进行估计。从结果看，还是后者略好。 平滑……又是一个调参的过程，参数调不好，再NB的算法也没用……简直就是NB的参数胜过NB的方法啊。但是不管怎样，最终还是得靠好方法来撑腰。 上面的实验还停留在“远古时期”，在现在有大规模语料的实际情况下，二元语法的数据稀疏问题已经基本消失了。在别的问题中，数据稀疏问题还是经常存在，选取好的平滑方法和参数，仍然是一个重要的问题。 前面我们讲个搜索引擎如何搜集网页,今天说下第二个过程网页预处理,其中中文分词就显得尤其重要,下面就详细讲解一下搜索引擎是怎么进行网页预处理的: 网页预处理的第一步就是为原始网页建立索引，有了索引就可以为搜索引擎提供网页快照功能;接下来针对索引网页库进行网页切分，将每一篇网页转化为一组词的集合;最后将网页到索引词的映射转化为索引词到网页的映射，形成倒排文件(包括倒排表和索引词表)，同时将网页中包含的不重复的索引词汇聚成索引词表。如下图所示: 一个原始网页库由若干个记录组成，每个记录包括记录头部信息(HEAD)和数据(DATA)，每个数据由网页头信息(header)，网页内容信息(content)组成。索引网页库的任务就是完成给定一个URL，在原始网页库中定位到该URL所指向的记录。 如下图所示: 对索引网页库信息进行预处理包括网页分析和建立倒排文件索引两个部分。中文自动分词是网页分析的前提。文档由被称作特征项的索引词(词或者字)组成，网页分析是将一个文档表示为特征项的过程。在对中文文本进行自动分析前，先将整句切割成小的词汇单元，即中文分词(或中文切词)。切词软件中使用的基本词典包括词条及其对应词频。 自动分词的基本方法有两种：基于字符串匹配的分词方法和基于统计的分词方法。 1) 基于字符串匹配的分词方法 这种方法又称为机械分词方法，它是按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功(识别出一个词)。 按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配;按照不同长度优先匹配的情况，可以分为最大或最长匹配，和最小或最短匹配;按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下： 一种基于词典的中文分词法的设计与实 现 摘要：中文分词就是把没有明显分隔标志的中文字串切分为词串，它是其他中文信息处理的基础，广泛应用于搜索引擎、自动翻译、语音合成、自动分类、自动摘要、自动校对等领域。就中文分词的基本方法作了简单阐述，并介绍了一种基于词典采用最大匹配法实现中文分词的方法。 关键词：中文分词；词库索引；正向最大匹配法 1 中文分词 中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解？其处理过程就是分词算法。 1.1中文分词方法的种类 中文自动分词方法有多种，一般来说大致可归结为以下三大类：基于词典的分词方法、基于统计的分词方法、基于规则和基于统计相结合的分词方法[2]。1.1.1基于词典的分词方法。基于词典的分词方法，又叫做基于字符串匹配的分词方法。其基本思想是：事先建立词库，其中包含所有可能出现的词。对于给定的待分词的汉子串Str，按照某种确定的原则切取Str 的子串，若该子串与词库中的某词条相匹配，则该子串是就是词，继续分割其余的部分，直到剩余部分为空；否则，该子串不是词，转到上面重新切取Str的子串进行匹配。1.1.2基于统计的分词方法。基于词典分词方法要借助词典来进行，而中文的构词非常灵活，词的数目几乎是无限的，因此要构造完备的词典几乎是不可能的。鉴于上述分词方法存在的这些缺点，一种基于统计的分词方法应运而生。这种方法撇开词典，根据字串出现的频率来判断这个字串是否是词。该方法对于大的语料，分全率还可以，但是对于小的语料分全率就比较低。该方法的另一个缺点就是不够准确，有些经常一起出现的单字构成的字串其实不是词。但是由于出现的频率很高，就被分出来当作词处理了，而且这样的“词”还非常多, 例如“这一”、“之一”、“有的”、“我的”、“许多的”等。实际应用的统计分词系统都要使用一部基本的分词词典进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。1.1.3基于规则和基于统计相结合的分词方法。该方法首先运用最大匹配作初步切分，然后对切分的边界处进行歧义探测，发现歧义，最后运用统计和规则相结合的方法来判断正确的切分[4]。运用不同的规则解决人名、地名、机构名识别，运用词法结构规则来生成复合词和衍生词。日前这种方法可以解决汉语中最常见的歧义类型：单字交集型歧义。并对人名、地名、机构名、后缀、动词/形容词重叠、衍生词等词法结构进行识别处理，基本解决了分词所面临的最关键的问题。若词典结构和算法设计优秀，分词速度将非常快。 1.2分词中的难题 有了成熟的分词算法，是否就能容易的解决中文分词的问题呢？事实远非如此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词过程中，有两大难题一直没有完全突破。1.2.1歧义识别。歧义是指同样的一句话，可能有两种或者更多的切分方法。例如：“表面的”，因为“表面”和“面的”都是词，那么这个短语就可以分成“表面的”和“表面的”，这种称为交叉歧义，像这种交叉歧义十分常见。“化妆和服装”可以分成“化妆和服装”或者“化妆和服装”。由于没有人的知识去理解，计算机很难知道到底哪个方案正确。交叉歧义 Baidu查询分词算法 查询处理以及分词技术 如何设计一个高效的搜索引擎?我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎.搜索引擎涉及到许多技术点,比如查询处理,排序算法,页面抓取算法,CACHE机制,ANTI-SPAM等等.这些技术细节,作为商业公司的搜索引擎服务提供商比如百度,GOOGLE等是不会公之于众的.我们可以将现有的搜索引擎看作一个黑盒,通过向黑盒提交输入,判断黑盒返回的输出大致判断黑盒里面不为人知的技术细节. 查询处理与分词是一个中文搜索引擎必不可少的工作,而百度作为一个典型的中文搜索引擎一直强调其”中文处理”方面具有其它搜索引擎所不具有的关键技术和优势.那么我们就来看看百度到底采用了哪些所谓的核心技术. 我们分两个部分来讲述:查询处理/中文分词. 一. 查询处理 用户向搜索引擎提交查询,搜索引擎一般在接受到用户查询后要做一些处理,然后在索引数据库里面提取相关的信息.那么百度在接受到用户查询后做了些什么工作呢? 1. 假设用户提交了不只一个查询串,比如”信息检索理论工具”.那么搜 索引擎首先做的是根据分隔符比如空格,标点符号,将查询串分割成若干子查询串,比如上面的查询就会被解析为:<信息检索,理论,工具>三个子字符串;这个道理 简单,我们接着往下看. 2. 假设提交的查询有重复的内容,搜索引擎怎么处理呢?比如查询”理论 工具理论”,百度是将重复的字符串当作只出现过一次,也就是处理成等价的”理论工具”,而GOOGLE显然是没有进行归并,而是将重复查询子串的权重增大进行处理.那么是如何得出这个结论的呢?我们可以将”理论工具”提交给百度,返回341,000篇文档,大致看看第一页的返回内容.OK.继续,我们提交查询”理论工具理论”,在看看返回结果,仍然是那么多返回文档,当然这个不能说明太多问题,那 看看第一页返回结果的排序,看出来了吗?顺序完全没有变化,而GOOGLE则排序有些变动,这说明百度是将重复的查询归并成一个处理的,而且字符串之间的先后出现顺序基本不予考虑(GOOGLE是考虑了这个顺序关系的). 3. 假设提交的中文查询包含英文单词,搜索引擎是怎么处理的?比如查询”电影BT下载”,百度的方法是将中文字符串中的英文当作一个整体保留,并以此为断点将中文切分开,这样上述的查询就切为<电影,BT,下载>,不论中间的英文是否一个字典里能查到的单词也好,还是随机的字符也好,都会当作一个整体来对待. 聚类分析算法解析 一、不相似矩阵计算 1.加载数据 data(iris) str(iris) 分类分析是无指导的分类，所以删除数据中的原分类变量。 iris$Species<-NULL 2. 不相似矩阵计算 不相似矩阵计算，也就是距离矩阵计算，在R中采用dist()函数，或者cluster包中的daisy()函数。dist()函数的基本形式是 dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2) 其中x是数据框（数据集），而方法可以指定为欧式距离"euclidean", 最大距离"maximum", 绝对值距离"manhattan", "canberra", 二进制距离非对称"binary" 和明氏距离"minkowski"。默认是计算欧式距离，所有的属性必须是相同的类型。比如都是连续类型，或者都是二值类型。 dd<-dist(iris) str(dd) 距离矩阵可以使用as.matrix()函数转化了矩阵的形式，方便显示。Iris数据共150例样本间距离矩阵为150行列的方阵。下面显示了1~5号样本间的欧式距离。 dd<-as.matrix(dd) 二、用hclust()进行谱系聚类法（层次聚类） 1.聚类函数 R中自带的聚类函数是hclust()，为谱系聚类法。基本的函数指令是 结果对象<- hclust（距离对象, method=方法） hclust()可以使用的类间距离计算方法包含离差法"ward"，最短距离法"single"，最大距离法"complete"，平均距离法"average"，"mcquitty"，中位数法"median" 和重心法"centroid"。下面采用平均距离法聚类。 hc <- hclust(dist(iris), method="ave") 2.聚类函数的结果 聚类结果对象包含很多聚类分析的结果，可以使用数据分量的方法列出相应的计算结果。 str(hc) 下面列出了聚类结果对象hc包含的merge和height结果值的前6个。其行编号表示聚类过程的步骤，X1，X2表示在该步合并的两类，该编号为负代表原始的样本序号，编号为正代表新合成的类；变量height表示合并时两类类间距离。比如第1步，合并的是样本102和143，其样本间距离是0.0，合并后的类则使用该步的步数编号代表，即样本-102和-143合并为1类。再如第6行表示样本11和49合并，该两个样本的类间距离是0.1，合并后的类称为6类。 head (hc$merge,hc$height) 基于二级Hash的快速最长匹配分词算法 殷鹏程，谭献海 西南交通大学，四川成都（610031） E-mail：ypc_swjtu@https://www.wendangku.net/doc/bd16225482.html, 摘要：中文分词是中文信息处理的基础，在海量的中文信息处理中，分词速度至关重要。本文根据中文单词的特点，通过分析现有词典分词算法，提出了一种基于二级Hash的快速最长匹配分词算法。试验结果表明，该算法保证了分词的最长匹配，同时提高了分词的速度，适用于小型搜索引擎和自动文本分类等应用。 关键词：中文分词；Hash词典；最长匹配 1. 引言 在中文信息处理中, 如机器翻译、自动分类等等，词是最小的具有独立活动的有意义的语言成分。然而中文文本在计算机内部表示时，不像英文中词与词之间都有空格隔开，中文词与词之间没有明显的分隔标记, 而是连续的汉字串。因此, 自动识别词的边界, 将连续的汉字串切分为带有分割标记的词串将是实现中文信息处理的首要问题。 现有的分词算法可分为三大类：基于词典的分词方法、基于理解的分词方法和基于统计的分词方法。无论哪种分词方法都需要将大量时间用于将待切分语句的切分为可能的词，然后再依据统计或语法方面的规则对切分出的词进行处理，得到一种最有可能的切分结果。如果能加快初始切分的速度，对于提高整个分词算法的速度也会有很大帮助。由于词语信息都以词典的形式存储, 所以在整个汉语分词过程中, 都需要频繁地访问词典以获得词语信息。因此词典的查询速度是整个分词系统处理效率的关键所在。 现行常用的词典数据结构主要基于Hash方法和索引树方法，根据汉字编码的一对一映射关系，实现了词典的快速查询，但两种方法在构造词典时都没有考虑词语的长度这个关键信息，因此不适合最长匹配算法。本文在Hash方法的基础上，提出一种新的词典结构，不仅对词语的首字进行Hash，而且根据词语的长度进行二次Hash。实验证明，新的词典结构不仅提高了分词速度，而且满足最长匹配的分词需求。 2．二级Hash词典的设计 为了提高分词的准确度，基于词典的分词方法通常采用最长匹配算法。实验证明，如果分成的词语越长、分出的词语越少，分词的精确度就越高。通常基于Hash方法的词典只对词语的首字符进行了Hash，这样的词典虽然能实现快速查询，但是如果采用最长匹配算法，则需要对词典进行多次查询，影响算法速度。为了使词典更适合最长匹配算法，通过对对汉字编码体系、汉语词语特点的分析，针对传统Hash词典的缺点，本文设计了一种基于二级Hash的词典结构。 2.1 汉字编码体系 汉字在计算机内部是以内码的形式进行存储的，汉字内码是汉字在汉字信息处理系统中最基本的表达形式，它与汉字交换码、汉字区位码有一定的对应关系。由于自定义编码顺序的特殊性，因而，可通过计算偏移量的方法来定位该汉字在编码表中任意的位置。国标GB2312汉字编码表共收录了6763个汉字，汉字在编码表中的偏移量计算公式如下： offset = (ch1 – 0xB0) * 94 + (ch2 – 0xA1) (1) 其中，offset代表某汉字在编码表中的位置， ch1、ch2代表汉字的内部码。 2.2 汉语词的特点 搜索引擎优化百度分词算法分析查询处理以及分词技术 随着搜索经济的崛起，人们开始越加关注全球各大搜索引擎的性能、技术和日流量。作为企业，会根据搜索引擎的知名度以及日流量来选择是否要投放丿告等； 作为普通网民，会根据搜索引擎的性能和技术来选择自己喜欢的引擎查找资料；作为技术人员，会把有代表性的搜索引擎作为研究对象。搜索引擎经济的崛起，又一次向人们证明了网络所蕴藏的巨大商机。网络离开了搜索将只剩下空洞杂乱的数据，以及大量等待去费力挖掘的金矿。 但是，如何设计一个高效的搜索引擎？我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎。搜索引擎涉及到许多技术点，比如查询处理，排序算法，页面抓取算法，CACH机制，ANTI-SPAM等等。这些技术细节，作为商业公司的搜索引擎服务提供商比如百度，GOOGL等是不会公之于众的。 我们可以将现有的搜索引擎看作一个黑盒，通过向黑盒提交输入，判断黑盒返回的输出大致判断黑盒里面不为人知的技术细节。 查询处理与分词是一个中文搜索引擎必不可少的工作，而百度作为一个典型的中文搜索引擎一直强调其"中文处理"方面具有其它搜索引擎所不具有的关键技术和优势。那么我们就来看看百度到底采用了哪些所谓的核心技术。 我们分两个部分来讲述：查询处理/中文分词。 一、查询处理 用户向搜索引擎提交查询，搜索引擎一般在接受到用户查询后要做一些处理，然后在索引数据库里面提取相关的信息。那么百度在接受到用户查询后做了些什么工作呢？ 1、假设用户提交了不只一个查询串，比如"信息检索理论工具"。 那么搜索引擎首先做的是根据分隔符比如空格，标点符号，将查询串分割成若 干子查询串，比如上面的查询就会被解析为：信息检索，理论，工具三个子字符串；这个道理简单，我们接着往下看。 2、假设提交的查询有重复的内容，搜索引擎怎么处理呢？比如查询"理论工具理论"，百度是将重复的字符串当作只出现过一次，也就是处理成等价的"理 论工具"，而GOOGL显然是没有进行归并，而是将重复查询子串的权重增大进行处理。那么是如何得出这个结论的呢？我们可以将"理论工具"提交给百度，返回341,000篇文档，大致看看第一页的返回内容。 OK继续，我们提交查询"理论工具理论"，在看看返回结果，仍然是那么多返回文档，当然这个不能说明太多问题，那看看第一页返回结果的排序，看出来了吗？顺序完全没有变化，而GOOGL E排序有些变动，这说明百度是将重复的查询归并成一个处理的，而且字符串之间的先后出现顺序基本不予考虑（GOOGL是考虑了这个顺序关系的）。 3、假设提交的中文查询包含英文单词，搜索引擎是怎么处理的？比如查询" 电影BT下载"，百度的方法是将中文字符串中的英文当作一个整体保留，并以 此为断点将中文切分开，这样上述的查询就切为电影，BT,下载，不论中间的 英文是否一个字典里能查到的单词也好，还是随机的字符也好，都会当作一个整体来对待。至于为什么，你用查询"电影dfdfdf下载"看看结果就知道了。当然如果查询中包含数字，也是如此办理。 到目前为止，一切很简单，也很清楚，百度怎么处理用户查询的呢？归纳如下：首先根据分割符号将查询分开，然后看看是否有重复的字符串，如果有，就抛弃多余的，只保留一个，接着判断是否有英文或者数字，如果有的话，把英文或者数字当作一个整体保留并把前后的中文切开。 接着该干什么呢？该考虑分词的问题了。 二、中文分词 首先，讲讲百度的分词时机或者条件问题，是否是个中文字符串百度就拿来切一下呢？非也，要想被百度的分词程序荣幸的切割一下也是要讲条件的，哪能是个字符串就切割啊？你当百度是卖锯条的么？ 一、为什么要进行中文分词？ 词是最小的能够独立活动的有意义的语言成分，英文单词之间是以空格作为自然分界符的，而汉语是以字为基本的书写单位，词语之间没有明显的区分标记，因此，中文词语分析是中文信息处理的基础与关键。 Lucene中对中文的处理是基于自动切分的单字切分，或者二元切分。除此之外，还有最大切分（包括向前、向后、以及前后相结合）、最少切分、全切分等等。 二、中文分词技术的分类 我们讨论的分词算法可分为三大类：基于字典、词库匹配的分词方法；基于词频度统计的分词方法和基于知识理解的分词方法。 第一类方法应用词典匹配、汉语词法或其它汉语语言知识进行分词，如：最大匹配法、最小分词方法等。这类方法简单、分词效率较高,但汉语语言现象复杂丰富，词典的完备性、规则的一致性等问题使其难以适应开放的大规模文本的分词处理。第二类基于统计的分词方法则基于字和词的统计信息，如把相邻字间的信息、词频及相应的共现信息等应用于分词，由于这些信息是通过调查真实语料而取得的，因而基于统计的分词方法具有较好的实用性。 下面简要介绍几种常用方法: 1）．逐词遍历法。 逐词遍历法将词典中的所有词按由长到短的顺序在文章中逐字搜索,直至文章结束。也就是说,不管文章有多短,词典有多大,都要将词典遍历一遍。这种方法效率比较低，大一点的系统一般都不使用。 2）．基于字典、词库匹配的分词方法（机械分词法） 这种方法按照一定策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。识别出一个词，根据扫描方向的不同分为正向匹配和逆向匹配。根据不同长度优先匹配的情况，分为最大（最长）匹配和最小（最短）匹配。根据与词性标注过程是否相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的方法如下： （一）最大正向匹配法 (ＭａｘｉｍｕｍＭａｔｃｈｉｎｇＭｅｔｈｏｄ)通常简称为ＭＭ法。其基本思想为：假定分词词典中的最长词有i个汉字字符，则用被处理文档的当前字串中的前i个字作为匹配字段，查找字典。若字典中存在这样的一个i字词，则匹配成功，匹配字段被作为一个词切分出来。如果词典中找不到这样的一个i字词，则匹配失败，将匹配字段中的最后一个字去掉，对剩下的字串重新进行匹配处理……如此进行下去，直到匹配成功，即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配，然后取下一个i字字串进行匹配处理，直到文档被扫描完为止。 中文搜索引擎的自动分词算法 !"#$%&’#(#($)!*+$’(#,-.$/#,01,()0.01,&’&2#0’30&’2,4)+()0 蒋 微5 西南财经大学成都 67889:; <摘要=提出了基于关键词搜索的两种自动分词算法>均以双词及三词作为搜索的最小单位5或基本单位;> 一种以栈实现?一种不借助栈且动态匹配实现>通过此两种算法均可进行发布网站@网页前网名入数据库的关键词标识提取及实现匹配后有效性的确认?以提高中文搜索引擎的搜索准确率及获得由网名入数据库前后同步性决定的快速响应>< 关键词=中文搜索引擎?自动分词?栈?非栈?关键词搜索 !A 3B C !1B D E FG H I F J G K I L I L F MG N O F K L I P Q RS G R T UF MV T W E F K UR T G K X P L M OG K TO L Y T ML MI P L RG K I L X N T ?L ME P L X PI E FE F K U RF K I P K T T E F K U R G K T H R T U G R I P T Q L M L Q H Q H M L I 5F K S G R L X H M L I ;L MR T G K X P L M O ?F M T L R L Q J N T Q T M I T U S W H R T F Z R I G X V ?G M U I P T F I P T K L R M F I S H I S W I P T E G W F Z U W M G Q L X Q G I X P L M O [\F I PG N O F K L I P Q R X G MT ]I K G X I I P T V T W E F K U L U T M I L Z L X G I L F MZ K F Q G M T I E F K VM G Q T T M I T K L M O I P T U G I G S G R T S T Z F K T S K F G U X G R I M T I M F U ?Z K F M I J G O T ?G M U X F M Z L K Q I P T Y G N L U L I W G Z I T K Q G I X P L M O R F G R I F L Q J K F Y T I P T P L O PG X X H K G X W F Z ^P L M T R T X P G K G X I T K R T G K X P T M O L M OG M UG X P L T Y T _H L X VK T R J F M R T U T I T K Q L M T US WR W M X P K F M L R Q S T Z F K T G M UG Z I T K M T I E F K VM G Q T T M I T K L M OI P T U G I G S G R T [‘4a bc C d 3^P L M T R T X P G K G X I T K R T G K X PT M O L M O ?G H I F J G K I L I L F M ?R I G X V ?M F M R I G X V ?V T W E F K UR T G K X P 自动分词系统是为中文搜索做预期和基础性的工作>通过常用词库的支持?它能在一定程度上智能地根据用户需要搜索到相关网站@网页及内容>本文将以类^语言描述两种不同的分词算法> e 算法的支撑 e [e 操作对象 定义75双词;f 存在于词库中以两个字构成的常用词> 定义g 5三词;f 存在于词库中以三个字构成的常用词> 算法的操作对象?即基本单位为双词或三词>范围缩小的依据为f h 单字词应以直接匹配的方式实现i j 四字或五字构成的词可用直接匹配的方式实现?其中可分解成若干双词或三词的词也可用逻辑组合的方式实现搜索> e [k 基本词词性针对网名?l 自动分词m 的分词范围缩小在动词和名词上? 其余为非重要成分>e [n 词库 作为自动分词系统的基础和载体?词库是必然的>要求对汉语常用词作穷举式的逐一调整录入?并以名词和动词进行分类得到词库>词库是本文算法的前提> k 算法的实现 k [e 算法 k [e [e 算法框架 此算法从左至右?以双词为基准?向右扩展>若发 现同一个字或一个词包含在左右相邻的两常用词内?则经判断分析?筛选出合乎逻辑的关键词入关键词组? 防止了l 断章取义m 的可能>特点为实现了无回溯的确定性算法> 注意f 此算法以双词为研究起点?同时进行关键词为三个字的词即三词的提取>前两字不为词?三个字才 为词的情况由子程序X P G K o p T ]I qF K U 5X F M R I X P G K o ;解决> k [e [k 算法的实现 变量说明f R H Q rr 关键词计数器> s \ rr 作为当前基准的双词对象>V T W t u rr 关键词组>v D r 当前双词向右扩展一位所得为三词> \ r 当前双词的右两个字组成双词>w r 当前双词的右字向右扩展一位成双词> D r 当前双词的右三个字组成三词> o g 88g 8789收到?g 88g 8x g y 改回 oo 蒋微?女?7y z 7年生?y y 级在读本科生? 攻读方向f 信息工程?信息管理>{6g {5 总g z z ;中文搜索引擎的自动分词算法 g 88g 年 《汉语分词的主要技术及其应用展望》 一、汉语自动分词的提出 词具有语音、语义和结构三大特征，其语义特征表现在必须具备一定的意义，表明客观现实中的某一事物的性质、特征、行为和关系等，没有意义的词是不存在的。词里包含有两种不同性质的意义：词汇意义和语法意义。词的结构特征表现在词在结构上是一个不可分割的整体，其意义不是它的几个构成成分（如果存在的话）的意义的简单总和。 人们在阅读时，大脑有一个模糊的分词过程，它是与视觉到声音的转换和语义理解交叉或同时进行的，并以语感的形式体现出来，由于文化修养和知识水平的差异，不同的人对词和非词，词和词组的预感差别很大。因而人工分词的同一性得不到保证。北京航空学院曾做过一个实验，三十余个具有高中文化水平的青年对五百字的一个语言材料人工分词，同一率只有50%左右。在大篇文字材料处理时，人工分词不仅速度慢，长时间单调枯燥工作也使错误切分次数大大增加。这些都表明人工分词不能满足汉字处理现代化的要求，但要对书面汉语实现计算机自动分词，并非易事，这与汉语特性有很大关系。与印欧语系相比，现代汉语至少在四个方面于分词不利：第一，汉语的词不分写，而且词无明确的形态标志，这给计算机进行汉语的词法分析带来一大障碍。其次，汉语是一种无形态变化的分析型语言，缺乏明显的句法形式标记，其语法主要靠虚词和不同的词序来实现。第三，汉语的形态不发达，增加了语言的表层结构对语义的依赖性，所以，汉语句子成分的语法作用强烈依赖于该成分的意义。第四，汉语构词具有极大的灵活性和自由性。只要词汇意义和语言习惯允许，就能组合起来，没有限制。如果在自动分词处理时，既不进行语法分析，也不进行语义理解，只是机械的匹配比较，那很容易实现，但必然会出现许多错误切分，而要提高分词精度，就必须进行语法分析和语义理解，于是就引发了一系列耐人寻味的问题。 汉语词自动切分是计算机中文信息处理的第一步，也是计算机科学界、语言文字学界以及信息管理学界所面临的挑战性难题，这一“瓶颈”的解决是计算机自然语言理解、人工智能、信息检索、机器翻译和自动文摘等领域突破的关键, 长期以来一直困扰着这一研究领域的许多专家学者。尽管汉语词自动切分研究已经取得了可喜的进展，但是在汉语词的规范、自动分词算法突破、切分歧义处理、自然语言理解和人工智能等诸多领域还存在着难以克服的阻碍，仍需要多个学科领域的专家学者们通力协作，才能获得新的突破。 二、现有的分词方法 为了克服汉语词计算机自动切分这一难题, 许多年来, 大量的学者都加入 了这一领域的研究, 使汉语自动分词取得了丰硕的研究成果。近年来, 语言学 界、人工智能领域和情报检索界的学者们, 在汉语自动分词与自动标引的研究 与实践上进行了大量的研究, 找到了许多解决汉语分词的方法，归纳起来有: 最大匹配法、逆向最大匹配法、逐词遍历法、设立切分标志法、最佳匹配法、 有穷多层次列举法、二次扫描法、高频优先分词法、基于期望的分词法、联想 ——回溯法、双向扫描法、邻接约束法、扩充转移网络分词法、语境相关法、 中文分词 一、概述 什么是中文分词 众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。例如，英文句子I am a student，用中文则为：“我是一个学生”。计算机可以很简单通过空格知道student是一个单词，但是不能很容易明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。我是一个学生，分词的结果是：我是一个学生。 中文分词技术 中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解？其处理过程就是分词算法。 现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。 1、基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下： 1）正向最大匹配法（由左到右的方向）； 2）逆向最大匹配法（由右到左的方向）； 3）最少切分（使每一句中切出的词数最小）。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机 很多算法的每一个计算步骤都是固定的，而在下面我们要讨论的概率算法，允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。 概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完 全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类:数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。 数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。 蒙特卡罗算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。 拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。 舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。 1 最大匹配法（Forward Maximum Matching method, FMM法）：选取包含6-8个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从右向左。 逆向最大匹配法（Backward Maximum Matching method, BMM法）：匹配方向与MM法相反，是从左向右。实验表明：对于汉语来说，逆向最大匹配法比最大匹配法更有效。 给定串：我是中国人 从左往右最长匹配优先： 读入‘我’，一个字当然是一个词 再读入‘是’，查表找‘我是’，不在表中，则‘我’是一个独立的词，‘是’还要下一步判断 读入‘中’‘是中’肯定不在表内，那‘是’也是一个独立的词，‘中’还要下一步判断 读入‘果’，‘中国’在表内 再读入‘人’，’中国人‘也在表内， 此时全部读完，’中国人‘是一个次 结果就是：我是中国人 从右往左也类似 最近折腾毕业论文，搞得人没心情写blog了。于是觉得不如把毕业论文里的东西贴出来当blog算了。这里主要介绍了我自己的中文分词算法，我觉得它比现在开源代码比较多的中文匹配法要好多了。这里的内容没有任何背景知识啥的，毕竟论文里的背景知道我也是从网上粘贴的，呵呵！因此这篇文章的内容可能适合做搜索引擎的人。如果要了解中文分词算法在搜索引擎中的重要性，或者最大匹配法的思想与过程，请去网上搜吧，资料还是蛮多的。 1.1.1 最大匹配法分词的缺陷 尽管最大匹配法分词是常用的解决的方案，但是无疑它存在很多明显的缺陷，这些缺陷也限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题有以下几点： 一、长度限制 由于最大匹配法必须首先设定一个匹配词长的初始值，这个长度限制是最大匹配法在效率与词长之间的一种妥协。我们来看一下以下两种情况： 分词技术研究报告 研究内容 目前,国内的每个行业、领域都在飞速发展,这中间产生了大量的中文信息资源,为了能够及时准确的获取最新的信息,中文搜索引擎是必然的产物。中文搜索引擎与西文搜索引擎在实现的机制和原理上大致雷同,但由于汉语本身的特点,必须引入对于中文语言的处理技术,而汉语自动分词技术就是其中很关键的部分。汉语自动分词到底对搜索引擎有多大影响？对于搜索引擎来说,最重要的并不是找到所有结果,最重要的是把最相关的结果排在最前面,这也称为相关度排序。中文分词的准确与否,常常直接影响到对搜索结果的相关度排序。分词准确性对搜索引擎来说十分重要,但如果分词速度太慢,即使准确性再高,对于搜索引擎来说也是不可用的,因为搜索引擎需要处理数以亿计的网页,如果分词耗用的时间过长,会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说,分词的准确性和速度,二者都需要达到很高的要求。 研究汉语自动分词算法,对中文搜索引擎的发展具有至关重要的意义。快速准确的汉语自动分词是高效中文搜索引擎的必要前提。本课题研究中文搜索引擎中汉语自动分词系统的设计与实现,从目前中文搜索引擎的发展现状出发,引出中文搜索引擎的关键技术------汉语自动分词系统的设计。首先研究和比较了几种典型的汉语自动分词词典机制,指出各词典机制的优缺点,然后分析和比较了几种主要的 汉语自动分词方法,阐述了各种分词方法的技术特点。针对课题的具体应用领域,提出改进词典的数据结构,根据汉语中二字词较多的特点,通过快速判断二字词来优化速度；分析中文搜索引擎下歧义处理和未登陆词处理的技术,提出了适合本课题的自动分词算法,并给出该系统的具体实现。最后对系统从分词速度和分词准确性方面进行了性能评价。本课题的研究将促进中文搜索引擎和汉语自动分词新的发展。 二、汉语自动分词系统的研究现状 1、几个早期的自动分词系统 自80年代初中文信息处理领域提出了自动分词以来,一些实用性的分词系统逐步得以开发,其中几个比较有代表性的自动分词系统在当时产生了较大的影响。 CDWS分词系统是我国第一个实用的自动分词系统,由北京航空航天大学计算机系于１９８３年设计实现,它采用的自动分词方法为最大匹配法,辅助以词尾字构词纠错技术。其分词速度为5-10字/秒,切分精度约为1/625。 ABWS是山西大学计算机系研制的自动分词系统,系统使用“两次扫描联想-回溯”方法,运用了较多的词法、句法等知识。其切分正确率为98.6%(不包括非常用、未登录的专用名词),运行速度为48词/分钟。 CASS是北京航空航天大学于1９８８年实现的分词系统。它使用正向增字最大匹配,运用知识库来处理歧义字段。其机械分词速度为 《统计计算》案例１,吕晓玲 应用潜在分类泊松回归模型及ＥＭ算法分析陈述偏好数据: 以网络购物使用次数为例 1． 问题提出 随着网络的兴起，网上购物已经在人们的生活中发挥着越来越重要的作用。网上购物以其方便快捷等特点吸引了很多购物者,但是也有一些人质疑网上购物安全性、不可触摸性等问题。影响人们选择网上购物的因素有很多，不同的人对网上购物也有不同的态度。大学生是网络购物这个群体的很重要的一部分，什么因素影响大学生对网络购物的选择？大学生由于对网络购物的态度取向不同可分为多少潜在的类别?本文应用陈述偏好方法（stat ｅd pr ｅｆerenc ｅ met ｈｏｄ)收集大学生网上购物的数据,并应用潜在分类泊松回归模型（l ａｔent ｃla ｓｓ P ｏi ｓs ｏｎ ｒe ｇｒession mode ｌ)及EM 算法分析数据，回答以上两个问题。 ２. 数据收集 源于心理学的陈述偏好调查已经被市场营销中研究消费者行为广泛应用。虽然在进行每个具体研究时操作不尽相同，总的原则是事先设定几个重要因素,每个因素有若干水平,然后提出一些假想情景，每个情景是这些因素不同水平的组合。受访者按照他们的喜好给不同的情景打分或者排序。研究者应用模型分析数据,寻找各因素的重要性。 为了确定影响网络购物的重要因素，我们首先开展了预调查，针对购买商品的种类、价格、邮费、卖家信用度、介绍商品详细程度以及网上购物节省时间和到货时间等因素对大学生进行了调查，并应用简单统计分析得到了对网上购物次数影响比较显著的四个因素,分别是购买商品的种类、价格、卖家信誉度以及介绍商品的详细程度。具体因素和因素水平如下所示: 种类:服饰,化妆品,文体 价格:50元,1００元，150元，200元,250元 卖家或网站的信誉度：１，2,3,4，5 介绍商品的详细程度：１，2,3,４,5 若每一种组合都进行调查则共有3555225???=组合，在这里运用了正交设计的方法进行试验设计，共进行75种不同的组合，将这75种组合分成25组，每组中包含3个场景(分别为3个不同的种类），每一个被调查者将被给定3个不同的场景。每个被调查者回答的问题是在特定的场景能够在十次购物中选择网上购物的可能次数。我们总共访问了197名在京大学生,得到了在588种场景下他们对网络购物的使用情况的有效回答。 3. 模型介绍 市场营销中常用的分析陈述偏好数据的方法是联合分析（c ｏnjoi ｎt an ａly ｓis ），我们这里使用泊松回归模型，因为：（1)因变量不是受访者对场景的排序,而是使用网络购物的次数,它是一个取值为离散整数的变量,可以假设服从泊松分布;（2）可以对泊松回归模型进一步应用潜在分类模型分析受访者的异质性。我们首先介绍泊松回归模型和潜在分类模型，然后介绍如何应用最大似然法和EM 算法估计参数。 令ij Y 为第i （I i ,...,1=）个个体在面临第j （J j ,...,1=)种场景时的选择，服从参数为ij λ的泊松分布。因为从平均的意义上来讲，ij λ取值越大意味着受访者越倾向于多次使用数据挖掘分类算法比较
二元语法(2-gram)分词中的平滑算法_光环大数据培训
中文分词切词超详细分析
一种基于词典的中文分词法的设计与实现
百度_baidu_搜索分词算法
聚类分析算法解析
基于二级Hash的快速最长匹配分词算法
搜索引擎优化百度分词算法分析
中文分词技术
中文搜索引擎的自动分词算法
分词方法详解
分词算法
概率算法
中文分词算法
分词技术研究报告-最新范文
应用潜在分类泊松回归模型及EM算法分析陈述偏好数据：