# 读取Glove文件。 注意： 不要试图修改文件以及路径
!pip install pulp
import numpy as np
from pulp import *

word2id={}
word2vec={}
with open("glove.6B.100d.txt","r",encoding="utf-8") as glovefile:
    for i,each_line in enumerate(glovefile):
        each_vec=each_line.strip().split(' ')
        word2vec[each_vec[0]]=np.array([float(i) for i in each_vec[1:]])
        word2id[each_vec[0]]=i


#分割句子为单个词
def split_sentence(sent):
    split_list=[]
    for each in sent.strip().split():
        if each in word2id:
            split_list.append(each.strip())
    return split_list
#获取单词对应的向量
def get_vector(split_list,word2vec,word2id):
    word_vector={}
    for each in split_list:
        word_vector[word2id[each]]=word2vec[each]#注意要用ID（即词表中的次序）来标识每个词，这样方便表示词在句子中出现的频率
    return word_vector
#计算句子中每个词的词频
def calculate_freq(split_list,word2id):
    freq=np.zeros(len(word2id))
    for each in split_list:
        freq[word2id[each]]=+1
    return freq/freq.sum()
#计算不同句子之间的单词的词向量距离
def cost(v1,v2):
    dist=np.linalg.norm(v1-v2)
    return dist
#基于词向量计算WMD组合
def solve_lp(split_list1,split_list2,vector1,vector2,freq1,freq2):
    list1_id=[word2id[each] for each in set(split_list1)]
    list2_id=[word2id[each] for each in set(split_list2)]
    
    problem=LpProblem("wmp_lp",LpMinimize)
    T=LpVariable.dicts("T",(list1_id,list2_id),lowBound=0,upBound=1)
    problem+=lpSum([T[i][j]*cost(vector1[i],vector2[j]) for i in list1_id for j in list2_id])
    for i in list1_id:
        problem+=lpSum(T[i][j] for j in list2_id)==freq1[i]
    for j in list2_id:
        problem+=lpSum(T[i][j] for i in list1_id)==freq2[j]
    problem.solve()
    return problem.objective.value()
    
    
# TODO: 编写WMD函数来计算两个句子之间的相似度

def WMD (sent1, sent2):
    """
    这是主要的函数模块。参数sent1是第一个句子， 参数sent2是第二个句子，可以认为没有经过分词。
    在英文里，用空格作为分词符号。
    
    在实现WMD算法的时候，需要用到LP Solver用来解决Transportation proboem. 请使用http://cvxopt.org/examples/tutorial/lp.html
    也可以参考blog： https://scaron.info/blog/linear-programming-in-python-with-cvxopt.html
    
    需要做的事情为：
    
    1. 对句子做分词： 调用 .split() 函数即可
    2. 获取每个单词的词向量。这需要读取文件之后构建embedding matrix. 
    3. 构建lp问题，并用solver解决
    
    可以自行定义其他的函数，但务必不要改写WMD函数名。测试时保证WMD函数能够正确运行。
    """
    split1=split_sentence(sent1)
    split2=split_sentence(sent2)
    
    vector1=get_vector(split1,word2vec,word2id)
    vector2=get_vector(split2,word2vec,word2id)
    
    freq1=calculate_freq(split1,word2id)
    freq2=calculate_freq(split2,word2id)
    
    wmd_dist=solve_lp(split1,split2,vector1,vector2,freq1,freq2)
    
    return wmd_dist
    

## TODO: 自己写至少4个Test cases来测试一下。 比如 print (WMD("people like this car", "those guys enjoy driving that"))

##       
sent1="someone knows that they konw nothing"
sent2="others believe they know everything"
sent3="what do you think of apple"
sent4="I like eating bananas"
print(WMD(sent1,sent2),WMD(sent1,sent3),WMD(sent3,sent4))