The present invention relates to an information processing apparatus, an information processing method, a program, and a data structure for processing a stream including a base stream and extension streams at a plurality of levels. A transmitter encodes an audio stream into a base stream BS and first to n-th extension streams Ext1 to ExtN. The transmitter refers to tables 90 and 91, generates TS packets 92 and 93-1 to 93-n having PIDs for the corresponding types of streams and the TS packets 90 and 91 of the tables, and outputs the generated TS packets to a receiver. The receiver refers to the TS packets 90 and 91 of the tables and determines the type(s) of stream(s) that it can process. The receiver selects the TS packets having the PID(s) associated with the stream(s) that it can process and decodes the TS packets. The present invention is applicable to a transmitter and a receiver that perform encoding and decoding.