Skip to content

Instantly share code, notes, and snippets.

@samuelclay

samuelclay/radix_trie.js

Created January 30, 2013 16:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save samuelclay/4674630 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save samuelclay/4674630 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. samuelclay created this gist Jan 30, 2013.
    303 changes: 303 additions & 0 deletions radix_trie.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,303 @@
    var RadixTrie = function(words) {
    this.T = {};
    this.initialize(words);
    };

    RadixTrie.prototype = {

    initialize: function(words) {
    var self = this;
    words = words || [];

    words.forEach(function(word) {
    self.insert(word);
    });
    },

    insert: function(word, T) {
    var self = this;
    var l = word.length;
    var prefix;
    word = word && word.toLowerCase();
    T = T || this.T;

    // Search for existing prefixes
    while (l--) {
    prefix = word.substr(0, l+1);
    if (T[prefix]) {
    // Found prefix, moving into subtrie
    if (!Object.keys(T[prefix]).length) {
    // If one word is a pure subset of another word, the prefix
    // should also point to the subset.
    T[prefix][""] = {};
    }
    return this.insert(word.substr(l+1), T[prefix]);
    }
    }

    // No prefix found means insert word and check for prefix collision
    var siblings = Object.keys(T);
    l = word.length;
    var siblingFound = siblings.some(function(sibling) {
    var s = 0;
    var commonPrefix;

    do {
    if (sibling[s] != word[s]) {
    if (s > 1) {
    commonPrefix = sibling.substr(0, s-1);
    }
    break;
    }
    } while (s++ < l)

    if (commonPrefix) {
    // Rearrange trie to move word with prefix collision into new
    // common prefix subtrie
    T[commonPrefix] = {};
    self.insert(sibling.substr(s-1), T[commonPrefix]);
    T[commonPrefix][sibling.substr(s-1)] = T[sibling];
    self.insert(word.substr(s-1), T[commonPrefix]);
    delete T[sibling];

    return true;
    }
    });

    // No siblings at this level? New branch.
    if (!siblingFound) {
    T[word] = {};
    }
    },

    lookup: function(word, limit, T, matchedPrefix) {
    limit = limit || 10;
    T = T || this.T;
    matchedPrefix = matchedPrefix || "";
    word = word && word.toLowerCase();
    var self = this;
    var l = word.length;
    var matches = [];

    // Search for existing prefixes and recurseively descend
    while (l--) {
    var prefix = word.substr(0, l+1);
    if (T[prefix]) {
    var suffix = word.substr(l+1);
    return this.lookup(suffix, limit, T[prefix], matchedPrefix + prefix);
    }
    }

    // No prefixes means check siblings on this level
    l = word.length;
    var siblings = Object.keys(T);
    var siblingFound = siblings.some(function(sibling) {
    var s = l;

    // Node parent is full word, so include all children as matches
    if (!s) {
    var nodeMatches = self.names(T[sibling], limit, matchedPrefix + sibling);
    matches = matches.concat(nodeMatches);
    }

    if (matches.length > limit) return true;

    // Check all child prefixes for matches
    while (s--) {
    if (sibling.substr(0, s+1) == word.substr(0, s+1)) {
    var siblingMatches = self.names(T[sibling], limit, matchedPrefix + sibling);
    matches = matches.concat(siblingMatches);
    return true;
    }
    }
    });

    // Match complete word that has no children
    if (!siblings.length && !word.length) {
    matches.push(matchedPrefix);
    }

    if (matches.length > limit) {
    matches = matches.slice(0, limit);
    }

    return matches;
    },

    // Retrieves all words below a node and helpfully adds the provided
    // prefix to each word.
    names: function(T, limit, matchedPrefix) {
    T = T || this.T;
    var self = this;
    var keys = Object.keys(T);
    var matches = [];
    matchedPrefix = matchedPrefix || "";

    // Recursively descend down to fetch all words
    if (keys.length) {
    keys.some(function(key) {
    if (Object.keys(T[key]).length) {
    var submatches = self.names(T[key], limit, matchedPrefix + key);
    matches = matches.concat(submatches);
    } else {
    matches.push(matchedPrefix + key);
    }
    if (matches.length > limit) {
    return true;
    }
    });
    } else {
    // No children, so just include self
    matches.push(matchedPrefix);
    }

    if (matches.length > limit) {
    matches = matches.slice(0, limit);
    }

    return matches;

    }

    };

    // Export for node.js
    if (typeof module !== 'undefined') {
    module.exports = {
    RadixTrie: RadixTrie
    };
    }

    window.ProperNames = [
    "Aaron", "Adam", "Adlai", "Adrian", "Agatha", "Ahmed", "Ahmet", "Aimee", "Al", "Alain", "Alan",
    "Alastair", "Albert", "Alberto", "Alejandro", "Alex", "Alexander", "Alexis", "Alf", "Alfred", "Alison", "Allan",
    "Allen", "Alvin", "Amanda", "Amarth", "Amedeo", "Ami", "Amigo", "Amir", "Amos", "Amy", "Anatole",
    "Anatoly", "Anderson", "Andre", "Andrea", "Andreas", "Andrew", "Andries", "Andy", "Angela", "Angus", "Anita",
    "Ann", "Anna", "Annard", "Anne", "Annie", "Anthony", "Anton", "Antonella", "Antonio", "Antony", "Archie",
    "Ariel", "Arlene", "Arne", "Arnold", "Art", "Arthur", "Audrey", "Avery", "Axel", "Barbara", "Barbra",
    "Barney", "Barrett", "Barrio", "Barry", "Bart", "Barton", "Bea", "Beckie", "Becky", "Belinda", "Ben",
    "Benjamin", "Benson", "Bernard", "Bernie", "Bert", "Bertrand", "Beth", "Betsy", "Betty", "Beverly", "Bill",
    "Billie", "Billy", "Bjorne", "Blaine", "Blair", "Blake", "Blayne", "Bob", "Bobbie", "Bobby", "Bonnie",
    "Boyce", "Boyd", "Brad", "Bradford", "Bradley", "Brandi", "Brandon", "Brandy", "Brenda", "Brendan", "Brender",
    "Brent", "Bret", "Brett", "Brian", "Briggs", "Brodie", "Brooke", "Bruce", "Bruno", "Bryan", "Bryce",
    "Bucky", "Bud", "Butler", "Byron", "Caleb", "Calvin", "Carisa", "Carl", "Carlo", "Carlos", "Carol",
    "Carole", "Caroline", "Carolyn", "Carsten", "Carter", "Cary", "Case", "Casey", "Casper", "Catherine", "Cathrin",
    "Cathryn", "Cathy", "Cecilia", "Celeste", "Celia", "Charleen", "Charlene", "Charles", "Charley", "Charlie", "Chet",
    "Chip", "Chris", "Christian", "Christie", "Christina", "Christofer", "Christophe", "Christopher", "Chuck", "Cindie", "Cindy",
    "Claire", "Clara", "Clare", "Clarence", "Clarissa", "Clark", "Claude", "Claudia", "Claudio", "Clay", "Clayton",
    "Clem", "Cliff", "Clifford", "Clyde", "Cole", "Coleen", "Colin", "Collin", "Connie", "Conrad", "Corey",
    "Cory", "Courtney", "Craig", "Cris", "Cristi", "Cristina", "Cristopher", "Curt", "Curtis", "Cynthia", "Cyrus",
    "Dale", "Dalton", "Damon", "Damone", "Dan", "Dana", "Dani", "Daniel", "Daniele", "Danielle", "Dannie",
    "Danny", "Darci", "Daren", "Darin", "Darrell", "Darren", "Darryl", "Daryl", "Dave", "David", "Dawn",
    "Dawson", "Dean", "Deb", "Debbie", "Debi", "Deborah", "Deirdre", "Del", "Delbert", "Denis", "Dennis",
    "Derek", "Devon", "Dewey", "Diana", "Diane", "Dick", "Dieter", "Dimetry", "Dimitry", "Dion", "Dirk",
    "Dominic", "Dominick", "Don", "Donal", "Donald", "Donn", "Donna", "Donne", "Donnie", "Donovan", "Dori",
    "Dorian", "Dorothy", "Dory", "Doug", "Douglas", "Doyle", "Drew", "Duane", "Duke", "Duncan", "Dustin",
    "Dwayne", "Dwight", "Dylan", "Earl", "Earle", "Earnie", "Ed", "Eddie", "Eddy", "Edgar", "Edith",
    "Edmond", "Edmund", "Eduardo", "Edward", "Edwin", "Eileen", "Elaine", "Eli", "Elias", "Elijah", "Eliot",
    "Elisabeth", "Elizabeth", "Ellen", "Elliot", "Elliott", "Elric", "Elsa", "Elvis", "Elwood", "Emil", "Emily",
    "Emma", "Emmett", "Eric", "Erick", "Erik", "Ernest", "Ernie", "Ernst", "Erwin", "Ethan", "Eugene",
    "Eva", "Evan", "Evelyn", "Everett", "Farouk", "Fay", "Felix", "Fletcher", "Floria", "Florian", "Floyd",
    "Frances", "Francis", "Francisco", "Francois", "Frank", "Franklin", "Fred", "Frederic", "Frederick", "Fritz", "Gabriel",
    "Gail", "Gale", "Galen", "Gary", "Gene", "Geoff", "Geoffrey", "George", "Gerald", "Gerard", "Gideon",
    "Gigi", "Gil", "Giles", "Gill", "Gilles", "Ginny", "Giovanni", "Glen", "Glenn", "Glynn", "Gordon",
    "Grace", "Graeme", "Graham", "Grant", "Granville", "Greg", "Gregg", "Gregge", "Gregor", "Gregory", "Gretchen",
    "Griff", "Guido", "Guillermo", "Gunnar", "Gunter", "Guy", "Gypsy", "Hal", "Hamilton", "Hank", "Hans",
    "Harmon", "Harold", "Harris", "Harry", "Hartmann", "Harv", "Harvey", "Hazel", "Heather", "Hector", "Heidi",
    "Hein", "Heinrich", "Heinz", "Helen", "Helge", "Henry", "Herb", "Herbert", "Herman", "Herve", "Hienz",
    "Hilda", "Hillary", "Hillel", "Himawan", "Hirofumi", "Hirotoshi", "Hiroyuki", "Hitoshi", "Hohn", "Holly", "Hon",
    "Honzo", "Horst", "Hotta", "Howard", "Hsi", "Hsuan", "Huashi", "Hubert", "Huey", "Hugh", "Hughes",
    "Hui", "Hume", "Hunter", "Hurf", "Hwa", "Hy", "Ian", "Ilya", "Ima", "Indra", "Ira",
    "Irfan", "Irvin", "Irving", "Irwin", "Isaac", "Isabelle", "Isidore", "Israel", "Izchak", "Izumi", "Izzy",
    "Jack", "Jackye", "Jacob", "Jacobson", "Jacques", "Jagath", "Jaime", "Jakob", "James", "Jamie", "Jan",
    "Jane", "Janet", "Janice", "Janos", "Jared", "Jarl", "Jarmo", "Jarvis", "Jason", "Jay", "Jayant",
    "Jayesh", "Jean", "Jean-Christophe", "Jean-Pierre", "Jeanette", "Jeanne", "Jeannette", "Jeannie", "Jeany", "Jef", "Jeff",
    "Jeffery", "Jeffie", "Jeffrey", "Jelske", "Jem", "Jenine", "Jennie", "Jennifer", "Jerald", "Jeremy", "Jerome",
    "Jerrie", "Jerry", "Jesper", "Jess", "Jesse", "Jesus", "Ji", "Jianyun", "Jill", "Jim", "Jimmy",
    "Jin", "Jinchao", "Jingbai", "Jinny", "Jiri", "Jisheng", "Jitendra", "Joachim", "Joanne", "Jochen", "Jock",
    "Joe", "Joel", "Johan", "Johann", "John", "Johnathan", "Johnnie", "Johnny", "Jon", "Jonathan", "Jones",
    "Jong", "Joni", "Joon", "Jordan", "Jorge", "Jos", "Jose", "Joseph", "Josh", "Joshua", "Josip",
    "Joubert", "Joyce", "Juan", "Judge", "Judith", "Judy", "Juergen", "Juha", "Julia", "Julian", "Juliane",
    "Julianto", "Julie", "Juliet", "Julius", "Jun", "June", "Jurevis", "Juri", "Jussi", "Justin", "Jwahar",
    "Kaj", "Kamel", "Kamiya", "Kanthan", "Karen", "Kari", "Karl", "Kate", "Kathleen", "Kathryn", "Kathy",
    "Kay", "Kayvan", "Kazuhiro", "Kee", "Kees", "Keith", "Kelly", "Kelvin", "Kemal", "Ken", "Kenn",
    "Kenneth", "Kent", "Kenton", "Kerri", "Kerry", "Kevan", "Kevin", "Kevyn", "Kieran", "Kiki", "Kikki",
    "Kim", "Kimberly", "Kimmo", "Kinch", "King", "Kirk", "Kirsten", "Kit", "Kitty", "Klaudia", "Klaus",
    "Knapper", "Knudsen", "Knut", "Knute", "Kolkka", "Konrad", "Konstantinos", "Kory", "Kris", "Kristen", "Kristi",
    "Kristian", "Kristin", "Kriton", "Krzysztof", "Kuldip", "Kurt", "Kusum", "Kyle", "Kylo", "Kyu", "Kyung",
    "Lana", "Lance", "Lanny", "Lar", "Larry", "Lars", "Laura", "Laurel", "Laurence", "Laurent", "Laurianne",
    "Laurie", "Lawrence", "Lea", "Leads", "Lee", "Leif", "Leigh", "Leila", "Leith", "Len", "Lenny",
    "Lenora", "Leo", "Leon", "Leonard", "Leora", "Les", "Leslie", "Lester", "Leung", "Lewis", "Lex",
    "Liber", "Lievaart", "Lila", "Lin", "Linda", "Linder", "Lindsay", "Lindsey", "Linley", "Lisa", "List",
    "Liyuan", "Liz", "Liza", "Lloyd", "Lois", "Lonhyn", "Lord", "Loren", "Lorenzo", "Lori", "Lorien",
    "Lorraine", "Lou", "Louie", "Louiqa", "Louis", "Louise", "Loukas", "Lowell", "Loyd", "Luc", "Lucifer",
    "Lucius", "Lui", "Luis", "Lukas", "Luke", "Lum", "Lyndon", "Lynn", "Lynne", "Lynnette", "Maarten",
    "Mac", "Magnus", "Mah", "Mahesh", "Mahmoud", "Major", "Malaclypse", "Malcolm", "Malloy", "Malus", "Manavendra",
    "Manjeri", "Mann", "Manny", "Manolis", "Manuel", "Mara", "Marc", "Marcel", "Marci", "Marcia", "Marco",
    "Marcos", "Marek", "Margaret", "Margie", "Margot", "Marguerite", "Maria", "Marian", "Marie", "Marilyn", "Mario",
    "Marion", "Mariou", "Mark", "Markus", "Marla", "Marlena", "Marnix", "Marsh", "Marsha", "Marshall", "Martha",
    "Martin", "Marty", "Martyn", "Marvin", "Mary", "Masanao", "Masanobu", "Mason", "Mat", "Mats", "Matt",
    "Matthew", "Matthias", "Matthieu", "Matti", "Maureen", "Maurice", "Max", "Mayo", "Mechael", "Meehan", "Meeks",
    "Mehrdad", "Melinda", "Merat", "Merril", "Merton", "Metin", "Micah", "Michael", "Micheal", "Michel", "Michelle",
    "Michiel", "Mick", "Mickey", "Micky", "Miek", "Mikael", "Mike", "Mikey", "Miki", "Miles", "Milner",
    "Milo", "Miltos", "Miriam", "Miriamne", "Mitch", "Mitchell", "Moe", "Mohammad", "Molly", "Mongo", "Monica",
    "Monty", "Moore", "Moran", "Morgan", "Morris", "Morton", "Moses", "Mosur", "Mott", "Murat", "Murph",
    "Murray", "Murthy", "Mwa", "Myrick", "Myron", "Mysore", "Nadeem", "Naim", "Nancy", "Nanda", "Naomi",
    "Naoto", "Naren", "Narendra", "Naresh", "Nate", "Nathan", "Nathaniel", "Natraj", "Neal", "Ned", "Neil",
    "Nelken", "Neville", "Nguyen", "Nhan", "Niall", "Nichael", "Nicholas", "Nici", "Nick", "Nicolas", "Nicolette",
    "Nicolo", "Niels", "Nigel", "Nikolai", "Nils", "Ning", "Ninja", "No", "Noam", "Noemi", "Nora",
    "Norbert", "Norm", "Norma", "Norman", "Nou", "Novo", "Novorolsky", "Ofer", "Olaf", "Old", "Ole",
    "Oleg", "Oliver", "Olivier", "Olof", "Olson", "Omar", "Orville", "Oscar", "Oskar", "Owen", "Ozan",
    "Pablo", "Page", "Pam", "Pamela", "Panacea", "Pandora", "Panos", "Pantelis", "Panzer", "Paola", "Part",
    "Pascal", "Pat", "Patrice", "Patricia", "Patricio", "Patrick", "Patty", "Paul", "Paula", "Pedro", "Peggy",
    "Penny", "Per", "Perry", "Pete", "Peter", "Petr", "Phil", "Philip", "Philippe", "Phill", "Phillip",
    "Phiroze", "Pia", "Piercarlo", "Pierce", "Pierette", "Pierre", "Piet", "Piete", "Pieter", "Pilar", "Pilot",
    "Pim", "Ping", "Piotr", "Pitawas", "Plastic", "Po", "Polly", "Pontus", "Pradeep", "Prakash", "Pratap",
    "Pratapwant", "Pratt", "Pravin", "Presley", "Pria", "Price", "Raanan", "Rabin", "Radek", "Rafael", "Rafik",
    "Raghu", "Ragnar", "Rahul", "Raif", "Rainer", "Raj", "Raja", "Rajarshi", "Rajeev", "Rajendra", "Rajesh",
    "Rajiv", "Rakhal", "Ralf", "Ralph", "Ram", "Ramadoss", "Raman", "Ramanan", "Ramesh", "Ramiro", "Ramneek",
    "Ramon", "Ramsey", "Rand", "Randal", "Randall", "Randell", "Randolph", "Randy", "Ranjit", "Raphael", "Rathnakumar",
    "Raul", "Ravi", "Ravindran", "Ravindranath", "Ray", "Rayan", "Raymond", "Real", "Rebecca", "Rees", "Reid",
    "Reiner", "Reinhard", "Renu", "Revised", "Rex", "Rhonda", "Ric", "Ricardo", "Rich", "Richard", "Rick",
    "Ricky", "Rik", "Ritalynne", "Ritchey", "Ro", "Rob", "Robbin", "Robert", "Roberta", "Roberto", "Robin",
    "Rod", "Rodent", "Roderick", "Rodger", "Rodney", "Roger", "Rogue", "Roland", "Rolf", "Rolfe", "Romain",
    "Roman", "Ron", "Ronald", "Ronni", "Root", "Ross", "Roxana", "Roxane", "Roxanne", "Roxie", "Roy",
    "Rudolf", "Rudolph", "Rudy", "Rupert", "Russ", "Russell", "Rusty", "Ruth", "Saad", "Sabrina", "Saify",
    "Saiid", "Sal", "Sally", "Sam", "Samir", "Samuel", "Sanand", "Sanche", "Sandeep", "Sandip", "Sandra",
    "Sandy", "Sanford", "Sangho", "Sanity", "Sanjay", "Sanjeev", "Sanjib", "Santa", "Saqib", "Sarah", "Sassan",
    "Saul", "Saumya", "Scot", "Scott", "Sean", "Sedat", "Sedovic", "Seenu", "Sehyo", "Sekar", "Serdar",
    "Sergeant", "Sergei", "Sergio", "Sergiu", "Seth", "Seymour", "Shadow", "Shahid", "Shai", "Shakil", "Shamim",
    "Shane", "Shankar", "Shannon", "Sharada", "Sharan", "Shari", "Sharon", "Shatter", "Shaw", "Shawn", "Shean",
    "Sheila", "Shel", "Sherman", "Sherri", "Shirley", "Sho", "Shutoku", "Shuvra", "Shyam", "Sid", "Sidney",
    "Siegurd", "Sigurd", "Simon", "Siping", "Sir", "Sjaak", "Sjouke", "Skeeter", "Skef", "Skip", "Slartibartfast",
    "Socorrito", "Sofia", "Sofoklis", "Son", "Sonja", "Sonny", "Soohong", "Sorrel", "Space", "Spass", "Spencer",
    "Spike", "Spock", "Spudboy", "Spy", "Spyros", "Sri", "Sridhar", "Sridharan", "Srikanth", "Srinivas", "Srinivasan",
    "Sriram", "Srivatsan", "Ssi", "Stacey", "Stacy", "Stagger", "Stan", "Stanislaw", "Stanley", "Stanly", "Starbuck",
    "Steen", "Stefan", "Stephan", "Stephanie", "Stephe", "Stephen", "Stevan", "Steve", "Steven", "Stewart", "Straka",
    "Stu", "Stuart", "Subra", "Sue", "Sugih", "Sumitro", "Sundar", "Sundaresan", "Sunil", "Suresh", "Surya",
    "Susan", "Susanne", "Susumu", "Suu", "Suwandi", "Suyog", "Suzan", "Suzanne", "Svante", "Swamy", "Syd",
    "Syed", "Sylvan", "Syun", "Tad", "Tahsin", "Tai", "Tait", "Takao", "Takayuki", "Takeuchi", "Tal",
    "Tammy", "Tanaka", "Tandy", "Tanya", "Tao", "Tareq", "Tarmi", "Taurus", "Ted", "Teresa", "Teri",
    "Teriann", "Terrance", "Terrence", "Terri", "Terry", "Teruyuki", "Thad", "Tharen", "The", "Theo", "Theodore",
    "Thierry", "Think", "Thomas", "Those", "Thuan", "Ti", "Tiefenthal", "Tigger", "Tim", "Timo", "Timothy",
    "Tobias", "Toby", "Todd", "Toerless", "Toft", "Tolerant", "Tollefsen", "Tom", "Tomas", "Tommy", "Tony",
    "Tor", "Torsten", "Toufic", "Tovah", "Tracey", "Tracy", "Tran", "Travis", "Trent", "Trevor", "Trey",
    "Triantaphyllos", "Tricia", "Troy", "Trying", "Tuan", "Tuna", "Turkeer", "Tyler", "Uri", "Urs", "Vadim",
    "Val", "Valentin", "Valeria", "Valerie", "Van", "Vance", "Varda", "Vassos", "Vaughn", "Venkata", "Vern",
    "Vernon", "Vic", "Vice", "Vick", "Vicki", "Vickie", "Vicky", "Victor", "Victoria", "Vidhyanath", "Vijay",
    "Vilhelm", "Vince", "Vincent", "Vincenzo", "Vinod", "Vishal", "Vistlik", "Vivek", "Vladimir", "Vladislav", "Wade",
    "Walt", "Walter", "Warren", "Wayne", "Wendell", "Wendi", "Wendy", "Werner", "Wes", "Will", "William",
    "Willie", "Wilmer", "Wilson", "Win", "Winnie", "Winston", "Wolf", "Wolfgang", "Woody", "Yvonne"
    ];


    $(document).ready(function() {
    var trie = new RadixTrie(window.ProperNames);

    $( "input" ).autocomplete({
    source: function(req, resp) {
    console.log(["Lookup", req.term, trie.lookup(req.term)]);
    resp(trie.lookup(req.term));
    }
    });
    });