Yuling Liu, Xingming Sun, Yongping Liu

ALGORITHM 1: HIDING ALGORITHM

Input: A PPT document T and a message to be hidden C`.

Output: A stego-document T`.

Steps:

(1)	Preprocess the body text of the PPT document T to extract a dictionary table D and a sentence template database S = {s1, s2…, sn}, where ss is a sentence template.
(2)	Partition the dictionary table D into 4 small tables D1, D2, D3, D4 according to the set of parts of speech P = {n, v, a, d} and construct a Huffman tree Hx for Dx` = 1, 2, 3, as follows.
(a)	Create a leaf node ni for each word in Dx and assign the occurrences of each word oi to the node ni.
(b)	Initialize a set Q to contain all of the leaf nodes.
(c)	Find in Q node ni and nj with the lowest occurrences and then remove node ni and nj from Q.
(d)	Create a new node nij with the occurrences oij = oi+oj and assign ni as its left child and nj as its right child.
(e)	If Q is empty, then tree Hx has been constructed and take nij as its root; else, add node nij to Q and go to Step 2c).
(3)	Randomly select a sentence template ss ∈ S.
(4)	For each tt ∈ S, substitute word ww for part-of-speech tt to generate a new sentence ss, where word ww is determined as follows:
(a)	Starting from the root of tree Hx, traverse Hx to its left child if the current bit of C` is 0 or to its right child.
(b)	Go to the next bit of C` and continue traversing in a similar way until ww is reached.
(5)	Repeat steps 3) through 4) until the end of C`L+m.
(6)	Write the generated sentences s1` s2` into the note pages of T to yield a stego-document T`.