Efficient pruning algorithm for hidden markov model speech recognition

Abstract

An efficient pruning method reduces central processing unit (CPU) loading during real time speech recognition by instructing the CPU to compare a current state's previously calculated probability score against a predetermined threshold value and to discard hypothesis containing states with probability scores below such threshold. After determining that the current state should be kept, the CPU is directed to locate an available slot in the scoring buffer where information about the current state is then stored. The CPU locates an available slot by comparing the current time-index with the time-index associated with each scoring buffer slot. When they are equal, the slot is considered not available; when the current time-index is greater, the slot is considered available. After the information about the current state is stored, the CPU then sets the current state's backpointer to point at the start state of the current best path if the current states represents a completed model. Regardless of the current state's status, the CPU then associates the current time-index with the time-indices of all the slots along the best path to the current state. The CPU then proceeds to calculate the probability score of the next current state and the method repeats until all states have been completed.