华为OD统一考试 - 中文分词模拟器
题目描述
给定一个连续不包含空格的字符串,该字符串仅包含英文小写字母及英文标点符号(逗号、分号、句号),同时给定词库,对该字符串进行精确分词。
说明:
- 精确分词:字符串分词后,不会出现重叠。即"ilovechina",不同词库可分割为"i,love,china","ilove,china",不能分割出现重叠的"i,ilove,china",i 出现重叠
- 标点符号不成词,仅用于断句
- 词库:根据外部知识库统计出来的常用词汇例:dictionary = ["i", "love", "china", "lovechina", "ilove"]
- 分词原则:采用分词顺序优先且最长匹配原则"ilovechina",假设分词结果 [i,ilove,lo,love,ch,china,lovechina],则输出 [ilove,china]错误输出:[i,lovechina],原因:"ilove" > 优先于 "lovechina" 成词错误输出:[i,love,china],原因:"ilove" > "i"遵循最长匹配原则
输入描述
第一行输入待分词语句 "ilovechina"
- 字符串长度限制:0 < length < 256
第二行输入中文词库 "i,love,china,ch,na,ve,lo,this,is,this,word"
- 词库长度限制:1 < length < 100000
输出描述
按顺序输出分词结果 "i,love,china"
用例
输入 | ilovechina i,love,china,ch,na,ve,lo,this,is,the,word |
输出 | i,love,china |
说明 | 无 |
输入 | iat i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful |
输出 | i,a,t |
说明 | 单个字母, 不在词库中且不成词则输出单个字母 |
输入 | ilovechina,thewordisbeautiful i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful |
输出 | i,love,china the,word,is,beauti,ful |
说明 | 标点符号为英文标点符号 |
题目解析
本题感觉题意不是很清晰。
我对题目的理解是:
句子:ilovechina
词库:[i,love,china,ch,na,ve,lo,this,is,the,word]
现在要用词库里面的词汇组成句子。并且选择词汇时,优先选择词库中靠前的,且长度最长的。
比如组成句子“ilovechina”的第一个词汇,必然是 "i" 开头的,因此我们去词库中找 "i" 开头的词汇,按词库顺序依次是:
- i
- is
其中 is 虽然是 i 开头,但是不符合句子后续部分要求,因此选择词库中词汇 “i”。
此时句子还剩下 "lovechina" 没有分词,则继续在词库中查找 "l" 开头的词汇,按词库顺序依次是:
- love
- lo
其中 "love" 是顺序靠前,且长度较长的,因此选择词库中词汇 "love"。
此时句子还剩下 "china" 没有分词,则继续在词库中查找 "c" 开头的词汇,按词库顺序依次是:
- china
- ch
其中 "china" 是顺序靠前,且长度较长的,因此选择词库中词汇 "china"。
此时句子"ilovechina" 完成分词,分词结果为:["i", "love", "china"]。
本题,我的疑惑主要在于用例2:
句子:"iat"
词库:[i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful]
按照之前的逻辑,首先找到组成句子的第一个词汇,该词汇必然以"i"开头,则匹配到词库中的词汇"i"。
接下来句子还剩"at",再去词库中查找"a"开头的词汇,发现没有。那么此时我的疑问来了:
- 是只针对句子剩余部分"at",进行输出单个字母的操作
- 还是针对整个句子"iat",进行输出单个字母的操作
对于这个用例,两种策略的输出结果都是一样,因为这个用例给的太有歧义了。
比如我给个例子:
句子:iloveat
词库:[i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful]
此时输出:i,love,a,t
还是输出:i,l,o,v,e,a,t
不在词库中且不成词则输出单个字母
上面我给的例子,i 在词库中,love在词库中,at不在词库中,因此只针对at执行输出单个字母操作。
一次你,我理解是输出:i,love,a,t
import Foundation func ODTest_2_22() { print("第一行输入待分词语句 \"ilovechina\"") print("字符串长度限制:0 < length < 256") var sentences = (readLine() ?? "").split(separator: /[,.;]/).map { String($0) } print("第二行输入中文词库 \"i,love,china,ch,na,ve,lo,this,is,this,word\"") print("词库长度限制:1 < length < 100000") var words = (readLine() ?? "").split(separator: /[,.;]/).map { String($0) } print("输出描述") print("按顺序输出分词结果 \"ilovechina\"") print("\(getResult())") func getResult() -> String { var wordSet: Set<String> = Set(words) // queue记录待分词语句 var queue: [String] = sentences // ans记录最终分词结果 var ans: [String] = [] while !queue.isEmpty { // 待分词的句子 let sentence = queue.removeFirst() var index = sentence.count for r in (1 ... sentence.count).reversed() { // 截取句子 [0,r) 范围子串词汇, 这样的就能实现优先最长匹配,并且由于是必须从0索引开始截取,因此满足了分词顺序优先 let fragment = String(sentence.prefix(r)) // 若词库中是否存在该子串词汇 if wordSet.contains(fragment) { // 则将对应子串词汇纳入结果 ans.append(fragment) // 我理解词库中每个词汇只能使用一次,因此这里将词库中使用过的词汇移除 wordSet.remove(fragment) // 若子串词汇只是句子部分,则句子剩余部分还要继续去词库中查找 if r < sentence.count { queue.insert(String(sentence.suffix(sentence.count - r)), at: 0) } break } index -= 1 } // 没有在词库中找到对应子串词汇,则输出单个字母 if index == 0 { // 注意,这里只放一个字母到结果中,句子剩余部分继续去词库中查找 ans.append(String(sentence.prefix(1)) + "") if sentence.count > 1 { queue.insert(String(sentence.suffix(1)), at: 0) } } } return ans.joined(separator: ",") } }