Simple Prefix Completer

A simple prefix completion library for node.js & Redis. Stores texts & their prefixes in redis according to the algorithm given by antirez in this gist. It's inefficient with space but leverages the redis sorted set data structure cleverly.

The use case it was developed for is tag auto-completion, for which I needed no fancy datastructures or scoring approaches. The only scoring used is lexical sorting. No additional data is stored along with the texts. All texts are stored and searched in lower case.

Depends only on redis.

Usage

npm install prefix-completer

Here's an example showing typical use: creating a completer dictionary, adding words to it, then requesting completions from it.

const completer = require('prefix-completer');
const async = require('async');

// make a dictionary
const tags = completer.create( { key: 'tags', db: 31 } );
console.log(`zkey: ${tags.rediskey}`); // -> 'tags'

// make a second completion dictionary
var usertags = completer.create( { key: 'users', db: 31 });
console.log(`zkey: ${usertags.rediskey}`); // -> 'usertags'

var wordlist = ['supernumary', ' superb ', 'Super', 'mary poppins', 'bert the sweep', 'codfish', 'sugar'];

async.series(
[
	function(cb) { tags.flush(cb) }, // clear for the example
	function(cb) { tags.add('supercalifragilisticexpialidocious', cb) }, // add a single word
	function(cb) { tags.addList(wordlist, cb) }, // add a list of words
	function(cb) { tags.complete('supe', 15, cb) }, // get completions for a prefix
	function(cb) { usertags.complete('supe', 15, cb) } // get completions from another dictionary
],
function(err, results)
{
	console.log(`added 1 completion to dict: ${results[1]}`);
	console.log(`added ${results[2].length} completions to dict`);
	console.log(`found ${results[3][1].length} completions for ${results[3][0]}:`);
	console.log(results[3][1]);
	console.log(`the user tags dictionary has ${results[4][1].length} completions for 'supe'`);
	process.exit(0);
});

API

All callback-accepting API functions also have a promise-returning *-Async version, created by Bluebird's promisify.

create()

completer = create([options])

Create a completion dictionary. Synchronous. Takes optional hash of parameters. Valid parameters:

redis: something to pass to redis's createClient(); can be a redis url client: an existing RedisClient db: integer specifying the redis database to select (defaults to 0) key: a short string key for the redis sorted set key; change it to namespace lookup dictionaries (defaults to 'COMP')

add()

completer.add(completion, function(err, added) {})

Add a string to the completion dictionary. Leading & trailing space are removed and the string is converted to lowercase. Responds with the exact string added. If the string was already present, responds with null. Can also accept an array of additions in the first parameter.

addList()

completer.add(stringlist, function(err, addedlist) {})

Add an array of strings to the completion dictionary. Responds with an array of the exact strings added. Skips strings that were already present.

complete()

completer.complete(prefix, maxresults, function(err, prefixcleaned, completions) {})

Search for completions for the passed-in search string. Responds with the exact string searched for and an array of completions containing at most maxresults strings. The maxresults parameter is optional; it defaults to 50 if not passed.

remove()

completer.remove(completion, function(err, removed) {})

Removes the specified completion from the dictionary. Responds with true if successful.

flush()

completer.flush(function(err, count) {})

Delete the key used to store this dictionary set. Passes the callback straight through to the redis DEL call, which responds with the number of keys deleted.

statistics()

completer.statistics(function(err, results))

Get statistics on the current state of the completion database. Responds with a hash containing the following keys:

total: total number of entries in the database leaves: number of completion phrases stored leaflen: characters used for completion phrases prefixlen: characters used for prefix storage

leaves()

completer.leaves(function(err, leaves))

Responds with an array containing all leaf nodes in the dictionary, that is, every valid completion. Does not strip the terminating * characters.

dump()

completer.dump(function(err, items))

Responds with an array containing all the items stored in the dictionary. Perhaps useful for debugging.

LICENSE

MIT