Methods and apparatus are disclosed for identifying media and, more particularly, to methods and apparatus for decoding identifiers after broadcast. An example method includes a portion of an identifying code from a media signal, determine a partition of the look-up table based on the portion of the identifying code wherein the partition of the look-up table includes reference signatures associated with the portion of the identifying code, and identify the media signal by comparing a signature extracted from the media signal to reference signatures in the partition of the look-up table.