# TODO: 第一步： 从综合类中文词库.xlsx 中读取所有中文词。
#  hint: 思考一下用什么数据结构来存储这个词典会比较好？ 要考虑我们每次查询一个单词的效率。 

import pandas as pd
from collections import defaultdict

df = pd.read_excel('综合类中文词库.xlsx', header=None)

dic_words = defaultdict(int)
for i in df[0].tolist():
    dic_words[i] += 1  # 保存词典库中读取的单词
print(f'词典长度: {len(dic_words)}')

# 以下是每一个单词出现的概率。为了问题的简化，我们只列出了一小部分单词的概率。 在这里没有出现的的单词但是出现在词典里的，统一把概率设置成为0.00001
# 比如 p("学院")=p("概率")=...0.00001

word_prob = {"北京":0.03,"的":0.08,"天":0.005,"气":0.005,"天气":0.06,"真":0.04,"好":0.05,"真好":0.04,"啊":0.01,"真好啊":0.02, 
             "今":0.01,"今天":0.07,"课程":0.06,"内容":0.06,"有":0.05,"很":0.03,"很有":0.04,"意思":0.06,"有意思":0.005,"课":0.01,
             "程":0.005,"经常":0.08,"意见":0.08,"意":0.01,"见":0.005,"有意见":0.02,"分歧":0.04,"分":0.02, "歧":0.005}

print (sum(word_prob.values()))

def word_break(s, dic):
    def sentences(cur):
        result = []
        if cur < len(s):
            for next in range(cur + 1, len(s) + 1):
                if s[cur:next] in dic: #列表切片是前闭后开的过程
                    result = result + [s[cur:next] + (tail and ',' + tail) for tail in sentences(next)]
        else:
            return ['']
        return result

    list_new = []
    for line in sentences(0):
        line = line.split(",")
        list_new.append(line)
    return list_new

import math
def get_best_segments(segments):
    scores = []
    for segment in segments:
        score = 0
        for word in segment:
            prob = word_prob[word] if word in word_prob else 0.00001
            score -= math.log(prob)
        scores.append(score)
    index = scores.index(min(scores))
    return segments[index]

## TODO 请编写word_segment_naive函数来实现对输入字符串的分词
def word_segment_naive(input_str):
    """
    1. 对于输入字符串做分词，并返回所有可行的分词之后的结果。
    2. 针对于每一个返回结果，计算句子的概率
    3. 返回概率最高的最作为最后结果
    
    input_str: 输入字符串   输入格式：“今天天气好”
    best_segment: 最好的分词结果  输出格式：["今天"，"天气"，"好"]
    """

    # TODO： 第一步： 计算所有可能的分词结果，要保证每个分完的词存在于词典里，这个结果有可能会非常多。 
    segments = word_break(input_str, dic_words)  # 存储所有分词的结果。如果次字符串不可能被完全切分，则返回空列表(list)
                   # 格式为：segments = [["今天"，“天气”，“好”],["今天"，“天“，”气”，“好”],["今“，”天"，“天气”，“好”],...]
    
    # TODO: 第二步：循环所有的分词结果，并计算出概率最高(?)的分词结果，并返回
    best_segment = get_best_segments(segments)
    return best_segment      

# 测试
print (word_segment_naive("北京的天气真好啊"))
print (word_segment_naive("今天的课程内容很有意思"))
print (word_segment_naive("经常有意见分歧"))

def DAG(sentence):
        DAG = {}    #DAG空字典，用来构建DAG有向无环图
        N = len(sentence)
        for k in range(N):
            tmplist = [] 
            i = k
            frag = sentence[k]
            while i < N:
                if frag in word_prob:
                    tmplist.append(i) 
                i += 1      
                frag = sentence[k:i + 1] 
            if not tmplist:
                tmplist.append(k)
            DAG[k] = tmplist
        return DAG

## TODO 请编写word_segment_viterbi函数来实现对输入字符串的分词
def word_segment_viterbi(input_str):
    """
    1. 基于输入字符串，词典，以及给定的unigram概率来创建DAG(有向图）。
    2. 编写维特比算法来寻找最优的PATH
    3. 返回分词结果
    
    input_str: 输入字符串   输入格式：“今天天气好”
    best_segment: 最好的分词结果  输出格式：["今天"，"天气"，"好"]
    """
    
    # TODO: 第一步：根据词典，输入的句子，以及给定的unigram概率来创建带权重的有向图（Directed Graph） 参考：课程内容
    #      有向图的每一条边是一个单词的概率（只要存在于词典里的都可以作为一个合法的单词），这些概率在 word_prob，如果不在word_prob里的单词但在
    #      词典里存在的，统一用概率值0.00001。
    #      注意：思考用什么方式来存储这种有向图比较合适？ 不一定有只有一种方式来存储这种结构。 
    N=len(sentence)
    graph = DAG(sentence)
    
    # TODO： 第二步： 利用维特比算法来找出最好的PATH， 这个PATH是P(sentence)最大或者 -log P(sentence)最小的PATH。
    #              hint: 思考为什么不用相乘: p(w1)p(w2)...而是使用negative log sum:  -log(w1)-log(w2)-...
    route={}
    route[N] = (0, 0)
    
    for idx in range(N - 1, -1, -1):
        distance = (((word_prob.get(sentence[idx:x + 1]) or 0) + route[x + 1][0], x) for x in dag[idx])
        route[idx] = max(distance)
    
    # TODO: 第三步： 根据最好的PATH, 返回最好的切分
    x = 0
    best_segment = []
    while x < N:
        y = route[x][1] + 1
        word = sentence[x:y]
        best_segment.append(word)
        x = y

    return best_segment      

# 测试
print (word_segment_naive("北京的天气真好啊"))
print (word_segment_naive("今天的课程内容很有意思"))
print (word_segment_naive("经常有意见分歧"))