为许多类似字符串编制索引的子字符串

本文关键字：字符串 索引 许多类 | 更新日期: 2023-09-27 18:03:44

我有一个大的数据集合，在这种情况下，想象一个80000多个String数组，所有数组都包含文件路径。

作为文件路径，这意味着它们中的大组以相同的路径开始，例如，我有50000多个文件以"/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，最好是一个利用公共路径来减少索引大小的索引，我不想消耗太多内存。

为许多类似字符串编制索引的子字符串

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

它可以做你想要的事情，它使用许多字符串，并用常见的前缀构建一个树，每个叶都是一个跟随其父代前缀序列的字符串(为了节省空间，你可以通过将其所有父代连接到叶中的前缀来构建(

然而，即使在速度很快的机器上，最初的几次搜索(例如"f">"fo">"foo"(也可能需要3或4秒。

这是你唯一需要优化的东西。创建一个非常简单的结构，它由三个哈希集组成——单个字符、两个字符和三个字符。一个字符散列索引的每个元素将包含包括索引字符的元素列表；两个字符的散列索引的每个元素将包含元素列表，该元素列表包括被索引的字符对；三个字符的索引也是如此。

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

一旦获得四个或更多字符，就返回到基于IndexOf的搜索，使用搜索项的最后三个字符在基于三个字符子字符串的哈希中查找初始列表。从列表中获得的项目数量相对较少，因此搜索速度应该更快。

另一个优化应该是在你有足够的项目显示给用户后立即停止搜索。例如，如果用户键入"tas"(来自"dataset"(，则三个字符的索引将为您提供50000次点击。抓住前20个(或你需要显示的数量(，跳过剩下的：用户会很快完善他们的搜索，所以额外的项目很可能很快就会被丢弃。

相关文章：