...

AI Studio用户名：肉禾在想桃子

作业1-1： 

AI Studio用户名：纠缠state
作业1-1：
（1）安装PaddlePaddle成功的截图：  

（2）结巴分词的使用：

（3）信息熵计算的代码如下，结果为10.33

import jieba
import os
import math
from collections import Counter
file_names = os.listdir('1946')

total_list = []
for f in file_names:
    path = os.path.join('1946', f)
    total_text = open(path).read()
    seg_list = list(jieba.cut(total_text))
    total_list += seg_list
# 词数统计
cnt_dict = Counter(total_list)
# 信息熵
c = 0
for a in cnt_dict:
    # 词出现的概率 = 出现次数/总词量
    cnt_dict[a] /= len(total_list)
    p = cnt_dict[a]
    c += p * math.log(p, 2)
c = -c
print("信息熵：", c)

作业1-2：
（1）对于长度为N的词典，长度为M的句子，最坏情况下每个词都需要切分，如果考虑用hash表存储词典，查找一个词的时间复杂度是O(1)，那么总的时间复杂度是O(M)；但这种存储不高效，一般用字典树，查找一个词的时间复杂度为O(该词的长度)，由于词最大的长度是整个句子的长度，所以这种情况下总的时间复杂度是O(M^2)。

（2）用递归的方法做，每次对当前切片查找，直到有一个切片存在于字典中，才继续定位下个切片。代码如下：

def count_seg(d, s, idx, l, res_list, res):
	if idx>=l:
		if res.copy() not in res_list:
			res_list.append(res.copy())
			print(res)
		return 
		
	for i in range(idx, l+1):
		if s[idx:i] in d:
			res.append(s[idx:i])
			count_seg(d, s, i, l, res_list,res)
			res.pop()
			
if __name__ == '__main__':
	d = ['南京','南京市','市长','长江','大桥','江','南','京','市','长','大','桥']
	s = '南京市长江大桥'
	res_list, res = [], []
	count_seg(d, s, 0, len(s),res_list,res)
	print("一共有{:d}种分词方式".format(len(res_list)))

运行结果如下：

（3）基于词典的分类还有：后向匹配法和双相匹配法，后向匹配的思想和前向匹配差不多，只是匹配方向不同；双相匹配是同时使用前向和后向匹配，对于有歧义的部分进一步处理。
还有基于概率图模型的方法，比如隐马尔科夫模型，把原始输入看成观测序列，而分词的规则看做是状态序列；条件随机场是判别式模型，本质是一个无向图，直接对序列进行建模。
基于深度学习的模型有，双向LSTM，BERT等。

AI Studio用户名：LXYTSOS

作业1-1

（1）安装paddle

