漢語(yǔ)分詞最大匹配方法

1、,漢語(yǔ)分詞:最大匹配方法,張?jiān)拢ɡ钫A指導(dǎo)）2015.9.15,,中文分詞的目的是將漢字序列切分為詞序列舉例說(shuō)明：輸入句子：他是研究生物化學(xué)的?？赡艿姆衷~：他 是 研究生 物化 學(xué) 的 。 他 是 研究生 物 化學(xué) 的 。 他 是 研究 生物 化學(xué) 的 。合理答案：他 是 研究 生物 化學(xué) 的 。,分詞任務(wù),從左到右尋找詞的最大匹配（

2、每次都貪心的找一個(gè)最長(zhǎng)的詞典詞）我們有一個(gè)詞典，用于存放所有可能的詞語(yǔ)，即除了單字，分詞結(jié)果中的每個(gè)詞均要在詞典中出現(xiàn)。,正向最大匹配算法,從左到右尋找詞的最大匹配從當(dāng)前位置開(kāi)始，向右截取最大長(zhǎng)度，組成當(dāng)前詞；和字典中的詞逐一進(jìn)行匹配；若匹配成功，則進(jìn)行下次匹配，下次匹配的當(dāng)前位置則為這次詞后面的那個(gè)字。如果未能匹配，就縮短長(zhǎng)度（長(zhǎng)度減一）重新截取，直到當(dāng)前詞與詞典中的詞匹配或者當(dāng)前詞是單字；,正向最大匹配算法,

3、從左到右尋找詞的最大匹配,正向最大匹配算法,例子：我是中國(guó)人 詞典中包括【中國(guó)、中國(guó)人】假設(shè)：最大詞長(zhǎng)為3,正向最大匹配算法,例子：我是中國(guó)人 第一輪：第一次："我是中"是選取的詞，在詞典中 未找到匹配項(xiàng) 第二次："我是"是選取的詞，在詞典中未 找到匹配項(xiàng) 第三次："我"是選取的詞，是單字，匹配 成功,正向最大

4、匹配算法,例子：我/是中國(guó)人 第二輪：第一次："是中國(guó)"是選取的詞，在詞典中 未找到匹配項(xiàng) 第二次："是中"是選取的詞，在詞典中未 找到匹配項(xiàng) 第三次："是"是選取的詞，是單字，匹配 成功,正向最大匹配算法,例子：我/是/中國(guó)人/ 第三輪：第一次："中國(guó)人"是選取的詞，在詞典中

5、 找到匹配項(xiàng)，匹配成功。 至此，短句中所有字匹配結(jié)束，該短句分詞結(jié)束。,正向最大匹配算法,從右到左尋找詞的最大匹配 與正向最大匹配的區(qū)別在于，從句子的末尾開(kāi)始，向左邊截取一定的長(zhǎng)度去匹配。,逆向最大匹配算法,從右到左尋找詞的最大匹配,逆向最大匹配算法,例子：我是中國(guó)人 第一輪：第一次："中國(guó)人"是選取的詞，在詞典中 找到匹配項(xiàng)，匹配成功,逆向最大匹配算法,例子：我是/

6、中國(guó)人 第二輪：第一次：因?yàn)槭Ｓ嘧謹(jǐn)?shù)已不足3，小于假 定的最大詞長(zhǎng)，所以選擇"我是"， 在詞典中未找到匹配項(xiàng) 第二次："是"是選取的詞，是單字，匹配 成功,逆向最大匹配算法,例子：我/是/中國(guó)人 第三輪：第一次：因?yàn)槭Ｓ嘧謹(jǐn)?shù)已不足3，小于假 定的最大詞長(zhǎng)，所以選擇"我"， 是單字，匹配成功 至此，短句中所

7、有字匹配結(jié)束，該短句 分詞結(jié)束。,逆向最大匹配算法,給定人工標(biāo)注的分詞答案，評(píng)價(jià)某一算法給出的結(jié)果。正確率(Precision) = 正確識(shí)別的詞數(shù) / 識(shí)別出的個(gè)體總數(shù)召回率(Recall) = 正確識(shí)別的個(gè)體總數(shù) / 測(cè)試集中存在的個(gè)體總數(shù)F值 = 正確率* 召回率 * 2 / (正確率 + 召回率),分詞算法評(píng)價(jià)：正確率/召回率/F值,思考：評(píng)價(jià)程序應(yīng)該怎么寫(xiě)？,utf-8是不定長(zhǎng)的，根據(jù)左側(cè)位1的個(gè)數(shù)來(lái)決定

8、占用了幾個(gè)字節(jié)，中文一般占2-4個(gè)字節(jié),UTF-8編碼,gbk的編碼方式是中文占兩個(gè)字節(jié)，英文占一個(gè)字節(jié),根據(jù)第一個(gè)字節(jié)的最高位來(lái)判斷如果第一個(gè)字節(jié)的最高位是1，則是兩個(gè)字節(jié)連在一起為一個(gè)字符，否則一個(gè)字節(jié)為一個(gè)字符中文的編碼范圍 第一個(gè)字節(jié) | 第二個(gè)字節(jié) 0x81-0xFE(129-254) | 0x40-0xFE(64-254),GBK編碼,,數(shù)據(jù)格式,四個(gè)編程任務(wù)（編程語(yǔ)言不限，Li

9、nux上運(yùn)行）,1. 構(gòu)建詞典（3分）給一個(gè)人工分好詞的文件data.conll，構(gòu)建一個(gè)詞典，輸出到一個(gè)文件中，起名為word.dict（格式自定義）2. 構(gòu)建毛文本（2分）將data.conll文件中的格式修改為：每行一句話(huà)，詞語(yǔ)之間無(wú)空格，起名為data.txt,四個(gè)編程任務(wù)（編程語(yǔ)言不限，Linux上運(yùn)行）,3. 前向（5分）或（二者只可以選一個(gè)）后向（7分）最大匹配分詞算法給定詞典word.dict，對(duì)data.txt