Building a Chinese Pinyin Input Method with Hidden Markov Models and Viterbi

Introduction

A simple Chinese pinyin input method was built by training a Hidden Markov Model (HMM) on the Jieba word library and applying the Viterbi algorithm to decode pinyin sequences into Chinese characters.

Principles

Hidden Markov Model (HMM) is a statistical model that describes a Markov process with hidden unknown parameters. In a pinyin input method, the observable parameters are the pinyin strings, while the hidden parameters are the corresponding Chinese characters.

Viterbi Algorithm

The Viterbi algorithm, a dynamic‑programming approach, is used to find the most probable sequence of hidden states (characters) given the observed pinyin sequence.

Model Definition

Three probability matrices—initial, transition, and emission—are stored in SQLite using SQLAlchemy models.

class Transition(BaseModel):
    __tablename__ = 'transition'
    id = Column(Integer, primary_key=True)
    previous = Column(String(1), nullable=False)
    behind = Column(String(1), nullable=False)
    probability = Column(Float, nullable=False)

class Emission(BaseModel):
    __tablename__ = 'emission'
    id = Column(Integer, primary_key=True)
    character = Column(String(1), nullable=False)
    pinyin = Column(String(7), nullable=False)
    probability = Column(Float, nullable=False)

class Starting(BaseModel):
    __tablename__ = 'starting'
    id = Column(Integer, primary_key=True)
    character = Column(String(1), nullable=False)
    probability = Column(Float, nullable=False)

Model Generation

The training script ( train/main.py) computes the three matrices from the Jieba dictionary and writes them into the SQLite database. The initial probability matrix counts characters that appear at the beginning of words; the transition matrix records one‑step character‑to‑character probabilities; the emission matrix records character‑to‑pinyin probabilities (using pypinyin for conversion). Natural‑logarithm scaling is applied to avoid underflow.

Viterbi Implementation

def viterbi(pinyin_list):
    """Viterbi algorithm implementation for the input method"""
    start_char = Emission.join_starting(pinyin_list[0])
    V = {char: prob for char, prob in start_char}
    for i in range(1, len(pinyin_list)):
        pinyin = pinyin_list[i]
        prob_map = {}
        for phrase, prob in V.iteritems():
            character = phrase[-1]
            result = Transition.join_emission(pinyin, character)
            if not result:
                continue
            state, new_prob = result
            prob_map[phrase + state] = new_prob + prob
        if prob_map:
            V = prob_map
        else:
            V = {}
    return V

Results and Issues

Running input_method/viterbi.py displays the decoded Chinese characters for a given pinyin input. However, several problems were observed:

Generating the transition matrix and writing it to the database is slow (≈10 minutes per run).

The emission matrix contains inaccurate pinyin‑character mappings, leading to mismatches.

The training corpus is small, so the input method does not handle long sentences well.