1

我有大量数据，在这种情况下，想象一个String包含所有文件路径的 80,000 多个数组。

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

4

2 回答 2

2

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

它完全符合您的要求，它需要许多字符串并使用字符串从公共前缀中构建一棵树，每个叶子都是一个字符串，遵循其父级中的一系列前缀（您可以通过将其所有父级连接到什么来构建在叶子中，以节省空间）

于 2013-03-14T05:07:47.813 回答
2

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

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

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

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

另一个优化应该是在您有足够的项目显示给用户时立即停止搜索。例如，如果用户键入"tas"(from "dataset")，您的三字符索引将为您提供 50000 次点击。抓取前 20 个（或您需要显示的任意数量），并跳过其余的：用户将很快优化他们的搜索，因此其他项目可能很快就会被丢弃。

于 2013-03-14T05:18:27.143 回答