You could make it dynamic. So when they type 'Abstrakt Painting' it remembers that it couldn't find anything and then they'll type in the correction. If it finds an entry, associate the first wrong entry with the right entry. You would probably want to give it a weighting of probability as well, that way if it happens multiple times that they type the wrong thing, then the right thing the software has a better sense that they didn't just give up and try something else.
I've always wondered how fuzzy searching works. I expect that there are other better ways of doing it, like finding a percentage of matched letters. You could split the string into an array and then do an array_diff against every possible search in the database. That would take ages though. There's probably some really interesting steps in this process that I don't have the knowledge to consider.