2024华为OD机试真题---中文分词模拟器

华为OD机试中的中文分词模拟器题目，通常要求考生对给定的不包含空格的字符串进行精确分词。这个字符串仅包含英文小写字母及英文标点符号（如逗号、分号、句号等），同时会提供一个词库作为分词依据。以下是对这类题目的详细解析

一、题目描述

给定一个连续不包含空格的字符串Q，该字符串仅包含英文小写字母及英文标点符号(逗号、分号、句号)，同时给定词库，对该字符串进行精确分词。

说明:
1、精确分词:字符串分词后，不会出现重复。即"ilovechina"，不同词库可分割为"i,love,china"，“ilove,china”，不能分割出现重的"i,ilove,china"，i出现重复。

2、标点符号不成词，仅用于断句。

3、词库:根据外部知识库统计出来的常用词汇例:dictionary=[“i”,“ove”,“china”,“lovechina”,“ilove”]

4、分词原则:采用分词顺序优先且最长匹配原则

• “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”

用例1

输入
ilovechina
i,love,china,ch,na,ve,lo,this,is,the,word
输出
i,love,china
说明
无

用例2

输入
iat
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful输出
i a,t

四、分词原则

• 精确分词：字符串分词后，不会出现重叠的情况。
• 分词顺序：按照字符串从左到右的顺序进行分词。
• 最长匹配：在分词时，优先匹配词库中最长的符合条件的词汇。
• 标点符号：标点符号不成词，仅用于断句。

五、代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class PreciseSegmentation {

    public static void main(String[] args) {
        // 使用Scanner读取输入
        Scanner scanner = new Scanner(System.in);
        // 读取待分词的句子
        String Q = scanner.nextLine();
        // 读取词库字符串
        String dictionaryStr = scanner.nextLine();
    
        // 将词库转换为集合
        Set<String> dictionary = new HashSet<>(Arrays.asList(dictionaryStr.split(",")));
    
        // 分词结果
        List<String> result = new ArrayList<>();
    
        // 当前处理的起始位置
        int start = 0;
    
        // 开始分词处理
        while (start < Q.length()) {
            // 初始化结束位置
            int end = start + 1;
            // 用于存储最长匹配的词
            String longestMatch = null;
    
            // 寻找最长匹配的词
            while (end <= Q.length()) {
                // 获取子字符串
                String sub = Q.substring(start, end);
                // 检查子字符串是否在词库中
                if (dictionary.contains(sub)) {
                    // 更新最长匹配的词
                    if (longestMatch == null || sub.length() > longestMatch.length()) {
                        longestMatch = sub;
                    }
                }
                // 移动结束位置
                end++;
            }
    
            // 如果找到匹配的词，将其加入结果列表
            if (longestMatch != null) {
                result.add(longestMatch);
                // 更新起始位置
                start += longestMatch.length();
            } else {
                // 如果没有找到匹配的词，将单个字符加入结果列表
                result.add(Q.substring(start, start + 1));
                // 移动起始位置
                start++;
            }
        }
    
        // 输出结果
        System.out.println(String.join(",", result));
    }
}

六、解题思路

解题思路如下：

1. 输入读取：

   • 使用Scanner类从标准输入读取两行数据。第一行是待分词的句子Q，第二行是词库字符串dictionaryStr。

2. 词库转换：

   • 将词库字符串dictionaryStr按逗号分隔，转换为String类型的列表。
   • 使用HashSet来存储词库中的词汇，以便进行快速的查找操作。这是因为HashSet的查找时间复杂度为O(1)，而列表的查找时间复杂度为O(n)。

3. 分词处理：

   • 初始化一个空列表result来存储分词结果。
   • 初始化一个变量start来记录当前处理的起始位置，初始值为0。
   • 使用一个外层while循环来遍历整个待分词的句子Q，直到start变量的值等于句子的长度。

