203、【数组】NLP分词实现（Python）

题目描述

给定一个词典，比如[“杭州”,“西湖”,“博物馆”,“杭州西湖博物馆”,“我”]​
对于输入的文本进分词：我在杭州的杭州西湖博物馆玩了一天​
分词结果处理为如下形式的字符串: 我\W 在 杭州\W 的 杭州西湖博物馆\W 玩了一天​

对于输入的文本进分词：我在杭州的杭州西湖博物玩了一天​
分词结果处理为如下形式的字符串: 我\W 在 杭州\W 的 杭州\W 西湖\W 博物玩了一天

代码实现

方法一
对字符串分割成列表元素，对每个列表元素设置一个哈希计数。按照按照词从大到小搜寻，每找到一个分词的词，就将对应的哈希位置记录为同一个数。最后，对每个词的最后一个位置增加标志。

s = "我在杭州的杭州西湖博物馆玩了一天"
# s = "我在杭州的杭州西湖博物玩了一天"
record = ["杭州","西湖","博物馆","杭州西湖博物馆","我"]


n = len(s)
tag = [0] * n

record.sort(key=lambda x: len(x), reverse=True)

# 哈希位置记录各个词
tag_num = 1
for key in record:
    for i in range(0, n - len(key)):
        print(s[i:i+len(key)])
        if s[i:i+len(key)] == key and tag[i] == 0:
            for j in range(i, i+len(key)):
                tag[j] = tag_num
            tag_num += 1

# 将词变成数组后，对每个连续对应位置下最后一个位置记录标志
res = list(s)
l, r = 0, 0
while l < n:
    if tag[l] != 0:
        r = l + 1
        while r < n and tag[r] == tag[l]:
            r += 1
        if r <= n:
            res[r - 1] = res[r - 1] + '\W'
        l = r + 1
    else:
        l += 1
        
print(''.join(res))        

方法二
更改列表长度对列表进行合并

s = "我在杭州的杭州西湖博物馆玩了一天"
s = "我在杭州的杭州西湖博物玩了一天"
record = ["杭州","西湖","博物馆","杭州西湖博物馆","我"]
# 将词表从最长的词到最短的词排序
record.sort(reverse=True, key=lambda x: len(x))
record_num = {}
# 对统一长度的单词进行统计
for word in record:
    length = len(word)
    if length in record_num.keys():
        record_num[length].append(word)
    else:
        record_num[length] = [word]
        
# 对字符串进行切分
word_list = list(s)


for k, v in record_num.items():
	# 从词典中最长的词开始遍历
    for word in v:
        for i in range(0, len(s)):
        	# 当区间中子串可组成词典中的词时，合并这一段区间（之前被标记过的一定不会被组成）
            if ''.join(word_list[i:i+len(word)]) == word:
                word_list = word_list[:i] + [''.join(word_list[i:i+len(word)])+'\W'] + word_list[i+len(word):]

print(''.join(word_list))