中文分词算法（正向最大匹配算法（FMM）、逆向最大匹配算法（RMM）和双向最大匹配算法（BMM））

1. 正向最大匹配算法（FMM）

算法原理

• 从左向右扫描： 算法从句子的最左端开始，依次向右扫描。
• 贪心策略： 在每个位置上，取词典中最长的可能匹配串（即“最大匹配”），如果匹配成功则作为一个词，否则逐步缩短匹配长度。
• 依赖词典： 分词效果依赖于词典中词条的完整性及准确性。

算法步骤

1. 确定窗口大小： 根据词典中最长词的长度来设定一个最大窗口长度。

   在实际应用中，最大窗口长度的设定既可以根据词典中最长词的长度来确定，也可以根据经验取一个常用的固定值。具体解释如下：

   • 词典覆盖与经验值：
     虽然在以下示例词典中，最长的词是 "研究生"（3 个字符），但在实际中文分词中，很多系统会预先设置一个固定的最大窗口长度（例如 4 或 5），这是因为大多数中文词语的长度通常不会超过这个范围。设定为 4 可以兼顾词典中可能遗漏的较长词以及提高算法的鲁棒性。
   • 预防词典不全：
     如果词典并不完全或者在某些应用场景中可能遇到超过词典中最长词的词语，使用比词典中最长词稍大的窗口长度可以确保算法在匹配时能覆盖所有可能的情况。
   • 常见设置：
     在很多中文分词工具中（例如 Jieba 分词），最大窗口长度通常设置为 4 或 5，因为经过统计，大部分中文词汇的长度都落在这个区间内。这种设置在实践中已经证明是一个平衡效率和准确性的合理选择。

   因此，示例中选择最大窗口长度为 4，主要是基于对中文词语长度分布的经验以及预防词典不全的考虑，即使在该词典中最长词只有 3 个字符，设定 4 也更具有普适性和鲁棒性。

2. 取子串： 从句子起始位置开始，取最大长度的子串进行匹配。

3. 匹配判断：

   • 若子串在词典中存在，则将其作为一个词。
   • 若不在词典中，则缩短子串长度（通常递减1个字符）继续查找。

4. 移动指针： 将匹配到的词从句子中去除，指针移动到剩余字符串的开头，重复上述过程直到整个句子处理完毕。

示例

假设词典中包含词条：
"研究", "研究生", "生命", "命", "的", "起源"

对于句子 "研究生命的起源"，正向最大匹配的过程如下：

1. 从左侧开始，设定窗口最大长度为4，取

   "研究生命"
   

   检查词典：

   • "研究生命" 不在词典中，缩短为 "研究生" → 匹配成功。

2. 将

   "研究生"
   

   从句子中去除，剩余

   "命的起源"
   

   • 从 "命的起源" 中，先取 "命的起源" 检查，不匹配，缩短为 "命的起" 依次缩减，最终匹配到 "命"（或如果词典中存在其他匹配词，可根据词典情况决定）。

3. 剩余部分继续分词，得到 "的" 和 "起源"。

最终分词结果可能为：
研究生 / 命 / 的 / 起源

注意： 这种贪心算法有时会因词典词条的划分不同产生歧义。

# 正向最大匹配
def pre_forward_max_match(sentence,s_dict):
    max_match_len = max(len(word) for word in s_dict)   #计算最大匹配字符数
    forword_list = [] #存放结果
    while len(sentence) >= 1:
        max_word_len = max_match_len
        while max_word_len > 1:
            # 如果该字符串存在于字典中
            if sentence[:max_word_len] in s_dict:
                # 将切分结果加入到结果列表中
                forword_list.append(sentence[:max_word_len])
                sentence = sentence[max_word_len:] #将句子已经切分的部分去掉
                break
            # 如果该字符串不存在于字典中，最大匹配字符数减一
            max_word_len -= 1
        if max_word_len == 1:
            forword_list.append(sentence[:1])
            sentence = sentence[1:]
    return forword_list

优缺点

• 优点：
  • 实现简单、计算效率高。
  • 适用于大规模文本的初步分词。
• 缺点：
  • 对于多义或重叠词语容易产生歧义（如“研究生”与“研究”之间的选择）。
  • 完全依赖词典，词典不全时效果较差。

2. 逆向最大匹配算法（RMM）

算法原理

• 从右向左扫描： 与正向匹配相反，逆向最大匹配从句子的最右端开始扫描。
• 贪心策略： 同样使用“最大匹配”的贪心思想，但匹配的方向反过来。
• 解决歧义： 在某些情况下，逆向匹配可以弥补正向匹配带来的分词歧义。

算法步骤

1. 确定窗口大小： 同样根据词典中最长词的长度设定窗口。
2. 取子串： 从句子的最右侧开始，取最大长度的子串。
3. 匹配判断：
   • 若子串存在于词典中，则将其作为一个词。
   • 若不匹配，则缩短子串长度，直至匹配成功或只剩一个字符。
4. 移动指针： 将匹配到的词从句子中去除，指针向左移动，直至整个句子被处理完毕。

示例

对于同一句子 "研究生命的起源"：

