Python实现从字符串末端匹配拆分后缀 避免错误拆分词根

问题背景 #

需求是根据给定的后缀列表，将输入句子里的单词按后缀拆分，避免词根中与后缀相同的字符被误拆分。比如internationally预期拆分结果为interna _tion _al _ly，但现有直接替换的代码会匹配到单词中间的er，输出错误的int _erna _tion _al _ly。

现有代码缺陷 #

现有代码逻辑为遍历后缀列表做全局字符串替换，这种方式会匹配单词任意位置的字符，完全没有区分匹配的内容是不是后缀，才会出现误拆分问题。

sentence = input()
suffixes = ["acy", "ance", "ence", "dom", "er", "or", "ism", "ist",
         "ty", "ment", "ness", "ship", "sion", "tion", "ate",
        "en", "fy", "ize", "able", "ible", "al",
        "esque", "ful", "ic", "ous", "ish", "ive",
        "less", "ed", "ing", "ly", "ward", "wise"]

for x in suffixes:
    y = " _" + x
    sentence = sentence.replace(x, y)

实现思路 #

按照从后往前倒序匹配的逻辑，步骤如下：

• 先把输入句子按空格拆成单个单词，逐个处理
• 针对单个单词，从末尾开始匹配：
  1. 提前计算所有后缀的最大长度，每次匹配最多取对应长度的字符，避免无效判断
  2. 从当前单词的剩余长度开始，优先尝试最长的后缀匹配（比如先试最长4位的后缀，不行再试3位、2位、1位），避免短后缀先匹配导致长后缀被截断
  3. 匹配到后缀就把后缀加上_前缀存储，然后把单词去掉该后缀，继续往前匹配
  4. 直到剩余单词部分没有匹配的后缀为止，把剩下的词根和所有匹配到的后缀倒序拼接，就是拆分后的单词
• 最后把所有处理完成的单词用空格拼回句子即可

可运行实现代码 #

# 预处理后缀为集合提升查找效率，同时统计最长后缀长度
suffixes = ["acy", "ance", "ence", "dom", "er", "or", "ism", "ist",
            "ty", "ment", "ness", "ship", "sion", "tion", "ate",
            "en", "fy", "ize", "able", "ible", "al",
            "esque", "ful", "ic", "ous", "ish", "ive",
            "less", "ed", "ing", "ly", "ward", "wise"]
suffix_set = set(suffixes)
max_suffix_len = max(len(s) for s in suffixes)

def split_word(word):
    parts = []
    current = word
    while current:
        # 匹配长度不超过最长后缀长度，也不超过当前剩余单词长度
        check_len = min(max_suffix_len, len(current))
        matched = False
        # 从最长到最短尝试匹配后缀
        for l in range(check_len, 0, -1):
            suffix_candidate = current[-l:]
            if suffix_candidate in suffix_set:
                parts.append(f"_{suffix_candidate}")
                current = current[:-l]
                matched = True
                break
        # 无匹配后缀时剩余部分就是词根，结束循环
        if not matched:
            break
    # 词根在前，后缀按顺序拼接
    return current + " " + " ".join(reversed(parts))

# 整句处理逻辑
sentence = input()
words = sentence.split()
processed_words = [split_word(word) for word in words]
result = " ".join(processed_words)
print(result)

测试效果 #

输入internationally，输出为预期的interna _tion _al _ly，不会再误匹配单词中间的er字符。

内容的提问来源于stack exchange，提问作者rereborn