子串索引许多类似的字符串

我有一个大型的数据集合，在这种情况下，想象一下所有包含文件路径的80,000+数组String。子串索引许多类似的字符串

作为文件路径，这意味着它们的大群组以相同的路径开始，例如，我有超过50,000个文件从"/dataset1/subsetAA/childX/"开始。

我想允许自由文本搜索这些路径。现在我做一个简单的断言，看起来像这样：

foreach(String term in terms) 
    if(path.IndexOf(term, StringComparison.OrdinalIgnoreCase) == -1) 
     return false; 
return true;

我保存的搜索结果，因为它们可以键入，所以你越键入它变得更快，但是最初的几个搜索（例如“f”>“fo”>“foo”）在快速机器上可能需要3或4秒。

我想建立一个子串索引，消除了我需要使用IndexOf，最好是利用通用路径来减少索引大小，我不想消耗太多的内存。

2013-03-14 Dai

了解被称为特里数据结构：http://en.wikipedia.org/wiki/Trie

这不正是你想要的东西，它需要很多的字符串，并建立一棵树了常见的前缀，用绳子，每片叶子是下面的字符串系列在其父母的前缀（您可以通过连接其所有的父母对什么是在叶建，以节省空间）

2013-03-14 05:07:47 Patashu

这有帮助，但是如何从任何节点搜索Trie？例如如果“foo”和“foz”在Trie中，我怎样才能搜索“oz”，而无需首先为每个“o”详尽搜索树，或者这是不可避免的？（尽管我可以低效地使用'Dictionary >'来查找起点）。有什么想法吗？ – Dai 2013-03-14 06:43:43

尝试不设计为从任何节点启动。更多的思考问题，我很喜欢dasblinkenlight的答案:) – Patashu 2013-03-14 07:44:52

但是最初几个搜索（如“F”>“FO”>“的foo“）甚至可以在快速机器上花费3或4秒。

这是您需要优化的唯一方法。创建一个非常简单的结构，它由三个散列集组成 - 对于单个字符，对于两个字符和对于三个字符。单字符散列索引的每个元素都将包含一个包含索引字符的元素列表;双字符散列索引的每个元素都将包含一个包含索引字符对的元素列表;三字符索引也会这样做。

当输入搜索的初始部分时，使用索引查找。例如，当键入f时，您将从第一个哈希表中获取包含f的项目列表。随着用户继续输入，您将从第二个索引获取"fo"密钥的项目，然后从第三个索引获取"foo"密钥。

只要您获得四个或更多字符，就会根据IndexOf返回搜索结果，使用搜索词的最后三个字符，根据三个字符的子字符串在散列中查找初始列表。您从列表中获得的项目数量相对较少，因此搜索速度会更快。

另一个优化应该是一旦有足够的项目显示给用户就停止搜索。例如，如果用户键入"tas"（来自"dataset"），那么您的三个字符的索引会给你50000个点击。抓住前20个（或者你需要显示的数量），然后跳过剩下的部分：用户会尽快完善他们的搜索，所以附加项目很快就会被丢弃。

2013-03-14 05:18:27 dasblinkenlight

回答