On Tue, Mar 13, 2012 at 6:14 AM, Holger Siegel <[email protected]> wrote:
>
> Am 13.03.2012 um 09:15 schrieb Morten Olsen Lysgaard:
>
>> I'd like to be able to do inexact lookups on the map. Firstly, ignore the 
>> difference between upper lower case, that's easy. But secondly, have a 
>> function:
>>
>> search :: (Num b) => Data.Map.Map String a -> String -> b -> [a]
>>
>> This function is like the normal lookup, but it takes an extra argument b. B 
>> is the allowed character error rate. That is the Levenstein distance divided 
>> on the length. It should return all the strings that has an error rate lower 
>> that b and in a ordered manner, best first.
>
> You could take a trie and extend the lookup functions so that it also returns 
> inexact matches up to a given error rate. That should be quite easy, because 
> the definition of Levenshtein distance is recursive as well as the trie's 
> lookup function.

There are also Burkhard-Keller trees, which are a pretty cool data
structure: http://hackage.haskell.org/package/bktrees-0.3.1

--S.

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to