wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> wildcard searching in dictionary
        
(Message started by: cuckoo on Sep 4^th, 2007, 2:41am)

Title: wildcard searching in dictionary
Post by cuckoo on Sep 4^th, 2007, 2:41am

I am doing research on string processing and come up the following problem:

D is fixed dictionary of words, you can preprocessing it to build some data structure as you like.
Now in the query phase, you are given a wildcard pattern, and you are asked to return all words in D that match with the pattern.

For example, if the wildcard pattern is "h**o", then you must return all words in D begin with 'h' and end with 'o'. "hello" is such a candidate.

Generally, you should build "index" on dictionary, not on the query pattern, since the latter changing from time to time.

Looking forward an elegant solution! ;D

Title: Re: wildcard searching in dictionary
Post by sk on Sep 4^th, 2007, 8:16am

use a ternary search tree

http://www.ddj.com/showArticle.jhtml?documentID=ddj9804a&pgno=4

u can recursively look for any reg ex. Will work out the the details and post it.