Paper: Time Mapping with Hypergraphs

ACL ID P98-1008
Title Time Mapping with Hypergraphs
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1998

Word graphs are able to represent a large num- ber of different utterance hypotheses in a very compact manner. However, usually they con- tain a huge amount of redundancy in terms of word hypotheses that cover almost identi- cal intervals in time. We address this problem by introducing hypergraphs for speech process- ing. Hypergraphs can be classified as an ex- tension to word graphs and charts, their edges possibly having several start and end vertices. By converting ordinary word graphs to hyper- graphs one can reduce the number of edges considerably. We define hypergraphs formally, present an algorithm to convert word graphs into hypergraphs and state consistency proper- ties for edges and their combination. Finally, we present some empirical results concerning graph size and parsing ef...