用于搜索文件名称并获取其路径的数据结构

Question

我将以动态方式插入文件名，大约直到10亿个名字。此外，我还想存储文件所在的路径，以便执行以下查询：

• 搜索是否存储文件名以获取其路径。
• 搜索与子字符串匹配的所有文件的名称，有点像查询（例如，如果搜索* o *，它将返回我joel，hola，ola，oso，osea，algo，如果搜索aa * ，它会回复我aaab，如果我搜索*所以，它将返回oso）。
• 删除文件名。

所以，我试图通过以下方式创建一种trie数据结构：

我有26个节点（英文字母az，我不打算将所有节点放在图像中，因为空间），这样如果我插入单词“hola”，那么我从节点创建一个边缘，字母'h'到节点字母'o'，其边缘有数据1，因为这个数字代表深度的水平。此外，在存储'a'的节点中，我将有一个映射结构以存储文件的路径，这是因为我肯定会在包含字母'a'的节点中存储很多路径。

话虽如此，我插入了以下词语：joel，hola，ola，oso，osea，algo，aaab。

我之所以这样做，是因为我不希望有很多带有sama lettres的节点（例如a，b等），但问题是我有很多边缘和sctructure需求

内存字节（我用C ++编程），其中w是一个大小的字符串。

如您所见，如果我搜索文件“jola”（未插入）的名称，则不会返回任何路径，这告诉我们不存储此类文件。

我怎样才能改善这个？是否可以减少边缘数量？还是有更好的结构和方法来做到这一点？我很乐意听到任何建议。

Answer 1

您既可以使用DAG（有向无环图），也可以使用不相交的集合操作技术（快速查找技术（*主要目标是查找））