• Post Reply Bookmark Topic Watch Topic
  • New Topic

Storing a Zillion Strings  RSS feed

 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anybody recall a post a few weeks back about needing to store millions of strings in memory and get to them quickly? I knew I'd read something useful in the past, but it took this long to bubble up in my brain. See Ternary Trees If that was your post way back then, lemme know if this helps. Thanks!
 
Ivan Jouikov
Ranch Hand
Posts: 269
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Whats wrong with BS tree?
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
TST stores the letters of a string in individual nodes. If you store alphabet and alphabetize the 2nd word adds 3 nodes with one letter instead of a single node with 10 letters. If you store enough plain text, the overlap starts to be significant. The search is claimed to be quick, and it can easily find all strings matching a prefix, and strings close to a key string. The article shows how to use it as a tiny in-memory database.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stan - are you thinking of this post? Seems like TST would be a good fit - thanks.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jim, that was it - thanks for making the connection!
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!