1. 从右侧开始，设定窗口最大长度，取

   "的起源"
   

   检查：

   • 如果 "的起源" 不在词典中，缩短为 "起源" → 匹配成功。

2. 剩余

   "研究生命的"
   

   继续从右侧取子串：

   • 可能匹配 "的"，再匹配 "生命" 或 "研究"（具体匹配结果取决于词典）。

3. 最终可能得到结果：
   研究 / 生命 / 的 / 起源

#逆向最大匹配算法
def after_forward_max_match(sentence,s_dict):
    max_match_len = max(len(word) for word in s_dict)   #计算最大匹配字符数
    forword_list = [] #存放结果
    while len(sentence) >= 1:
        max_word_len = max_match_len
        while max_word_len > 1:
            if sentence[-max_word_len:] in s_dict:
                # print(sentence[-max_word_len:])
                forword_list.append(sentence[-max_word_len:])
                
                sentence = sentence[:-max_word_len]
                break
            max_word_len -= 1
        if max_word_len == 1:
            forword_list.append(sentence[-1:])
            sentence = sentence[:-1]
    forword_list = forword_list[::-1]
    return forword_list

优缺点

• 优点：
  • 在某些句子结构中能减少因正向匹配带来的歧义。
  • 有时能更好地识别词典中靠后部分的词。
• 缺点：
  • 同样依赖词典，词典不完善时可能出现错误分词。
  • 部分情况下可能会和正向匹配产生不同的分词结果，增加了后续结果的判断难度。

3. 双向最大匹配算法（BMM）

算法原理

• 结合正向与逆向结果： 同时采用正向最大匹配和逆向最大匹配两种方法，对同一句子分别进行分词。
• 比较两种结果： 根据预设规则对两个分词结果进行比较，选择更优的分词方案。
• 常用比较标准：
  • 分词后词语总数：通常词数较少的方案被认为更合理（因为过度切分会产生过多单字词）。
  • 单字词的数量：如果词数相同，选择单字词较少的结果。
  • 若两者完全一致，则可以直接采用任一结果。

算法步骤

1. 正向分词： 对句子使用 FMM 得到一个分词结果。
2. 逆向分词： 对句子使用 RMM 得到另一个分词结果。
3. 结果比较：
   • 如果两个分词结果的词数不同，选择词数较少的作为最终结果。
   • 如果词数相同，则比较单字词（仅由一个汉字组成）的数量，较少者优先。
   • 如果以上两项仍无法决断，则可以结合其他启发式规则或依靠人工判断。
4. 输出最终结果。

示例

仍以 "研究生命的起源" 为例：

• 正向匹配结果：
  可能为 "研究生" / "命" / "的" / "起源" （词数为4，其中存在一个单字词 "命"）。
• 逆向匹配结果：
  可能为 "研究" / "生命" / "的" / "起源" （词数同样为4，但单字词较少）。
• 比较选择：
  由于两者词数相同，进一步比较单字词数量，逆向匹配方案中的 "研究" 和 "生命"均为多字词，因此选取逆向匹配结果。

为了更直观的看见正向正向最大匹配、逆向最大匹配和双向最大匹配的结果，我这里是直接print()输出的，在实际应用场景中，最好还是之间return输出就好

def two_max_match(sentence, s_dict):
    # 正向最大匹配
    pre_match = pre_forward_max_match(sentence, s_dict)
    print('正向最大匹配分词的结果是',pre_match)
    
    # 逆向最大匹配
    after_match = after_forward_max_match(sentence, s_dict)
    print('逆向最大匹配分词的结果是',after_match)
    
    # 1. 词数少的优先
    if len(pre_match) < len(after_match):
        return print('双向最大匹配分词结果是',pre_match)
    elif len(pre_match) > len(after_match):
        return print('双向最大匹配分词结果是',after_match)

    # 2. 词数相同，单字词少的优先
    forward_count = sum([len(i) == 1 for i in pre_match])
    backward_count = sum([len(i) == 1 for i in after_match])
    if forward_count < backward_count:
        return print('双向最大匹配分词结果是',pre_match)
    else:
        return print('双向最大匹配分词结果是',after_match)

优缺点

• 优点：
  • 能在一定程度上弥补单一方向匹配的不足，降低歧义分词的风险。
  • 综合两种算法的优点，通常能得到更合理的分词结果。
• 缺点：
  • 计算复杂度较高，需要同时运行两种匹配过程。
  • 当两种方法的结果均存在错误时，依然可能产生不理想的分词结果。

4.总应用结果示例

sentence = '研究生命起源'
s_dict = ['研究','研究生','生命','命','的','起源']
result = two_max_match(sentence,s_dict)
result

# 运行结果
正向最大匹配分词的结果是 ['研究生', '命', '起源']
逆向最大匹配分词的结果是 ['研究', '生命', '起源']
双向最大匹配分词结果是 ['研究', '生命', '起源']

5.总结与比较

注意：

• 词典质量： 三种算法都依赖于词典，词典不全或质量较低都会影响分词结果。
• 歧义问题： 分词过程中的歧义问题往往需要结合上下文或引入统计信息、机器学习方法（如 HMM、CRF）来进一步解决。
• 应用场景： 对于实际应用，可以根据需求选择合适的分词策略，或结合多种算法共同使用。