系統程序員成長計劃-文本處理(一)
狀態機(2)
o 用有窮狀態機解一道面試題。
剛畢業的時候，我到一家外企面試，面試題里有這樣一道題：
統計一篇英文文章里的單詞個數。
有多種方法可以解這道題，這里我們選擇用有窮狀態機來解，做法如下：
先把這篇英文文章讀入到一個緩沖區里，讓一個指針從緩沖區的頭部一直移到緩沖區的尾部，指針會處于兩種狀態：“單詞內”或“單詞外”，加上后面提到的初始狀態和接受狀態，就是有窮狀態機的狀態集。緩沖區中的字符集合就是有窮狀態機的字母表。
如果當前狀態為“單詞內”，移到指針時，指針指向的字符是非單詞字符(如標點和空格)，那狀態會從“單詞內”轉換到“單詞外”。如果當前狀態為“單
詞外”， 移到指針時，指針指向的字符是單詞字符(如字母)，那狀態會從“單詞外”轉換到“單詞內”。這些轉換規則就是狀態轉換函數。
指針指向緩沖區的頭部時是初始狀態。
指針指向緩沖區的尾部時是接受狀態。
每次當狀態從“單詞內”轉換到“單詞外”時，單詞計數增加一。
這個有窮狀態機的圖形表示如下：
下面我們看看程序怎么寫：
int count_word(const char* text)
{
/*定義各種狀態，我們不關心接受狀態，這里可以不用定義。*/
enum _State
{
STAT_INIT,
STAT_IN_WORD,
STAT_OUT_WORD,
}state = STAT_INIT;
int count = 0;
const char* p = text;
/*在一個循環中，指針從緩沖區頭移動緩沖區尾*/
for(p = text; *p != '\0'; p++)
{
switch(state)
{
case STAT_INIT:
{
if(IS_WORD_CHAR(*p))
{
/*指針指向單詞字符，狀態轉換為單詞內*/
state = STAT_IN_WORD;
}
else
{
/*指針指向非單詞字符，狀態轉換為單詞外*/
state = STAT_OUT_WORD;
}
break;
}
case STAT_IN_WORD:
{
if(!IS_WORD_CHAR(*p))
{
/*指針指向非單詞字符，狀態轉換為單詞外，增加單詞計數*/
count++;
state = STAT_OUT_WORD;
}
break;
}
case STAT_OUT_WORD:
{
if(IS_WORD_CHAR(*p))
{
/*指針指向單詞字符，狀態轉換為單詞內*/
state = STAT_IN_WORD;
}
break;
}
default:break;
}
}
if(state == STAT_IN_WORD)
{
/*如果由單詞內進入接受狀態，增加單詞計數*/
count++;
}
return count;
}
用狀態機來解這道題目，思路清晰，程序簡單，不易出錯。
這道題目只是為了展示一些奇技淫巧，還是有一些實際用處呢？回答這個問題之前，我們先對上面的程序做點擴展，不只是統計單詞的個數，而且要分離出里面的每個單詞。
int word_segmentation(const char* text, OnWordFunc on_word, void* ctx)
{
enum _State
{
STAT_INIT,
STAT_IN_WORD,
STAT_OUT_WORD,
}state = STAT_INIT;
int count = 0;
char* copy_text = strdup(text);
char* p = copy_text;
char* word = copy_text;
for(p = copy_text; *p != '\0'; p++)
{
switch(state)
{
case STAT_INIT:
{
if(IS_WORD_CHAR(*p))
{
word = p;
state = STAT_IN_WORD;
}
break;
}
case STAT_IN_WORD:
{
if(!IS_WORD_CHAR(*p))
{
count++;
*p = '\0';
on_word(ctx, word);
state = STAT_OUT_WORD;
}
break;
}
case STAT_OUT_WORD:
{
if(IS_WORD_CHAR(*p))
{
word = p;
state = STAT_IN_WORD;
}
break;
}
default:break;
}
}
if(state == STAT_IN_WORD)
{
count++;
on_word(ctx, word);
}
free(copy_text);
return count;
}
狀態機不變，只是在狀態轉換時，做是事情不一樣。這里從“單詞內”轉換到其它狀態時，增加單詞計數，并分離出當前的單詞。至于拿分離出的單詞來做什么，由傳入的回調函數決定，比如可以用來統計每個單詞出現的頻率。
但如果討論還是限于英文文章，這個程序的意義仍然不大，現在來做進一步擴展。我們考慮的文本不再是英文文章，而是一些文本數據，這些數據由一些分隔符分開，我們把數據稱為token，現在我們要把這些token分離出來。
typedef void (*OnTokenFunc)(void* ctx, int index, const char* token);
#define IS_DELIM(c) (strchr(delims, c) != NULL)
int parse_token(const char* text, const char* delims, OnTokenFunc on_token, void* ctx)
{
enum _State
{
STAT_INIT,
STAT_IN,
STAT_OUT,
}state = STAT_INIT;
int count = 0;
char* copy_text = strdup(text);
char* p = copy_text;
char* token = copy_text;
for(p = copy_text; *p != '\0'; p++)
{
switch(state)
{
case STAT_INIT:
case STAT_OUT:
{
if(!IS_DELIM(*p))
{
token = p;
state = STAT_IN;
}
break;
}
case STAT_IN:
{
if(IS_DELIM(*p))
{
*p = '\0';
on_token(ctx, count++, token);
state = STAT_OUT;
}
break;
}
default:break;
}
}
if(state == STAT_IN)
{
on_token(ctx, count++, token);
}
on_token(ctx, -1, NULL);
free(copy_text);
return count;
}
用分隔符分隔的文本數據有很多，如：
環境PATH，它由‘:’分開的多個路徑組成。如：
/usr/lib/qt-3.3/bin:/usr/kerberos/bin:/backup/tools/jdk1.5.0_18/bin/:/usr/lib/ccache:/usr/local/bin:/bin:/usr/bin:/home/lixianjing/bin
文件名，它由‘/’分開的路徑組成。如：
/usr/lib/qt-3.3/bin
URL中的參數，它‘&’分開的多個key/value對組成。
hl=zh-CN&q=limodev&btnG=Google+搜索&meta=&aq=f&oq=
所有這些數據都可以用上面的函數處理，所以這個小函數是頗具實用價值的。