from collections import defaultdict ''' 最大匹配算法 Maximum Match { 正向最大匹配, 逆向最大匹配, 双向最大匹配; 分词算法设计中的几个基本原则： 1、颗粒度越大越好：用于进行语义分析的文本分词，要求分词结果的颗粒度越大， 即单词的字数越多，所能表示的含义越确切，如：“公安局长”可以分为“公安 局长”、“公安局 长”、“公安局长” 都算对，但是要用于语义分析，则“公安局长”的分词结果最好（当然前提是所使用的词典中有这个词） 2、切分结果中非词典词越少越好，单字字典词数越少越好， 这里的“非词典词”就是不包含在词典中的单字，而“单字字典词”指的是可以独立运用的单字， 如“的”、“了”、“和”、“你”、“我”、“他”。 例如：“技术和服务”，可以分为“技术 和服 务”以及“技术 和 服务”， 因为“务”字无法独立成词（即词典中没有），而“和”字可以单独成词（词典中要包含）， 因此“技术 和服 务”有1个非词典词，而“技术 和 服务”有0个非词典词，因此选用后者。 3、总体词数越少越好，在相同字数的情况下，总词数越少， 说明语义单元越少，那么相对的单个语义单元的权重会越大，因此准确性会越高。 } ''' # 加载词典 def load_dict(path): word_dict = set()#创建一个去重集合 with open(path, 'r',encoding='UTF-8') as f: for line in f: word_dict.add(line.strip())#Python strip() 方法用于移除字符串头尾指定的字符（默认为空格或换行符）或字符序列。注意：该方法只能删除开头或是结尾的字符，不能删除中间部分的字符。 return word_dict # 正向最大匹配算法 # 返回list[tuple(word, len)]的形式, tuple[0]为词,tuple[1]为词的长度，当长度为0时代表该词为非词典词 def MM(sentence, max_len, word_dict): if not sentence or sentence is None: raise Exception("sentence can not be empty or None")#句子不能为空 #如果引发Exception异常，后面的代码将不能执行 result = [] i = 0 while i < len(sentence): end = i + max_len if i + max_len < len(sentence) else len(sentence)#一行表达式，真值放在if之前 # if i + max_len < len(sentence): # end = i + max_len # else: # end = len(sentence) temp = sentence[i] index = i for j in range(i + 1, end + 1): if sentence[i:j] in word_dict:#词典分割 temp = sentence[i:j] index = j if index == i: result.append((temp, 0)) i += 1 else: result.append((temp, len(temp))) i = index return result # 逆向匹配算法 # 返回list[tuple(word, len)]的形式, tuple[0]为词,tuple[1]为词的长度，当长度为0时代表该词为非词典词 def RMM(sentence, max_len, word_dict): if not sentence or sentence is None: raise Exception("sentence can not be empty or None") result = [] i = len(sentence) - 1 while i >= 0: start = i - max_len + 1 if i - max_len + 1 > 0 else 0 temp = sentence[i] index = i for j in range(start, i + 1): if sentence[j:i+1] in word_dict: temp = sentence[j:i+1] index = j - 1 break if index == i: result.append((temp, 0)) i -= 1 else: result.append((temp, len(temp))) i = index result.reverse() return result # 双向最大匹配 # 根据大颗粒度词越多越好，非词典词和单字词越少越好原则 def BMM(sentence, max_len, word_dict): if not sentence or sentence is None: raise Exception("sentence can not be empty or None") foward_result = MM(sentence, max_len, word_dict) backward_result = RMM(sentence, max_len, word_dict) def count_result(result): counter = defaultdict(int) for r in result: if r[1] == 0: counter['OOV'] += 1#非词典单词 # print(counter) elif r[1] == 1: counter['single'] += 1#单字词 #print(counter) else: counter['multi'] += r[1]#多字词的字数 # print(counter) return counter['multi'] - counter['OOV'] - counter['single'] print(counter) foward_count = count_result(foward_result) backward_count = count_result(backward_result) if foward_count > backward_count: return foward_result else: return backward_result path = './data/dict.txt' max_len = 3#最长的词为 中华人民共和国 共7个字 word_dict = load_dict(path) result = MM('我们在野生动物园玩。', max_len, word_dict) print(result) result = RMM('我们在野生动物园玩。', max_len, word_dict) print(result) result = BMM('我们在野生动物园玩', max_len, word_dict) print(result)
一起学NLP，练着玩玩！