从.NET中的10000个项目中自动完成

我有一个内存约10K对象的集合。我想让用户能够键入部分项目名称或描述并显示自动完成列表。什么是有效的方法来做到这一点？我真的需要尽可能快的响应时间，用户速度非常快。从.NET中的10000个项目中自动完成

非常感谢，玛丽

2011-01-22 Mary Shields

UI是用什么构建的？ Windows Forms，WPF，一个来自ASP.Net的Web应用程序？ – 2011-01-22 23:16:05

这是ASP MVC应用程序，网页将通过控制器在按键JSONP上请求。 – 2011-01-23 00:27:48

这不是一个.net特定的答案，但通常解决此问题的方法是创建一个索引并预先计算自动完成列表，这些列表存储在maps-of-maps-map- of-of-maps-of-lists结构（见下文）。它基本上是一个执行trie。

基本上，你有一个哈希映射（REAL散列映射，以O（1）的实现），其中键是可能的子串。对于每个键字符串“XYZ”，它指向包含所有包含“XYZ”的对象的数据的映射;使用键“XYZA”，“XYZB”等...然后，一旦您达到N个字符（N个地图深），您的最后一个地图值就是包含该N个字符串的所有实际对象的列表。

然后你回顾一下你的集合，并且为每个对象计算长度为M到N的所有可能的子字符串（我假设你只想在输入> = M个字符时自动完成;太长的子字符串是无用的）地图。

的数据结构如下：

TopMap => { 
      'A' => Map_for_A 
      'B' => Map_for_B 
       ... 
      } 

Map_For_A => { 
      'AA' => Map_for_AA 
      'AB' => Map_for_AB 
       ... 
      } 
Map_For_AB => { 
      'ABC' => Map_for_ABC 
      'ABD' => Map_for_ABD 
       ... 
      } 
Map_For_ABD => { 
      'ABDE' => List_For_ABDE 
      'ABDX' => List_For_ABDX 
      }

来源

2011-01-22 23:22:10 DVK

安排您的数据作为Trie。

来源

2011-01-22 23:18:27

具体而言，如果需要全文搜索，则使用后缀树：http://en.wikipedia.org/wiki/Suffix_tree – 2011-01-22 23:22:16

的最快方式是使用例如字面控制下降这些值在一个网页的JavaScript变量（字符串数组）说，然后使用这样的：

http://docs.jquery.com/Plugins/autocomplete#Example

来源

2011-01-22 23:19:31 Luis

10'000个对象确实不多。

以下就足够了。

foreach(cItem Item in ItemList) 
{ 
    if(regex.match(Item.Name, "expression")) 
     //Add Item to autocomplete results; 


     //Break if more than 10 matches 

} 



for(i = 0; i < 10 && i < autocomplete_results.Length; ++i) 
{ 
      // display first 10 matches 
}

来源

2011-01-22 23:19:40

通常你不希望给用户，例如每一种可能的选择 - 如果项目的列表是一组名称，输入字母“E”，并在其中获得每一个名字用E在下拉菜单中对于用户而言既不高效也不快速执行。您是否考虑过仅在用户输入3个（或更多）字符时提示结果？

如果这组项目是静态的，这将（可能）允许您预先计算每个独特的3或4个字符集的项目集，并将它们存储在列表字典中，如下所示：

Dictionary<String, List<Item>> itemsByKey;

来源

2011-01-22 23:19:43

您可以使用Trie数据结构（或前缀树）来保存项目的名称。请参阅维基百科上非常详细的article，其中描述了此数据结构的原理并提供了一些基准测试结果。

Trie树的每个节点可以被实现为对应于各个数据串的第N位置时，其中N是节点的深度字符的排序列表。然后您可以使用binary search高效地执行数据查找。

，使其在工作你的情况，只是一味地对应于先前输入前缀的最后一个节点。当用户键入下一个字母时，只需搜索相应的直接子。各自的子树内

一切都是可能的匹配，因此可以提供给用户。为了使自动填充更加智能化，您可以跟踪各个数据项的频率并仅显示最常见的数据项。

来源

2011-01-22 23:21:08

你没有说你正在使用的用户界面。如果您使用ASP.NET Web表单，则可以使用AjaxControlToolkit中的“自动完成”控件。

在这里你可以找到一个演示：http://www.asp.net/ajax/ajaxcontroltoolkit/Samples/AutoComplete/AutoComplete.aspx

来源

2011-01-22 23:22:30

从.NET中的10000个项目中自动完成

回答

相关问题