The invention provides apparatus and methods for embedding and recovering watermarking information based on host-matching codes. A code selector provides codes to be embedded in the host signal. The code selector associates distinct input data strings to be embedded into the host signal with distinct code sets. Codes from the associated code sets are selected to represent the input data strings based on an analysis of the host signal (i.e. "host-matching"). The code selector may associate the distinct input data strings with distinct code sets based on a predefined mapping. An embedder embeds the codes into the host signal to provide a watermarked signal. An extractor at a decoder extracts the embedded codes from the watermarked signal. A code interpreter interprets the codes to recover the data represented thereby. The interpreter may perform a many-to-one mapping of an extracted code to the associated data string.