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

Question

我将以动态方式插入文件名，大约有 10 亿个名称。此外，我还想存储文件所在的路径，以便进行以下查询:

搜索是否存储文件名以获取其路径。

搜索与子字符串匹配的所有文件的名称，有点像查询(例如，如果搜索 *o*，它将返回我 joel、hola、ola、oso、osea、algo，如果搜索 aa* ，它将返回我 aaab，如果我搜索 *so，它将返回 oso)。

删除文件名。

所以，我试图通过以下方式制作一种特里数据结构:

我有 26 个节点(英文字母 az，我不会将所有节点都放在图像中，因为空格)，这样如果我插入单词“hola”，那么我会从带有字母“h”的节点到节点创建一条边带有字母 'o' 并且其边缘的数据为 1，因为该数字表示深度的级别。此外，在存储“a”的节点中，我将有一个映射结构来存储文件的路径，这是因为我肯定会在包含字母“a”的节点中存储很多路径.

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



我这样做是因为我不想有很多带有 sama 字母的节点(例如 a、b 等)，但问题是我有很多边和结构需要



内存字节(我用 C++ 编程)，其中 w 是一个大小为 的字符串.

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

How can I improve this? Is it any way to reduce the number of edges? or there exists a better structure and way to do this? I am very open to hear of any suggestion.

Answer 1

过去我解决了一个有点类似的问题，用于存储填字游戏的单词表，并非常快速地找到单词。我称之为“ super 索引”。我的主要目标是速度，而不是存储大小，但最初的问题并没有说明作者认为什么是“改进”:也许是大小，也许是速度，也许是算法复杂性。我的方法在相对较小的复杂性下产生了巨大的速度，但在存储大小方面却有相当大的节省。方法如下:

使用树，而不是图。树中的每个节点最多有 26 个“条目”。每个条目代表字母表中的一个字母，并包含指向子节点的链接，或者，如果条目属于叶节点，则指向“有效负载”的链接，在您的情况下是“路径”。因此，当节点包含给定字母的条目时，这表示在该位置存在带有该字母的“名称”。 (位置是树中节点的深度。)

按名称长度分隔所有名称，因为这很容易确定。为每个名称长度使用完全独立的树。这意味着在每棵树中，所有叶节点都处于完全相同的深度，并且树中包含附加数据(在您的情况下为路径)的唯一节点是叶节点。这使事情变得非常简单。

所以，搜索算法如下:

在不同名称长度的所有不同树中，使用与您要搜索的“名称”长度相对应的树。

从您要查找的“名称”的第一个字母开始，并在树的根节点处。

在当前节点中查找当前字母的条目；如果不存在这样的条目，则未找到该名称，已完成。否则:

如果我们到达了一个叶节点，那么名称已经找到，返回有效载荷，在你的情况下是一个“路径”。否则:

移至您要查找的单词的下一个字母；按照从当前节点中找到的条目到下一个子节点的链接；转到第 3 步。

如您所见，这是一个相当简单的算法，并且保证非常快。如果没有任何进一步的优化，存储要求将是每个名称存储一个“条目”的顺序，并且一个“条目”将由一个字符和一个指针组成。

然后，有许多可能的优化。例如，“条目”在推理您的数据结构时可能是有用的概念，但在实际实现中可能会完全消失:在每个节点中，您可以有一个“摘要”32 位机器字，其中每个前 26 位表示节点中是否存在字母表的相应字母，然后是指向子节点(或有效载荷)的指针数组，其中包含与摘要字中设置的位一样多的元素。