精华内容
下载资源
问答
  • Distributed Algorithms (中文名:分布式算法)
  • 最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法,分为正向和逆向,原理都是一样的。正向最大匹配算法,故思意,从左向右扫描寻找词的最大匹配。首先我们可以规定一个词的最大长度,每次扫描的时候寻找...

    最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法,分为正向和逆向,原理都是一样的。

    正向最大匹配算法,故名思意,从左向右扫描寻找词的最大匹配。

    首先我们可以规定一个词的最大长度,每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配,如果没有找到,就缩短长度继续寻找,直到找到或者成为单字。

    实例:

    S1="计算语言学课程是三个课时" ,设定最大词长MaxLen = 5  ,S2= " "

    字典中含有三个词:[计算语言学]、[课程]、[课时]

    (1)S2="";S1不为空,从S1左边取出候选子串W="计算语言学";

    (2)查词表,“计算语言学”在词表中,将W加入到S2中,S2=“计算语言学/  ”,        并将W从S1中去掉,此时S1="课程是三个课时";

    (3)S1不为空,于是从S1左边取出候选子串W="课程是三个";

    (4)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程是三";

    (5)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程是";

    (6)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程"

    (7)查词表,W在词表中,将W加入到S2中,S2=“计算语言学/  课程/  ”,并        将W从S1中去掉,此时S1="是三个课时";

    (8)S1不为空,于是从S1左边取出候选子串W="是三个课时";

    (9)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三个课";

    (10)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三个";

    (11)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三"

    (12)查词表,W不在词表中,将W最右边一个字去掉,得到W=“是”,这时     W是单字,将W加入到S2中,S2=“计算语言学/  课程/  是/  ”,并将     W从S1中去掉,此时S1="三个课时";

    (13)S1不为空,从S1左边取出候选子串W="三个课时";

    (14)查词表,W不在词表中,将W最右边一个字去掉,得到W="三个课";

    (15)查词表,W不在词表中,将W最右边一个字去掉,得到W="三个";

    (16)查词表,W不在词表中,将W最右边一个字去掉,得到W=“三”,这时     W是单字,将W加入到S2中,S2=“计算语言学/  课程/  是/  三/  ”,并    将W从S1中去掉,此时S1="个课时";

    (17)S1不为空,从S1左边取出候选子串W="个课时";

    (18)查词表,W不在词表中,将W最右边一个字去掉,得到W="个课";

    (19)查词表,W不在词表中,将W最右边一个字去掉,得到W=“个”,     这时W是单字,将W加入到S2中,S2=“计算语言学/  课程/  是/       三/  个/  ",并将W从S1中去掉,此时S1="课时";

    (20)S1不为空,从S1左边取出候选子串W="课时";

    (21)查词表,W在词表中,将W加入到S2中,S2=“计算语言学/  课程/       是/  三/  个/  课时/  ",并将W从S1中去掉,此时S1=""。

    (22)S1为空,输出S2作为分词结果,分词过程结束。

    中文分词算法的Python实现:

    脚本接受两个参数,一个是输入文件的路径,另一个是词典的路径。

    它的运行方法如下:

    python max-match.py

    #!/usr/bin/env python

    import cPickle as pickle

    import sys

    window_size=5

    def max_match_segment(line, dic):

    # write your code here

    chars = line.decode("utf8")

    words = []

    idx = 0

    while idx < len(chars):

    matched = False

    for i in xrange(window_size, 0, -1):

    cand=chars[idx:idx+i].encode("utf8")

    if cand in dic:

    words.append(cand)

    matched = True

    break

    if not matched:

    i = 1

    words.append(chars[idx].encode("utf8"))

    idx += i

    return words

    if __name__=="__main__":

    try:

    fpi=open(sys.argv[1], "r")

    except:

    print >> sys.stderr, "failed to open file"

    sys.exit(1)

    try:

    dic = pickle.load(open(sys.argv[2], "r"))

    except:

    print >> sys.stderr, "failed to load dict %s" % sys.argv[2]

    sys.exit(1)

    try:

    fpo = open("out.txt","w")

    except:

    print >> sys.stderr, "failed to load out.txt"

    sys.exit(1)

    for line in fpi:

    fpo.write("\t".join( max_match_segment(line.strip(), dic) ))

    当然,这只是最基础的,还可以有很多高级的优化,比如说改成Trie树版本的,控制最大词长度的等等。

    在Hadoop上运行基于RMM中文分词算法的MapReduce程序

    原文:http://xiaoxia.org/2011/12/18/map-reduce-program-of-rmm-word-count-on-hadoop/ 在Hadoop上运行基于RMM中文分词 ...

    Mmseg中文分词算法解析

    Mmseg中文分词算法解析 @author linjiexing 开发中文搜索和中文词库语义自己主动识别的时候,我採用都是基于mmseg中文分词算法开发的Jcseg开源project.使用场景涉及搜索 ...

    分词 &vert; 双向匹配中文分词算法python实现

    本次实验内容是基于词典的双向匹配算法的中文分词算法的实现.使用正向和反向最大匹配算法对给定句子进行分词,对得到的结果进行比较,从而决定正确的分词方法. 算法描述正向最大匹配算法先设定扫描的窗口大小ma ...

    【nlp】中文分词基础原则及正向最大匹配法、逆向最大匹配法、双向最大匹配法的分析

    分词算法设计中的几个基本原则: 1.颗粒度越大越好:用于进行语义分析的文本分词,要求分词结果的颗粒度越大,即单词的字数越多,所能表示的含义越确切,如:“公安局长”可以分为“公安 局长”.“公安局 长” ...

    MMSeg中文分词算法

    Java中有一些开源的分词项目,比如:IK.Paoding.MMSEG4J等等.这里主要说的是MMSEG4J中使用的MMSeg算法.它的原文介绍在:http://technology.chtsai.o ...

    中文分词算法工具hanlp源码解析

    词图 词图指的是句子中所有词可能构成的图.如果一个词A的下一个词可能是B的话,那么A和B之间具有一条路径E(A,B).一个词可能有多个后续,同时也可能有多个前驱,它们构成的图我称作词图. 需要稀疏2维 ...

    hanlp源码解析之中文分词算法详解

    词图 词图指的是句子中所有词可能构成的图.如果一个词A的下一个词可能是B的话,那么A和B之间具有一条路径E(A,B).一个词可能有多个后续,同时也可能有多个前驱,它们构成的图我称作词图. 需要稀疏2维 ...

    MMSEG 中文分词算法 翻译

    算法原文位于:http://technology.chtsai.org/mmseg/ http://www.360doc.com/content/13/0217/15/11619026_2661428 ...

    算法:二分查找(python版)

    #!/usr/bin/env python #coding -*- utf:8 -*- #二分查找#时间复杂度O(logn)#一个时间常量O(1)将问题的规模缩小一半,则O(logn) import ...

    随机推荐

    Unity3D设计原则

    原则1:单一职责 原则2:里氏替换原则(子类扩展但不改变父类功能) 原则3:依赖倒置原则 原则4:接口隔离原则 原则5:迪米特法则(最少知道原则) 原则6:开闭原则 原则1:单一职责原则 说到单一职责 ...

    使用git将代码push到osc上

    1.下载git客户端 2.在osc上创建项目 ①使用:git bash here ②在目录下执行:git init ③ssh-keygen -t rsa -C "xqs@gmail.com& ...

    HDU 4049 Tourism Planning(动态规划)

    Tourism Planning Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

    JS代码的加载

    HTML页面中JS的加载原理:在加载HTML页面的时候,当浏览器遇到内嵌的JS代码时会停止处理页面,先执行JS代码,然后再继续解析和渲染页面.同样的情况也发生在外链的JS文件中,浏览器必须先花时间下载 ...

    mac&lpar;osx&rpar; apache无法启动 localhost无法访问服务器&lbrack;&rsqb;

    问题描述:由于删除了/private/var/log下面的日志,导致重启电脑后apache无法正常工作. 删除log的初衷是:当系统用久了,日志文件占据了几十个G的硬盘容量. 造成的后果:重启电脑后a ...

    mybatis缓存创建过程

    带着 上篇 的问题,再来看看mybatis的创建过程 1.从SqlSessionFactoryBuilder解析mybatis-config.xml开始 对文件流解析 XMLConfigBuilder ...

    jquery 中ajax的参数

    url: 要求为String类型的参数,(默认为当前页地址)发送请求的地址. type: 要求为String类型的参数,请求方式(post或get)默认为get.注意其他http请求方法,例如put和 ...

    mvc设计模式的优点

    软件设计的理念是:高内聚,低耦合.采用三层: UI:(jsp,servlet), service:(具体的业务实现), dao:(对数据库的操作) 的设计模式来指导项目开发可以使得项目各层之间是一个粗 ...

    Mac idea 执行testng用例,提示&percnt;MODULE&lowbar;WORKING&lowbar;DIR&percnt;目录不存在解决办法

    idea 下载git代码 执行testng用例,报错: 下午4:47 Error running 'Test.apkStart': Cannot start process, the working ...

    springBoot bean注入

    1.@Component:把普通pojo实例化到spring容器中,相当于配置文件中的 2.@Autow ...

    展开全文
  • 神策杯2018高校算法大师赛(中文关键词提取)第二代码方案
  • 中文分词算法研究

    千次阅读 2016-06-30 23:00:47
    中文分词基本算法主要分类 中文分词算法总结 介绍分词语料—— 中文分词入门之资源  互联网时代的社会语言学:基于SNS的文本数据挖掘 字标注问题 先看一个句子:我是一程序员。将所有字分为4类,S表示单字...


    分词算法有基于字典、基于规则和基于统计的,这里主要讲基于统计的方法。


    中文分词基本算法主要分类                     

    中文分词算法总结

    介绍分词语料——    中文分词入门之资源   

    互联网时代的社会语言学:基于SNS的文本数据挖掘


    字标注问题
    先看一个句子:我是一名程序员。将所有字分为4类,S表示单字,B表示词首,M表示词中,E表示词尾。
    如果我们知道上述句子中每个字的类别,即:

    我/S 是/S 一/B 名/E 程/B 序/M 员/E 。/S

    那么我们就可以知道这个句子的分词结果:我 是 一名 程序员 。

    从这里可以看出,分词问题转化成了一个分类问题,即对每个字分类。

    目前主要以字标注的分词方法为主。所谓汉字标注分词,就是将分词过程看作为每个汉字进行分类的过程,通过对句子中每个汉字进行标记来切分。常见的汉字标注分词方法是根据汉字在词语中出现的不同位置标注不同的标签。例如可以用“O”表示汉字单独成词,“B”表示汉字出现在词头,“I”表示汉字出现在词的中间或是末尾。因此分词问题就被转化成一个纯粹的序列数据标记问题,可以使用很多序列标记算法进行分词计算。因此汉字标注的分词方法成为研究分词经常使用的方法。

    HMM分词方法


    介绍一下使用的资源,分词使用的语料来自于SIGHAN Bakeoff 2005的 icwb2-data.rar

    四类标签的集合是 {B,E,M,S},其含义如下:

    B:一个词的开始

    E:一个词的结束

    M:一个词的中间

    S:单字成词

    举例:你S现B在E应B该E去S幼B儿M园E了S


    用四类标签为msr_training.utf8做好标记后,就可以开始用统计的方法构建一个HMM。我们打算构建一个2-gram(bigram)语言模型,也即一个1阶HMM,每个字符的标签分类只受前一个字符分类的影响。现在,我们需要求得HMM的状态转移矩阵 A 以及混合矩阵 B。其中:

                                         Aij = P(Cj|Ci)  =  P(Ci,Cj) / P(Ci) = Count(Ci,Cj) / Count(Ci)

                                         Bij = P(Oj|Ci)  =  P(Oj,Ci) / P(Ci) = Count(Oj,Ci) / Count(Ci)

    公式中C = {B,E,M,S},O = {字符集合},Count代表频率。在计算Bij时,由于数据的稀疏性,很多字符未出现在训练集中,这导致概率为0的结果出现在B中,为了修补这个问题,我们采用加1的数据平滑技术,即:

                                         Bij = P(Oj|Ci)  =  (Count(Oj,Ci) + 1)/ Count(Ci)

    设定初始向量Pi = {0.5, 0.0, 0.0, 0.5}(M和E不可能出现在句子的首位)。至此,HMM模型构建完毕。


    如何利用隐马尔科夫模型解决分词问题,请看下面:

    字标注问题

    在找到解决方案之前,我们最好先用数学的语言来描述一下这个问题。当我们得到一个句子时,我们可以把它看做一个向量。令句子s有共计n个单词,第i个单词用xi来表示,显然s = x1, x2, ... xn。因此问题可以描述成,对于每个单词xi,我们需要分别给定一个标注yi,因而获得句子的标注y = y1, y2, ... yn。


    综上所述,训练模型时我们期望对于任何一个句子s,我们需要得到所有可能出现的标注的概率p(y | s),其中概率最大的y即是我们需要的结果。最终的表达式为tagging(s)= arg max(p(y|s))。


    接下来,我们需要考虑如何建立训练集并从中学习出上述的模型。首先,我需要获得一个已经标注好的语料库,语料库中有若干句子,每个句子中的每个词都已有标识。然后,对于语料库中出现的所有的句子s与对应的标识y,我们可以学习出条件概率p(y, s),即某个句子与其对应标识的出现概率。其次,由于语料库无法包含所有可能出现的句子,所以我们希望能够得到一个更加宽泛的表达式,通过贝叶斯公式,我们可以非常看出p(y, s) = p(y) * p(s | y),同时p(y | s) = p(y) * p(s | y) / p(s);我们需要比较的是p(y | s)中的最大值而无需获得p(y | s),因此显然p(s)的具体取值并不重要,因此我们只需要考虑tagging(s)= arg max(p(y) * p(s | y))。


    由于语料库无法保存所有客观存在的句子,我们必须找到一种方法来估计p(y)与p(s | y)的取值,而其中一种非常有名的方法就是隐马尔科夫模型。


    隐马尔科夫模型
    我们依然回到上述问题,给定一个句子s = x1, x2, ... xn,我们给出一个标识组合y = y1, y2, ... yn,使得y = arg max(p(y) * p(s | y)) = arg max(p(x1, x2, ... , xn, y1, y2, ..., yn))。


    我们对每个句子做一点优化:
    1)增加一个开始符号”*“,我们定义所有句子都是以”*“开始,即X-1 = X0 = *;
    2)增加一个结束符号”STOP“,我们定义所有句子都是以”STOP“结束。


    同时,隐马尔科夫模型需要我们做一些额外的假设来简化模型:
    1)yk只与前几个元素相关,即标识的语义相关性只影响前后几个元素;
    2)单词xk与对应的yk不受其他单词的影响,即p(xi | yi)相互独立
    .


    经过简化以后,我们以三阶隐马尔科夫模型为例,表达式为 tagging(s)= arg max(p(y|s))=arg max(p(y1, y2, … yn | x1, x2, … xn) )= arg max(p(y) * p(s | y))=arg max(p(y1, y2, … yn) * p(x1, x2, … xn | y1, y2, … yn) )= arg max(∏q(yj | yj-2, yj-1) * ∏ e(xi | yi))。显然,简化后的模型,单个单词在语料库中出现的频率会远远高于句子整体出现的频率。


    求解这个max问题可以用动态规划方法,即隐马尔科夫模型里的viterbi算法。现在我们可以写入一个观察序列,用Viterbi算法获得一个隐藏序列(分词结果),实现每个字都有一个状态,且这个状态链对应的概率是最大的


    NLP | 自然语言处理 - 标注问题与隐马尔科夫模型(Tagging Problems, and Hidden Markov Models)


    Itenyh版-用HMM做中文分词四:A Pure-HMM 分词器


    基于HMM2-Trigram字符序列标注的中文分词器Java实现

    中文分词与马尔科夫模型之二(隐马尔科夫模型与维特比)



    最大熵模型


    中文分词模型之最大熵模型


    中文分词入门之字标注法3


    使用Python,字标注及最大熵法进行中文分词

    参考论文《Maximum Entropy Word Segmentation of Chinese Text



    条件随机场


    使用crf进行汉字标注方法很重要的一个问题就是特征选择。



    深度学习


    Deep Learning 在中文分词和词性标注任务中的应用 - peghoty - 博客频道 - CSDN.NET


    利用 word2vec 训练的字向量进行中文分词

    TensorFlow入门(六) 双端 LSTM 实现序列标注(分词)

    深度学习(三十八)初识DL在自然语言序列标注中的应用-未完待续

    kcws分词模型


    Python 文本挖掘:jieba中文分词和词性标注


    python︱六款中文分词模块尝试:jieba、THULAC、SnowNLP、pynlpir、CoreNLP、pyLTP

    NLP+词法系列(一)︱中文分词技术小结、几大分词引擎的介绍与比较




    网上也有很多中文分词的开源项目:

    ik-analyser:Java语言

    http://code.google.com/p/ik-analyzer/

    paoding

    http://code.google.com/p/paoding/

    cjk-tokenizer:C++实现

    http://code.google.com/p/cjk-tokenizer/

    mmseg4j:实现了 Chih-Hao Tsai 的 MMSeg 算法

    http://code.google.com/p/mmseg4j/

    imdict-chinese-analyzer:算法基于隐马尔科夫模型(Hidden Markov Model, HMM),是中国科学院计算技术研究所的ictclas中文分词程序的重新实现(基于Java),可以直接为lucene搜索引擎提供简体中文分词支持。

    http://code.google.com/p/imdict-chinese-analyzer/

     

    另外,还有

    海量的中文分词,目前性能和效果最好的分词

    http://www.hylanda.com

    哈工大信息检索实验室的LTP平台,支持分词,标引,句法分析等多种任务。

    http://ir.hit.edu.cn/demo/ltp/



    展开全文
  • 算法导论中文版,著名的经典大作,这可是好书啊,还是中文版,找了好久才找到的
  • 算法导论中文

    2015-06-04 10:02:39
    国外著名算法与数据结构教材,包含了很多算法,可供计算机专业学员参考学习
  • 开源中文分词算法

    2020-12-09 17:47:02
    是更多的考虑了互联网用户在产品及址信息搜索这块的应用,IK特别适用于搜索商家,产品,址,如商品交易,美食,娱乐,电子地图等,因为它是基于这样 的应用诞生的。IK在一开始的设计的时候,它有一个隐形的目标...

    一,IK Analyzer(暗黑的“不朽之王Immortal King”) :

    IK Analyzer
    是更多的考虑了互联网用户在产品及名址信息搜索这块的应用,IK特别适用于搜索商家,产品,名址,如商品交易,美食,娱乐,电子地图等,因为它是基于这样
    的应用诞生的。IK在一开始的设计的时候,它有一个隐形的目标,是对数词,量词,专有名词的增强处理,这是由于它的基于web
    gis搜索的需求定位决定的。
    在IKQueryparser 中,它不是简单的返回所有分词结果的组合,而是建立起一个分词树,将有可能的组合放在一起,它的输出会类似于这样:(“永和” && “服装” && “饰品”) || (“和服”&& “装饰”), 通过这个搜索逻辑去索引中进行匹配。

    二,JE-MManalyzer:

    它的算法具有歧义分析,比较适合做垂直搜索和信息挖掘。他的中文名称是“极易”,开发者的理念是-简单即是美。

    三,中科院的分词器(ICTCLAS):

    中科院的分词器很牛,其切分结果明显基于语义分析。 下载地址http://ictclas.org/Down_OpenSrc.asp

    四,paoding:

    paoding的结构设计的非常灵活,适合于对其进行开源改造。

    五,mmseg4j:

    单从mmseg4j 的项目介绍上看,它是一个很纯粹的基于词典分词的实现,既有细粒度的切分,也有最大长度的切分。应该说,是一个学习词典分词的很好的典范。

    IK分词多些但速度比paoding差些。

    =========================

    对比

    1.用户自定义词库:

    paoding :支持不限制个数的用户自定义词库,纯文本格式,一行一词,使用后台线程检测词库的更新,自动编译更新过的词库到二进制版本,并加载

    imdict :暂时不支持用户自定义词库。但 原版 ICTCLAS 支持。支持用户自定义 stop words

    mmseg4j :自带sogou词库,支持名为 wordsxxx.dic, utf8文本格式的用户自定义词库,一行一词。不支持自动检测。 -Dmmseg.dic.path

    ik : 支持api级的用户词库加载,和配置级的词库文件指定,无 BOM 的 UTF-8 编码,\r\n 分割。不支持自动检测。

    2. 速度(基于官方介绍,非自己测试)

    paoding :在PIII 1G内存个人机器上,1秒 可准确分词 100万 汉字
    imdict :483.64 (字节/秒),259517(汉字/秒)
    mmseg4j : complex 1200kb/s左右, simple 1900kb/s左右
    ik :具有50万字/秒的高速处理能力

    3. 算法和代码复杂度

    paoding :svn src 目录一共1.3M,6个properties文件,48个java文件,6895 行。使用不用的 Knife切不同类型的流,不算很复杂。

    imdict :词库 6.7M(这个词库是必须的),src 目录152k,20个java文件,2399行。使用 ICTCLAS HHMM隐马尔科夫模型,“利用大量语料库的训练来统计汉语词汇的词频和跳转概率,从而根据这些统计结果对整个汉语句子计算最似然(likelihood)的切分”

    mmseg4j : svn src 目录一共 132k,23个java文件,2089行。MMSeg 算法 ,有点复杂。

    ik : svn src 目录一共6.6M(词典文件也在里面),22个java文件,4217行。多子处理器分析,跟paoding类似,歧义分析算法还没有弄明白。

    4. 文档

    paoding :几乎无。代码里有一些注释,但因为实现比较复杂,读代码还是有一些难度的。
    imdict : 几乎无。 ICTCLAS 也没有详细的文档,HHMM隐马尔科夫模型的数学性太强,不太好理解。
    mmseg4j : MMSeg 算法是英文的,但原理比较简单。实现也比较清晰。
    ik : 有一个pdf使用手册,里面有使用示例和配置说明。

    5. 其它

    paoding :引入隐喻,设计比较合理。search 1.0 版本就用的这个。主要优势在于原生支持词库更新检测。主要劣势为作者已经不更新甚至不维护了。
    imdict :进入了 lucene trunk,原版 ictclas 在各种评测中都有不错的表现,有坚实的理论基础,不是个人山寨。缺点为暂时不支持用户词库。
    mmseg4j : 在complex基础上实现了最多分词(max-word),但是还不成熟,还有很多需要改进的地方。
    ik :针对Lucene全文检索优化的查询分析器IKQueryParser

    结论

    个人觉得,可以在 mmseg4j 和 paoding 中选一个。关于这两个分词效果的对比,可以参考:

    http://blog.chenlb.com/2009/04/mmseg4j-max-word-segment-compare-with-paoding-in-effect.html

    或者自己再包装一下,将 paoding 的词库更新检测做一个单独的模块实现,然后就可以在所有基于词库的分词算法之间无缝切换了。

    ps,对不同的 field 使用不同的分词器是一个可以考虑的方法。比如 tag 字段,就应该使用一个最简单的分词器,按空格分词就可以了。

    ======================================
    对paoding je、IK等进行测试,发现JE使用时一不注意就容易出现在索引或者检索时内存泄漏,其加载字典时花费内存45m左右,所以在运行时一般会在环境下设置内存参数 -Xmx256M等方法解决

    paoding 比较麻烦的是要设置字典的环境变量,一般做法是新建环境变量
    PAODING_DIC_HOME 再加入字典路径(如 F:\paoding-analysis\dic)
    这种方法在项目移位后还得配置字典环境,麻烦
    可以直接把paoding源文件夹下的paoding-dic-home.properties拷贝的你自己的
    项目src文件夹下,然后将paoding-dic-home.properties文件中的
    #paoding.dic.home=dic修改成
    paoding.dic.home=F:/paoding-analysis/dic即可

    当然你可以自己建一个名为paoding-dic-home.properties的文件
    在里面加入一条语句paoding.dic.home=F:/paoding-analysis/dic(字典路径,自己换)

    别忘记拷贝lib文件夹下的jar文件到项目中,
    commons-logging.jar一定不能少

    ----------------------------下面是对同一个文件分词时间消耗
    Time taken for PaoDing Analyzer behaviour : 1156 milli seconds
    Time taken for IK Analyzer behaviour : 1531 milli seconds
    Time taken for JE Analyzer behaviour : 1719 milli seconds

    原文地址:阅读原文

    展开全文
  • 最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法,分为正向和逆向,原理都是一样的。 正向最大匹配算法,故思意,从左向右扫描寻找词的最大匹配。 首先我们可以规定一个词的最大长度,每次扫描的时候...

    最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法,分为正向和逆向,原理都是一样的。

    正向最大匹配算法,故名思意,从左向右扫描寻找词的最大匹配。

    首先我们可以规定一个词的最大长度,每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配,如果没有找到,就缩短长度继续寻找,直到找到或者成为单字。

    实例:

    S1="计算语言学课程是三个课时" ,设定最大词长MaxLen = 5  ,S2= " "

    字典中含有三个词:[计算语言学]、[课程]、[课时]

    (1)S2="";S1不为空,从S1左边取出候选子串W="计算语言学";
    (2)查词表,“计算语言学”在词表中,将W加入到S2中,S2=“计算语言学/  ”,        并将W从S1中去掉,此时S1="课程是三个课时";
    (3)S1不为空,于是从S1左边取出候选子串W="课程是三个";
    (4)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程是三";
    (5)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程是";
    (6)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程"
    (7)查词表,W在词表中,将W加入到S2中,S2=“计算语言学/  课程/  ”,并        将W从S1中去掉,此时S1="是三个课时";

    (8)S1不为空,于是从S1左边取出候选子串W="是三个课时";
    (9)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三个课";
    (10)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三个";
    (11)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三"
    (12)查词表,W不在词表中,将W最右边一个字去掉,得到W=“是”,这时     W是单字,将W加入到S2中,S2=“计算语言学/  课程/  是/  ”,并将     W从S1中去掉,此时S1="三个课时";
    (13)S1不为空,从S1左边取出候选子串W="三个课时";
    (14)查词表,W不在词表中,将W最右边一个字去掉,得到W="三个课";
    (15)查词表,W不在词表中,将W最右边一个字去掉,得到W="三个";
    (16)查词表,W不在词表中,将W最右边一个字去掉,得到W=“三”,这时     W是单字,将W加入到S2中,S2=“计算语言学/  课程/  是/  三/  ”,并    将W从S1中去掉,此时S1="个课时";

    (17)S1不为空,从S1左边取出候选子串W="个课时";
    (18)查词表,W不在词表中,将W最右边一个字去掉,得到W="个课";
    (19)查词表,W不在词表中,将W最右边一个字去掉,得到W=“个”,     这时W是单字,将W加入到S2中,S2=“计算语言学/  课程/  是/       三/  个/  ",并将W从S1中去掉,此时S1="课时";
    (20)S1不为空,从S1左边取出候选子串W="课时";
    (21)查词表,W在词表中,将W加入到S2中,S2=“计算语言学/  课程/       是/  三/  个/  课时/  ",并将W从S1中去掉,此时S1=""。
    (22)S1为空,输出S2作为分词结果,分词过程结束。

    中文分词算法的Python实现:

    脚本接受两个参数,一个是输入文件的路径,另一个是词典的路径。

    它的运行方法如下:

     

    python max-match.py <data> <dict>


     

    #!/usr/bin/env python
    import cPickle as pickle
    import sys
    
    window_size=5
    
    def max_match_segment(line, dic):
        # write your code here
        chars = line.decode("utf8")
        words = []
        idx = 0
        while idx < len(chars):
            matched = False
            for i in xrange(window_size, 0, -1):
                cand=chars[idx:idx+i].encode("utf8")
                if cand in dic:
                    words.append(cand)
                    matched = True
                    break
            if not matched: 
                i = 1
                words.append(chars[idx].encode("utf8"))
            idx += i
    
        return words
    
    if __name__=="__main__":
    
        try:
            fpi=open(sys.argv[1], "r")
        except:
            print >> sys.stderr, "failed to open file"
            sys.exit(1)
    
        try:
            dic = pickle.load(open(sys.argv[2], "r"))
        except:
            print >> sys.stderr, "failed to load dict %s" % sys.argv[2]
            sys.exit(1)
        try:
            fpo = open("out.txt","w")
        except:
            print >> sys.stderr, "failed to load out.txt"
            sys.exit(1)
        for line in fpi:
            fpo.write("\t".join( max_match_segment(line.strip(), dic) ))

     


    当然,这只是最基础的,还可以有很多高级的优化,比如说改成Trie树版本的,控制最大词长度的等等。

     

    实例参考自:北大詹卫东老师“中文信息处理基础”的课件 :http://ishare.iask.sina.com.cn/f/22509596.html



     

    转载于:https://www.cnblogs.com/james1207/p/3306384.html

    展开全文
  • NSGA2算法中文版详细介绍

    万次阅读 多人点赞 2017-09-01 15:14:31
    Deb在1995年发表的一篇为《Multiobjective function optimization using nondominated sorting genetic algorithms》的论文中提出的。该算法在快速找到Pareto前沿和保持种群多样性方面都有很好的效果,不过在这么...
  • 业内最著名的计算机算法书 - 算法导论 中文版 第三版
  • 著名信息学用书《算法导论》的中文版 这是麻省理工学院2001年秋季课程《算法导论》的所有课程资料,
  • Message Digest Algorithm MD5(中文名为消息摘要算法第五版)为计算机安全领域广泛使用的一种散列函数,用以提供消息的完整性保护。该算法的文件号为RFC 1321(R.Rivest,MIT Laboratory for Computer Science and ...
  • 经典的算法书,而且是中文版的哦,非常不错! 这是第一版的中文版<算法导论>,当时名字为<现代计算机常用数据结构和算法>,也是根据英文版的算法导论翻译的.
  • 著名信息学用书《算法导论》的中文版(3-1) 这是麻省理工学院2001年秋季课程《算法导论》的所有课程资料,包括有:课本(含有习题,chm格式),课堂讲稿(ppt转pdf格式),作业及其答案(pdf格式),测验及其答案(pdf...
  • 中文分词常用算法

    千次阅读 2009-06-22 11:57:00
    一个是词典未登录词的识别,比如人名,地名,机构等。 下面我们以百度为例,看看几种不同的算法对切词的影响。 首先,讲讲百度的分词时机或者条件问题,是否是个中文字符串百度就拿来切一下呢?非也,要想被百度...
  • 美国著名计算机科学家Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein等编著的算法巨著,详细全面介绍算法相关知识。
  • ( 算法导论(中文版)(现代计算机常用数据结构和算法),非常著名的一本书,所有程序员都应该好好研究的一本书。
  • 来自 | 大数据文摘,禁二次转载上次小编给大家推荐了一个能让算法动起来的开源项目之后,有热心的读者推荐了另一个算法可视化的网站。小编打开之后,立即被起画风所折服,所以决定探索一番。先给出网站地址:...
  • 著名信息学用书《算法导论》的中文版 这是麻省理工学院2001年秋季课程《算法导论》的所有课程资料,包括有:课本(含有习题,chm格式),课堂讲稿(ppt转pdf格式),作业及其答案(pdf格式),测验及其答案(pdf格式),...
  • 大数据文摘出品作者:蒋宝尚上次文摘菌给大家推荐了一个能让算法动起来的开源项目之后,有热心的读者给文摘菌推荐了另一个算法可视化的网站。文摘菌打开之后,立即被起画风所折服,所以决定探索一番。先给出网站地址...
  • Java数据结构和算法中文第二版 著名的算法书籍

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,971
精华内容 788
关键字:

中文算法名