Watermark embedding and extraction method and apparatus in compressed streams

A method of extracting a watermark bit-sequence from a data stream of symbols compressed using a dictionary-based compression scheme with variable length indices, comprising:

• identifying the divisions for a non-watermark value range, a zero-bit watermark value range and a one-bit watermark value range within a set of m-bit index values;
• receiving an input index value potentially having an embedded watermark value;
• classifying the input index value as a member of one of the divisions within the set of m-bit index values;
• setting a next bit of the watermark bit-sequence to a zero value when the input index value is in the zero-bit watermark value range;
• and
• setting a next bit of the watermark bit-sequence to a one value when the input index value is in the one-bit watermark value range.

A computer program product for embedding a watermark bit-sequence in a data stream of symbols compressed using dictionary-based compression scheme with variable length indices, tangibly stored on a computer-readable medium, comprising instructions operable to cause a programmable processor to:

• receive a request to transmit an index value from a set of m-bit index values used to compress one or more symbols in the data stream;
• identify divisions in the set of m-bit index values including a non-watermark value range, a zero-bit watermark value range and a one-bit watermark value range;
• determine a watermark bit value corresponding to the watermark bit sequence as either a zero-bit value or a one-bit value;
• transmit the index value in the one-bit watermark value range when the watermark bit value is determined to be a one-bit value;
• and
• transmit the index value in the zero-bit watermark value range when the watermark bit value is determined to be a zero-bit value.

A computer program product for extracting a watermark bit-sequence from a data stream of symbols compressed using a dictionary-based compression scheme with variable length indices, tangibly stored on a computer-readable medium, comprising instructions operable to cause a programmable processor to:

• identify the divisions for a non-watermark value range, a zero-bit watermark value range and a one-bit watermark value range within a set of m-bit index values;
• receive an input index value potentially having an embedded watermark value;
• classify the input index value as a member of one of the divisions within the set of m-bit index values;
• set a next bit of the watermark bit-sequence to a zero value when the input index value is in the zero-bit watermark value range;
• and
• set a next bit of the watermark bit-sequence to a one value when the input index value is in the one-bit watermark value range.

An apparatus for embedding a watermark bit-sequence in a data stream of symbols compressed using dictionary-based compression scheme with variable length indices, comprising:

• means for receiving a request to transmit an index value from a set of m-bit index values used to compress one or more symbols in the data stream;
• means for identifying divisions in the set of m-bit index values including a non-watermark value range, a zero-bit watermark value range and a one-bit watermark value range;
• means for determining a watermark bit value corresponding to the watermark bit sequence as either a zero-bit value or a one-bit value;
• means for transmitting the index value in the one-bit watermark value range when the watermark bit value is determined to be a one-bit value;
• and
• means for transmitting the index value in the zero-bit watermark value range when the watermark bit value is determined to be a zero-bit value.

An apparatus for extracting a watermark bit-sequence from a data stream of symbols compressed using a dictionary-based compression scheme with variable length indices, comprising:

• means for identifying the divisions for a non-watermark value range, a zero-bit watermark value range and a one-bit watermark value range within a set of m-bit index values;
• means for receiving an input index value potentially having an embedded watermark value;
• means for classifying the input index value as a member of one of the divisions within the set of m-bit index values;
• means for setting a next bit of the watermark bit-sequence to a zero value when the input index value is in the zero-bit watermark value range;
• and
• means for setting a next bit of the watermark bit-sequence to a one value when the input index value is in the one-bit watermark value range.