autocorrect with efficient tree data structure

globals.coffee

global.c = console.log.bind console
global._ = require 'lodash'
global.fs = require 'fs'
global.color = require 'bash-color'



c 'hi'

main_000.coffee

require './globals.coffee'



lookup_node_at_prefix = ({ prefix, tree }) ->
    cursor = tree
    prefix_rayy = prefix.split ''
    for char in prefix_rayy
        cursor = cursor.chd_nodes[char]
        # c cursor is undefined
        if cursor is undefined
            return 'Not found.'
    return cursor


break_ties = ({ candides }) ->
    # for now will just return the first,
    # but later can implement the logic for lexicographic order
    candides[0]


map_prefix_to_word = ({ dictionary, prefix }) ->
    # c color.green prefix
    # c dictionary
    candides = []
    for word in dictionary
        if word.indexOf(prefix) is 0
            candides.push word
    if candides.length > 1
        return break_ties { candides }
    else
        return candides.pop()


blob = fs.readFileSync 'string_dictionary.txt', 'utf8'

the_dictionary = blob.split '\n'
the_dictionary = _.map the_dictionary, (word, idx) ->
    word.toLowerCase()
c the_dictionary

tree =
    chd_nodes: {}
    prefix: ''

for word, idx in the_dictionary
    cursor = tree
    prefix = ''
    unless word.length < 1
        for char, jdx in word
            prefix+= char
            if not _.includes(_.keys(cursor.chd_nodes), char)
                cursor.chd_nodes[char] =
                    match_word: map_prefix_to_word({ prefix, dictionary: the_dictionary })
                    prefix: prefix
                    chd_nodes: {}
            cursor = cursor.chd_nodes[char]
c tree

c color.green "\n \n So now everything is built. \n \n"


# test:
prefix_000 = 'cece'

the_node = lookup_node_at_prefix
    prefix: prefix_000
    tree: tree

c the_node

package.json

{
    "dependencies": {
        "bash-color": "latest",
        "commander": "latest",
        "lodash": "latest"
    }
}

string_dictionary.txt

aardvark
armadillo
armament
bevy
between
betwixt
cavalier
canteen
lamarkian
landmark
llama
suave
submarine
tipsy
trenton
zebra

I'm using nodemon so to test I just edit prefix_000's value on line 64 and click save. The terminal should be side-by-side with the text-editor so you can test pretty much live like that.

Assumes:

• nodemon and coffee installed globally, npm i ran locally for the package.json contents.
• The above files are in a common dir and nodemon main_000.coffee.

https://github.com/kulicuu/autocorrect-autocomplete