Thanks for the tip, facelessuser, that is really cool.
I wanted this for a powershell script of mine, so implemented it as a c# powershell module. It should be simple enough to adapt to another project. There is a class with the fuzzy logic I described below (with one change), a WPF user control that tries to emulate ST2 (to me at least), a WPF dialog that will host the control, and one poweshell cmdlet.https://bitbucket.org/dwarburton/fuzzyselector
the one change i made to the algorithm from my earlier post was to increase the cost for spaces between characters after each match. So after the first character is matched then the score increases 2x for each place the pointer moves and 3x after the second match and so on. This means the algorithm will prefer strings that match characters in clusters over those where the matches are spread about, or at least that is the idea.
I haven't thought of a good way to implement choice memoization, but I would like to. Persistent storage would be ideal but that ties it to a concrete implementation a little bit.