精华内容
下载资源
问答
  • python 双向最大匹配算法 双向最大匹配算法 双向最大匹配算法
  • 下面是前向最大匹配、后项最大匹配和双向最大匹配的具体实现,使用的是python。 class WordSeg(object): def __init__(self, dic): self.dic = dic self.window_size = len(max(dic, key=len, default='')) ...

    下面是前向最大匹配、后项最大匹配和双向最大匹配的具体实现,使用的是python。

    class WordSeg(object):
        def __init__(self, dic):
            self.dic = dic
            self.window_size = len(max(dic, key=len, default=''))
    
        def forward_max_match(self, text):
            fmm_result = []
            index = 0
            text_length = len(text)
            piece = ''
            while index < text_length:
                for size in range(self.window_size + index, index, -1):
                    piece = text[index:size]
                    if piece in self.dic:
                        index = size - 1
                        break
                index += 1
                fmm_result.append(piece)
            return fmm_result
    
        def backward_max_match(self, text):
            bmm_result = []
            index = len(text)
            piece = ''
            while index > 0:
                for size in range(index - self.window_size, index):
                    piece = text[size:index]
                    if piece in self.dic:
                        index = size + 1
                        break
                index -= 1
                bmm_result.append(piece)
            bmm_result.reverse()
            return bmm_result
    
        def bi_directional_max_match(self, text):
            fmm_list = self.forward_max_match(text)
            bmm_list = self.backward_max_match(text)
            if len(fmm_list) != len(bmm_list):
                return fmm_list if len(fmm_list) < len(bmm_list) else bmm_list
            else:
                is_same = True
                fmm_single = 0
                bmm_single = 0
                for i in range(0, len(fmm_list)):
                    if fmm_list[i] != bmm_list[i]:
                        is_same = False
                    if len(fmm_list[i]) == 1:
                        fmm_single += 1
                    if len(bmm_list[i]) == 1:
                        bmm_single += 1
                if is_same:
                    return fmm_list
                else:
                    return fmm_list if fmm_single < bmm_single else bmm_list
    dic = ['研究', '研究生', '生命', '命', '的', '起源']
    text = '研究生命的起源'
    print('分词前的句子:', text)
    wordSeg = WordSeg(dic)
    fmm_result = wordSeg.forward_max_match(text)
    print('前向最大匹配:', fmm_result)
    bmm_result = wordSeg.backward_max_match(text)
    print('后向最大匹配:', bmm_result)
    bdmm_result = wordSeg.bi_directional_max_match(text)
    print('双向最大匹配:', bdmm_result)

    结果:

    分词前的句子: 研究生命的起源
    前向最大匹配: ['研究生', '命', '的', '起源']
    后向最大匹配: ['研究', '生命', '的', '起源']
    双向最大匹配: ['研究', '生命', '的', '起源']

    展开全文
  • 龙源期刊网http://www.qikan.com.cn警务应用中基于双向最大匹配法的中文分词算法实现作者:陶伟来源:《电子技术与软件工程》2016年第04期摘要中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、自然...

    龙源期刊网

    http://www.qikan.com.cn

    警务应用中基于双向最大匹配法的中文分词

    算法实现

    作者:陶伟

    来源:《电子技术与软件工程》

    2016

    年第

    04

    中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、自然语言理解

    等中文信息处理领域的基础。目前中文分词依然是中文信息处理的瓶颈之一,本文对常见中文

    分词算法进行研究,并针对警务应用的场景,在经典的

    Jieba

    中文分词算法的逆向匹配法基础

    上提出双向最大匹配法,最后验证改进后的算法在中文分词准确度方面的提升。

    【关键词】中文分词

    双向最大匹配法

    警务应用

    1

    研究背景

    公安机关日常工作中采集到的数据,大多为碎片化数据,具多源、量大、且又离散如何有

    效提取这些非结构化数据中的有效信息以方便警务应用系统进行进一步分析处理,为案件侦

    破、情报分析等提供服务,关键技术就是利用中文分词算法将这些描述性的中文语句转变为结

    构化数据。

    2

    中文分词技术简介

    2.1

    中文分词算法分类

    中文分词技术属于自然语言处理技术范畴,现有分词算法分为基于规则的分词方法、基于

    统计的分词算法和基于理解的分词方法。

    基于规则的分词方法中占主流地位的是正向最大匹配法和逆向最大匹配法。由于汉语单字

    成词的特点,

    正向最小匹配和逆向最小匹配一般很少使用。逆向匹配的切分精度一般高于正

    向匹配,遇到的歧义现象也比较少。由大数据量的统计表明正向和逆向最大匹配的错误率分别

    1/ 169

    1/ 245

    ,但这种精度还远远不能满足实际的需要。实际使用的分词系统,都是把机

    械分词作为一种初分手段,还需通过利用各种其它的语言信息来进一步提高切分的准确率。

    基于统计的方法是基于多个汉字同时出现的概率,

    通过对语料库有监督或无监督的学

    习,

    得到描述一种语言的语言模型

    (常用一阶隐马尔可夫模型(

    1stHMM

    )

    )

    ,该方法优点

    是只要有足够的训练文本即可降低未登录词的影响。

    2.2 Jieba

    分词算法

    展开全文
  • 分词是自然语言处理的一个...前向最大匹配算法后向最大匹配算法双向最大匹配算法三种方法思想都很简单,今天我们用python实现前向最大匹配算法。前向最大匹配算法,顾名思义,就是从待分词句子的左边向右边搜索,...

    分词是自然语言处理的一个基本工作,中文分词和英文不同,字词之间没有空格,可以将中文分词方法简单归纳为:基于词表的分词方法

    基于统计的分词方法

    基于序列标记的分词方法

    其中,基于词表的分词方法最为简单,根据起始匹配位置不同可以分为:前向最大匹配算法

    后向最大匹配算法

    双向最大匹配算法

    三种方法思想都很简单,今天我们用python实现前向最大匹配算法。

    前向最大匹配算法,顾名思义,就是从待分词句子的左边向右边搜索,寻找词的最大匹配。我们需要规定一个词的最大长度,每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配,如果没有找到,就缩短长度继续寻找,直到找到字典中的词或者成为单字。

    下面是我的代码。word_dict = [             ]

    test_str = (text):

    text:

    (text) == :

    text

    text word_dict:

    text

    :

    small = (text) -         text = text[:small]

    getSeg(text)

    ():

    test_strword_dict

    test_str = test_str.strip()

    max_len = ((word) word word_dict)

    result_str = []      result_len =     (test_str)

    test_str:

    tmp_str = test_str[:max_len]

    seg_str = getSeg(tmp_str)

    seg_len = (seg_str)

    result_len = result_len + seg_len

    seg_str.strip():

    result_str.append(seg_str)

    test_str = test_str[seg_len:]

    (result_str)

    __name__ == :

    main()

    看一下分词的结果吧!

    3541465c8eedb428bc27f5f7b46d9c3f.png

    本文来自:机器在学习

    展开全文
  • 按照匹配方法来划分,主要有正向最大匹配、逆向最大匹配以及双向最大匹配。 1. 正向最大匹配 正向最大匹配(Maximum Match,MM): 从左向右取待切分汉语句的m个字符作为匹配字段,m为机器词典中最长词条的字符数。...

    基于规则的分词是一种机械分词方法,需要不断维护和更新词典,在切分语句时,将语句的每个字符串与词表中的每个次进行逐一匹配,找到则切分,找不到则不予切分。

    按照匹配方法来划分,主要有正向最大匹配、逆向最大匹配以及双向最大匹配。

    1. 正向最大匹配

    正向最大匹配(Maximum Match,MM):

    1. 从左向右取待切分汉语句的m个字符作为匹配字段,m为机器词典中最长词条的字符数。
    2. 查找机器词典并进行匹配。若匹配成功,则将这个匹配字段作为一个词切分出来。 若匹配不成功,则将这个匹配字段的最后一个字去掉,剩下的字符串作为新的匹配字段,进行再次匹配,重复以上过程,直到切分出所有词为止。

    比如我们现在有个词典,最长词的长度为5,词典中存在“南京市长”“长江大桥”和 “大桥”3个词。现采用正向最大匹配对句子“南京市长江大桥”进行分词,那么首先从句 子中取出前5个字“南京市长江”,发现词典中没有该词,于是缩小长度,取前4个字“南 京市长”,词典中存在该词,于是该词被确认切分。再将剩下的“江大桥”按照同样方式 切分,得到“江”“大桥”,最终分为“南京市长”“江”“大桥”3个词。显然,这种结果不是我们所希望的。

    正向最大匹配法示例代码如下:

    class MaximumMatch:
        """正向最大匹配的中文分词器"""
        def __init__(self):
            self.window_size = 3  # 字典中最长词条的字符数
    
        def cut(self, text):
            global piece
            result = []
            index = 0  # 前指针
            text_length = len(text)
            dictionary = {'研究', '研究生', '声明', '起源'}
            while text_length > index:
                for r_index in range(self.window_size+index, index, -1):  # 后指针
                    piece = text[index: r_index]
                    if piece in dictionary:
                        index = r_index - 1
                        break
    
                index = index + 1
                result.append(piece)
            return result
    
    
    if __name__ == '__main__':
        text = '研究生命的起源'
        tokenizer = MaximumMatch()
        print(tokenizer.cut(text))
    

    输出结果:

    ['研究生', '命', '的', '起源']
    

    2. 逆向最大匹配

    逆向最大匹配简称为RMM法。RMM法的基本原理与MM法大致相同,不同的是分词切分的方向与MM法相反。

    逆向最大匹配法从被处理文档的末端开始匹配扫描,每次取最末端的m个字符(m为词典中最长词数作为匹配字段,若匹配失败,则去掉匹配字段最前面的一个字,继续匹配。相应地,它使用的分词词典是逆序词典,其中的每个词条都将按逆序方式存放。在实际处理时,先将文档进行倒排处理,生成逆序文档。然后,根据逆序词典,对逆序文档用正向最大匹配法处理即可。

    由于汉语中偏正结构较多,若从后向前匹配,可以适当提高精确度。所以,逆向最大匹配法比正向最大匹配法的误差要小。统计结果表明,单纯使用正向最大匹配的错误率为1/169,单纯使用逆向最大匹配的错误率为1/25。比如之前的“南京市长江大桥”,按照逆向最大匹配,最终得到“南京市”“长江大桥”的分词结果。当然,如此切分并不代表完全正确、可能有个叫“江大桥”的“南京市长”也说不定。

    逆向最大匹配法示例代码如下:

    class ReverseMaximumMatch:
        """逆向最大匹配"""
        def __init__(self):
            self.window_size = 3
    
        def cut(self, text):
            result = []
            right = len(text)  # 右指针
            dic = {'研究', '研究生', '生命', '命', '的', '起源'}
            global piece
            while right > 0:
                for left in range(right - self.window_size, right):  # 固定右指针,左指针逐渐右移
                    piece = text[left: right]  # 切片
                    if piece in dic:  # 当命中时
                        right = left + 1  # 命中更新
                        break
                right = right - 1  # 自然更新
                result.append(piece)
            result.reverse()
            return result
    
    if __name__ == '__main__':
        text = '研究生命的起源'
        rmm_tokenizer = ReverseMaximumMatch()
        print(rmm_tokenizer.cut(text))
    

    输出结果:

    ['研究', '生命', '的', '起源']
    

    3. 双向最大匹配

    双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法得到的结果进行比较,然后按照最大匹配原则,选取词数切分最少的作为结果。据SunM.s.和 Benjamin K…研究表明,对于中文中90.0%左右的句子,正向最大匹配和逆向最大匹配的切分结果完全重合且正确,只有大概9.0%的句子采用两种切分方法得到的结果不一样,但其中必有一个是正确的(歧义检测成功),只有不到1.0%的句子,或者正向最大匹配和逆向最大匹配的切分结果虽重合却都是错的,或者正向最大匹配和逆向最大匹配的切分结果不同但两个都不对(歧义检测失败)。这正是双向最大匹配法在实用中文信息处理系统中得以广泛使用的原因所在。

    前面列举的“南京市长江大桥”采用双向最大匹配法进行切分,中间产生“南京市/江/大桥”和“南京市/长江大桥”两种结果,最终选取词数较少的“南京市/长江大桥”这一结果。

    双向最大匹配的规则如下所示:

    1. 如果正反向分词结果词数不同,则取分词数量较少的那个结果(上例:“南京市江/大桥”的分词数量为3,而“南京市/长江大桥”的分词数量为2,所以返回分词数量为2的结果)
    2. 如果分词结果词数相同,则:
      ① 分词结果相同,就说明没有歧义,可返回任意一个结果。
      ② 分词结果不同,返回其中单字较少的那个。比如前文示例代码中,正向最大匹配返回的结果为“[‘研究生’,‘命’,‘的起源’]”,其中单字个数为2个;而逆向最大匹配返回的结果为“[研究’,生命’, ‘的’,‘起源’]",其中单字个数为1。所以返回的是逆向最大匹配的结果。

    代码如下:

    class BidirectionalMaximumMatch:
        """双向最大匹配"""
        def _count_single_char(self, world_list: List[str]):
            """
            统计单字成词的个数
            """
            return sum(1 for word in world_list if len(word) == 1)
    
        def cut(self, text: str):
            mm = MaximumMatch()
            rmm = ReverseMaximumMatch()
            f = mm.cut(text)
            b = rmm.cut(text)
            if len(f) < len(b):
                return f
            elif len(f) > len(b):
                return b
            else:
                return b if self._count_single_char(f) >= self._count_single_char(b) else f
    
    if __name__ == '__main__':
        text = '研究生命的起源'
        bmm = BidirectionalMaximumMatch()
        print(bmm.cut(text))
    

    输出结果:

    ['研究', '生命', '的', '起源']
    

    基于规则的分词一般都较为简单高效,但是词典的维护面临很庞大的工作量。在网络发达的今天,网络新词层出不穷,很难通过词典覆盖所有词。另外,词典分词也无法区分歧义以及无法召回新词。


    在实际项目中,我们是否会考虑使用规则分词?
    虽然使用规则分词的分词准确率看上去非常高,但是规则分词有几个特别大的问题:
    ① 不断维护词典是非常烦琐的,新词总是层出不穷,人工维护费时费力;
    ② 随着词典中条目数的增加,执行效率变得越来越低;
    ③ 无法解决歧义问题。
    所以在这里不建议采用规则分词法。

    展开全文
  • 基于词库的双向最大匹配算法 本文介绍了基于词库的双向最大匹配算法。该算法实现简单,分词效果依赖于词库。在词库相当的情况下,分词效果不错。某些情况下甚至强于基于隐马尔科夫模型的智能分词。 【双向最大...
  • 双向最大匹配法(Bi-directction Matching method,BM) 双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较,从而决定正确的分词方法。据SunM.S. 和 Benjamin K.T.(1995)的研究表明...
  • 完成正向、逆向和双向最大匹配算法import java.io.*;import java.util.*;/*** 正向最大匹配* 逆向最大匹配* 双向最大匹配*/public class TwoMaxMatch {private static final int MAX_LENGTH = 5;public static void ...
  • /usr/bin/python#encoding=gbkimport sysdictMaxLength = 5dctDict = {}encoding='gbk''''初始化字典、初始化最大词长'''def initDct(dct):global dctDictglobal dictMaxLengthdctobj = open(dct)for line in dctobj...
  • 双向最大匹配算法(含完整代码实现,ui界面)正向最大匹配算法,逆向最大匹配算法 一、理论描述 中文分词(Chinese Word Segmentation) 指的是将一个汉字序列切分成一个一个单独的词。分词就是将连续的字序列按照一定...
  • 前向最大匹配def fmmseg(sen,max,strs):'''sen: 待切分句子max: 最大切分长度strs: 词典列表'''maxs=maxreturnlist=[]while len(sen)>0:while max>0:if(max==1):returnlist.append(sen[:1])sen=sen[1:]max=...
  • 文章目录自然语言处理系列十一规则分词正向最大匹配法逆向最大匹配法双向最大匹配法总结 自然语言处理系列十一 规则分词 规则分词是基于字典、词库匹配的分词方法(机械分词法),其实现的主要思想是:切分语句时,...
  • 双向最大匹配方法 双向最大匹配方法是一种基于词典的分词方法。基于词典的分词方法是按照一定策略将待分析的汉字串与一个“大机器词典”中的词条进行匹配,若在词典中找到某个字符串,则匹配成功。 按照扫描方向的...
  • 一种改进的双向最大匹配分词算法,池万泱,孟祥武,中文自然语言处理技术构成中,最重要,也是最基本的技术就是中文分词。本文在深入研究相关文献后,提出一种改进的双向最大匹配
  • java实现双向最大匹配算法

    千次阅读 2018-05-22 16:24:34
    结合正向最大匹配算法和反向最大匹配算法得出的双向最大匹配算法,第一部分是正向,第二部分是反向,然后相比较两种算法,得出最优答案 package Bi_MM; import java.io.BufferedReader; import java.io....
  • 双向最大匹配算法(Bi-directction Matching method)是将最大匹配法得到的分词结果和逆向最大匹配法得到的结果通过双向最大匹配算法的规则进行筛选而得到。 #-*- coding:utf-8 -*- ''' @project: exuding-nlp-all @...
  • 双向最大匹配法:将正反最大匹配法得到的分词进行比较,按照最大匹配原则,选取词数切分最少的作为结果。 Python代码如下: #逆向匹配 class RMM(): def __init__(self, dic_path): self.dictionary = set()#集合...
  • 双向最大匹配法进行中文分词

    千次阅读 2017-01-25 20:58:58
    双向最大匹配法进行中文分词
  • 这篇将使用Java实现基于规则的中文分词算法,一个中文词典将实现准确率高达85%的分词结果。使用经典算法:正向最大匹配和反向最大匹配算法,然后双剑合璧,双向最大匹配
  • 中文分词算法—最大匹配法1 正向最大匹配法FMM2 反向最大匹配法BMM3 双向最大匹配法4 python实现代码5 参考文献 1 正向最大匹配法FMM 2 反向最大匹配法BMM 3 双向最大匹配法 4 python实现代码 5 参考文献 user_dict ...
  • 完成正向、逆向和双向最大匹配算法 import java.io.*; import java.util.*; /** * 正向最大匹配 * 逆向最大匹配 * 双向最大匹配 */ public class TwoMaxMatch { private static final int MAX_LENGTH = 5; ...
  • 正向最大匹配法分词目标:在词典中进行扫描,尽可能地选择与词典中最长单词匹配的词作为目标分词,然后进行下一次匹配。算法流程:假设词典中最长的单词为 5 个(MAX_LENGTH),那么最大匹配的起始子串字数也为 5 个(1...
  • 使用python实现正向、逆向和双向最大匹配算法 正向最大匹配 class leftMax(object): def __init__(self,dict_path): self.dictionary = set() #定义字典 self.maximum = 0 #最大匹配长度 with open(dict_path,...
  • 本人初学nlp,使用的是机械工业出版社的《python自然语言处理实战核心技术与算法》,学习到了双向最大匹配法,于是写下这篇文章记录一下整个代码的工作原理以及相应的理解。 目录一、匹配切分二、算法代码及详谈1. ...
  • 双向最大匹配算法 """ #导入正向最大匹配算法和逆向最大匹配算法 import FMM import BMM #词典元素存储变量 dict_words = [] #初始化函数,载入词典 def init(): with open("dict/dict.txt","r",encoding="utf-8...
  • 文章目录自然语言处理系列十规则分词双向最大匹配法总结 自然语言处理系列十 规则分词 规则分词是基于字典、词库匹配的分词方法(机械分词法),其实现的主要思想是:切分语句时,将语句特定长的字符串与字典进行...
  • 本篇博客使用Java编程语言实现基于规则的双向最大匹配算法,算是NLP里的一个hello world了。 2 理论描述 基于规则的自动分词算法 (1) 事先人工建立好分词词典和分词规则库。 (2) 原理为基于字符串匹配进行分词,...
  • 基于N-gram的双向最大匹配中文分词

    千次阅读 2017-11-04 16:38:32
    摘要: 这次实验的内容是中文分词。将一个句子的所有词用空格隔开,将一个字串转换为一个词序列。 而我们用到的分词算法是基于字符串的分词方法中的正向最大匹配算法和逆向最大匹配...双向最大匹配算法是两个算法的
  • 使用正向和反向最大匹配算法对给定句子进行分词,对得到的结果进行比较,从而决定正确的分词方法。算法描述正向最大匹配算法先设定扫描的窗口大小maxLen(最好是字典最长的单词长度),从左向右取待切分汉语句的maxLen...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 510
精华内容 204
关键字:

双向最大匹配