Current token Next token Output Added to Dictionary Null TO TO BE TO TO BE= < 1 > BE OR BE BE OR= < 2 > OR NOT OR OR NOT= < 3 > NOT TO NOT NOT TO= < 4 > TO BE OR < 1 > TO BE OR= < 5 > OR NOT TO < 3 > OR NOT TO= < 6 > TO BE OR WHAT < 5 > TO BE OR WHAT= < 7 > WHAT ♯ WHAT Table 1: LZW encoding of the tokens composing the string ”TO BE OR NOT TO BE OR NOT TO BE OR WHAT”. The compressor tries to substitute pattern codes referring to sequences of words which occurred previously in the text. FCD ( x,y ) = | D ( x ) | − ∩ ( D ( x ) ,D ( y )) | D ( x ) | (2) 6 process is not of interest for us, as the only thing that will be used is the 102 dictionary. 103 The patterns contained in the dictionary D ( x ) are then sorted in ascend- 104 ing alphabetical order to enable the binary search of each pattern in time 105 O ( logN ), where N is the number of entries in D ( x ). The dictionary is finally 106 stored for future use: this procedure may be carried out offline and has to be 107 performed only once for each data instance. Whenever a string x is checked 108 against a database containing n dictionaries, a dictionary D ( x ) is extracted 109 from x as described and matched against each of the n dictionaries. The 110 FCD between x and an object y represented by D ( y ) is defined as: 111 where | D ( x ) | and | D ( y ) | are the sizes of the relative dictionaries, repre- 112 sented by the number of entries they contain, and ∩ ( D ( x ) ,D ( y )) is the num- 113