微软谷歌的一道面试题：如何分隔没有空格标点的英文句子
给你一个没有间隔的字符串“thisisasentence”，如何将他分割成如下的句子：“this is a sentence”。
提供一个函数用来检验一个字符串是不是单词：bool dic(char* w)；
完成下列的函数。要求效率尽可能快。
bool Detect(char* str)
{
}
尽量写出完整思路，最好有伪代码。
[解决办法]
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"是可能的最长词，可以立即结束本次贪婪了。
中科院有一份开源的中文词语分割的软件，具体名称忘记了，可以找来看看。
[解决办法]
//純手打, 樓主就當偽代碼看吧.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 没完全按照给定的格式
#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#没用过，代码随便写的，语法可能会有错误，不过算法大家应当都能看懂的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 "" // 如果字符串无法分割成单词，则返回""}