機(jī)考E卷200分題 - 中文分詞模擬器
題目描述
給定一個連續(xù)不包含空格的字符串,該字符串僅包含英文小寫字母及英文標(biāo)點(diǎn)符號(逗號、分號、句號),同時(shí)給定詞庫,對該字符串進(jìn)行精確分詞。
說明:
1. 精確分詞:字符串分詞后,不會出現(xiàn)重疊。即"ilovechina",不同詞庫可分割為"i,love,china",“ilove,china”,不能分割出現(xiàn)重疊的"i,ilove,china",i 出現(xiàn)重疊
2. 標(biāo)點(diǎn)符號不成詞,僅用于斷句
3. 詞庫:根據(jù)外部知識庫統(tǒng)計(jì)出來的常用詞匯例:dictionary = [“i”, “l(fā)ove”, “china”, “l(fā)ovechina”, “ilove”]
4. 分詞原則:采用分詞順序優(yōu)先且最長匹配原則
“ilovechina”,假設(shè)分詞結(jié)果 [i,ilove,lo,love,ch,china,lovechina],則輸出 [ilove,china]
錯誤輸出:[i,lovechina],原因:“ilove” > 優(yōu)先于 “l(fā)ovechina” 成詞
錯誤輸出:[i,love,china],原因:“ilove” > "i"遵循最長匹配原則
輸入描述
第一行輸入待分詞語句
“ilovechina”
- 字符串長度限制:0 < length < 256
第二行輸入中文詞庫 “i,love,china,ch,na,ve,lo,this,is,this,word”
- 詞庫長度限制:1 < length < 100000
輸出描述
按順序輸出分詞結(jié)果 “i,love,china”
用例1
輸入
ilovechina
i,love,china,ch,na,ve,lo,this,is,the,word
12
輸出
i,love,china
1
說明 無
用例2
輸入
iat
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful
12
輸出
i,a,t
1
說明
單個字母,不在詞庫中且不成詞則輸出單個字母
用例3
輸入
ilovechina,thewordisbeautiful
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful
12
輸出
i,love,china the,word,is,beauti,ful
1
說明
標(biāo)點(diǎn)符號為英文標(biāo)點(diǎn)符號
解題思路
題目的要求是給定一個連續(xù)的字符串,該字符串只包含英文小寫字母和英文標(biāo)點(diǎn)符號(逗號、分號、句號),同時(shí)給出一個詞庫。你需要根據(jù)這個詞庫將字符串進(jìn)行分詞。
這里的分詞有兩個原則:
1. 分詞順序優(yōu)先:如果一個字符串可以被分割成多種可能的詞序列,那么應(yīng)該優(yōu)先選擇在詞庫中出現(xiàn)順序較前的詞。例如,如果詞庫是 [“i”, “l(fā)ove”, “china”, “l(fā)ovechina”, “ilove”],那么字符串 “ilovechina” 應(yīng)該被分割為 “ilove,china”,而不是 “i,lovechina”,因?yàn)?“ilove” 在詞庫中出現(xiàn)的順序比 “l(fā)ovechina” 要前。
2. 最長匹配原則:如果一個字符串可以被分割成多種可能的詞序列,那么應(yīng)該優(yōu)先選擇長度較長的詞。例如,如果詞庫是 [“i”, “l(fā)ove”, “china”, “l(fā)ovechina”, “ilove”],那么字符串 “ilovechina” 應(yīng)該被分割為 “ilove,china”,而不是 “i,love,china”,因?yàn)?“ilove” 的長度比 “i” 要長。
注意,標(biāo)點(diǎn)符號不會成為詞的一部分,它們只用于斷句。如果一個字符不在詞庫中,也不是標(biāo)點(diǎn)符號,那么它會被當(dāng)作一個單獨(dú)的詞。
用例模擬
ilovechina,thewordisbeautiful
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful
12
在這個例子中,輸入的句子是 “ilovechina,thewordisbeautiful”,字典中的單詞是 “i”, “l(fā)ove”, “china”,
“ch”, “na”, “ve”, “l(fā)o”, “this”, “is”, “the”, “word”, “beauti”, “tiful”, “ful”。
1. 首先,將字典中的每個單詞插入到 Trie 中。這個過程中,Trie 會根據(jù)字典中的單詞構(gòu)建出相應(yīng)的路徑。
2. 然后,開始遍歷句子中的每個字符。首先遇到的字符是 ‘i’,在 Trie 中可以找到以 ‘i’ 為起點(diǎn)的單詞 “i”,所以將 “i” 添加到結(jié)果中。
3. 接下來的字符是 ‘l’,在 Trie 中可以找到以 ‘l’ 為起點(diǎn)的最長單詞 “l(fā)ove”,所以將 “l(fā)ove” 添加到結(jié)果中。
4. 然后的字符是 ‘c’,在 Trie 中可以找到以 ‘c’ 為起點(diǎn)的最長單詞 “china”,所以將 “china” 添加到結(jié)果中。
5. 接下來的字符是 ‘,’,這是一個非字母字符,直接將其添加到結(jié)果中。
6. 然后的字符是 ‘t’,在 Trie 中可以找到以 ‘t’ 為起點(diǎn)的最長單詞 “the”,所以將 “the” 添加到結(jié)果中。
7. 接下來的字符是 ‘w’,在 Trie 中可以找到以 ‘w’ 為起點(diǎn)的最長單詞 “word”,所以將 “word” 添加到結(jié)果中。
8. 然后的字符是 ‘i’,在 Trie 中可以找到以 ‘i’ 為起點(diǎn)的最長單詞 “is”,所以將 “is” 添加到結(jié)果中。
9. 接下來的字符是 ‘b’,在 Trie 中可以找到以 ‘b’ 為起點(diǎn)的最長單詞 “beauti”,所以將 “beauti” 添加到結(jié)果中。
10. 最后的字符是 ‘f’,在 Trie 中可以找到以 ‘f’ 為起點(diǎn)的最長單詞 “ful”,所以將 “ful” 添加到結(jié)果中。
11. 遍歷完句子中的所有字符后,得到的結(jié)果是 “i,love,china,the,word,is,beauti,ful”。
所以,這個程序的輸出應(yīng)該是 “i,love,china,the,word,is,beauti,ful”。
C++
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm> // 添加這一行
using namespace std;
// 定義 TrieNode 類,每個節(jié)點(diǎn)包含一個布爾值 isWord 和一個 TrieNode 類型的數(shù)組 children
struct TrieNode {
bool isWord;
TrieNode* children[26];
TrieNode() {
isWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
// 創(chuàng)建 Trie 的根節(jié)點(diǎn)
TrieNode* root = new TrieNode();
// 插入方法,用于向 Trie 中插入一個單詞
void insert(string word) {
TrieNode* node = root;
// 遍歷單詞中的每個字符
for (char c : word) {
// 如果當(dāng)前字符對應(yīng)的子節(jié)點(diǎn)為空,則創(chuàng)建一個新的子節(jié)點(diǎn)
if (node->children[c - 'a'] == nullptr) {
node->children[c - 'a'] = new TrieNode();
}
// 移動到下一個子節(jié)點(diǎn)
node = node->children[c - 'a'];
}
// 標(biāo)記當(dāng)前節(jié)點(diǎn)為一個單詞的結(jié)束
node->isWord = true;
}
int main() {
// 讀取輸入的句子,并將其轉(zhuǎn)換為小寫
string sentence;
getline(cin, sentence);
transform(sentence.begin(), sentence.end(), sentence.begin(), ::tolower);
// 讀取輸入的字典,字典中的單詞以逗號分隔
string dictionary;
getline(cin, dictionary);
stringstream ss(dictionary);
string word;
while (getline(ss, word, ',')) {
insert(word);
}
vector<string> result;
int i = 0;
// 遍歷句子中的每個字符
while (i < sentence.size()) {
// 如果當(dāng)前字符不是字母,則直接將其添加到結(jié)果中
if (!isalpha(sentence[i])) {
result.push_back(sentence.substr(i, 1));
i++;
continue;
}
int j = sentence.size();
// 從句子的末尾開始,尋找以 i 為起點(diǎn)的最長的在字典中存在的單詞
while (j > i) {
TrieNode* node = root;
bool isWord = true;
for (int k = i; k < j; k++) {
// 如果當(dāng)前字符不是字母,或者在 Trie 中不存在對應(yīng)的子節(jié)點(diǎn),則說明當(dāng)前的字符串不是一個單詞
if (!isalpha(sentence[k]) || node->children[sentence[k] - 'a'] == nullptr) {
isWord = false;
break;
}
// 移動到下一個子節(jié)點(diǎn)
node = node->children[sentence[k] - 'a'];
}
// 如果找到了一個單詞,則結(jié)束循環(huán)
if (isWord && node->isWord) {
break;
}
// 如果沒有找到單詞,則縮短當(dāng)前的字符串
j--;
}
// 如果沒有找到單詞,則將當(dāng)前字符作為一個單獨(dú)的單詞添加到結(jié)果中
if (j == i) {
result.push_back(sentence.substr(i, 1));
i++;
} else {
// 如果找到了單詞,則將該單詞添加到結(jié)果中
result.push_back(sentence.substr(i, j - i));
i = j;
}
}
// 輸出結(jié)果,單詞之間以逗號分隔
for (int i = 0; i < result.size(); i++) {
if (i > 0) {
cout << ",";
}
cout << result[i];
}
cout << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
Java
import java.util.*;
public class Main {
// 定義 TrieNode 類,每個節(jié)點(diǎn)包含一個布爾值 isWord 和一個 TrieNode 類型的數(shù)組 children
static class TrieNode {
boolean isWord;
TrieNode[] children = new TrieNode[26];
}
// 創(chuàng)建 Trie 的根節(jié)點(diǎn)
static TrieNode root = new TrieNode();
// 插入方法,用于向 Trie 中插入一個單詞
public static void insert(String word) {
TrieNode node = root;
// 遍歷單詞中的每個字符
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
// 如果當(dāng)前字符對應(yīng)的子節(jié)點(diǎn)為空,則創(chuàng)建一個新的子節(jié)點(diǎn)
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
// 移動到下一個子節(jié)點(diǎn)
node = node.children[c - 'a'];
}
// 標(biāo)記當(dāng)前節(jié)點(diǎn)為一個單詞的結(jié)束
node.isWord = true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 讀取輸入的句子,并將其轉(zhuǎn)換為小寫
String sentence = scanner.nextLine().toLowerCase();
// 讀取輸入的字典,字典中的單詞以逗號分隔
String[] dictionary = scanner.nextLine().split(",");
// 將字典中的每個單詞插入到 Trie 中
for (String word : dictionary) {
insert(word.toLowerCase());
}
List<String> result = new ArrayList<>();
int i = 0;
// 遍歷句子中的每個字符
while (i < sentence.length()) {
// 如果當(dāng)前字符不是字母,則直接將其添加到結(jié)果中
if (sentence.charAt(i) < 'a' || sentence.charAt(i) > 'z') {
result.add(sentence.substring(i, i + 1));
i++;
continue;
}
int j = sentence.length();
// 從句子的末尾開始,尋找以 i 為起點(diǎn)的最長的在字典中存在的單詞
while (j > i) {
TrieNode node = root;
boolean isWord = true;
for (int k = i; k < j; k++) {
// 如果當(dāng)前字符不是字母,或者在 Trie 中不存在對應(yīng)的子節(jié)點(diǎn),則說明當(dāng)前的字符串不是一個單詞
if (sentence.charAt(k) < 'a' || sentence.charAt(k) > 'z' || node.children[sentence.charAt(k) - 'a'] == null) {
isWord = false;
break;
}
// 移動到下一個子節(jié)點(diǎn)
node = node.children[sentence.charAt(k) - 'a'];
}
// 如果找到了一個單詞,則結(jié)束循環(huán)
if (isWord && node.isWord) {
break;
}
// 如果沒有找到單詞,則縮短當(dāng)前的字符串
j--;
}
// 如果沒有找到單詞,則將當(dāng)前字符作為一個單獨(dú)的單詞添加到結(jié)果中
if (j == i) {
result.add(sentence.substring(i, i + 1));
i++;
} else {
// 如果找到了單詞,則將該單詞添加到結(jié)果中
result.add(sentence.substring(i, j));
i = j;
}
}
// 輸出結(jié)果,單詞之間以逗號分隔
System.out.println(String.join(",", result));
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
javaScript
// 定義 TrieNode 類,每個節(jié)點(diǎn)包含一個布爾值 isWord 和一個 TrieNode 類型的數(shù)組 children
class TrieNode {
constructor() {
this.isWord = false; // 標(biāo)記該節(jié)點(diǎn)是否為一個單詞的結(jié)束
this.children = new Array(26).fill(null); // 存儲子節(jié)點(diǎn)的數(shù)組,每個元素對應(yīng)一個字母
}
}
// 創(chuàng)建 Trie 的根節(jié)點(diǎn)
let root = new TrieNode();
// 插入方法,用于向 Trie 中插入一個單詞
function insert(word) {
let node = root; // 從根節(jié)點(diǎn)開始
for (let i = 0; i < word.length; i++) {
let c = word.charCodeAt(i) - 'a'.charCodeAt(0); // 計(jì)算當(dāng)前字符對應(yīng)的索引
// 如果當(dāng)前字符對應(yīng)的子節(jié)點(diǎn)為空,則創(chuàng)建一個新的子節(jié)點(diǎn)
if (node.children[c] == null) {
node.children[c] = new TrieNode();
}
// 移動到下一個子節(jié)點(diǎn)
node = node.children[c];
}
// 標(biāo)記當(dāng)前節(jié)點(diǎn)為一個單詞的結(jié)束
node.isWord = true;
}
let readline = require('readline');
let rl = readline.createInterface({
input: process.stdin, // 輸入流
output: process.stdout // 輸出流
});
let lines = []; // 存儲輸入的每一行
rl.on('line', function (line) {
lines.push(line); // 當(dāng)讀取到一行時(shí),將其添加到 lines 數(shù)組中
}).on('close', function() { // 當(dāng)讀取完所有輸入時(shí)
let sentence = lines[0].toLowerCase(); // 獲取句子,并將其轉(zhuǎn)換為小寫
let dictionary = lines[1].split(","); // 獲取字典,字典中的單詞以逗號分隔
for (let word of dictionary) {
insert(word.toLowerCase()); // 將字典中的每個單詞插入到 Trie 中
}
let result = []; // 存儲結(jié)果
let i = 0;
// 遍歷句子中的每個字符
while (i < sentence.length) {
// 如果當(dāng)前字符不是字母,則直接將其添加到結(jié)果中
if (sentence.charCodeAt(i) < 'a'.charCodeAt(0) || sentence.charCodeAt(i) > 'z'.charCodeAt(0)) {
result.push(sentence.substring(i, i + 1));
i++;
continue;
}
let j = sentence.length;
// 從句子的末尾開始,尋找以 i 為起點(diǎn)的最長的在字典中存在的單詞
while (j > i) {
let node = root;
let isWord = true;
for (let k = i; k < j; k++) {
// 如果當(dāng)前字符不是字母,或者在 Trie 中不存在對應(yīng)的子節(jié)點(diǎn),則說明當(dāng)前的字符串不是一個單詞
if (sentence.charCodeAt(k) < 'a'.charCodeAt(0) || sentence.charCodeAt(k) > 'z'.charCodeAt(0) || node.children[sentence.charCodeAt(k) - 'a'.charCodeAt(0)] == null) {
isWord = false;
break;
}
// 移動到下一個子節(jié)點(diǎn)
node = node.children[sentence.charCodeAt(k) - 'a'.charCodeAt(0)];
}
// 如果找到了一個單詞,則結(jié)束循環(huán)
if (isWord && node.isWord) {
break;
}
// 如果沒有找到單詞,則縮短當(dāng)前的字符串
j--;
}
// 如果沒有找到單詞,則將當(dāng)前字符作為一個單獨(dú)的單詞添加到結(jié)果中
if (j == i) {
result.push(sentence.substring(i, i + 1));
i++;
} else {
// 如果找到了單詞,則將該單詞添加到結(jié)果中
result.push(sentence.substring(i, j));
i = j;
}
}
// 輸出結(jié)果,單詞之間以逗號分隔
console.log(result.join(","));
});
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
Python
# 定義 TrieNode 類,每個節(jié)點(diǎn)包含一個布爾值 is_word 和一個 TrieNode 類型的數(shù)組 children
class TrieNode:
def __init__(self):
self.is_word = False # 標(biāo)記該節(jié)點(diǎn)是否為一個單詞的結(jié)束
self.children = [None] * 26 # 存儲子節(jié)點(diǎn)的數(shù)組,每個元素對應(yīng)一個字母
# 創(chuàng)建 Trie 的根節(jié)點(diǎn)
root = TrieNode()
# 插入方法,用于向 Trie 中插入一個單詞
def insert(word):
node = root # 從根節(jié)點(diǎn)開始
for c in word:
index = ord(c) - ord('a') # 計(jì)算當(dāng)前字符對應(yīng)的索引
# 如果當(dāng)前字符對應(yīng)的子節(jié)點(diǎn)為空,則創(chuàng)建一個新的子節(jié)點(diǎn)
if node.children[index] is None:
node.children[index] = TrieNode()
# 移動到下一個子節(jié)點(diǎn)
node = node.children[index]
# 標(biāo)記當(dāng)前節(jié)點(diǎn)為一個單詞的結(jié)束
node.is_word = True
# 輸入句子,并將其轉(zhuǎn)換為小寫
sentence = input().lower()
# 輸入字典,字典中的單詞以逗號分隔
dictionary = input().split(",")
for word in dictionary:
insert(word.lower()) # 將字典中的每個單詞插入到 Trie 中
result = [] # 存儲結(jié)果
i = 0
# 遍歷句子中的每個字符
while i < len(sentence):
# 如果當(dāng)前字符不是字母,則直接將其添加到結(jié)果中
if not sentence[i].isalpha():
result.append(sentence[i])
i += 1
continue
j = len(sentence)
# 從句子的末尾開始,尋找以 i 為起點(diǎn)的最長的在字典中存在的單詞
while j > i:
node = root
is_word = True
for k in range(i, j):
# 如果當(dāng)前字符不是字母,或者在 Trie 中不存在對應(yīng)的子節(jié)點(diǎn),則說明當(dāng)前的字符串不是一個單詞
if not sentence[k].isalpha() or node.children[ord(sentence[k]) - ord('a')] is None:
is_word = False
break
# 移動到下一個子節(jié)點(diǎn)
node = node.children[ord(sentence[k]) - ord('a')]
# 如果找到了一個單詞,則結(jié)束循環(huán)
if is_word and node.is_word:
break
# 如果沒有找到單詞,則縮短當(dāng)前的字符串
j -= 1
# 如果沒有找到單詞,則將當(dāng)前字符作為一個單獨(dú)的單詞添加到結(jié)果中
if j == i:
result.append(sentence[i])
i += 1
else:
# 如果找到了單詞,則將該單詞添加到結(jié)果中
result.append(sentence[i:j])
i = j
# 輸出結(jié)果,單詞之間以逗號分隔
print(",".join(result))
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
C語言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// 定義 TrieNode 結(jié)構(gòu)體,每個節(jié)點(diǎn)包含一個布爾值 isWord 和一個 TrieNode 類型的數(shù)組 children
struct TrieNode {
int isWord;
struct TrieNode* children[26];
};
// 創(chuàng)建 Trie 的根節(jié)點(diǎn)
struct TrieNode* root;
// 插入方法,用于向 Trie 中插入一個單詞
void insert(char* word) {
struct TrieNode* node = root;
// 遍歷單詞中的每個字符
for (int i = 0; i < strlen(word); i++) {
char c = word[i];
// 如果當(dāng)前字符對應(yīng)的子節(jié)點(diǎn)為空,則創(chuàng)建一個新的子節(jié)點(diǎn)
if (node->children[c - 'a'] == NULL) {
node->children[c - 'a'] = (struct TrieNode*)calloc(1, sizeof(struct TrieNode));
}
// 移動到下一個子節(jié)點(diǎn)
node = node->children[c - 'a'];
}
// 標(biāo)記當(dāng)前節(jié)點(diǎn)為一個單詞的結(jié)束
node->isWord = 1;
}
int main() {
root = (struct TrieNode*)calloc(1, sizeof(struct TrieNode));
// 讀取輸入的句子,并將其轉(zhuǎn)換為小寫
char sentence[1000];
fgets(sentence, 1000, stdin);
for (int i = 0; i < strlen(sentence); i++) {
sentence[i] = tolower(sentence[i]);
}
// 讀取輸入的字典,字典中的單詞以逗號分隔
char dictionary[1000];
fgets(dictionary, 1000, stdin);
char* word = strtok(dictionary, ",");
while (word != NULL) {
insert(word);
word = strtok(NULL, ",");
}
char result[1000] = "";
int i = 0;
// 遍歷句子中的每個字符
while (i < strlen(sentence)) {
// 如果當(dāng)前字符不是字母,則直接將其添加到結(jié)果中
if (!isalpha(sentence[i])) {
strncat(result, &sentence[i], 1);
i++;
continue;
}
int j = strlen(sentence);
// 從句子的末尾開始,尋找以 i 為起點(diǎn)的最長的在字典中存在的單詞
while (j > i) {
struct TrieNode* node = root;
int isWord = 1;
for (int k = i; k < j; k++) {
// 如果當(dāng)前字符不是字母,或者在 Trie 中不存在對應(yīng)的子節(jié)點(diǎn),則說明當(dāng)前的字符串不是一個單詞
if (!isalpha(sentence[k]) || node->children[sentence[k] - 'a'] == NULL) {
isWord = 0;
break;
}
// 移動到下一個子節(jié)點(diǎn)
node = node->children[sentence[k] - 'a'];
}
// 如果找到了一個單詞,則結(jié)束循環(huán)
if (isWord && node->isWord) {
break;
}
// 如果沒有找到單詞,則縮短當(dāng)前的字符串
j--;
}
// 如果沒有找到單詞,則將當(dāng)前字符作為一個單獨(dú)的單詞添加到結(jié)果中
if (j == i) {
strncat(result, &sentence[i], 1);
i++;
} else {
// 如果找到了單詞,則將該單詞添加到結(jié)果中
char temp[100];
strncpy(temp, &sentence[i], j - i);
temp[j - i] = '\0';
strcat(result, temp);
i = j;
}
strcat(result, ",");
}
// 輸出結(jié)果,單詞之間以逗號分隔
printf("%s\n", result);
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
編程精選網(wǎng)(www.codehuber.com),程序員的終身學(xué)習(xí)網(wǎng)站已上線!
如果這篇【文章】有幫助到你,希望可以給【JavaGPT】點(diǎn)個贊??,創(chuàng)作不易,如果有對【后端技術(shù)】、【前端領(lǐng)域】感興趣的小可愛,也歡迎關(guān)注?????? 【JavaGPT】??????,我將會給你帶來巨大的【收獲與驚喜】??????!
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布!