4. 最长匹配查找：

   • 在外层循环内部，初始化一个变量end来表示当前查找的结束位置，初始值为start + 1。
   • 初始化一个变量longestMatch来存储当前找到的最长匹配的词汇，初始值为null。
   • 使用一个内层while循环来查找从start到end之间的所有可能的子字符串，并检查它们是否在词库中。
   • 如果找到一个匹配的词汇，并且它的长度大于当前longestMatch的长度（或者longestMatch为null），则更新longestMatch的值。
   • 每次内层循环结束时，end的值都会增加1，以继续查找下一个可能的子字符串。

5. 结果处理：

   • 当内层循环结束后，检查longestMatch是否为null。
   • 如果longestMatch不为null，说明找到了一个匹配的词汇，将其添加到result列表中，并更新start的值为start + longestMatch.length()，以便继续处理下一个词汇。
   • 如果longestMatch为null，说明在当前位置没有找到匹配的词汇，此时将当前位置的单个字符作为一个词汇添加到result列表中，并将start的值增加1。

6. 输出结果：

   • 使用String.join(",", result)将result列表中的词汇用逗号连接起来，形成一个字符串。
   • 输出该字符串作为分词结果。

这个解题思路遵循了最长匹配原则和分词顺序优先的原则，确保了分词结果的准确性和合理性。同时，通过使用HashSet来存储词库中的词汇，提高了查找效率。

七、运行示例解析

运行示例解析如下：

输入：

1. 待分词的句子：ilovechina
2. 词库字符串：i,love,china,ch,na,ve,lo,this,is,the,word

步骤解析：

1. 初始化：

   • Q = "ilovechina"
   • 词库字符串被分割并存储在HashSet中，即dictionary = {i, love, china, ch, na, ve, lo, this, is, the, word}
   • result = []（空列表，用于存储分词结果）
   • start = 0（当前处理的起始位置）

2. 分词处理：

   • 外层while循环开始，条件是start < Q.length()，即start < 9。

   第一次外层循环：

   • end = start + 1 = 1
   • 内层while循环开始，条件是end <= Q.length()，即1 <= 9。
     • sub = Q.substring(0, 1) = "i"，dictionary.contains("i")返回true。
     • 更新longestMatch = "i"。
     • end递增为2。
     • sub = Q.substring(0, 2) = "il"，dictionary.contains("il")返回false。
     • end递增为3。
     • sub = Q.substring(0, 3) = "ilo"，dictionary.contains("ilo")返回false。
     • end递增为4。
     • sub = Q.substring(0, 4) = "ilov"，dictionary.contains("ilov")返回false。
     • end递增为5。
     • sub = Q.substring(0, 5) = "ilove"，dictionary.contains("ilove")返回false。
     • end递增为6。
     • sub = Q.substring(0, 6) = "ilovec"，dictionary.contains("ilovec")返回false。
     • end递增为7。
     • sub = Q.substring(0, 7) = "ilovech"，dictionary.contains("ilovech")返回false。
     • end递增为8。
     • sub = Q.substring(0, 8) = "ilovechi"，dictionary.contains("ilovechi")返回false。
     • end递增为9。
     • sub = Q.substring(0, 9) = "ilovechina"，dictionary.contains("ilovechina")返回false（虽然这不是词库中的词，但因为我们是从头开始找，所以会继续尝试更短的词）。
     • 内层循环结束，因为end已经超过Q.length()。
   • longestMatch = "i"，将其加入result，即result = ["i"]。
   • 更新start = 1。

   后续的外层循环（类似地处理）：

   • start = 1时，找到longestMatch = "love"，加入result，即result = ["i", "love"]。
   • start = 6时，找到longestMatch = "china"，加入result，即result = ["i", "love", "china"]。
   • 此时start = 11，已经超过Q.length()，外层循环结束。

3. 输出结果：

   • 使用String.join(",", result)将result列表中的词汇用逗号连接起来，得到"i,love,china"。
   • 输出该字符串。

最终输出：

i,love,china

注意：在这个例子中，尽管词库中有一些无关的词（如ch, na, ve, lo等），但它们并没有影响分词的结果，因为分词算法总是尝试找到最长的匹配词。