首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图

微软谷歌的一道面试题:怎么分隔没有空格标点的英文句子

2014-06-14 来源:读书人网 【读书人网(Reader8.cn):综合教育门户网站】
微软谷歌的一道面试题:如何分隔没有空格标点的英文句子给你一个没有间隔的字符串“thisisasentence”,如何将

微软谷歌的一道面试题:如何分隔没有空格标点的英文句子
给你一个没有间隔的字符串“thisisasentence”,如何将他分割成如下的句子:“this is a sentence”。
提供一个函数用来检验一个字符串是不是单词:bool dic(char* w);
完成下列的函数。要求效率尽可能快。
bool Detect(char* str)
{

}

尽量写出完整思路,最好有伪代码。


[解决办法]

C/C++ code
bool Detect(char* str){    int len = strlen(str);    //字符匹配完毕,返回true    if(0 == len)    {        return true;    }    //递归匹配剩余字符    //回溯体现在i++上面    for(int i=0;i<len;i++)    {        //伪码,复制str[0]--str[i]建立一个字符串        char word[] = make_str(str,0,i);        if(true == dic(word))        {            if(true == Detect(str+i+1))            {//如果剩下的字符构成单词串                return true;            }        }    }    //当 i== len时,说明剩下的全部字符不构成单词,返回false    return false;}
[解决办法]
自然语言分词方面的问题。现行一般采用逆向贪婪算法和正向贪婪算法相结合的方式。

所谓贪婪算法是指总是查找可以构成词的最长的字符串,例如"thisisasentence"正向搜索"this"时,尝试"thisi",而"thisi"不是一个词,"thisis"也不是词,以此类推,直到"thisisasentence"也不是一个词,因此退回得到"this",再次检测以"i"开头的; 对于"sent",容易检测到"sentence"是一个词,因此不会分割成"sent"和"ence"。可以设置最长词限制,不用贪婪整个语句。

一般逆向贪婪算法的正确率更高一些,采用正向逆向双向结合可以得到更优结果。

效率问题一般需要考虑词典的结构安排,一般是索引表或者类似的结构,可以高效确定后续词有否有可能。

例如存在词典五级散列:t->h->i->s->(?)
如果第五级散列中不存在i则可以立刻证明"this"是可能的最长词,可以立即结束本次贪婪了。

中科院有一份开源的中文词语分割的软件,具体名称忘记了,可以找来看看。
[解决办法]
C/C++ code
//純手打, 樓主就當偽代碼看吧.bool Detect(char* str){    int nLen = strlen(str);    int i, j;    int nRet;    int* pSplit = (int*)malloc(nlen*sizeof(int));    char* pCurStr = (char*)malloc((nlen+1)*sizeof(char));    memset(pSpilt, 0, nlen*sizeof(int));    for(i=0; i<nLen; i++)    {      memcpy(pCurStr, str, i+1);      pCurStr[i+1] = '\0';      if(dic(pCurStr))      {        pSpilt[i] = 1;        continue;      }      for(j=0; j<i; j++)      {         if(pSpilt[j]==1 && dic(pCurStr+j+1))         {           pSpilt[i] = 1;           break;         }      }    }    nRet = pSpilt(nLen-1);    free(pCurStr);    free(pSplit);    return nRet;}
[解决办法]
无聊写了一个,指定一个txt文件生成字典,dic 和 Detect 没完全按照给定的格式
C/C++ code
#include "stdafx.h"#define MAX_LENGTH 50char buff[MAX_LENGTH];int words = 0;int maxlen=0;typedef struct ALPHABET{    char alpha;    bool isWord;    int deep;    ALPHABET* next[26];} ALPHABET;ALPHABET* newAlpha(char ch=0){    ALPHABET *a = new ALPHABET;    memset(a,0,sizeof(ALPHABET));    a->alpha = ch;    return a;}void deleteAlpha(ALPHABET* a){    if(a==NULL)return;    for(int i=0;i<26;++i)    {        if(a->next[i]!=NULL)            deleteAlpha(a->next[i]);    }    delete a;}void analysWord(ALPHABET* a, char* word){    if(*word!=0)    {        int p = *word-'a';        if(a->next[p]==NULL)        {            a->next[p] = newAlpha(*word);            a->next[p]->deep = a->deep+1;        }        analysWord(a->next[p], word+1);    }    else if(!a->isWord)    {        a->isWord = true;        //cout<<buff<<' ';        if(a->deep>maxlen)maxlen=a->deep;        ++words;    }}ALPHABET* dic(ALPHABET* a,const char* w){    int p;    //if(*w==0&&a->isWord)return a;    p = *w-'a';    if(p<0||p>25)return NULL;    if(a->next[p]!=NULL)    {        if(a->next[p]->isWord)            return a->next[p];        return dic(a->next[p], w+1);    }    return NULL;}char* ostns=NULL;char* curpos=NULL;int Detect(ALPHABET* a,ALPHABET* cur, const char* s){    const char* str = s;    if(curpos==NULL || ostns==NULL)return 0;    ALPHABET *tmp = dic(cur, str);    if(tmp==NULL)    {        if(*s!='\0')        {            //cout<<"Not a sentence."<<endl;            return 0;        }        else        {            *curpos = '\0';            cout<<ostns<<endl;            return 1;        }    }    else if(tmp==cur)    {        *(curpos++) = ' ';                return Detect(a, a, str);    }    else    {        memcpy(curpos, s, tmp->deep-cur->deep);        curpos+=tmp->deep-cur->deep;        char* tmppos = curpos;        if(!Detect(a, tmp, str+tmp->deep-cur->deep))        {            curpos = tmppos;            *(curpos++) = ' ';            return Detect(a, a, str+tmp->deep-cur->deep);        }    }    return 1;}int _tmain(int argc, _TCHAR* argv[]){    if(argc<2)    {        cout<<_T("please set a dict file.");    }    else    {        TCHAR* dictfile = argv[1];        ALPHABET* a = newAlpha();        FILE* pfdict = NULL;        pfdict = fopen(dictfile, "r");        if(!pfdict)            cout<<"bad fiename."<<endl;        else        {            int ch;            ch = fgetc(pfdict);            char* pc = buff;            while(!feof(pfdict))            {                *pc = (char)ch;                if((*pc>'A'-1 && *pc<'Z'+1))                    *pc+='a'-'A';                if((*pc>'a'-1 && *pc<'z'+1))                {                    ++pc;                    if((pc-buff)>maxlen)maxlen=(pc-buff);                }                else                {                    if(pc>buff)                    {                        *pc=0;                        analysWord(a, buff);                    }                    pc = buff;                }                ch = fgetc(pfdict);            }            cout<<words<<" word(s).max length is "<<maxlen<<endl;            fclose(pfdict);        }        string s1;        while(1)        {            cout<<"please input a sentence(empty to exit):"<<endl;            getline(cin, s1);            if(s1.length()==0)break;            ostns = new char[s1.length()*2+1];            curpos = ostns;            cout<<Detect(a,a,s1.c_str())<<endl;            delete ostns;            curpos = NULL;        }        deleteAlpha(a);    }    return 0;} 


[解决办法]

C# code
// 该函数为递归算法,C#没用过,代码随便写的,语法可能会有错误,不过算法大家应当都能看懂的string Detect(char* str){    string leftstr;    string rightstr;    string leftword;    string rightword;    // 如果字符串本身就是个单词,则返回该单词    if dic(str) then    {        return str;    }    // 将字符串分成两部分,判断每部分是否可分割成单词,循环试验每一种分割方式    for(int i = 1, i < s.length(), i ++)    {        // 分割字符串,位置i为分割点         leftstr = ...;        rightstr = ...;        // 左侧字符转换为单词        leftword = Detect(leftstr)        // 如果左侧转换成功,则进行右侧字符串的转换        if leftword.length() > 0         {            // 右侧字符串转换成单司            rightword = Detect(rightstr)            // 如果右侧也转换成功,则将两边转换的结果合并就是最终结果            if (rightword.length() > 0)            {                return leftword + " " + rightword    // 返回分割结果            }        }    }    return ""    // 如果字符串无法分割成单词,则返回""}