Re: Storing large strings for future equality checks
On Wed, 8 Jun 2011, Abu Yahya wrote:
A small application that I'm making requires me to store very long
strings (>1000 characters) in a database.
So >1000, but by any chance <2000? <4000?
I will need to use these strings later to compare for equality to
incoming strings from another application. I will also want to add some
of the incoming strings to the storage, if they meet certain criteria.
For my application, I get a feeling that storing these strings in my
table will be a waste of space, and will impact performance due to
retrieval and storage times, as well as comparison times.
I assume by 'table' you mean an in-memory hashtable. I wouldn't be so
quick to discount this - how many strings do you have? If you had 25 000
2000-character strings, that would be 100 MB; that's not an exorbitant
amount. Access would be pretty quick.
I considered using an SHA-512 hash of these strings and storing them in
the database. However, while these will save on storage space, it will
take time to do the hashing before comparing an incoming string. So I'm
still wasting time. (Collisions due to hashing will not be a problem,
since an occasional false positive will not be fatal for my
application).
If you're using a database, don't bother with a hash, just put the whole
string in, index the column, and then do equality queries on it. A B-tree
index will deal with this kind of query pretty efficiently.
If you wanted to pursue in-memory approaches, i'd suggest constructing a
trie of some sort. Tries are very fast at retrieval, don't need to access
the whole key to identify a miss, and only need to access the whole key
once to identify a hit - you always walk through the key from beginning to
end (perhaps skipping some characters in some kinds of tree), stopping as
soon as the key doesn't match, and only reaching the end if it does match.
I haven't found a good overview of the current state of the art in tries,
but look up Patricia tries, Judy tries, burst tries, fusion tries, and HAT
tries. You could consider only storing a prefix of the strings - the first
100 characters, say - in the trie, to save memory, with the leaves having
pointers to where the complete strings are stored on disk.
tom
--
The sun just came out, I can't believe it