DynamicArray與NShortPath是ICTCLAS中的基礎類,本人在完成了基礎改造工作后,就著手開始對Segment分詞進行移植與改造。SharpICTCLAS中的改造主要體現在以下幾方面:
1)合并不同類中的部分代碼
原有ICTCLAS中使用了SegGraph與Segment兩個類完成分詞過程,SegGraph類負責完成原子分詞與segGraph的生成,而Segment類負責BiSegGraph的生成和NShortPath優化,而最終的人名、地名識別以及Optimum優化又分散在了Segment類與WordSegment類中。
SharpICTCLAS將原有SegGraph類與Segment合二為一,因為它們所作的工作僅僅是分詞中的幾個步驟而已。而WordSegment類中基本保留了原有內容,因為這個類更多的做一些外圍工作。
2)改造了程序中用到的部分數據結構
原有ICTCLAS大量使用了數組與二維數組,由于數組的固有缺陷使得我們隨處可以看到如此這般的數組定義:
m_pWordSeg = new PWORD_RESULT[MAX_SEGMENT_NUM];
由于不知道最終會分成幾個詞,所以定義數組時只能用最大的容量 MAX_SEGMENT_NUM
進行預設,所以一旦存在某些異常數據就會造成“溢出”錯誤。
而SharpICTCLAS中大量使用了 List<int[]>
的方式記錄結果 ,范型的List首先可以確保結果集的數量可以動態調整而不用事先定義,另外每個結果的數組長度也可各不相同。
再有的改造就是在Segment類中使用了鏈表結構處理結果,這大大簡化了原有ICTCLAS中的數組結構帶來的種種問題。
3)大量使用了靜態方法
由于某些過程的調用根本不需要建立對象,這些過程僅僅完成例行計算而已,因此將這些方法聲明為靜態方法更合適,何況靜態方法的調用效率比實例方法高。因此本人在將ICTCLAS移植到C#平臺上時,將盡可能的方法定義成靜態方法。
下面我就說說SharpICTCLAS中Segment類的一些主要內容:
1、主體部分
比較典型的一個運算過程可以參考BiSegment方法,代碼(經過簡化)如下:
{
WordResult[] tmpResult;
WordLinkedArray linkedArray;
m_pWordSeg = new List<WordResult[]>();
m_graphOptimum = new RowFirstDynamicArray<ChainContent>();
//---原子分詞
atomSegment = AtomSegment(sSentence);
//---檢索詞庫,加入所有可能分詞方案并存入鏈表結構
segGraph = GenerateWordNet(atomSegment, coreDict);
//---檢索所有可能的兩兩組合
biGraphResult = BiGraphGenerate(segGraph, smoothPara, biDict, coreDict);
//---N 最短路徑計算出多個分詞方案
NShortPath.Calculate(biGraphResult, nKind);
List<int[]> spResult = NShortPath.GetNPaths(Predefine.MAX_SEGMENT_NUM);
//---對結果進行優化,例如合并日期等工作
for (int i = 0; i < spResult.Count; i++)
{
linkedArray = BiPath2LinkedArray(spResult[i], segGraph, atomSegment);
tmpResult = GenerateWord(spResult[i], linkedArray, m_graphOptimum);
if (tmpResult != null)
m_pWordSeg.Add(tmpResult);
}
return m_pWordSeg.Count;
}
從上面代碼可以看出,已經將原有ICTCLAS的原子分詞功能合并入Segment類了。
就拿“他在1月份大會上說的確實在理”這句話來說,上面幾個步驟得到的中間結果如下:
他在1月份大會上說的確實在理
//==== 原子切分:
始##始, 他, 在, 1, 月, 份, 大, 會, 上, 說, 的, 確, 實, 在, 理, 末##末,
//==== 生成 segGraph:
row: 0, col: 1, eWeight: 329805.00, nPOS: 1, sWord:始##始
row: 1, col: 2, eWeight: 19823.00, nPOS: 0, sWord:他
row: 2, col: 3, eWeight: 78484.00, nPOS: 0, sWord:在
row: 3, col: 4, eWeight: 0.00, nPOS: -27904, sWord:未##數
row: 4, col: 5, eWeight: 1900.00, nPOS: 0, sWord:月
row: 4, col: 6, eWeight: 11.00, nPOS: 28160, sWord:月份
row: 5, col: 6, eWeight: 1234.00, nPOS: 0, sWord:份
row: 6, col: 7, eWeight: 14536.00, nPOS: 0, sWord:大
row: 6, col: 8, eWeight: 1333.00, nPOS: 28160, sWord:大會
row: 7, col: 8, eWeight: 6136.00, nPOS: 0, sWord:會
row: 7, col: 9, eWeight: 469.00, nPOS: 0, sWord:會上
row: 8, col: 9, eWeight: 23706.00, nPOS: 0, sWord:上
row: 9, col: 10, eWeight: 17649.00, nPOS: 0, sWord:說
row: 10, col: 11, eWeight: 358156.00, nPOS: 0, sWord:的
row: 10, col: 12, eWeight: 210.00, nPOS: 25600, sWord:的確
row: 11, col: 12, eWeight: 181.00, nPOS: 0, sWord:確
row: 11, col: 13, eWeight: 361.00, nPOS: 0, sWord:確實
row: 12, col: 13, eWeight: 357.00, nPOS: 0, sWord:實
row: 12, col: 14, eWeight: 295.00, nPOS: 0, sWord:實在
row: 13, col: 14, eWeight: 78484.00, nPOS: 0, sWord:在
row: 13, col: 15, eWeight: 3.00, nPOS: 24832, sWord:在理
row: 14, col: 15, eWeight: 129.00, nPOS: 0, sWord:理
row: 15, col: 16, eWeight:2079997.00, nPOS: 4, sWord:末##末
//==== 生成 biSegGraph:
row: 0, col: 1, eWeight: 3.37, nPOS: 1, sWord:始##始@他
row: 1, col: 2, eWeight: 3.37, nPOS: 0, sWord:他@在
row: 2, col: 3, eWeight: 3.74, nPOS: 0, sWord:在@未##數
row: 3, col: 4, eWeight: -27898.79, nPOS: -27904, sWord:未##數@月
row: 3, col: 5, eWeight: -27898.75, nPOS: -27904, sWord:未##數@月份
row: 4, col: 6, eWeight: 9.33, nPOS: 0, sWord:月@份
row: 5, col: 7, eWeight: 13.83, nPOS: 28160, sWord:月份@大
row: 6, col: 7, eWeight: 9.76, nPOS: 0, sWord:份@大
row: 5, col: 8, eWeight: 13.83, nPOS: 28160, sWord:月份@大會
row: 6, col: 8, eWeight: 9.76, nPOS: 0, sWord:份@大會
row: 7, col: 9, eWeight: 7.30, nPOS: 0, sWord:大@會
row: 7, col: 10, eWeight: 7.30, nPOS: 0, sWord:大@會上
row: 8, col: 11, eWeight: 2.11, nPOS: 28160, sWord:大會@上
row: 9, col: 11, eWeight: 8.16, nPOS: 0, sWord:會@上
row: 10, col: 12, eWeight: 3.42, nPOS: 0, sWord:會上@說
row: 11, col: 12, eWeight: 4.07, nPOS: 0, sWord:上@說
row: 12, col: 13, eWeight: 4.05, nPOS: 0, sWord:說@的
row: 12, col: 14, eWeight: 7.11, nPOS: 0, sWord:說@的確
row: 13, col: 15, eWeight: 4.10, nPOS: 0, sWord:的@確
row: 13, col: 16, eWeight: 4.10, nPOS: 0, sWord:的@確實
row: 14, col: 17, eWeight: 11.49, nPOS: 25600, sWord:的確@實
row: 15, col: 17, eWeight: 11.63, nPOS: 0, sWord:確@實
row: 14, col: 18, eWeight: 11.49, nPOS: 25600, sWord:的確@實在
row: 15, col: 18, eWeight: 11.63, nPOS: 0, sWord:確@實在
row: 16, col: 19, eWeight: 3.92, nPOS: 0, sWord:確實@在
row: 17, col: 19, eWeight: 10.98, nPOS: 0, sWord:實@在
row: 16, col: 20, eWeight: 10.97, nPOS: 0, sWord:確實@在理
row: 17, col: 20, eWeight: 10.98, nPOS: 0, sWord:實@在理
row: 18, col: 21, eWeight: 11.17, nPOS: 0, sWord:實在@理
row: 19, col: 21, eWeight: 5.62, nPOS: 0, sWord:在@理
row: 20, col: 22, eWeight: 14.30, nPOS: 24832, sWord:在理@末##末
row: 21, col: 22, eWeight: 11.95, nPOS: 0, sWord:理@末##末
//==== NShortPath 初步切分的到的 N 個結果:
始##始, 他, 在, 1, 月份, 大會, 上, 說, 的, 確實, 在, 理, 末##末,
始##始, 他, 在, 1, 月份, 大會, 上, 說, 的, 確實, 在理, 末##末,
始##始, 他, 在, 1, 月份, 大, 會上, 說, 的, 確實, 在, 理, 末##末,
始##始, 他, 在, 1, 月, 份, 大會, 上, 說, 的, 確實, 在, 理, 末##末,
始##始, 他, 在, 1, 月份, 大, 會上, 說, 的, 確實, 在理, 末##末,
//==== 經過數字、日期合并等策略處理后的 N 個結果:
始##始, 他, 在, 1月份, 大會, 上, 說, 的, 確實, 在, 理, 末##末,
始##始, 他, 在, 1月份, 大會, 上, 說, 的, 確實, 在理, 末##末,
始##始, 他, 在, 1月份, 大, 會上, 說, 的, 確實, 在, 理, 末##末,
始##始, 他, 在, 1月, 份, 大會, 上, 說, 的, 確實, 在, 理, 末##末,
始##始, 他, 在, 1月份, 大, 會上, 說, 的, 確實, 在理, 末##末,
這些內容在前面的文章中已經涉及過,我這里主要說說SharpICTCLAS中兩處地方的內容,分別是原子分詞以及數字日期合并策略。
2、原子分詞
原子分詞看起來應當是程序中最簡單的部分,無非是將漢字逐一分開。但是也是最值得改進的地方。SharpICTCLAS目前仍然沿用了原有ICTCLAS的算法并做了微小調整。但我對于 這種原子分詞方法不太滿意,如果有機會,可以考慮使用一系列正則表達式將某些“原子”詞單獨摘出來。比如“甲子”、“乙亥”等年份信息屬于原子信息,還有URL、Email等都可以預先進行原子識別,這可以大大簡化后續工作。因此日后可以考慮這方面的處理。
3、對結果的處理
ICTCLAS與SharpICTCLAS都通過NShortPath計算最短路徑并將結果以數組的方式進行輸出,數組僅僅記錄了分詞的位置,我們還需要通過一些后續處理手段將這些數組轉換成“分詞”結果。
原有ICTCLAS的實現如下:
{
BiPath2UniPath(nSegRoute[i]); //Path convert to unipath
GenerateWord(nSegRoute, i); //Gernerate word according the Segmentation route
i++;
}
其中這個BiPath2UniPath方法做的工作可以用如下案例說明:
例如“他說的確實在理”
BiPath:(0, 1, 2, 3, 6, 9, 11, 12)
0 1 2 3 4 5 6 7 8 9 10 11 12
始##始 他 說 的 的確 確 確實 實 實在 在 在理 理 末##末
經過轉換后
UniPath:(0, 1, 2, 3, 4, 6, 7, 8)
0 1 2 3 4 5 6 7 8
始##始 他 說 的 確 實 在 理 末##末
由此可見UniPath記錄了針對原子分詞的分割位置。而后面的GenerateWord方法又針對這個數組去做合并及優化工作。
本人在SharpICTCLAS的改造過程中發現在這里數組的表述方式給后續工作帶來了很大的困難(可以考慮一下,讓你合并鏈表中兩個相鄰結點簡單呢還是數組中兩個相鄰結點簡單?),所以我決定在SharpICTCLAS中將BiPath轉換為鏈表結構供后續使用,實踐證明簡化了不少工作。
這點在BiSegment方法中有所體現,如下:
linkedArray = BiPath2LinkedArray(spResult[i], segGraph, atomSegment);
這樣改造后,還使得原有ICTCLAS中 int *m_npWordPosMapTable;
不再需要,與其相關的代碼也可以一并刪除了。
4、日期、數字合并策略
數字、日期等合并以及拆分策略的實施是在GenerateWord方法中實現的,原有ICTCLAS中,該方法是一個超級龐大的方法,里面有不下6、7層的if嵌套、while嵌套等,分析其內部功能的工作異常復雜。經過一番研究后,我將其中的主要功能部分提取出來,改用了“管道”方式進行處理,簡化了代碼復雜度。但對于部分邏輯結構異常復雜的日期時間識別功能,SharpICTCLAS中仍然保留了絕大多數原始內容。
讓我們先來看看原始ICTCLAS的GenerateWord方法(超級長的一個方法):
bool CSegment::GenerateWord(int **nSegRoute, int nIndex)
{
unsigned int i = 0, k = 0;
int j, nStartVertex, nEndVertex, nPOS;
char sAtom[WORD_MAXLENGTH], sNumCandidate[100], sCurWord[100];
ELEMENT_TYPE fValue;
while (nSegRoute[nIndex][i] != - 1 && nSegRoute[nIndex][i + 1] != - 1 &&
nSegRoute[nIndex][i] < nSegRoute[nIndex][i + 1])
{
nStartVertex = nSegRoute[nIndex][i];
j = nStartVertex; //Set the start vertex
nEndVertex = nSegRoute[nIndex][i + 1]; //Set the end vertex
nPOS = 0;
m_graphSeg.m_segGraph.GetElement(nStartVertex, nEndVertex, &fValue, &nPOS);
sAtom[0] = 0;
while (j < nEndVertex)
{
//Generate the word according the segmentation route
strcat(sAtom, m_graphSeg.m_sAtom[j]);
j++;
}
m_pWordSeg[nIndex][k].sWord[0] = 0; //Init the result ending
strcpy(sNumCandidate, sAtom);
while (sAtom[0] != 0 && (IsAllNum((unsigned char*)sNumCandidate) ||
IsAllChineseNum(sNumCandidate)))
{
//Merge all seperate continue num into one number
//sAtom[0]!=0: add in 2002-5-9
strcpy(m_pWordSeg[nIndex][k].sWord, sNumCandidate);
//Save them in the result segmentation
i++; //Skip to next atom now
sAtom[0] = 0;
while (j < nSegRoute[nIndex][i + 1])
{
//Generate the word according the segmentation route
strcat(sAtom, m_graphSeg.m_sAtom[j]);
j++;
}
strcat(sNumCandidate, sAtom);
}
unsigned int nLen = strlen(m_pWordSeg[nIndex][k].sWord);
if (nLen == 4 && CC_Find("第上成±—+∶·./",
m_pWordSeg[nIndex][k].sWord) || nLen == 1 && strchr("+-./",
m_pWordSeg[nIndex][k].sWord[0]))
{
//Only one word
strcpy(sCurWord, m_pWordSeg[nIndex][k].sWord); //Record current word
i--;
}
else if (m_pWordSeg[nIndex][k].sWord[0] == 0)
//Have never entering the while loop
{
strcpy(m_pWordSeg[nIndex][k].sWord, sAtom);
//Save them in the result segmentation
strcpy(sCurWord, sAtom); //Record current word
}
else
{
//It is a num
if (strcmp("--", m_pWordSeg[nIndex][k].sWord) == 0 || strcmp("—",
m_pWordSeg[nIndex][k].sWord) == 0 || m_pWordSeg[nIndex][k].sWord[0] ==
'-' && m_pWordSeg[nIndex][k].sWord[1] == 0)
//The delimiter "--"
{
nPOS = 30464; //'w'*256;Set the POS with 'w'
i--; //Not num, back to previous word
}
else
{
//Adding time suffix
char sInitChar[3];
unsigned int nCharIndex = 0; //Get first char
sInitChar[nCharIndex] = m_pWordSeg[nIndex][k].sWord[nCharIndex];
if (sInitChar[nCharIndex] < 0)
{
nCharIndex += 1;
sInitChar[nCharIndex] = m_pWordSeg[nIndex][k].sWord[nCharIndex];
}
nCharIndex += 1;
sInitChar[nCharIndex] = '\0';
if (k > 0 && (abs(m_pWordSeg[nIndex][k - 1].nHandle) == 27904 || abs
(m_pWordSeg[nIndex][k - 1].nHandle) == 29696) && (strcmp(sInitChar,
"—") == 0 || sInitChar[0] == '-') && (strlen
(m_pWordSeg[nIndex][k].sWord) > nCharIndex))
{
//3-4月 //27904='m'*256
//Split the sInitChar from the original word
strcpy(m_pWordSeg[nIndex][k + 1].sWord, m_pWordSeg[nIndex][k].sWord +
nCharIndex);
m_pWordSeg[nIndex][k + 1].dValue = m_pWordSeg[nIndex][k].dValue;
m_pWordSeg[nIndex][k + 1].nHandle = 27904;
m_pWordSeg[nIndex][k].sWord[nCharIndex] = 0;
m_pWordSeg[nIndex][k].dValue = 0;
m_pWordSeg[nIndex][k].nHandle = 30464; //'w'*256;
m_graphOptimum.SetElement(nStartVertex, nStartVertex + 1,
m_pWordSeg[nIndex][k].dValue, m_pWordSeg[nIndex][k].nHandle,
m_pWordSeg[nIndex][k].sWord);
nStartVertex += 1;
k += 1;
}
nLen = strlen(m_pWordSeg[nIndex][k].sWord);
if ((strlen(sAtom) == 2 && CC_Find("月日時分秒", sAtom)) || strcmp
(sAtom, "月份") == 0)
{
//2001年
strcat(m_pWordSeg[nIndex][k].sWord, sAtom);
strcpy(sCurWord, "未##時");
nPOS = - 29696; //'t'*256;//Set the POS with 'm'
}
else if (strcmp(sAtom, "年") == 0)
{
if (IsYearTime(m_pWordSeg[nIndex][k].sWord))
//strncmp(sAtom,"年",2)==0&&
{
//1998年,
strcat(m_pWordSeg[nIndex][k].sWord, sAtom);
strcpy(sCurWord, "未##時");
nPOS = - 29696; //Set the POS with 't'
}
else
{
strcpy(sCurWord, "未##數");
nPOS = - 27904; //Set the POS with 'm'
i--; //Can not be a time word
}
}
else
{
//早晨/t 五點/t
if (strcmp(m_pWordSeg[nIndex][k].sWord + strlen
(m_pWordSeg[nIndex][k].sWord) - 2, "點") == 0)
{
strcpy(sCurWord, "未##時");
nPOS = - 29696; //Set the POS with 't'
}
else
{
if (!CC_Find("∶·./", m_pWordSeg[nIndex][k].sWord + nLen - 2) &&
m_pWordSeg[nIndex][k].sWord[nLen - 1] != '.' &&
m_pWordSeg[nIndex][k].sWord[nLen - 1] != '/')
{
strcpy(sCurWord, "未##數");
nPOS = - 27904; //'m'*256;Set the POS with 'm'
}
else if (nLen > strlen(sInitChar))
{
//Get rid of . example 1.
if (m_pWordSeg[nIndex][k].sWord[nLen - 1] == '.' ||
m_pWordSeg[nIndex][k].sWord[nLen - 1] == '/')
m_pWordSeg[nIndex][k].sWord[nLen - 1] = 0;
else
m_pWordSeg[nIndex][k].sWord[nLen - 2] = 0;
strcpy(sCurWord, "未##數");
nPOS = - 27904; //'m'*256;Set the POS with 'm'
i--;
}
}
i--; //Not num, back to previous word
}
}
fValue = 0;
nEndVertex = nSegRoute[nIndex][i + 1]; //Ending POS changed to latter
}
m_pWordSeg[nIndex][k].nHandle = nPOS; //Get the POS of current word
m_pWordSeg[nIndex][k].dValue = fValue;
//(int)(MAX_FREQUENCE*exp(-fValue));//Return the frequency of current word
m_graphOptimum.SetElement(nStartVertex, nEndVertex, fValue, nPOS, sCurWord);
//Generate optimum segmentation graph according the segmentation result
i++; //Skip to next atom
k++; //Accept next word
}
m_pWordSeg[nIndex][k].sWord[0] = 0;
m_pWordSeg[nIndex][k].nHandle = - 1; //Set ending
return true;
}
SharpICTCLAS中,對這段超長代碼進行了功能剝離,采用一種“流水線”式的處理流程,不同工作部分負責處理不同功能,而將處理結果節節傳遞(很象設計模式中的職責鏈模式),這樣使得整體結構變的清晰起來。SharpICTCLAS中GenerateWord方法定義如下:
RowFirstDynamicArray<ChainContent> m_graphOptimum)
{
if (linkedArray.Count == 0)
return null;
//--------------------------------------------------------------------
//Merge all seperate continue num into one number
MergeContinueNumIntoOne(ref linkedArray);
//--------------------------------------------------------------------
//The delimiter "--"
ChangeDelimiterPOS(ref linkedArray);
//--------------------------------------------------------------------
//如果前一個詞是數字,當前詞以“-”或“-”開始,并且不止這一個字符,
//那么將此“-”符號從當前詞中分離出來。
//例如 “3 / -4 / 月”需要拆分成“3 / - / 4 / 月”
SplitMiddleSlashFromDigitalWords(ref linkedArray);
//--------------------------------------------------------------------
//1、如果當前詞是數字,下一個詞是“月、日、時、分、秒、月份”中的一個,則合并,且當前詞詞性是時間
//2、如果當前詞是可以作為年份的數字,下一個詞是“年”,則合并,詞性為時間,否則為數字。
//3、如果最后一個漢字是"點" ,則認為當前數字是時間
//4、如果當前串最后一個漢字不是"∶·./"和半角的'.''/',那么是數
//5、當前串最后一個漢字是"∶·./"和半角的'.''/',且長度大于1,那么去掉最后一個字符。例如"1."
CheckDateElements(ref linkedArray);
//--------------------------------------------------------------------
//遍歷鏈表輸出結果
WordResult[] result = new WordResult[linkedArray.Count];
WordNode pCur = linkedArray.first;
int i = 0;
while (pCur != null)
{
WordResult item = new WordResult();
item.sWord = pCur.theWord.sWord;
item.nPOS = pCur.theWord.nPOS;
item.dValue = pCur.theWord.dValue;
result[i] = item;
m_graphOptimum.SetElement(pCur.row, pCur.col, new ChainContent(item.dValue, item.nPOS, pCur.sWordInSegGraph));
pCur = pCur.next;
i++;
}
return result;
}
從中可以看到linkedArray作為“繡球”在多個處理流程中被傳遞和加工,最終輸出相應的結果。只是CheckDateElement方法內容涉及到的東西太多,因此目前看來其實現仍有些臃腫,日后可以進一步進行功能的剝離。
- 小結
1)Segment類是SharpICTCLAS中最大的一個類,實現了分詞過程中一些關鍵的步驟。
2)Segment類對原有ICTCLAS中的代碼做了大量修改,力爭通過新的數據結構簡化原有操作。
3)Segment中定義了部分靜態方法以提高調用效率。
來源:http://www.cnblogs.com/zhenyulu/category/85598.html