c0bra has asked for the wisdom of the Perl Monks concerning the following question:

I know this is similar to a question this site had a while ago but it's a little bit different.

I'd like to do fuzzy lookups on keys in a hash. Assume that the hash is lexically sorted.

Is there any way to do it without cycling through the values? I know Tie::Hash::Regex does something similar but it has to grep through the entire hash. Is there any way to maybe use the B-Tree method and find closer matches until you get what you want?

I really have no idea.

Thanks

Replies are listed 'Best First'.
Re: Fuzzy hash key lookups
by Dog and Pony (Priest) on Aug 01, 2002 at 15:17 UTC
    Tie::Hash::Approx might be what you want. :)
    You have moved into a dark place.
    It is pitch black. You are likely to be eaten by a grue.
[reply]
Re: Fuzzy hash key lookups
by Abigail-II (Bishop) on Aug 01, 2002 at 15:21 UTC
    Hashes are not sorted, so your premises of "assume that the hash is lexically sorted" makes as much sense as "assume that the array is Wednesday". At best what you can archieve is to have some sort of datastructure that keeps the keys sorted, and you have a tied hash interface to that datastructure.

    A sorted search tree might be the solution you are looking for, but that depends on what you mean by "fuzzy". Do you want to do a "nearest" query, nearest measured over the way you have sorted your data? In that case, a tree will work. Or do you mean that if you search with "abadabafupla", a result of "abadabaxupla" is wanted because there's only on letter that's different? In that case you need a completely different datastructure.

    Of course, any datastructure whose search queries take a scalar and give a scalar as return can be hidden being a tied hash.

    Abigail

[reply]
      Well a B-Tree is sorted, isn't it?

      And by fuzzy I mean lookups by regexes like in Tie::Hash::Regex. If the lookup matches multiple keys, they're all returned.

      If you search for just "abadabafupla" it should return the data for "abadabafupla" and only "abadabafupla".

[reply]
        A B-Tree isn't a hash, is it?

        Your second line confuses me. If you want to do the same as in Tie::Hash::Regex, why don't you use Tie::Hash::Regex?

        Oh, you want to do it without searching all the keys, and you think that sorting will help? How would you sort if the regex could contain a leading dot?

        Abigail

[reply]
Re: Fuzzy hash key lookups
by sauoq (Abbot) on Aug 01, 2002 at 18:22 UTC
    Is there any way to do it without cycling through the values [of the keys]?

    No. 

    -sauoq
"My two cents aren't worth a dime.";
[reply]

Back to Seekers of Perl Wisdom