java - 实现一个带有子序列匹配的 sortedMap

Question

我想实现一个带有键和值的 sortedMap，以便可以通过提供一些子序列来搜索键。例如， map 包含 3 个条目:

abcd -> obj1
def -> obj2
abccd -> obj3

对于查询ac，结果应该是包含第一个和第三个条目的子图，但是对于查询acc，应该只返回第三个条目。

我应该在内部使用什么样的数据结构来有效地返回这样的子图？例如，Treemap 将键存储在树(trie)中以根据前缀高效地返回子图？

Answer 1

总结一下我在评论中写的内容，我会做如下:

1. 使用条目 [2-char subsequence -> list of words] 创建附加索引 HashMap。
2. 另外:从给定的单词生成所有不同的 2-char 子序列，将这个单词添加到索引映射的每个相应条目。
3. 查询时:从一个查询中生成所有不同的 2-char 子序列，在其中找到对应于索引映射中最短列表的一个，取这个列表。通过full query对其进行过滤，并从主 map 中收集相应的值。

如果查询由一个字符组成，则执行全扫描。我相信这比为单个字符创建额外的索引具有更好的空间/复杂性，尤其是当很少有 1 个字符的查询时。