BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ coolwc (小包) 于 (Tue Jan 26 22:23:01 2010) 提到: 给出一个拼音串第一步：切分成最大单音节组合【例1】xiangan xiang'an 【例2】xianguo xian'guo 第二步：能够处理末尾的错误拼音串【例3】xiangand xiang'an'd 第三步：能够中间的错误拼音串【例4】xiangwwan xiang'w'wan 所有拼音组合：[upload=1][/upload] ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Wed Jan 27 09:11:49 2010) 提到: 这是算法题吗？ ☆─────────────────────────────────────☆ coolwc (小包) 于 (Wed Jan 27 10:46:08 2010) 提到: 是呀是呀动态规划【在 wks 的大作中提到: 】 : 这是算法题吗？ ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Wed Jan 27 14:50:03 2010) 提到: viterbi算法？ ☆─────────────────────────────────────☆ coolwc (小包) 于 (Wed Jan 27 15:37:44 2010) 提到: 还用不上统计学办法【在 wks 的大作中提到: 】 : viterbi算法？ ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Wed Jan 27 15:52:08 2010) 提到: 试试这个算法。（可惜不是用c++实现的）画出chart（字母边界作为节点，如果从一个边界到另一个边界之间的部分是一个单词，就有弧）然后找出chart中优先度最高的弧串（优先度按照弧的个数少的优先，一样的首单词长的优先，然后第二个单词长的优先，。。。）为了纠错，把所有的拼音的前缀加入组合集了，然后，每个字母也加进去（拼音不可能有以iuv开头的） from Queue import PriorityQueue prefix_list = list(reversed(sorted([ "a", "ai", "an", "ang", "ao", "b", "ba", "bai", "ban", "bang", "bao", "be", "bei", "ben", "beng", "bi", "bia", "bian", "biao", "bie", "bin", "bing", "bo", "bu", "c", "ca", "cai", "can", "cang", "cao", "ce", "cen", "ceng", "ch", "cha", "chai", "chan", "chang", "chao", "che", "chen", "cheng", "chi", "cho", "chon", "chong", "chou", "chu", "chua", "chuai", "chuan", "chuang", "chui", "chun", "chuo", "ci", "co", "con", "cong", "cou", "cu", "cua", "cuan", "cui", "cun", "cuo", "d", "da", "dai", "dan", "dang", "dao", "de", "dei", "den", "deng", "di", "dia", "dian", "diang", "diao", "die", "din", "ding", "diu", "do", "don", "dong", "dou", "du", "dua", "duan", "dui", "dun", "duo", "e", "ei", "en", "eng", "er", "f", "fa", "fan", "fang", "fe", "fei", "fen", "feng", "fo", "fou", "fu", "g", "ga", "gai", "gan", "gang", "gao", "ge", "gei", "gen", "geng", "go", "gon", "gong", "gou", "gu", "gua", "guai", "guan", "guang", "gui", "gun", "guo", "h", "ha", "hai", "han", "hang", "hao", "he", "hei", "hen", "heng", "ho", "hon", "hong", "hou", "hu", "hua", "huai", "huan", "huang", "hui", "hun", "huo", "i", "j", "ji", "jia", "jian", "jiang", "jiao", "jie", "jin", "jing", "jio", "jion", "jiong", "jiu", "ju", "jua", "juan", "jue", "jun", "k", "ka", "kai", "kan", "kang", "kao", "ke", "ken", "keng", "ko", "kon", "kong", "kou", "ku", "kua", "kuai", "kuan", "kuang", "kui", "kun", "kuo", "l", "la", "lai", "lan", "lang", "lao", "le", "lei", "len", "leng", "li", "lia", "lian", "liang", "liao", "lie", "lin", "ling", "liu", "lo", "lon", "long", "lou", "lu", "lua", "luan", "lun", "luo", "lv", "lva", "lvan", "lve", "lvn", "m", "ma", "mai", "man", "mang", "mao", "me", "mei", "men", "meng", "mi", "mia", "mian", "miao", "mie", "min", "ming", "miu", "mo", "mou", "mu", "n", "na", "nai", "nan", "nang", "nao", "ne", "nei", "nen", "neng", "ni", "nia", "nian", "niang", "niao", "nie", "nin", "ning", "niu", "no", "non", "nong", "nou", "nu", "nua", "nuan", "nun", "nuo", "nv", "nve", "o", "ou", "p", "pa", "pai", "pan", "pang", "pao", "pe", "pei", "pen", "peng", "pi", "pia", "pian", "piao", "pie", "pin", "ping", "po", "pou", "pu", "q", "qi", "qia", "qian", "qiang", "qiao", "qie", "qin", "qing", "qio", "qion", "qiong", "qiu", "qu", "qua", "quan", "que", "qun", "r", "ra", "ran", "rang", "rao", "re", "ren", "reng", "ri", "ro", "ron", "rong", "rou", "ru", "rua", "ruan", "rui", "run", "ruo", "s", "sa", "sai", "san", "sang", "sao", "se", "sei", "sen", "seng", "sh", "sha", "shai", "shan", "shang", "shao", "she", "shei", "shen", "sheng", "shi", "sho", "shon", "shong", "shou", "shu", "shua", "shuai", "shuan", "shuang", "shui", "shun", "shuo", "si", "so", "son", "song", "sou", "su", "sua", "suan", "sui", "sun", "suo", "t", "ta", "tai", "tan", "tang", "tao", "te", "ten", "teng", "ti", "tia", "tian", "tiao", "tie", "tin", "ting", "to", "ton", "tong", "tou", "tu", "tua", "tuan", "tui", "tun", "tuo", "u", "v", "w", "wa", "wai", "wan", "wang", "we", "wei", "wen", "weng", "wo", "wu", "x", "xi", "xia", "xian", "xiang", "xiao", "xie", "xin", "xing", "xio", "xion", "xiong", "xiu", "xu", "xua", "xuan", "xue", "xun", "y", "ya", "yan", "yang", "yao", "ye", "yi", "yin", "ying", "yo", "yon", "yong", "you", "yu", "yua", "yuan", "yue", "yun", "z", "za", "zai", "zan", "zang", "zao", "ze", "zei", "zen", "zeng", "zh", "zha", "zhai", "zhan", "zhang", "zhao", "zhe", "zhei", "zhen", "zheng", "zhi", "zho", "zhon", "zhong", "zhou", "zhu", "zhua", "zhuai", "zhuan", "zhuang", "zhui", "zhun", "zhuo", "zi", "zo", "zon", "zong", "zou", "zu", "zua", "zuan", "zui", "zun", "zuo",]))) prefix_set = set(prefix_list) def split_dp(letters): begin_to_ends = {} for begin in xrange(len(letters)): for end in xrange(begin+1,len(letters)+1): if letters[begin:end] in prefix_set: if begin in begin_to_ends: begin_to_ends[begin].append(end) else: begin_to_ends[begin]=[end] pq = PriorityQueue() pq.put((0,(-0,),0,())) while not pq.empty(): num_of_words, neg_word_lengths, matched_letters, matches = pq.get() if matched_letters == len(letters): result = matches break for end in begin_to_ends.get(matched_letters,[]): span_word = letters[matched_letters:end] new_tuple = ( num_of_words+1, neg_word_lengths+(-len(span_word),), end, matches+(span_word,)) pq.put(new_tuple) print new_tuple return result split=split_dp if __name__=='__main__': try: while True: line = raw_input().strip() print "'".join(split(line)) except EOFError: pass ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Wed Jan 27 15:54:06 2010) 提到: 复杂度O((n^2)*log(s))，n是字母数，s是前缀集大小 ☆─────────────────────────────────────☆ coolwc (小包) 于 (Wed Jan 27 16:32:41 2010) 提到: 经测试无问题 ☆─────────────────────────────────────☆ coolwc (小包) 于 (Wed Jan 27 16:58:56 2010) 提到: 晚上写一个回溯算法的cpp实现 ☆─────────────────────────────────────☆ jokerlee (Jackal The Dire) 于 (Wed Jan 27 18:56:10 2010) 提到: 【在 coolwc 的大作中提到: 】 : 给出一个拼音串 : 第一步：切分成最大单音节组合 : 第二步：能够处理末尾的错误拼音串 : ................... 这和分词的最大匹配是一样的吧，不是很长的话回溯一下就回溯穷举，要么动态规划，一般正向反向扫一边就ok了 ☆─────────────────────────────────────☆ coolwc (小包) 于 (Wed Jan 27 19:08:45 2010) 提到: 写个实现呗【在 jokerlee 的大作中提到: 】 : : 这和分词的最大匹配是一样的吧， : 不是很长的话回溯一下就回溯穷举，要么动态规划，一般正向反向扫一边就ok了 : ................... ☆─────────────────────────────────────☆ Thinker (思想者) 于 (Wed Jan 27 21:32:37 2010) 提到: 搜狗团队这个应该做得很明白【在 coolwc (小包) 的大作中提到: 】 : 给出一个拼音串 : 第一步：切分成最大单音节组合 : 【例1】xiangan xiang'an : ................... ☆─────────────────────────────────────☆ jokerlee (Jackal The Dire) 于 (Wed Jan 27 23:32:27 2010) 提到: 【在 coolwc 的大作中提到: 】 : 写个实现呗 ...坚决不上当.... ☆─────────────────────────────────────☆ coolwc (小包) 于 (Thu Jan 28 00:51:57 2010) 提到: 很简单的问题【在 Thinker 的大作中提到: 】 : 搜狗团队这个应该做得很明白 : -- : --------------------------- : ................... ☆─────────────────────────────────────☆ coolwc (小包) 于 (Thu Jan 28 00:52:09 2010) 提到: #include <string> #include <iostream> #include <fstream> #include <set> using namespace std; set<string> g_pydict; const bool GOOD = true; const bool WRONG = false; struct segment_info{ unsigned int start; unsigned int length; bool tag; }; inline bool TEST_PYSEG(const string& seg){return g_pydict.find(seg)!=g_pydict.end();} inline void PRINT_PYSEG(const string& buffer, const segment_info& lastseg, const char* seperator="'"){cout << buffer.substr(lastseg.start, lastseg.length) << seperator;}; int main(){ /* Load all pinyin compositions */ ifstream fin("zuhe.txt"); if(!fin){ cout<<"error when open zuhe.txt\n"; exit(-1); } string buffer; while(getline(fin, buffer)){ g_pydict.insert(buffer); } cerr << "**PYDICT Loaded\n"; while(getline(cin,buffer)){ /* Start pinyin segmenting */ segment_info lastseg,saveseg; lastseg.start=0; lastseg.length=1; lastseg.tag=GOOD; saveseg.start=0; saveseg.length=0; while(lastseg.start+lastseg.length<buffer.length()){ if(lastseg.tag==GOOD){ //如果前次切分是好的切分那么下次切分要试图向后扩展切分串 string segment = buffer.substr(lastseg.start, lastseg.length+1); if(TEST_PYSEG(segment)){ //可以后向扩展 saveseg=lastseg; lastseg.length++; continue; } else{ //不能扩展了 //看看是否需要回溯 segment = buffer.substr(lastseg.start+lastseg.length,2); if(TEST_PYSEG(segment)){ //不需要回溯，可以自己成词 PRINT_PYSEG(buffer, lastseg); saveseg=lastseg; lastseg.start=lastseg.start+lastseg.length; lastseg.length=2; continue; } else{ //回溯 //看看回溯是否成功 if(lastseg.start==0 & lastseg.length==1){ //拼音串的头一次切分就出错了，没有回溯的必要 lastseg.tag=WRONG; continue; } segment = buffer.substr(saveseg.start+saveseg.length,2); /* 这里只看回溯后的最先两个字母是否是合法拼音，因为在所有拼音串中任何合法拼音串的前两个字母都必然是合法拼音串 */ if(TEST_PYSEG(segment)){ //回溯成功，是有效回溯 PRINT_PYSEG(buffer, saveseg); lastseg.start=saveseg.start+saveseg.length; lastseg.length=2; continue; } else{ //回溯失败，不应该回溯，是错误拼音串 PRINT_PYSEG(buffer, lastseg); lastseg.start=lastseg.start+lastseg.length; lastseg.length=1; lastseg.tag=WRONG; //PRINT_PYSEG(buffer, lastseg); continue; } } } } else{ //如果前次切分是错误拼音串，那么下次切分从原地开始重新切分 PRINT_PYSEG(buffer, lastseg); string segment = buffer.substr(lastseg.start+lastseg.length, 2); if(TEST_PYSEG(segment)){ //切分成功 lastseg.start=lastseg.start+lastseg.length; lastseg.length=2; lastseg.tag=GOOD; continue; } else{ //不用回溯了，因为前面也是个错误拼音串，两个连起来必然也是错误的 lastseg.start++; lastseg.length=1; lastseg.tag=WRONG; continue; } } } PRINT_PYSEG(buffer, lastseg, "\n"); } }

[合集] 提个好玩的问题--拼音切分