（2）（3）jieba分词的使用以及对人民日报语料库的分词，计算信息熵。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
__title__ = 
__author__ = liuxiangyu
__mtime__ = 2020/2/26 10:50
"""
import os
import math
import jieba

data_path = 'data'
word_frequency = dict()
word_counts = 0
entropy = 0

for file_name in os.listdir(data_path):
    with open(os.path.join(data_path, file_name), encoding='utf-8') as f:
        content = []
        lines = f.readlines()
        for line in lines:
            line = line.strip().replace(' ', '').replace('\n', '')\
                .replace('“', '').replace('”', '').replace('、', '')\
                .replace('，', '').replace('。', '').replace('。', '')\
                .replace('（', '').replace('）', '').replace('-', '')
            content.append(line)
        content = ''.join(content)
        seg_list = jieba.cut(content)
        seg_list = list(seg_list)
        word_counts += len(seg_list)
        for seg in seg_list:
            if seg not in word_frequency.keys():
                word_frequency[seg] = 1
            else:
                word_frequency[seg] += 1

for k, v in word_frequency.items():
    p = v / word_counts
    entropy -= p * math.log(p)

print('entropy: ', entropy)

作业1-2

（1）需要匹配的次数为n * (m*(m+1)/2)，所以计算复杂度是O(NM^2)

（2）使用栈，入栈当前的候选分词，栈顶元素弹出时，在这个词语基础上对后续句子进行切分，把候选词入栈，重复上述过程。

# 伪代码
# 返回第一次切分出现的候选词
def forward_segment(text):
    # 从词典中搜索当前可能的分词候选
stack = []
candidates = forward_segment(text)
#所有候选词的树形结构
tree = Tree()
tree.root = 'bos'
tree.root.child = candidates
stack.push(candidates)
while(stack is not None):
    word = stack.pop()
    next_candidates = forward_segment(text.split(word)[1])
    tree.get_node_by_value(word).child = next_candidates 
    segments[word] = next_candidates
    stack.push(next_candidates)

（3）其他分词算法

1、逆向最长匹配
在使用正向最长匹配分词时，有时会产生意料之外的结果，比如“研究生命起源”，会被切分成[研究生, 命, 起源]，因此有人提出逆向最长匹配，从后往前扫描，保留最长词汇。然而还是产生于前向最长匹配同样的问题，因此有人提出综合两种规则，期待取长补短，也就是双向最长匹配。

2、双向最长匹配
在分词时，有时正向效果好，有时逆向效果好，双向最长匹配的思想是从两种结果中挑选出更好的一个。流程如下：同时执行正向和逆向最长匹配，若两者的词数不同，则返回词数更少的那一个，否则返回两者中单字最少的那一个。当单字数也相同时，优先返回逆向最长匹配结果。

AI Studio用户名：星光ld1

作业1-1：

信息熵统计代码（只统计了RMRB1946年5月数据）

信息熵统计结果 

AI Studio用户名：Love萌

作业1-1：

AI Studio用户名：叶璟kessing

作业1.1

作业1.2

AI Studio用户名：phoinikas

作业1-1:

（1）Paddle本地安装

（2）Jieba分词的三种模式

（3）人民日报语料的切词和统计

作业1-2:

（1）最坏情况只能单字，一共要尝试匹配的词有M(M-1)个，复杂度为O(NM^2)

（2）递归回溯

（3）

基于词典分词的除了正向最大匹配还有逆向最大匹配、双向最大匹配。

逆向最大匹配与正向区别是逆向是循环去掉前面的字进行匹配。双向最大匹配对正向和反向的结果进行比较，比较规则：如果正反向分词结果词数不同，选择分词数量较少的；如果分词结果词数相同，选择单字较少的。

基于统计分词的除了n-gram还有隐马尔可夫模型、条件随机场、神经网络分词等。

Jieba分词是词典分词和统计分词都有的混合分词。

AI Studio用户名：javaroom

作业1-1：

（1）paddlepaddle安装

本人电脑显卡为vega56， 所以安装cpu版本
安装：
pip3 install paddlepaddle -i https://pypi.tuna.tsinghua.edu.cn/simple

（2）学习使用PaddleNLP下面的LAC模型或Jieba分词

（3）对人民日报语料完成切词，并通过统计每个词出现的概率，计算信息熵

# -*- coding: utf-8 -*-
"""
__title__ =
__author__ = javaroom
__date__ = 2020/2/26 15:32
"""

import os
import math
import jieba
from collections import Counter

def word_count(filepath):
word_list = []
file_list = os.listdir(filepath)
for file in file_list:
path = os.path.join(filepath, file)
text = open(path, encoding='utf-8').read()
text = text.strip().replace(' ', '').replace('\n', '').replace('“', '') \
.replace('”', '').replace('、', '') \
.replace('，', '').replace('。', '').replace('。', '') \
.replace('（', '').replace('）', '').replace('-', '')
seg_list = jieba.cut(text)
word_list += seg_list
word_count = Counter(word_list)
# 计算信息熵
entropy = 0
for word in word_count:
word_count[word] /= len(word_list)
percent = word_count[word]
entropy += percent * math.log(percent, 2)
entropy = -entropy
print("信息熵：", entropy)

if __name__ == '__main__':
file_dir = '194605'
word_count(file_dir)

C:\Python37\python.exe C:/Users/Administrator/PycharmProjects/paddletest/fenci/jiebatest.py
Building prefix dict from the default dictionary ...
Loading model from cache C:\Users\ADMINI~1\AppData\Local\Temp\jieba.cache
Loading model cost 0.650 seconds.
Prefix dict has been built successfully.
信息熵： 11.762779320674147

Process finished with exit code 0

作业1-2：

（1）思考一下，假设输入一个词表里面含有N个词，输入一个长度为M的句子，那么最大前向匹配的计算复杂度是多少？

从后向前，依次和词表里N个词进行比较，那么应该是N*(m(m+1)/2)

（2）给定一个句子，如何计算里面有多少种分词候选，你能给出代码实现吗？

最多的分词候选，那么急于最大前向匹配算法，从后到前，每匹配上1词，算1个。

（3）除了最大前向匹配和N-gram算法，你还知道其他分词算法吗，请给出一段小描述。

前向最大匹配算法：从前向后寻找在词典中存在的词。

后向最大匹配算法：与前向最大匹配算法类似，只是方向相反，即从后向前寻找词典中存在的词并输出。

双向最大匹配算法：双向最大匹配算法的原理就是将正向最大匹配算法和逆向最大匹配算法进行比较，从而确定正确的分词方法。

AI Studio用户名：javaroom

作业1-1：

（1）paddlepaddle安装

本人电脑显卡为vega56， 所以安装cpu版本
安装：
pip3 install paddlepaddle -i https://pypi.tuna.tsinghua.edu.cn/simple

（2）学习使用PaddleNLP下面的LAC模型或Jieba分词

（3）对人民日报语料完成切词，并通过统计每个词出现的概率，计算信息熵

# -*- coding: utf-8 -*-
"""
__title__ =
__author__ = javaroom
__date__ = 2020/2/26 15:32
"""

import os
import math
import jieba
from collections import Counter

def word_count(filepath):
word_list = []
file_list = os.listdir(filepath)
for file in file_list:
path = os.path.join(filepath, file)
text = open(path, encoding='utf-8').read()
text = text.strip().replace(' ', '').replace('\n', '').replace('“', '') \
.replace('”', '').replace('、', '') \
.replace('，', '').replace('。', '').replace('。', '') \
.replace('（', '').replace('）', '').replace('-', '')
seg_list = jieba.cut(text)
word_list += seg_list
word_count = Counter(word_list)
# 计算信息熵
entropy = 0
for word in word_count:
word_count[word] /= len(word_list)
percent = word_count[word]
entropy += percent * math.log(percent, 2)
entropy = -entropy
print("信息熵：", entropy)

if __name__ == '__main__':
file_dir = '194605'
word_count(file_dir)

C:\Python37\python.exe C:/Users/Administrator/PycharmProjects/paddletest/fenci/jiebatest.py
Building prefix dict from the default dictionary ...
Loading model from cache C:\Users\ADMINI~1\AppData\Local\Temp\jieba.cache
Loading model cost 0.650 seconds.
Prefix dict has been built successfully.
信息熵： 11.762779320674147

Process finished with exit code 0

作业1-2：

（1）思考一下，假设输入一个词表里面含有N个词，输入一个长度为M的句子，那么最大前向匹配的计算复杂度是多少？

从后向前，依次和词表里N个词进行比较，那么应该是N*(m(m+1)/2)

（2）给定一个句子，如何计算里面有多少种分词候选，你能给出代码实现吗？

最多的分词候选，那么急于最大前向匹配算法，从后到前，每匹配上1词，算1个。

（3）除了最大前向匹配和N-gram算法，你还知道其他分词算法吗，请给出一段小描述。

前向最大匹配算法：从前向后寻找在词典中存在的词。

后向最大匹配算法：与前向最大匹配算法类似，只是方向相反，即从后向前寻找词典中存在的词并输出。

双向最大匹配算法：双向最大匹配算法的原理就是将正向最大匹配算法和逆向最大匹配算法进行比较，从而确定正确的分词方法。

AI Studio用户名：星光ld1

作业1-2：

(1) N词 M句
最坏情形下单字匹配，算法复杂度为：
N*(M)+N*(M-1)+N*(M-2)+...+N*1=N*(M*(M+1)/2)
(2) 基于前向最大匹配的算法设计

def segment(word_dict, sentence, start, end, candiate_list, tmp):
    if start >= end:
        if tmp.copy() not in candiate_list:
            candiate_list.append(tmp.copy())
        return
    
    for i in range(start, end+1):
        if sentence[start:i] in word_dict:
            tmp.append(sentence[start:i])
            segment(word_dict, sentence, i, end, candiate_list, tmp)
            tmp.pop()
			
if __name__ == '__main__':
	word_dict = ['今天','天','是','个','好','气','天气','好天气']
	sentence = '今天是个好天气'
	candiate_list, tmp = [], []
	segment(word_dict, sentence, 0, len(sentence), candiate_list, tmp)
	print(candiate_list)
	print("共%d种!" % len(candiate_list))

(3) 最大后向匹配，最大双向匹配
最大后向匹配：与前向最大匹配算法类似，只是方向相反，即从后向前寻找词典中存在的词并输出。
双向最大匹配算法的原理就是将正向最大匹配算法和逆向最大匹配算法进行比较，从而确定正确的分词方法。
步骤如下：
1.比较正向最大匹配和逆向最大匹配结果。
2.如果分词数量结果不同，那么取分词数量较少的那个。
如果分词数量结果相同：
- 分词结果相同，可以返回任何一个。
- 分词结果不同，返回单字数比较少的那个，
- 如果单字数个数也相同，则任意返回一个。

AI Studio用户名: nfspp

作业1-1

(1): 已发班主任

(2):

(3)

1-2:

(1) 最坏的情况是句子里面没有一个字出现在词典里. 假设查字典的时间复杂度为O(1), 则总复杂度为O(M); 假设查字典复杂度为O(N), 则总复杂度为O(M*N)即O(N^2)

(2)句子长度设为n. 如果没有词典. 则所有可能的分词候选为1+2+3+...+n=(1+n)*n/2种

如果存在词典. 首先要说明的是: 如果词典不能覆盖所有的字(存在oov), 我都会把单字看作一个词来对待. 借鉴了同学@纠缠state 递归的做法 . 但我是从单字出发组合成词, 也考虑进了词典不能完全覆盖的情况.

(3) 其他分词方法还有

后向最大匹配法, 跟前向一样只是方向相反.
双向最大匹配法, 同时做前向和后向最大匹配, 结果选分到的词多的.
基于隐马尔可夫或者条件随机场模型, 使用标注好的语料训练分词器
基于神经网络的语言模型. 包括LSTM, 预训练模型(BERT, ERNIE)等, 也是使用标注数据训练

AI Studio用户名：哓哓晓培

百度账号:18877286876

作业内容较多,为了写的更加清楚,我写成了一篇博客:https://blog.csdn.net/zbp_12138/article/details/104517306

作业1-1：因为文章太多,这里我只选了三篇文章 

这样看到三篇文章合起来的信息熵是8.8,再来看看每个词出现的概率,往上翻:

你、了出现的概率都挺高的,但是大部分被切出来的词只出现过一次

作业1-2：

（1）

这里我打算举个例子来分析:“祝人民日报创刊”

这句话含有3个词(祝、人民日报、创刊),句子的长度为7,使用最大向前匹配算法取词，如果匹配失败，每次去掉匹配字段最后面的一个字:

第一轮:

“祝人民日报创刊”,没有匹配,去掉一个字,变为"祝人民日报创"
“祝人民日报创”,没有匹配,去掉一个字,变为"祝人民日报"
“祝人民日报”,没有匹配,去掉一个字,变为"祝人民日"
“祝人民日”,没有匹配,去掉一个字,变为"祝人民"
“祝人民”,没有匹配,去掉一个字,变为"祝人"
“祝人”,没有匹配,去掉一个字,变为"祝"
“祝"成功匹配,去掉"祝”,进行下一轮
第二轮:

“人民日报创刊”,没有匹配,去掉一个字,变为"人民日报创"
“人民日报创”,没有匹配,去掉一个字,变为"人民日报"
“人民日报”,成功匹配,去掉"人民日报",进行下一轮
第三轮:

"创刊"成功匹配,句子结束,结束循环
由此我们看到使用最大向前匹配算法切词时,词表里面含有N个词则进行N轮循环,而一轮循环下又有循环,最大循环次数为M(句子长度),因此时间复杂度用大O表示法可以表示为O(NM)

（2）

我们还是拿刚刚的例子举例:‘祝人民日报创刊’,一说到有多少种情况,我想到的是阶乘,这句话有7个字,如果按照7的阶乘算:7*6*5*4*3*2*1=5040

当然,这里不是列出这七个字所有的排列组合,至少把顺序给出来了,那结果肯定就要比5040要少。除此之外,我们还可以通过规定词语的最大长度,但是题目没有规定,我们则按最大长度为7来执行

class NLP_DEMO(object):
    def __init__(self):
        self.dic = ['祝人民日报创刊','祝人民日报创','人民日报创刊','祝人民日报','人民日报创','民日报创刊','祝人民日','人民日报','民日报创','日报创刊','祝人民','人民日','民日报','日报创','报创刊','祝人','人民','民日','日报','报创','创刊','祝','人','民','日','报','创','刊']
        self.str = '祝人民日报创刊'
        self.length = len(self.str)
        self.res_list, self.res = [], []

	def count_seg(self, idx):
        if idx>=self.length:
            if self.res.copy() not in self.res_list:
                self.res_list.append(self.res.copy())
                print(self.res)
            return

        for i in range(idx,self.length+1):
            if self.str[idx:i] in self.dic:
                self.res.append(self.str[idx:i])
                self.count_seg(i)
                self.res.pop()

    def out_put(self):
        print("一共有{:d}种分词方式".format(len(self.res_list)))

def main():
    nlp_demo = NLP_DEMO()
    nlp_demo.count_seg(0)
    nlp_demo.out_put()

if __name__ == '__main__':
    main(

(3)既然刚刚提到了最大前向匹配算法,那我自然而然就想到了最大后向匹配算法,与前向最大匹配算法类似，只是方向相反，即从后向前寻找词典中存在的词并输出。

而双向最大匹配算法是前两者的集合:

1.比较正向最大匹配和逆向最大匹配结果。
2.如果分词数量结果不同，那么取分词数量较少的那个;如果分词数量结果相同： (1).分词结果相同，可以返回任何一个 (2).分词结果不同，返回单字数比较少的那个

AI Studio用户名：chenyh2009cyh

作业1-1：

（1）

(2)

(3)

作业1-2：

(1) O(mmn)

(2)

（3）
后向最大匹配算法：
例：我们是正常的生命体（max_len = 6）

第一轮：取子串 “正常的生命体”，后向取词，如果匹配失败，每次去掉匹配字段最前面的一个字。

“正常的生命体”，扫描词典中的6字单词，没有匹配，

“常的生命体”，扫描词典中的5字单词，没有匹配，

“的生命体”，扫描词典中的4字单词，没有匹配，

“生命体”，扫描词典中的3字单词，匹配成功，输出“生命体”，输入变为“我们是正常的”。

第二轮：取子串“我们是正常的”

以此类推，直到输入长度为0时，扫描终止。

AI Studio用户名：macclover

作业1-1
（1）下载飞桨本地并安装成功,将截图发给班主任:

推荐 conda 创建环境 进行安装,因为paddle 更新较快,不同版本下有些细微的差异.包括生成的model 也可能会有使用上的一些小问题.

建议用ubuntu 环境,对paddle-gpu功能支持的比较完整.

paddle建议安装1.6及以上,对NLP支持完整

需要安装paddlehub​

（2）学习使用PaddleNLP下面的LAC模型或Jieba分词

LAC模型地址：https://github.com/PaddlePaddle/models/tree/release/1.6/PaddleNLP/lexical_analysis

模型评估
我们基于自建的数据集训练了一个词法分析的模型，可以直接用这个模型对测试集 ./data/test.tsv 进行验证，

# baseline model
bash run.sh eval
得到结果:
​

# ERNIE finetuned model
bash run_ernie.sh eval
得到结果:  
​

模型训练
基于示例的数据集，可通过下面的命令，在训练集 ./data/train.tsv 上进行训练，示例包含程序在单机单卡/多卡，以及CPU多线程的运行设置

Warning: 若需进行ERNIE Finetune训练，需自行下载 ERNIE 开放的模型，下载链接为： https://baidu-nlp.bj.bcebos.com/ERNIE_stable-1.0.1.tar.gz，下载后解压至 ./pretrained/ 目录下。
# baseline model, using single GPU
sh run.sh train_single_gpu

模型预测
加载已有的模型，对未知的数据进行预测

# baseline model
sh run.sh infer
得到结果:
​ 
 

（3）对人民日报语料完成切词，并通过统计每个词出现的概率，计算信息熵

语料地址：https://github.com/fangj/rmrb/tree/master/example/1946%E5%B9%B405%E6%9C%88

下载到本地后,先用paddleNLP的预处理进行分词预处理 :

​

原来CPU 10小时 1GB文本 ,GPU只需要50分钟.完成. paddle在分词速度上优势明显.

分别按月\年\所有 三个时间维度 统计词频:

​​可以发现每一年的新闻都有一些不同的高频词汇,反映当时的政治面貌

接着计算信息熵: 

作业1-2

（1）思考一下，假设输入一个词表里面含有N个词，输入一个长度为M的句子，那么最大前向匹配的计算复杂度是多少？

对于长度为N的词典，长度为M的句子，最坏情况下每个词都需要切分，一般用字典树存储词典，查找一个词的时间复杂度为O(该词的长度)，复杂度是O(N*M), 由于词最大的长度是整个句子的长度，所以计算复杂度是O(M^2)

（2）给定一个句子，如何计算里面有多少种分词候选，你能给出代码实现吗？

paddle的分词只支持精确模式,这里用jieba做初步处理.
匹配算法直接引用网友"纠缠state "的实现

​

（3）除了最大前向匹配和N-gram算法，你还知道其他分词算法吗，请给出一段小描述。

比如:

1.逆向最大匹配算法RMM:该算法是正向最大匹配的逆向思维，匹配不成功，将匹配字段的最前一个字去掉，实验表明，逆向最大匹配算法要优于正向最大匹配算法。

2. 双向最大匹配法:是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。

作业1-1

（1）安装飞桨PaddlePaddle成功的截图

（2）学习使用PaddleNLP下面的LAC模型或Jieba分词

• 代码

  # encoding=utf-8
  import jieba
  jieba.enable_paddle()
  strs=["百度AI Studio真的很不错","南京长江大桥","我不是一个个个结巴巴"]
  for count, str in enumerate(strs,start=1):
  seg_list = jieba.cut(str,use_paddle=True) # 使用paddle模式
  print(count)
  print('/'.join(list(seg_list)))​

• 结果

  /Users/grey/NLP/bin/python /Users/grey/PycharmProjects/NLP/stutter.py
  1
  Paddle enabled successfully......
  2020-02-26 11:14:20,372-DEBUG: Paddle enabled successfully......
  百度/AI Studio/真/的/很不错
  2
  南京长江大桥
  3
  我/不是/一个个个/结巴巴​​

（3）对人民日报语料完成切词，并通过统计每个词出现的概率，计算信息熵

• 代码

  import os
  import codecs
  import jieba
  import re
  import math
  
  path = "194605"
  words = []
  words_frequency = dict()
  
  # 去除标点符号、空格、换行、下划线等
  def replace_all_blank(value):
  result = re.sub('\W+', '', value).replace("_", '')
  return result
  
  # 得到包括所有词的数组
  for root, dirs, files in os.walk(path):
  for name in files:
  filePath = os.path.join(root, name)
  f = codecs.open(filePath, 'r', 'utf-8')
  fileContent = f.read()
  f.close()
  fileContent = replace_all_blank(fileContent)
  seg_list = jieba.cut(fileContent)
  seg_list = list(seg_list)
  words += seg_list
  
  # 计算词频
  words_count = len(words)
  entropy = 0
  
  for word in words:
  if word not in words_frequency.keys():
  words_frequency[word] = 1
  else:
  words_frequency[word] += 1
  
  for k, v in words_frequency.items():
  p = v / words_count
  entropy -= p * math.log(p)
  
  #按照词频排序
  words_sorted = list(words_frequency.items())
  words_sorted.sort(key=lambda e: e[1], reverse=True)
  
  # 输出结果
  print('entropy: ', entropy)
  print('top 3 words: ', words_sorted[1],words_sorted[2],words_sorted[3])​​

• 结果

  entropy: 8.226938281616315
  top 3 words: ('在', 1557) ('了', 1291) ('国民党', 885)​​

作业1-2

（1）思考一下，假设输入一个词表里面含有N个词，输入一个长度为M的句子，那么最大前向匹配的计算复杂度是多少？

• 若规定词的最大长度为M，则最多的搜索次数为N*(M+M-1+...+2+1)，因此算法复杂度为O(NM^2)。

（2）给定一个句子，如何计算里面有多少种分词候选，你能给出代码实现吗？

• 代码（递归）

  def count_seg_candidates(candidate, remained, dictionary):
  if len(remained) == 0:
  print('/'.join(candidate))
  return 1
  count = 0
  for i in range(1, len(remained)+1):
  if (remained[:i]) not in dictionary:
  continue
  count += count_seg_candidates(candidate + [remained[:i]], remained[i:], dictionary)
  return count
  
  d = ['南京','市','长江','大桥','江大桥','市长']
  text = '南京市长江大桥'​
  print('分词候选数',count_seg_candidates([],text,d))

• 示例

  南京/市/长江/大桥
  南京/市长/江大桥
  分词候选数 2​

（3）除了最大前向匹配和N-gram算法，你还知道其他分词算法吗，请给出一段小描述。

• 最大前向匹配算法是基于词表的分词方法，N-gram算法是基于统计的分词方法，还有一类为基于序列标注的分词方法，例如HMM的分词方法，CRF的分词方法和基于深度学习的端到端的分词方法等。HMM有三类基本问题：预测，平滑和解码。与HMM不同的是，CRF是一种判别式模型，CRF通过定义条件概率P(Y∣X)来描述模型。基于深度学习的端到端分词方法需要较大的语料训练才能有明显的优势。

忘记写AI Studio用户名啦，特此补上，善良的古语123。

重新提交：由于超时的缘故，复制粘贴的代码格式都乱了，新手第一次提交，以后会注意的，抱歉！

AI Studio: 善良的古语123

作业1-1

（1）安装飞桨PaddlePaddle成功的截图

（2）学习使用PaddleNLP下面的LAC模型或Jieba分词

# encoding=utf-8
import jieba

strs=["百度AI Studio真的很不错","南京长江大桥","我不是结巴"]
for count, str in enumerate(strs,start=1):
    seg_list = jieba.cut(str)
    print(count)
    print('/'.join(list(seg_list)))

1
百度/AI Studio/真/的/很不错
2
南京长江大桥
3
我/不是/一个个个/结巴巴​​

（3）对人民日报语料完成切词，并通过统计每个词出现的概率，计算信息熵

import os
import codecs
import jieba
import re
import math

path = "194605"
words = []
words_frequency = dict()

# 去除标点符号、空格、换行、下划线等
def replace_all_blank(value):
    result = re.sub('\W+', '', value).replace("_", '')
    return result

# 得到包括所有词的数组
for root, dirs, files in os.walk(path):
    for name in files:
        filePath = os.path.join(root, name)
        f = codecs.open(filePath, 'r', 'utf-8')
        fileContent = f.read()
        f.close()
        fileContent = replace_all_blank(fileContent)
        seg_list = jieba.cut(fileContent)
        seg_list = list(seg_list)
        words += seg_list

# 计算词频
words_count = len(words)
entropy = 0

for word in words:
    if word not in words_frequency.keys():
        words_frequency[word] = 1
    else:
        words_frequency[word] += 1

for k, v in words_frequency.items():
    p = v / words_count
    entropy -= p * math.log(p)

#按照词频排序
words_sorted = list(words_frequency.items())
words_sorted.sort(key=lambda e: e[1], reverse=True)

# 输出结果
print('entropy: ', entropy)
print('top 3 words: ', words_sorted[1],words_sorted[2],words_sorted[3])

entropy: 8.226938281616315
top 3 words: ('在', 1557) ('了', 1291) ('国民党', 885)​​

作业1-2

（1）思考一下，假设输入一个词表里面含有N个词，输入一个长度为M的句子，那么最大前向匹配的计算复杂度是多少？

• 若规定词的最大长度为M，则最多的搜索次数为N*(M+M-1+...+2+1)，因此算法复杂度为O(NM^2)。

（2）给定一个句子，如何计算里面有多少种分词候选，你能给出代码实现吗？

def count_seg_candidates(candidate, remained, dictionary):
    print(candidate)
    print(remained)
    if len(remained) == 0:
        print('/'.join(candidate))
        return 1
    count = 0
    for i in range(1, len(remained)+1):
        print(i)
        if (remained[:i]) not in dictionary:
            continue
        count += count_seg_candidates(candidate + [remained[:i]], remained[i:], dictionary)
    return count

d = ['南京','市','长江','大桥','江大桥','市长']
text = '南京市长江大桥'
print('分词候选数',count_seg_candidates([],text,d))

南京/市/长江/大桥
南京/市长/江大桥
分词候选数 2​

（3）除了最大前向匹配和N-gram算法，你还知道其他分词算法吗，请给出一段小描述。

• 最大前向匹配算法是基于词表的分词方法，N-gram算法是基于统计的分词方法，还有一类为基于序列标注的分词方法，例如HMM的分词方法，CRF的分词方法和基于深度学习的端到端的分词方法等。HMM有三类基本问题：预测，平滑和解码。与HMM不同的是，CRF是一种判别式模型，CRF通过定义条件概率P(Y∣X)来描述模型。基于深度学习的端到端分词方法需要较大的语料训练才能有明显的优势。

AI Studio用户名：lsvine_bai

作业1-1

（1）安装paddle

（2）学习使用PaddleNLP下面的LAC模型或Jieba分词

# encoding=utf-8
import jieba

strs=["百度AI Studio真的很不错","南京长江大桥","我不是结巴"]
for count, str in enumerate(strs,start=1):
seg_list = jieba.cut(str)
print(count)
print('/'.join(list(seg_list)))
1
百度/AI Studio/真/的/很不错
2
南京长江大桥
3
我/不是/一个个个/结巴巴​​

作业1-2:

（1）最坏情况只能单字，一共要尝试匹配的词有N*(M+M-1+...+2+1)个，复杂度为O(NM^2)。

（3）其他分词算法

1、逆向最长匹配
在使用正向最长匹配分词时，有时会产生意料之外的结果，比如“研究生命起源”，会被切分成[研究生, 命, 起源]，因此有人提出逆向最长匹配，从后往前扫描，保留最长词汇。然而还是产生于前向最长匹配同样的问题，因此有人提出综合两种规则，期待取长补短，也就是双向最长匹配。

2、双向最长匹配
在分词时，有时正向效果好，有时逆向效果好，双向最长匹配的思想是从两种结果中挑选出更好的一个。流程如下：同时执行正向和逆向最长匹配，若两者的词数不同，则返回词数更少的那一个，否则返回两者中单字最少的那一个。当单字数也相同时，优先返回逆向最长匹配结果。

AI Studio用户名：jianghaoyu123

作业1-1

(1) 已经安装成功。

(2) 已利用jieba分词进行分词。

(3)解：
计算所得的信息熵为8.4748 (去掉了一些停顿助词)
具体思路为先读取各个原始文件，取其文章的文字部分，再进行停顿词和符号的去除，接着进行分词，再统计词频以字典的形式存储，最后将字典转换成DataFrame统计信息熵。

# -*- coding:utf-8 -*-
import jieba
import os 
import re
import pandas as pd
import numpy as np

#去掉符号的函数
def remove_tokens(tem):   
   punct = ('!', '"', '#', '$', '%', '&', '(', ')', '*', '+', ',', '-', '.', '/', ':', ';', '<', '=', '>', '?', '@', '[', '\\', ']', '_', 
              '{', '|', '}', '~', '°', '±', '×', '—', '‘', '’', '“', '”', '′', '″', '≤', '≥', '①', '②', '③', '④', '⑤', '⑥',
              '⑦', '⑧', '⑨', '⑩', '、', '。', '《', '》', '【', '】', '〔', '〕', '！', '＂', '（', '）', '，', '：', '；', '？', '～',
              '￥','。','.','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','1','2',
               '3','4','5','6','7','8','9','0','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U',
               'V','W','X','Y','Z','\n','\t','\u3000')
   for key in punct:
       tem=tem.replace(key, ' ')
   return tem

#去除常见的停顿助词的函数,可以从专门的库里面下载，这里手打了几个作为示例
def remove_zhuci(tem):   
   zhuci = ('的','了', '和', '与','阿','啊','啦','唉','呢','吧','哇','呀','不仅','虽然','但是','而且','因为','所以',
                  '不但','但','不只','一些','甚至','接着','然后','之','已','于','在','我','你','他','她','是','着','也',
                '说','要','对','不','都','这','那','又','并','就','去','它')
   for key in zhuci:
       tem=tem.replace(key, ' ')
   return tem

#分词函数
def words_count(file):
   char1=''
   char2='
\n'
   with open(file, 'r',encoding='UTF8') as f:
      raw = f.read()
   nPos1=raw.find(char1)
   nPos2=raw.find(char2)
   raw=raw[nPos1+len(char1):nPos2]   
   raw=remove_tokens(raw)
   raw=remove_zhuci(raw)
   word_list = list(jieba.cut(raw, cut_all=False))
   return word_list
                     
#构建字典，统计词频的函数
def word_dict(word_list,word_fre):
   for word in word_list:
      if word in word_fre.keys():
         word_fre[word] += 1
      else:
         word_fre[word] = 1
   del word_fre[' ']         
   return word_fre

#读取所有的数据并进行分词以及创建词频字典
word_fre={}  #储存词频的字典
path_tem="./rmrb"
for file in os.listdir(path_tem):
   file_tem = os.path.join(path_tem,file)
   word_list = words_count(file_tem)
   word_fre= word_dict(word_list,word_fre)

#词频字典转换成pandas格式，计算信息熵
data=pd.DataFrame(index=range(len(word_fre)),columns = ['单词','词频'])
i=0
for key,value in word_fre.items():
   data.iloc[i,0]=key
   data.iloc[i,1]=value
   i=i+1
data['词频']=data['词频'].astype('float')
data.sort_values(by='词频',axis=0,ascending=False)
data['词频']=data['词频']/(data['词频'].sum(axis=0))
informationentropy=-(np.log(data['词频'])*data['词频']).sum() #信息熵的计算

作业1-2

(1) 解：
设句子的长度为M，词表里有N个单词。
为了计算最大前向匹配的计算复杂度，考虑最坏情况，假设每次取词的Max_len=M,词表中N个单词每个单词的长度都为1。
第一轮，取子串，子串长度为M,则第一轮需要比较M*N次；
第二轮，去掉第一个字，取剩余字符为子串，子串长度为M-1,则第二轮需比较(M-1)*N次；
...
第M轮，去掉前M-1个字，取剩余字符为子串,子串长度为M-(M-1)=1,则第M轮需比较1*N次；
所以，一共需要比较N*(1+M)*M/2次，即计算复杂度为N*(1+M)*M/2;

(2) 解：
思路：首先建立分词的有向无环图，接着利用有向图，得到所有的路径，即可得到所有候选分词组合的种类数量。

代码部分：
# -*- coding:utf-8 -*-
#首先，假设我们有一个词表，词表以集合变量word_dict表示，里面储存了所有的单词；再假设我们有一个句子，句子假设以字符串变量sentence表示。
word_dict={'XX','XX',...'XX'} #word_dict是我们的已知字典词表
word={}; #先建立一个空字典储存所有的字对应的可能分词，构成有向图；
for i in range(len(sentence)):
   word[sentence[i]]=[];  #每个字建立一个列表储存所有的分词，构成有向图的顶点。
   for j in range(i+1,len(sentence)):
      if sentence[i:j] in word_dict:
          word[i].append(j)  #j表示每个分词中最后一个字的位置加一，构成了有向图中的边。

##利用递归法，构建函数寻找有向图所有的可能路径，并返回最终所有可能路径的数量。
def findAllPath(word,start=0,path=[]): 
    path = path +[start]
    if start >= len(word):
        return [path]
 
    paths = [] #存储所有路径    
    for node in word[start]:
        if node not in path:
            newpaths = findAllPath(word,node,path)   #此处用到递归，寻找所有路径
            print(newpaths)
            for newpath in newpaths:
                paths.append(newpath)    
    return (paths)
Nums=findAllPath(word,0,[]) #所有的可能分词组合的种类数量。

(3) 答:
除了最大前向匹配和N-gram算法，还有以下的分词算法：
① 逆向最大匹配法：
与正向前向匹配法类似，区别在于从句子的末尾开始处理，如果匹配不成功则减去最前面的一个字。
② 双向最大匹配法
将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，利用一些设定的规则，例如分词所得词条数最小的为最优的方法，从而决定正确的分词方法。
③ 最短路径分词算法
即第(2)题所采用的算法，首先将一句话中的所有词匹配出来，构成词图，之后寻找从起始点到终点的最短路径作为最佳组合方式。
④ HMM隐马尔可夫模型
利用四个隐含状态描述不同字在词中的位置，B表示词组的开头，M词组的中间，E词组的结尾，S表示单字成词。通过标注好的分词训练集，可以得到HMM的各个参数，然后使用维特比算法来解释测试集，得到分词结果。
此外，还有基于深度学习的BERT、ALBERT模型等等。