import?re
from?collections?import?Counter
import?sys

if?len（sys.argv）?????sys.exit（‘ERROR?命令行參數依次為：訓練語料文件、測試語料文件‘）

#打開文件
try:
????#?訓練語料
????file_in?=?open（sys.argv[1]?‘r‘?encoding=‘UTF-8‘）
????#?測試數據集
????file_testdata?=?open（sys.argv[2]?‘r‘?encoding=‘GBK‘）
????#?輸出結果
????file_out?=?open（‘./output.txt‘?‘w‘?encoding=‘UTF-8‘）
except?IOError?as?e:
????sys.exit（e）

#?詞庫，key-詞??val-頻次
wordList?=?Counter（）??

#?寫入詞庫
strlist?=?file_in.readlines（）
for?strLine?in?strlist:
????#?過濾空行
????strLine?=?strLine.strip（）
????if?not?strLine:
????????continue
????linelist?=?re.split（‘?+|\n‘?strLine）
????linelist?=?linelist[1:]??#?去掉行首標簽
????linelist?=?list（map（lambda?x:?x[:x.find（‘/‘?0）].strip（）?linelist））??#?去掉詞尾的標記并且去除首尾的空格
????wordList.update（linelist）

#讀取測試集
intputstrList?=?file_testdata.readlines（）;
#將初始的詞庫保留下來，防止之前的測試污染詞庫
ini_wordlist=wordList;

#以行為單位進行分詞
for?input_str?in?intputstrList:
	#恢復初始詞庫
????wordList=ini_wordlist
????inputStrLen?=?len（input_str）

????i?j?=?0?0
????#?計算平滑值，實現策略是，對于在詞庫中的詞直接加入待拆解pool除此之外之外只有單字可以入池
????#?即：對于OOV不進行處理，OOV中的詞以單字的形式進行切分。因此預處理，直接考察所有的單字，加入詞庫中，有利于計算平滑值
????#?如果需要平滑，則將詞庫中所有的詞的頻次加1
????laplaceList?=?[]
	#找到不在詞庫里面的單字
????while?i?????????if?not?wordList.get（input_str[i]）:
????????????laplaceList.append（input_str[i]）
????????i?=?i?+?1
	
	#存在需要修正的單字，將原來詞庫里面的所有的詞詞頻加1，將修正單字的詞頻設置為1
	#達到了歸一化修正的目的
????if?len（laplaceList）:
????????wordList.update（wordList.keys（））
????????wordList.update（laplaceList）

????N?=?sum（wordList.values（））??#?詞庫中總的詞數
????MaxLen?=?len（max（wordList.keys（）?key=len））??#?詞的最大長度

????#?切分結果的數據結構[START?END?RATE?RATE_CAL?LAW?]
????#?START?END?分別指向的就是子串的起始和終止位置本身
	#?Rate詞在詞庫中的概率，RATE_CAL詞的累積概率
	#?LAW?最佳左鄰詞的起始位置
????START?END?RATE?RATE_CAL?LAW?=?0?1?2?3?4

????word_pool?=?[]??#?可能作為切分結果的字符串池
????word_cal?=?[]??#?存放單個的切分數據

????i?j?=?0?0
????#?找到所有可能的劃分，并且寫入rate
????while?i?????????j?=?i
????????while?j?????????????times?=?wordList.get（input_str[i:j?+?1]）
????????????if?times:
????????????????rate?=?times?/?N??#?計算概率
????????????????if?i?==?0:
????????????????????#?句首詞，累加的概率等于詞在詞庫中的概率
????????????????????word_cal?=?[i?j?rate?rate?-1]
????????????????else:
????????????????????word_cal?=?[i?j?rate?-1?-1]
????????????word_pool.append（word_cal）
????????????j?=?j?+?1
????????i?=?i?+?1

????#?求rate_cal
????for?word?in?word_pool:
????????if?word[RATE_CAL]?==?-1:
			#找到左鄰詞的集合
????????????candidate?=?list（filter（lambda?x:?x[END]?==?word[START]?-?1?word_pool））
????????????#找到最大的左鄰詞
????????????rate_cal_max?=?max（candidate?key=lambda?x:?x[RATE_CAL]）
????????????#計算當前詞的累積概率
????????????word[RATE_CAL]?=?rate_cal_max[RATE_CAL]?*?word[RATE]
????????????#最佳左鄰詞的起始位置
????????????word[LAW]?=?rate_cal_max[START]

????#?結果集合，保存的內容是字符串
????res_list?=?[]

????#?查找最優的詞尾
????bestEndCandadaite?=?list（filter（lambda?x:?x[END]?==?inputStrL

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????4547??2017-12-07?13:48??n-gram?-?副本\n-gram.py
?????文件???????21974??2017-11-29?00:40??n-gram?-?副本\testset.txt
?????文件????10670780??2017-10-22?23:04??n-gram?-?副本\北大（人民日報）語料庫199801.txt
?????目錄???????????0??2017-12-07?13:48??n-gram?-?副本\