Challenge: compress co-occuring columns into cartesian product

Question

This challenge is inspired by a problem I encountered recently out in the real-world, though ultimately I cheated and found a workaround.

Challenge

The input is a space-separated table of characters (each line is a row, and every line will have the same number of columns). Your challenge is to group together co-occurring column values and output a 'compressed' table, and there may be duplicate rows. Let's look at an example:

input:

A X I
B X I
A Y I
B X I
B Y I

output:

AB XY I

The output is parsed as the cartesian product between each column:

AB XY = A X, B X, A Y, B Y

The union of cartesian products of columns in each output row must exactly match the set of all unique input rows. In other words, no skipping input rows and no specifying input rows that don't exist!

For further exampling, note that if the third column contained anything other than I, this would be harder to compress:

input:

A X I
B Y I
A Y $
B X I
B Y I

output:

A X I
A Y $
B XY I

Rules

• no non-standard libraries or calls to high-level compression functions. The spirit of the question is to write the algorithm yourself!
• output must be in the same format as inputs (zipping your output files is cheating)
• no hard-coding the answers of each test file. Your program needs to be able to handle arbitrary (correct) inputs.

Scoring (lowest wins)

• Size of your program in bytes (you may count the name of the input as a single byte)
• Plus the size (in bytes) of all of your output files on the given tests.
• -10% bonus if you have the fastest program (as it runs on my machine). Speed will be measured as the average time on 10 randomly generated test cases using generate.py 6 8 4 6 5 (the same 10 files for each program of course)

Test Files

These files are generated with this python script. The answer keys aren't guaranteed to be the minimum compression - you may be able to do better!

• Input 1, Answer Key 1, generated with python generate.py 5 10 4 6 5
• Input 2, Answer Key 2, python generator.py 7 6 2 4 6
• Input 3, Answer Key 3, ...edit: the numbers here were wrong

Answer 1

I'll start things off with the simplest possible answer.. According to my own specifications, the input file qualifies as a 'compression' of itself (albeit not a very efficient one).

Python: 22+3359+183735+239 with 10% bonus = 168619.5

print open('testfile').read()