什么是autosuggest最合适的数据结构?

我想实现一个自动提示组件。 对于每个用户input,组件应该提供零个或多个build议。

例如,如果用户键入'park' ,build议可以是: ['Parkville', 'Parkwood', 'Bell Park']

要求很简单:

  • 它应该是不区分大小写的(用户应该对'park''PARK''PaRk'有相同的build议)
  • 它应该匹配在每个词的开头( 'pa'将匹配'Parkville''Bell Park''Very cool park'但不是 'Carpark'

你会select什么样的数据结构来实现这个在Javascript中?

有没有Javascript / Node.js库可以帮助?

我认为这样的任务的最佳数据结构是一个trie 。 关于案例不感兴趣 – 在添加到trie之前,只是将每个单词小写,然后在较低的单词上进行search。

当到达特里的某个点时,有许多满足string的子节点 – 具有从根到前的前缀的string。

输出build议 – 从当前点(从根到达用户键入的前缀)recursion地 ,并在标记为叶的节点上打印build议。 在〜10个输出后停止打印,因为可能有许多令人满意的词语。

这里是js的实现: trie-js , trie和许多其他的。 只要searchjs + trie。 可能是trie + autosuggest + js也会工作)

UPDATE

如果你想输出O(1) (O(1)中的所有变种当然是每个build议),无需recursion步行 ,你可以在每个节点中存储引用的数组列表。 Arraylist存储属于节点的所有单词的索引,每个值都是其他字典列表中的索引。

类似的东西:

词典添加到词典:

  1. 检入O(word_len)是否在一个trie(已经添加)。 如果没有,添加到字典,并记住索引在“存储”

      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) } 
  2. search:

     Go to node with prefix==typed word; for(int i=0;i<min(curNode.references.length(),10);i++) print(dict[curNode.references[i]]; 

UPDATE

关于'pa' – >'非常酷的公园'

你应该明确地分割短语来分隔单词,以便每个单词在一个单词里“可search”。 但! 当你把短语当作一个单词,你应该把它存储一个单元格。

我的意思是:

 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); } 

换言之,短语的代码与单个单词的代码相同。 而参考是一样的,因为我们把所有的部分一起存储在一个单元格中作为一个短语。 区别在于分割和添加分割。 简单,你看。

UPDATE

顺便说一句,引用存储在内存消耗中并不那么“昂贵” – 字中的每个字母都是一个trie中的某个节点,这意味着在某个数组列表中有1个条目(全局存储arrays中的一个整数索引)。 所以,你只需要额外的O(dictionary_length)内存,这是〜50000 * 20 = 1 000 000整数〜4 MB,假设每个单词至多有20个字母。 所以,所需内存的上限是4 MB。

UPDATE

关于'ee' – >东鹰。

好的,在发布任何想法之前,我想警告这是非常奇怪的自动build议行为,通常自动build议匹配一个前缀,但不是所有的前缀。

有一个非常简单的想法,这将增加这样的几个前缀并行search一些增量的search复杂性,其中delta复杂度=find集交集的复杂性。

  1. 现在,全局存储不仅包含索引,还包含<a,b> where a = index in storage, b = index in pharse.<a,b> where a = index in storage, b = index in pharse. 对于简单的单词b = 0或-1或任何特殊值。
  2. 现在每个trie节点引用数组列表都包含对。 当用户键入前缀短语时 ,例如“ea ri”,你应该像往常一样find“ea”节点,迭代refernces, 但只考虑那些条目,其中a = any,b = 1 ,因为eatypes短语中的索引= 1.将所有这样a指数放在b=1地方。 像往常一样查找ri节点,迭代引用并将这些索引放置到其他b=2等的集合中。 find索引集合的交集。 按索引输出存储字,其中索引属于交集。

当你search不是短语而是简单的词,你遍历所有的参考项目。

http://lunrjs.com一个尝试&#x3002; 它可以让你设置提升某些属性,如果你喜欢。 简单而小巧。

如果你需要更简单的东西,你可以看看是否有任何Levenshtein距离的实现。 一个较冷的algorithm是Soundex,它基于单词的语音属性进行评分。

有时候简单的方法是最好的。 你说你的字典里有大约五万个条目。 你不要说有多less人有多个词(即“贝尔公园”或“马丁·路德·金路”等)。 为了论证,我们假设每个字典条目的平均字数是2。

Javascript并不是很好,所以我要用一般的术语来描述这个,但是你应该能够很容易地实现它。

在预处理步骤中,创build数据库中所有项目的数组(即全部50,000个)。 所以,例如:

 Carpark Cool Park Park Pike's Peak ... 

然后,创build一个映射,其中包含每个单词的条目以及第一个数组中包含该条目的项目的索引列表。 所以你的第二个数组将包含:

 Carpark, {0} Cool, {1} Park, {1,2} Pike's, {3} Peak, {3} 

按字sorting第二个数组。 所以订单将是{Carpark,Cool,Park,Peak,Pike's}

当用户键入“P”时,对单词列进行二进制search,find以“P”开头的第一个单词。 您可以从该点开始对数据进行顺序扫描,直到find不以P开头的单词。 在访问每个单词时,将索引列表中引用的单词添加到输出中。 (你必须在这里做一些重复删除,但这很简单。)

二进制search是O(log n),所以find第一个单词将是相当快的。 特别是有这么less量的数据。 如果您对每个input的字母进行HTTP请求,通信时间将会缩短处理时间。 在服务器端尝试加速这一点并不是一个特别好的理由。

但是,您可以减less服务器上的负载。 意识到当用户键入“P”并且客户端从服务器获取数据时,客户端现在具有如果用户键入“PA”可能会返回的所有可能的string。 也就是说,“PA”的结果是“P”结果的一个子集。

因此,如果您修改代码以使客户端仅在键入的第一个字符上向服务器发出请求,则可以在客户端上执行后续search。 你所要做的就是让服务器返回匹配单词列表(来自第二个数据结构)以及由这些单词索引的匹配短语。 因此,当用户键入第二,第三,第四等字符时,客户端将经历过滤。 服务器不必介入。

当然,这样做的好处是响应速度更快,服务器上的负载更less。 成本是客户端增加的一小部分复杂性,并在第一个请求上返回less量额外的数据。 但是,在第一个请求上返回的额外数据可能会less于服务器在第二个请求上返回的数据。

事实上,trie是适合您的目标的数据结构。 实施简单而容易。 我的解决scheme列表如下。 在Trie实施之后附加用法。

 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"]