本题按顺序模拟五个清洗步骤即可。先把每篇文档中的连续空白合并成一个空格,并去掉首尾空格,然后判断长度是否合法;接着扫描规范化后的字符串,把连续的字母数字字符提取成小写单词;之后用哈希集合判断是否精确命中黑名单;再用哈希表统计每个连续三个单词组成的 3-gram,若某个 3-gram 出现次数超过 M,则丢弃;最后把整篇文档的单词序列作为语义指纹,放入哈希集合中去重,只保留第一次出现的文档。最终输出的是规范化后的字符串。
设所有文档总长度为 S,提取出的单词总数为 W。
每篇文档只需要进行常数次线性扫描,3-gram 统计和去重也都是哈希操作,因此总时间复杂度为 O(S + W),可视为 O(S)。
为了防止大语言模型(LLM)在生成时出现“复读机”现象,并确保训练语料的语义纯净,你需要模拟数据清洗引擎,模型给定 N 篇待清洗文档,你需要按顺序执行以下五大清洗规则,只有全部通过的文档,才会被保留并进入最终的训练集。
清洗规则:
第 1 行包含 5 个整数:N,L,R,M,K,分别代表文档数、最小长度、最大长度、3−gram 最大允许出现次数、黑名单词汇数。
第 2 行包含 K 个由空格分隔的黑名单词汇(保证全为小写),如果 K=0,则跳过此行,直接进入到文档内容。 接下来的 N 行,每行包含一篇原始文档(可能包含各种标点、标点和多余空格)。
按顺序输出所有通过清洗的高质量文档,每篇文档占一行。
输入
3 10 100 2 1
spam
Buy cheap SPAM!!!
He is a spammer
He is, A! Spammer.
输出
He is a spammer
说明
第 1 行表示:文档数为 3,最小长度为 10,最大长度为 100,3−gram 最大允许出现次数为 2,黑名单词汇数为 1。
第 2 行表示黑名单词汇为 spam。
文档 1:规范化后为 Buy cheap SPAM!!!,提取单词为 ["buy", "cheap", "spam"],精确命中了黑名单 spam,丢弃。
文档 2:规范化后为 He is a spammer.,单词为 ["he", "is", "a", "spammer"],spammer 不触发 spam 拦截,保留。
文档 3:规范化后为 He is, A! Spammer.,单词为 ["he", "is", "a", "spammer"],单词序列与文档 2 完全相同,触发去重,丢弃。
输入
2 10 200 2 0
a b c a b c a b c
a b c a b c
输出
a b c a b c
说明
第 1 行表示:文档数为 2,最小长度为 10,最大长度为 100,3−gram 最大允许出现次数为 2,黑名单词汇数为 0
黑名单词汇数为 0,所以从第 2 行开始为文档内容
文档 1:3−gram ["a", "b", "c"] 出现了 3 次,> 阈值 2 次,丢弃