The mnemonist from yomguithereal

Roadmap

MultiIndex
CompositeIndex
MultiSet
MultiMap
InvertedIndex
SearchIndex
Fuzzy?
Deque
BloomFilter
DoublyLinkedList
SuffixTree
VPTree
Buckhard-Keller Tree
SymSpell
QuadTree, MX-CIF QuadTree
k d tree
Interval tree
Utils, set operators
Static matrix + triangular
Radix tree, Patricia tree
Index
M-tree
BitSet
LRUCache
CoverTree
MarisaTrie
BiMap
UnsafeBiMap
Table
Multi Vantage Point Tree
Binary Tree
RedBlack Tree
ArrayTrie, DoubleArrayTrie StaticArrayTrie etc.
Sparse Matrix, Sparse Vector
Cuckoo filter
HeapSet, HeapMap
Static bit array
Dynamic Typed arrays (1.5 factor by default)
SparseSet
Anagram Tree
Palindrom Tree
Wavelet Tree
t-digest
SparseArray
CircularBuffer
BipBuffer
Nested Sets
Perfect Hashmaps
Static search set
TrieMap
BoundedHeap, Min-Max Heap
Spatial Hashmap
https://github.com/pabloem/advanced_arrays
Elias Fano QuasiSuccint Indices
Sparse Table
Tupled Stack
Disjoint Set
dawgmap, dafsa
GADDAG
Count Min sketch
PH-Tree
BallTree
HAMT
Unrolled Linked list
Fenwick Tree
Inversion List
TokenMap
CallWheel / HashedWheelTimer
HAT hashed array tree, HAT Trie
GapBuffer
x fast trie critbit trie y fast z fast
Compressed bit vectors rrr etc.
Default map
Static stack
Piece Table
RoaringBitmap
Vocab (alternative to incrementalmap)
Hyperloglog
SoftHeap
Boundaries Trie like web entities
Stern Brocot tree

Decide what is iterating over a multiset

clean up #.size & #.distinctSize etc.

Possibility to refactor Trie.get to save one condition in the loop

First argument to consume iterable?

Create CompositeIndex to simplify Index API

Adding merge capabilities to index

Make sure there is an example of usage for each structure

BKTree child traversal heuristics for large distances

iterate plain object's prototype key

the code in iterate.js

// The target is a plain object
for (k in target)
  callback(target[k], k);

should add a test of target.hasOwnProperty(k)

Serialize bloom filter?

The API docs don't mention how to save or load a bloom filter....

Linked List implementation details

@dheavy, I created a benchmark here to assess what was the best storage strategy for the list's node.

Tested strategies are:

Raw object
2-Array (tuple)
Node class
Object.create(null)

Benchmarks seems to point toward raw objects but I notice some strange v8 optimizations going on. Meaning that the order of the tests, notably between raw objects & 2-arrays change dramatically.

What do you think?

Consider using version 5.0 of the SymSpell algorithm

Please consider updating Mnemonist to use version 5.0 of the SymSpell algorithm (instead of version 3.0).
v5.0 fixes some bugs which prevented the suggestion to be complete under some circumstances.
A new prefix indexing method also significantly reduces the memory consumption.
See https://github.com/wolfgarbe/symspell#changes-in-v50 for details.

Benchmark to determine which typed array to use for the bitset

Support for types

This is a cool library. Data structure has growing importance on FE since more logic is pushed to client side. It would be nice if this library can have DefinitelyTyped 😄

Standard serialization/deserialization API across all data-structures

Currently one can serialize mnemonist data-structures with .toJSON but there does not appear to be a standard way to deserialize. I'd like to be able to cache mnemonist structures in the browser or to send pre-processed structures to the client over a network.

To achieve serialization/deserialization at the moment, one has to write custom functions which often need to re-iterate over the entire data set. Re-iterating may be prohibitively expensive for large structures i.e. this sucks most for the exact use-cases where mnemonist would be most useful.

e.g. there should be a way to do something like:

dest.fromJSON(src.toJSON())

and ideally the deserialization process would need to do minimal reprocessing, it would basically just dump the data into place, something like:

dest.root = src.toJSON()

For example, I'd hoped this exact thing would work for Trie, except that toJSON loses the size information, and if you added .size to the structure produced by toJSON, you'd potentially break any 3rd party code consuming the current toJSON format.

Therefore, you should probably should use something other than toJSON, instead create a new API pair e.g. serialize/deserialize which produces/consumes a representation whose structure users would consider opaque because:

the best encoding for fast serialization/deserialization may not be JSON (e.g. bloom filters) and
you want to be able to have the freedom to change the serialization format so you're not stuck working with some inefficient representation simply because you want to avoid breaking the public toJSON API.

Perhaps serialize would just generate JSON or a JS object for now, but you don't want to be locked into that, nor into the structure it produces.

Related to #28

Performance benchmark

#Can you please add a section comparing the performance against the alternatives in plain JavaScript??

I made some tests and actually I got better results without the library. Perhaps I'm not using it properly. Here is the code I used:

var Trie = require('mnemonist/trie');
var query = 'rom';

var words = [];
const dictionary = ['category', 'romance'];

for (var i = 0; i < 10000; i++) {
  words.push(dictionary[i % 2] + i);
}

console.time('ES5');
var result = words.filter(function(word) {
  return word.startsWith(query);
});
console.log(result.length);
console.timeEnd('ES5');

console.time('mnemonist');
// Let's create a trie from our words
var trie = Trie.from(words);

// Now let's query our trie
var wordsWithMatchingPrefix = trie.get(query);
console.log(wordsWithMatchingPrefix.length);
console.timeEnd('mnemonist');

I tried to use the version on npm by installing globally: npm install --global damerau-levenshtein

This did not prevent the error message described above.

Would you please advise where the required damerau-levenshtein file is to be found. Shouldn't it be part of the mnemonist package?

Many thanks.

suggestion to standardize Iterate callback's arguments

Wouldn't it be better to standardize the callback in iterate with (value, index|key, target)?

in iterate.js:

line 21

callback(target[i], i)

vs line 27 (Array.prorotype.forEach)

target.forEach(callback)

Also, if callback returns false break the loop.

var LinkedList = require('mnemonist/linked-list');

Would it be better to have:

var LinkedList = require('mnemonist/LinkedList');

@jacomyal what do you think of this?

yomguithereal / mnemonist Goto Github PK

mnemonist's Introduction

Mnemonist

Installation

Documentation

Contribution

License

mnemonist's People

Contributors

Stargazers

Watchers

Forkers

mnemonist's Issues

Recommend Projects

Recommend Topics

Recommend Org