问题定义

给定数组arr，长度T，其中某些arr[i]到arr[j]存在转移概率，将arr分成k组，使得arr的整体分组和最大。 对于arr的每一个子数组arr[i..j]，其分组值定义为 arr[i]到arr[j]的转移概率 arr的分组和是其每一个子数组的分组值之和

问题求解

正向定义

定义数据g[i]为arr[0..i]的最大分组和 在g[j], 0 <= j < i已知的前提下，将 arr[j .. i] 分成一组，则g[i] = g[j] + trans[j, i] ，所以 $$g[i] = max(g[j] + trans(j, i)), 0 \le j < i$$ g[T - 1]即为所求。

反向定义

定义数据g[i]为arr[i..T-1]的最大分组和，其余定义与正向定义类似

说明

jieba/init.py中的Tokenizer.calc与wordseg/ViterbiCWS.py中的ViterbiSearch的实现是等价的，均可实现序列的最大分组，不同点在于

  1. DAG的定义不同 如对于句子"学生会主动完成作业"，
{0: [0, 1, 2], 1: [1], 2: [2, 3], 3: [3, 4], 4: [4], 5: [5, 6], 6: [6], 7: [7, 8], 8: [8]}  # jieba
{0: [0], 1: [0, 1], 2: [0, 2], 3: [3], 4: [3, 4], 5: [5], 6: [5, 6], 7: [7], 8: [7, 8]}  # ViterbiSearch
  1. 用于实现DP的状态定义不同 jieba使用的正向定义，ViterbiSearch使用的是反向定义

代码实现

使用反向定义，实现逻辑与ViterbiSearch一致。 可以尝试提升“学生会”的词频，使得cut能且分出“学生会”。 或者提升 长江大桥 的词频，使得cut能切分出 “长江大桥”

freq = {
    "学生": 400,
    "学生会": 20,
    "完成": 500,
    "作业": 300,
    "主动": 400,
    "学": 10,
    "生": 10,
    "会": 20,
    "主": 50,
    "动": 10,
    "完": 100,
    "成": 55,
    "作": 40,
    "业": 5,
    "大桥": 20,
    "南京": 60,
    "南京市": 30,
    "市长": 40,
    "江大桥": 888,
    "长江大桥": 666,
    "南": 10,
    "京": 40,
    "市": 6,
    "长": 7,
    "江": 50,
    "大": 5,
    "桥": 40,
}

total = 3000


def build_dag(sentence: str) -> dict:
    """
    构建以每个token结尾的有向词图
    如 "学生会主动完成作业" => {0: [0], 1: [0, 1], 2: [0, 2], 3: [3], 4: [3, 4], 5: [5], 6: [5, 6], 7: [7], 8: [7, 8]}
    :param sentence:
    :return:
    """
    n = len(sentence)
    dag = {
        i: [j for j in range(i + 1) if freq.get(sentence[j:i + 1], 0)]
        for i in range(n)
    }
    return dag


def route(sentence: str, dag: dict):
    """
    g[i] = (prob, j)，prob为sentence[0..i]的最大分组和，j为sentence[i]所属的分组起始位置
    g[i].prob = max(g[j] + trans(j, i)), 0 <= j < i
    g[i].j = argmax max(g[j] + trans(j, i)), 0 <= j < i
    :param sentence:
    :param dag:
    :return:
    """
    n = len(sentence)
    g = {-1: (0, 0)}
    logtotal = math.log(total)
    for idx in range(n):
        g[idx] = max(
            (
                g[idx - 1][0] + math.log(freq.get(sentence[x: idx + 1]) or 1) - logtotal,
                x
            )
            for x in dag[idx]
        )
    return g


def cut(sentence: str):
    dag = build_dag(sentence)
    g = route(sentence, dag)

    n = len(sentence)
    segments = deque()
    idx = n - 1
    while idx >= 0:
        prev = g[idx][1]
        segments.appendleft(sentence[prev: idx + 1])
        idx = prev - 1
    return segments


if __name__ == '__main__':
    sents = [
        "学生会主动完成作业",
        "南京市长江大桥"
    ]
    for sent in sents:
        print("%s => %s" % (sent, "/".join(cut(sent))))
    # 学生会主动完成作业 => 学生/会/主动/完成/作业
    # 南京市长江大桥 => 南京/市长/江大桥