前言

大家都知道，英文的分詞由于單詞間是以空格進(jìn)行分隔的，所以分詞要相對(duì)的容易些，而中文就不同了，中文中一個(gè)句子的分隔就是以字為單位的了，而所謂的正向最大匹配和逆向最大匹配便是一種分詞匹配的方法，這里以詞典匹配說(shuō)明。

最大匹配算法是自然語(yǔ)言處理中的中文匹配算法中最基礎(chǔ)的算法，分為正向和逆向，原理都是一樣的。

正向最大匹配算法，故名思意，從左向右掃描尋找詞的最大匹配。

首先我們可以規(guī)定一個(gè)詞的最大長(zhǎng)度，每次掃描的時(shí)候?qū)ふ耶?dāng)前開(kāi)始的這個(gè)長(zhǎng)度的詞來(lái)和字典中的詞匹配，如果沒(méi)有找到，就縮短長(zhǎng)度繼續(xù)尋找，直到找到或者成為單字。

下面話不多說(shuō)了，來(lái)一起看看詳細(xì)的介紹吧。

實(shí)例：

S1="計(jì)算語(yǔ)言學(xué)課程是三個(gè)課時(shí)" ,設(shè)定最大詞長(zhǎng)MaxLen = 5 ,S2= " "

字典中含有三個(gè)詞：[計(jì)算語(yǔ)言學(xué)]、[課程]、[課時(shí)]

    （1）S2=""；S1不為空，從S1左邊取出候選子串W="計(jì)算語(yǔ)言學(xué)"；

    （2）查詞表，“計(jì)算語(yǔ)言學(xué)”在詞表中，將W加入到S2中，S2=“計(jì)算語(yǔ)言學(xué)/ ”， 并將W從S1中去掉，此時(shí)S1="課程是三個(gè)課時(shí)"；

    （3）S1不為空，于是從S1左邊取出候選子串W="課程是三個(gè)"；

    （4）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="課程是三"；

    （5）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="課程是"；

    （6）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="課程"

    （7）查詞表，W在詞表中，將W加入到S2中，S2=“計(jì)算語(yǔ)言學(xué)/ 課程/ ”，并 將W從S1中去掉，此時(shí)S1="是三個(gè)課時(shí)"；

    （8）S1不為空，于是從S1左邊取出候選子串W="是三個(gè)課時(shí)"；

    （9）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="是三個(gè)課"；

    （10）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="是三個(gè)"；

    （11）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="是三"

    （12）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W=“是”，這時(shí) W是單字，將W加入到S2中，S2=“計(jì)算語(yǔ)言學(xué)/ 課程/ 是/ ”，并將 W從S1中去掉，此時(shí)S1="三個(gè)課時(shí)"；

    （13）S1不為空，從S1左邊取出候選子串W="三個(gè)課時(shí)"；

    （14）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="三個(gè)課"；

    （15）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="三個(gè)"；

    （16）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W=“三”，這時(shí) W是單字，將W加入到S2中，S2=“計(jì)算語(yǔ)言學(xué)/ 課程/ 是/ 三/ ”，并 將W從S1中去掉，此時(shí)S1="個(gè)課時(shí)"；

    （17）S1不為空，從S1左邊取出候選子串W="個(gè)課時(shí)"；

    （18）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W="個(gè)課"；

    （19）查詞表，W不在詞表中，將W最右邊一個(gè)字去掉，得到W=“個(gè)”， 這時(shí)W是單字，將W加入到S2中，S2=“計(jì)算語(yǔ)言學(xué)/ 課程/ 是/ 三/ 個(gè)/ "，并將W從S1中去掉，此時(shí)S1="課時(shí)"；

    （20）S1不為空，從S1左邊取出候選子串W="課時(shí)"；

    （21）查詞表，W在詞表中，將W加入到S2中，S2=“計(jì)算語(yǔ)言學(xué)/ 課程/ 是/ 三/ 個(gè)/ 課時(shí)/ "，并將W從S1中去掉，此時(shí)S1=""。

    （22）S1為空，輸出S2作為分詞結(jié)果，分詞過(guò)程結(jié)束。

而至于為什么選擇python這個(gè)語(yǔ)言呢？大概是因?yàn)槲抑車(chē)擞玫蒙侔桑揖拖雵L試突破，不過(guò)我也不諱言，我的C/C++，java等等高級(jí)語(yǔ)言用的也不多，雖說(shuō)編程語(yǔ)言這個(gè)東西，基本上只要熟悉一個(gè)，其他的都好學(xué)，不過(guò)我在python上嘗到了甜頭，索性就用這個(gè)語(yǔ)言了。

中文分詞算法的Python實(shí)現(xiàn)：

腳本接受兩個(gè)參數(shù)，一個(gè)是輸入文件的路徑，另一個(gè)是詞典的路徑。

它的運(yùn)行方法如下：

python max-match.py <data> <dict>

#!/usr/bin/env python
import cPickle as pickle
import sys

# 詞語(yǔ)最大長(zhǎng)度為5
window_size=5

def max_match_segment(line, dic):
 # write your code here
 chars = line.decode("utf8")
 words = []
 idx = 0
 # 判斷索引是否超過(guò)chars的長(zhǎng)度
 while idx < len(chars):
  matched = False
  for i in xrange(window_size, 0, -1):
   cand=chars[idx:idx+i].encode("utf8")
   if cand in dic:
    words.append(cand)
    matched = True
    break
  # 判斷for中是否匹配到數(shù)據(jù)
  if not matched:
   i = 1
   words.append(chars[idx].encode("utf8"))
  idx += i

 return words

if __name__=="__main__":

 try:
  fpi=open(sys.argv[1], "r")
 except:
  print >> sys.stderr, "failed to open file"
  sys.exit(1)

 try:
  dic = pickle.load(open(sys.argv[2], "r"))
 except:
  print >> sys.stderr, "failed to load dict %s" % sys.argv[2]
  sys.exit(1)
 try:
  fpo = open("out.txt","w")
 except:
  print >> sys.stderr, "failed to load out.txt"
  sys.exit(1)
 for line in fpi:
  fpo.write("\t".join( max_match_segment(line.strip(), dic) ))

當(dāng)然，這只是最基礎(chǔ)的，還可以有很多高級(jí)的優(yōu)化，比如說(shuō)改成Trie樹(shù)版本的，控制最大詞長(zhǎng)度的等等。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論