javascript - 自动提示最合适的数据结构是什么？

Question

我想实现一个自动提示组件。对于每个用户输入，组件应该提供零个或多个建议。

例如，如果用户输入 'park'，建议可以是:['Parkville', 'Parkwood', 'Bell Park']。

要求很简单:

• 它应该不区分大小写(用户应该得到与 'park'、'PARK' 和 'PaRk' 相同的建议)
• 它应该匹配每个单词的开头('pa' 将匹配 'Parkville'、'Bell Park' 和 '非常酷的公园'，但不是 'Carpark')

您会选择哪种数据结构在 Javascript 中实现它？

是否有任何 Javascript/Node.js 库可以提供帮助？

Answer 1

我认为此类任务的最佳数据结构是 trie .关于不区分大小写 - 在添加到 trie 之前将每个单词小写并对小写单词执行搜索。

当您到达 trie 的某个点时，有一些子 Node 是满足字符串 - 具有从根到当前点的前缀的字符串。

输出建议 - 从当前点(从根到达用户输入的前缀)递归地 walk 并在标记为叶子的 Node 上打印建议。在 ~10 个输出后停止打印，因为 trie 可能有很多令人满意的单词。

这是 js 实现:trie-js , trie和许多其他人。搜索js+trie就可以了。可能trie+autosuggest+js也行)

更新 1

如果要输出O(1)中的所有变体(当然，每个建议的 O(1))，如果没有递归遍历，您可以在每个 Node 中存储引用数组列表。 Arraylist存储属于 Node 的所有单词的索引，每个值都是其他字典araylist中的索引。

类似的东西:

向字典添加单词:

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. 搜索:

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

换句话说，短语的代码与单个单词的代码相同。和引用是一样的，因为我们将所有部分一起存储在一个单元格中作为一个短语。区别在于按部分拆分和添加pharse。很简单，你看。

更新 3

顺便说一句，引用存储在内存消耗方面并不那么“昂贵”——单词中的每个字母都是 trie 中的某个 Node ，这意味着某个数组列表中有 1 个条目(该单词在全局存储数组中的一个整数索引)。所以，你只需要额外的 O(dictionary_length) 内存，即 ~ 50000*20 = 1 000 000 个整数 ~ 4 MB，假设每个单词最多有 20 个字母。因此，所需内存的上限为 4 MB。

更新 4

关于'e e' --> 东鹰。

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

有一个非常简单的想法，它会增加搜索复杂度，这样多个前缀并行搜索对于一些增量，其中增量复杂度 = 查找集交集的复杂度。

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

当您搜索的不是短语而是简单的词时，您会遍历所有 引用项。