java - 使用什么数据结构来索引数据以进行部分 %infix% 搜索？

Question

想象一下，您有一个巨大的数据缓存，要通过 4 种方式进行搜索：

1. 完全符合
2. 字首％
3. ％后缀
4. %中缀%

我将Trie用于前 3 种类型的搜索，但除了顺序处理大量元素之外，我不知道如何处理第 4 种类型的搜索。

Answer 1

如果您的数据集很大，请使用像Apache Solr这样的搜索平台，这样您就不会陷入性能混乱。

Answer 2

对于＃4，我在想如果您预先计算每个字符的出现次数，那么您可以在该表中查找在搜索字符串中至少有相同次数出现的字符。

该算法的效率可能取决于数据的性质和搜索字符串。在这里给出一些例子以获得更好的答案可能会很有用。

Answer 3

您可以为 2（键按正常顺序）和 3（键反向）构建可导航的地图或集合（例如 TreeMap 或 TreeSet）

对于选项 4，您可以构建一个集合，其中每个起始字母都有一个键。您可以根据您的要求简化此操作。这可能会导致使用更多空间，但会获得 O(log n) 查找时间。