中文分词 - 正向最大匹配

2024-04-30 18:39:30 浏览数 (3)

分词

正向最大匹配 方法一

  • 分词步骤
  1. 收集一个词表
  2. 对于一个待分词的字符串，从前向后寻找最长的，在词表中出现的词，在词边界做切分
  3. 从切分处重复步骤2，直到字符串末尾
  • 实现方式
  1. 找出词表中最大长度词
  2. 从字符串开头开始选取最大词长度的窗口，检查窗口内的词是否在词表中
  3. 如果在词表中，在词边界处进行切分，之后移动到词边界处，重复步骤2
  4. 如果不在词表中，窗口右边界回退一个字符，然后检查窗口词是否在词表中

加载词表，并确定词表中词最大长度

代码语言：javascript复制
# 加载词表，并确定词表中词最大长度
def load_dict(word_dict_path):
  words_dict = {}
  max_word_length = 0
  with open(word_dict_path, encoding="utf8") as f:
    for line in f:
      word = line.strip()
      words_dict[word] = 0
      max_word_length = max(max_word_length, len(word))
  return words_dict, max_word_length

正向最大匹配 - 方法一

代码语言：javascript复制
def forward_max_matching(toCutString, word_dict, max_length):
  words = []    # 保存分词
  while toCutString != "":
    length = min(max_length, len(toCutString))    # 确认待切分字符串长度和最大长度如果待切分词小于最大词长度时
    word = toCutString[:length]
    while word not in word_dict:
      if len(word) == 1:    # 如果词长度是1，那就退出循环
        break
      word = word[:len(word)-1]
    words.append(word)
    toCutString = toCutString(len(word):)
  return words

正向最大匹配 - 利用前缀字典

上面方法虽然可行，但是当字符串长度特别长的时候耗时比较久，性能上有一些缺陷，这时候我们可以利用前缀字典进行优化，提高代码执行效率

  • 实现方式：
  1. 从前向后进行查找
  2. 如果窗口内的词是一个词前缀，则继续扩大窗口
  3. 如果窗口内的词不是一个词前缀，则记录已发现的词，并将窗口移动到词边界

加载前缀字典

代码语言：javascript复制
def load_prefix_dict(path):
  prefix_dict = {}
  with open(path, encoding="utf8") as f:
    for line in f:
      word = line.strip()
      for i in range(1, len(word)):
        if word[:i] not in prefix_dict:
          prefix_dict[word[:i]] = 0    # 0表示这不是词，但是是词前缀
      prefix[word] = 1    # 1表示这是一个词
  return prefix_dict

利用词前缀进行切词

代码语言：javascript复制
def forward_max_matching(tocutstring, prefix_dict):
  if tocutstring == "":
    return []
  words = []    # 放切好的词
  start_index, end_index = 0, 1    # 记录窗口的起始位置
  window = tocutstring[start_index: end_index]    # 从第一个字开始
  find_word = window  # 将第一个字先当作默认词
  while start_index < len(tocutstring):
    # 窗口没有在词典里出现
    if window not in prefix_dict or end_index > len(tocutstring):
      words.append(find_word)    # 证明这个字不是前缀，可以分词
      start_index  = len(find_word)
      end_index = start_index   1
      window = tocutstring[start_index: end_index]    # 更新窗口
      find_word = window
    # 窗口在词典中，而且表示是一个词
    elif prefix_dict[window] == 1:
      find_word = window  # 找了了一个词，但是还要看有没有比他更长的词
      end_index  = 1
      window = string[start_index:end_index]
    # 窗口是一个前缀
    elif prefix_dict[window] == 0:
      end_index  = 1    # 向后错一位继续找
      window = string[start_index:end_index]
  # 最后找到的window如果不在词典里，把单独的字加入切词结果
  if prefix_dict.get(window) != 1:
    words  = list(window)
  else:
    words.append(window)
  return words

利用前缀字典的方法虽然代码稍显复杂，但效率会比第一种方式快很多。

字符串 中文分词 window word 效率

1 人点赞