Message from JavaScript discussions

May 2017

— The linked list would be weighted by length, essentially a typed array consisting of tuples of words. If looking for (X = Hell in a set with "Hello" and "Hop" in it, you could make the following deductions:
1. All the characters in X are in the character set. X might exist in the word set.
2. The largest, first word in the list, starting with "H" and skipped to through one or more pointers in the skip list, is 5 characters; too long to be X. It also matches by 4/5 characters, and It is "Hello", however we do not store this information or otherwise compute it due to the first condition.
3. The next word with the best match to the first word, or next shortest size is only 3 characters long. it is not long enough to be X, however there are no more words in the list which are larger or equal to the size of X, and thus X is definitely not in the list.

Message permanent page


You could make other decuctions as well due to the nature of the skip list, some of which would be handled in the algorithm which constructs the list


word: [1,0,3,3,8],
nextLen: 4,
nextShare: 2,
next: [object Object]

— But by doing that, you can run a search, "Do all characters in X exist in the character set", and if so, then run your probabilistic search on the linked list

Message permanent page

— Because the character set only has unique characters, the first check has a linear time complexity of O(n) with n being the number of unique characters in the set, but not words

Message permanent page

— A bloom filter is slower than a native set.

— It's meant to be faster than a DB lookup.

— Hmmm

— Is binary search impossible?

— I could just store ascii values as digits:
[ 72, 101, 108, 108, 111 ]

— And then keep list sorted

— And check at the middle of the list if the first char matches, then go to 1 / 4 or 3 / 4 based on higher / lower, then repeat for the next level, and keep going

Message permanent page