universal-automata / liblevenshtein-coffeescript Goto Github PK

First of all thanks for sharing your work with the world!

I'm using the Javascript version, and I have a question regarding the .dictionary(locations, false) bit here:

(code below is in es6)

import levenshtein from 'liblevenshtein';
const transducer = new levenshtein
  .Builder()
  .dictionary(locations, false) // What does false mean?
  .algorithm('transposition')
  .include_distance(false)
  .build();
...
const matches = transducer.transduce(query, 1);

When should I pass true and when should I pass false to .dictionary()?

How could I guarantee that matches are in the same order as locations?

For example, if query = 'elbourne', and locations is:

['melbourne', 'sydney', 'london', 'selbourne', 'adelaide', 'delbourne'];

I want to make sure that matches is:

['melbourne', 'selbourne', 'delbourne']

(the order of locations is preserved in matches)

https://wiki.saucelabs.com/

I've already registered the project, I just need to create the browser tests.

please update the node version under engines in package json file so that the package can be installed using yarn in newer versions versions of node

Triangle inequality states |a + b| <= |a| + |b|, not that they are equal. I blame this error on hacking at 3am.

https://github.com/universal-automata/liblevenshtein-coffeescript/blob/master/src/levenshtein/builder.coffee#L473

This is good work. Wondering how to extend this to make it search against a database (instead of against in-memory dictionary)?

For example, if the original dictionary of strings were stored in, say, ElasticSearch or MongoDB etc. what is the best way to utilize this ?

Please see that the following test will fail:

// https://github.com/universal-automata/liblevenshtein-coffeescript/blob/master/src/collection/dawg.coffee
// Test 
var dictionary = [ "about", "after", "all", "and", "about and", "afterall" ];
var dawg = new Dawg(dictionary);
console.log(dawg.accepts("after"));

This fails because the construction of the Dawg is stomping on the nodes of prefixes, thus causing the 'is_final' attribute to be set to false.

The important thing to realize is that the original article which this algorithm is patterned on requires that a list be sorted before it is added. The reason for this is because that is the only way to be certain that the previous word has the possibility of being a prefix to the next word being inserted.

This won't work because there is no guarantee that, given an unsorted list, the previous word will share a prefix with the current word. (That guarantee is ensured by having a presorted list):

# Find longest common prefix between word and previous word
i = 0; previous_word = @previous_word
upper_bound =
  if word.length < previous_word.length
    word.length
  else
    previous_word.length

i += 1 while i < upper_bound and word[i] is previous_word[i]

As far as I can tell, the only way to construct a Dawg from an unsorted list would be to construct the entire trie first, then compress it. The reason that the referenced algorithm is so efficient is because pre-sorting guarantees that a trie branch can be minimized directly after construction.