All you really have to do is store the exceptions - you're not going to rate transitions that you're satisfied with.

Let's imagine that you can rate a transition as either very good, good, bad or very bad. Since all FIDs have their lower bit cleared (i.e. they're even), all you have to store for each transition is two sixteen-bit numbers - four bytes for every transition stored. The low order bit of each number encodes the transition rating, and is XORed out to give the FID. When you read the table in you store it as a hash of hashes keyed on the 'outgoing' song.

Simple, really...

Save the whales. Feed the hungry. Free the mallocs.