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

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

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

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

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

所以，搜索算法如下：

1. 在不同名称长度的所有不同树中，使用与您要搜索的“名称”长度相对应的树。
2. 从您要查找的“名称”的第一个字母开始，位于树的根节点。
3. 查找当前节点中当前字母的条目；如果不存在这样的条目，则未找到该名称，完成。否则：
4. 如果我们到达了叶节点，则已找到名称，返回有效负载，在您的情况下是“路径”。否则：
5. 转到您要查找的单词的下一个字母；沿着当前节点中找到的条目到下一个子节点的链接；转到步骤 3。

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

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