Searcheable BTree

Sebastian Sastre ssastre at seaswork.com.ar
Thu Sep 16 00:42:52 UTC 2004


Avi I've loaded the 29 version of Btree. When the test ran it fails
because TernarySearchTree class is not in the image. 

Then I've downloaded and installed the sources from the path of the SM:

Collections-TST-avi.3.mcz.zip

And it seems to be OK

Regards,

Sebastián Sastre
ssastre at seaswork.com.ar
www.seaswork.com.ar


> -----Mensaje original-----
> De: squeak-dev-bounces at lists.squeakfoundation.org 
> [mailto:squeak-dev-bounces at lists.squeakfoundation.org] En 
> nombre de Avi Bryant
> Enviado el: Miércoles, 15 de Septiembre de 2004 17:52
> Para: The general-purpose Squeak developers list
> Asunto: Re: Searcheable BTree
> 
> 
> 
> On Sep 15, 2004, at 7:21 PM, Sebastian Sastre wrote:
> 
> > I was reading about tries. I think the tries are pretty 
> much like we 
> > need but the implementation is not trivial enough to 
> develop it now. 
> > Perhaps at the long run. Anyway I think the IndexedCollection could 
> > help a lot by now.
> >
> > Please let me know I you has the range key selection of the BTree.
> 
> Well, I didn't touch BTree today, but I did release to SM a 
> new version 
> of the BTree package: it now includes a TernarySearchTree (class 
> TSTree), which strikes a nice balance between Tries and BTrees.  From 
> the reading I've done, it's likely the best data structure to use 
> whenever you have string keys stored in an OODB.  As well as 
> the usual 
> #at: and #do:, it has #matchesForPrefix: (and #matchesForPrefix:do:), 
> as well as #matchesForString:distance: and 
> #matchesForString:distance:do:.  These last two are 
> interesting - they 
> give you the values for any keys within a specified Levenshtein 
> distance (adds/removes/modifies of chars) of the provided 
> string.  So, 
> for example,
> 
> words matchesForString: 'squeak' distance: 2
> 
> might give the values for the keys 'squeaker' and 'squawk', and
> 
> words matchesForString: 'squeak' distance: 1
> 
> would give the values for 'squeal' and 'squeaky'.
> 
> The basics are there, but feel free to fill out any further protocol 
> you need.  For example, the article on Ternary Search Trees below 
> describes implementing a pattern-matching search, where you can leave 
> some characters as wildcards:
> 
http://home.od.ua/~relayer/algo/data/tern/lead.htm

It may also be useful to have some keysAndValues variants of the 
methods which I've implemented as values-only.

Avi


---
Incoming mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.760 / Virus Database: 509 - Release Date: 10/09/2004
 

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.760 / Virus Database: 509 - Release Date: 10/09/2004
 




More information about the Squeak-dev mailing list