javascript - autosuggest 最合适的数据结构是什么？

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

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

要求很简单:

应该不区分大小写(用户应该得到相同的 'park' 、 'PARK' 和 'PaRk' 建议)

它应该在每个单词的开头匹配( 'pa' 将匹配 'Parkville' 、 'Bell Park' 和 'Very cool park' 、 但不匹配 'Carpark' )

你会选择什么数据结构来在 Javascript 中实现它？

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

最佳答案

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

当您到达特里的某个点时，有许多满足字符串的子 Node - 字符串的前缀从根到当前点。

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

这是 js 实现: trie-js 、 trie 和许多其他实现。只需搜索 js+trie。可能是 trie+autosuggest+js 也可以工作)

更新

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

类似的东西:

向 dict 添加单词:

检查 O(word_len) 是否在一个特里(已添加)。如果没有，请添加到字典并记住“存储”中的索引

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

搜索:

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

更新

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

您应该明确地将短语拆分为单独的单词，以便每个单词都可以在特里“搜索”。但!当您将短语视为一个词时，您应该将其存储在一个单元格中。

我是说:

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

换句话说，短语的代码与单个单词的代码相同。引用是相同的，因为我们将所有部分作为一个短语存储在一个单元格中。不同之处在于分部分割和相加。很简单，你看。

更新

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

更新

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

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

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

现在全局存储不仅包含索引，还包含成对 <a,b> where a = index in storage, b = index in pharse. 对于简单的单词 b=0 或 -1 或任何特殊值。

现在每个 trie Node 引用 arraylist 都包含对。当用户输入前缀短语时，例如“ea ri”，您应该像往常一样找到 'ea' Node ，遍历引用 但只考虑那些条目，其中 a=any, b=1 ，因为类型中的 ea 索引短语 = 1. 将所有这样的 a 索引放在 b=1 的某个集合中。像往常一样找到 ri Node ，遍历引用并将这些 a 索引放到 b=2 等其他集合中。查找索引集的交集。按索引输出存储词，其中索引属于集合的交集。

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

关于javascript - autosuggest 最合适的数据结构是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29966149/