隐马尔可夫模型（HMM）：字符插入与删除问题的处理方法

Great question—this is a common pain point when first adapting vanilla HMMs for spell correction, since basic HMMs only account for matching or substituting characters, not skipping (deletions) or adding (insertions) them. Let’s break this down, especially for your specific example.

First: Extend the HMM to Support Edit Operations #

Vanilla HMMs where each state maps directly to a character (like your c → a → t setup) can’t handle insertions/deletions out of the box. To fix this, we need to modify the model to include transitions and emissions that represent the three core edit operations (plus matching):

• Match: Transition from state S_i (representing the i-th correct character) to S_{i+1}, emitting the correct character (e.g., S_c → S_a emits a).
• Delete: Transition from S_i to S_{i+1} without emitting any character (an empty/ε emission). This represents skipping the i-th correct character in the observation.
• Insert: Stay in state S_i while emitting an extra character that isn’t part of the correct sequence. This accounts for extra characters in the observation.
• Substitute: Transition from S_i to S_{i+1} while emitting a different character (e.g., S_a → S_t emits x instead of a).

Applying This to Your Example #

Your scenario: Correct state sequence is c → a → t, observation is c → t, and your initial model only has c → a transitions (no c → t). Here’s how to handle the missing a (a deletion):

1. Add a delete transition from the a state to the t state:

   • We don’t need a direct c → t transition. Instead, define a transition from S_a (the state for correct character a) to S_t with an ε emission (no character output).
   • Assign this transition a probability based on how often characters get deleted in your training data (e.g., if short vowels like a are frequently deleted, this probability would be higher).

2. The valid path through the model becomes:

   • Start at S_c → emit c (matches the first observation) → transition to S_a → take the delete transition to S_t (emits nothing, skipping the a in the correct sequence) → emit t (matches the second observation).

This path explains the observation sequence c → t without needing a direct c → t transition in your original model.

For Insertions (Bonus) #

If you had an observation like c → x → a → t (inserted an x after c), you’d handle it by:

• Adding an insert transition that stays in S_c while emitting x (or any other possible character).
• The path would be: S_c emits c → stay in S_c (insert transition) emits x → transition to S_a emits a → transition to S_t emits t.

Key Takeaway #

The core idea is that you don’t need to add direct transitions between non-consecutive correct characters. Instead, you extend the model with ε-emitting delete transitions (for missing characters) and self-loop insert transitions (for extra characters). These transitions are calibrated using training data that includes known spelling errors and their corrections, so the model learns how likely each edit operation is.

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