# -*- coding: utf-8 -*-
"""Viterbi 解码算法。

按 ARCHITECTURE.md Phase 3 拆分建议，从 ``common/Utils.py`` 迁出。
类型：CORE（模型推理后处理，人工主导）。

原位置：``common/Utils.py`` 第 129-157 行的 ``viterbi_decode``。
``common/Utils.py`` 仍 re-export ``viterbi_decode``，老 import 不受影响。

说明：
    ARCHITECTURE.md 提到 ``decode``、``viterbi_decode``。``common/Utils.py``
    中只有 ``viterbi_decode``；名为 ``decode`` 的函数分散在 ``foolnltk/``、
    ``product/``、``complaint/`` 等模块中，不属于 Utils.py 拆分范围。
    本文件只迁 ``viterbi_decode``。
"""
from __future__ import absolute_import

import numpy as np

__all__ = ["viterbi_decode"]


def viterbi_decode(score, transition_params):
    """Decode the highest scoring sequence of tags outside of TensorFlow.

    This should only be used at test time.

    Args:
      score: A [seq_len, num_tags] matrix of unary potentials.
      transition_params: A [num_tags, num_tags] matrix of binary potentials.

    Returns:
      viterbi: A [seq_len] list of integers containing the highest scoring tag
          indices.
      viterbi_score: A float containing the score for the Viterbi sequence.
    """
    trellis = np.zeros_like(score)
    backpointers = np.zeros_like(score, dtype=np.int32)
    trellis[0] = score[0]

    for t in range(1, score.shape[0]):
        v = np.expand_dims(trellis[t - 1], 1) + transition_params
        trellis[t] = score[t] + np.max(v, 0)
        backpointers[t] = np.argmax(v, 0)

    viterbi = [np.argmax(trellis[-1])]
    for bp in reversed(backpointers[1:]):
        viterbi.append(bp[viterbi[-1]])
    viterbi.reverse()

    viterbi_score = np.max(trellis[-1])
    return viterbi, viterbi_score