universal-automata / liblevenshtein-coffeescript Goto Github PK
View Code? Open in Web Editor NEWVarious utilities regarding Levenshtein transducers. (CoffeeScript / JavaScript / Node.js)
License: MIT License
Various utilities regarding Levenshtein transducers. (CoffeeScript / JavaScript / Node.js)
License: MIT License
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
)
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.
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.