Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A Radix Trie (aka PATRICIA trie) implemented in JavaScript. Play with it at this interactive JS fiddle: http://jsfiddle.net/jCYAw/
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));
}
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.