Piero Cavina <p.cavina@xxxxxxxxxxxxx> wrote:
>I'd like to know more details about the comparison algorithm.
It's something like the LZW-algorithm that is/was used in file-
compressors (ZIP, RAR, ARJ...). First i'm doing an RLE compression
on both files that i want to compare, this eliminates long
sequences of the same byte, because those could give wrong results.
The main part is the dictionary based compression. First i'm
building a dictionary for file A. This means all byte sequences are
sorted into a binary search tree. Then i'll try to find matching
sequences in this tree for file B. The more sequences i need, the
lower is the identity. Then i'm doing the same thing for file B vs.
file A and compute the average.
Example:
You have two files which only differ by one byte.
- after RLE compression both files have a size of 4000 bytes.
- we get three sequences (one before, one after the different byte
and the different byte itself). Each sequence counts 2, except
those that are only one byte long, which count 1. This gives a
total of 5. Then we subract 2, because identical files consist of
exactly one sequence, and we get 3.
- the result is computed: (1-3/4000)*100 = 99.925% (my program
would display 99 because i'm truncating the results)
It's a very simple approach, but the results are quite good.
It's interseting that Pac Man and Brick-Kick match that much, i
guess they used the same (flickering) routine to display the
ghost/penguins. Maybe it's (nearly) the same kernel.
Btw: Which game was released first? If it was Brick-Kick, that
would explain, how it was possible to finish Pac Man in six weeks,
(and why it became that bad).
>And I didn't know that so many PAL carts had been dumped. It would
be
>interesting to understand which are the differences with the NTSC
dumps.
You can find those dumps at:
http://www.geocities.com/TimesSquare/Adventure/5869
Thomas
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
