我想实现一个自动建议组件。 对于每个用户输入，该组件应提供零个或多个建议。
例如，如果用户输入'park' ，建议可以是：['Parkville', 'Parkwood', 'Bell Park']。
要求很简单：
'park'，'PARK'和'PaRk'）'pa'将匹配'Parkville'，'Bell Park'和'Very cool park'，但不是'Carpark'）您会选择哪种数据结构来使用JavaScript实现此功能？
是否有任何JavaScript / Node.js库可以帮助实现此功能？
如果您想在不进行递归遍历的情况下以O(1)的时间复杂度（当然，每个建议需要O(1)的时间）输出所有变体，则可以在每个节点中存储引用的数组列表。数组列表存储属于该节点的所有单词的索引，每个值是另一个字典数组列表中的索引。
就像这样:
将单词添加到字典中：
Check in O(word_len) is it in a trie (already added). If not, add to dictionary and remember index in "storage"
if(!inTrie(word)){
dict.push(word);
index = dict.length-1; //zero based indices
// now adding to trie
for each node visited while addition to trie : node.references.push(index)
}
Search:
Go to node with prefix==typed word;
for(int i=0;i<min(curNode.references.length(),10);i++)
print(dict[curNode.references[i]];
更新2
关于 'pa' --> '非常酷的公园'
你绝对应该将短语拆分为单独的单词，以便每个单词在trie中都是“可搜索的”。但是！由于您将短语视为一个单词，因此应将其存储在一个单元格中。
我的意思是：
String phrase = "Very cool parl";
dict.push(phrase);
index = dict.length-1;
parts[] = split(phrase);
for part in parts{
add part - for each node visited while addition of part perform node.references.push(index);
}
<a,b>，其中a = 存储中的索引，b = 短语中的索引。对于简单的单词，b = 0或-1或任何特殊值。a索引放入某个集合中，其中b = 1。像往常一样找到ri节点，迭代引用并将那些a索引放入另一个集合中，其中b = 2等等。找到索引集合的交集。输出存储单词的索引，其中索引属于集合的交集。当您搜索简单单词而不是短语时，您需要迭代所有引用项。
Carpark
Cool Park
Park
Pike's Peak
...
接下来，创建一个包含每个单词条目和指向包含该单词的第一个数组项的索引列表的映射。因此，您的第二个数组将包含：
Carpark, {0}
Cool, {1}
Park, {1,2}
Pike's, {3}
Peak, {3}
将第二个数组按单词排序。因此顺序应为{Carpark,Cool,Park,Peak,Pike's}。
当用户键入“P”时，在单词数组上执行二进制搜索，以找到以“P”开头的第一个单词。您可以从该点开始对数据进行顺序扫描，直到到达不以P开头的单词为止。在访问每个单词时，请将索引列表中引用的单词添加到输出中。（您需要进行一些去重操作，但这很容易。）
二进制搜索是O（log n），因此找到第一个单词将非常快。特别是对于如此少量的数据。如果您对每个键入的字母执行HTTP请求，则通信时间将超过处理时间。没有特别好的理由尝试在服务器端加速此过程。
但是，您可以减少服务器的负载。意识到当用户键入“P”并且客户端从服务器获取数据时，客户端现在拥有可能返回的所有可能字符串，如果用户键入“PA”，则来自“PA”的结果是来自“P”的结果的子集。
所以，如果您修改了代码，使客户端仅在键入第一个字符时向服务器发出请求，您可以在客户端上进行后续搜索。您需要做的就是让服务器返回匹配单词列表（来自第二个数据结构）以及由这些单词索引的匹配短语列表。因此，当用户键入第二个、第三个、第四个等字符时，客户端会执行过滤过程，而无需涉及服务器。试试http://lunrjs.com，它可以让你设置某些属性的提升，如果你喜欢的话。简单而小巧。
如果你需要更简单的东西，你可以看看是否有Levenshtein Distance的任何实现。一个更酷的算法是Soundex，它根据单词的语音特性进行评分。
function TrieNode(ch) {
this.key = ch;
this.isTail = false;
this.children = [];
}
TrieNode.prototype = {
constructor : TrieNode,
/**
* insert keyword into trie
*/
insert : function(word) {
if (word && word.length == 0)
return;
var key = word[0];
if (this.children[key] == null) {
this.children[key] = new TrieNode(key);
}
if (word.length == 1) {
this.children[key].isTail = true;
} else if (word.length > 1) {
this.children[key].insert(word.slice(1));
}
},
/**
* return whether a word are stored in trie
*/
search : function(word) {
if (word && word.length == 0 || this.children[word[0]] == null)
return false;
if (word.length == 1) {
return this.children[word[0]].isTail;
} else {
return this.children[word[0]].search(word.slice(1));
}
},
/**
* NOTICE: this function works only if length of prefix longer than minimum trigger length
*
* @param prefix
* keywords prefix
* @returns {Array} all keywords start with prefix
*/
retrieve : function(prefix) {
var MINIMUM_TRIGGER_LENGTH = 1;
if (prefix == null || prefix.length < MINIMUM_TRIGGER_LENGTH)
return [];
var curNode = this.walk(prefix);
var collection = [];
curNode && curNode.freetrieve(prefix, collection);
return collection;
},
walk : function(prefix) {
if (prefix.length == 1) {
return this.children[prefix];
}
if (this.children[prefix[0]] == null) {
return null;
}
return this.children[prefix[0]].walk(prefix.slice(1));
},
freetrieve : function(got, collection) {
for ( var k in this.children) {
var child = this.children[k];
if (child.isTail) {
collection.push(got + child.key);
}
child.freetrieve(got + child.key, collection);
}
}
}
// USAGE lists below
function initTrieEasily(keywords){
let trie= new TrieNode();
keywords.forEach(word => trie.insert(word));
return trie;
}
var words=['mavic','matrix','matrice','mavis','hello world'];
var trie=initTrieEasily(words);
trie.retrieve('ma'); // ["mavic", "mavis", "matrix", "matrice"]
trie.retrieve("mat") // ["matrix", "matrice"]
trie.search("hello"); // "false"
trie.search("hello world"); //"true"
trie.insert("hello");
trie.search("hello"); // "true"
trie.retrieve("hel"); // ["hello", "hello world"]