从文件路径列表构建目录树

Question

我正在寻找一种高效的方法，将文件列表解析为树形结构。这个列表可能包含数亿个文件路径。

暴力解决方案是在每个目录分隔符出现的位置上拆分每个路径，并通过字符串比较遍历整个树，在目录和文件条目中添加内容，但这样会非常慢。

输入数据通常按字母顺序排序，因此列表可能如下所示：

C:\Users\Aaron\AppData\Amarok\Afile C:\Users\Aaron\AppData\Amarok\Afile2 C:\Users\Aaron\AppData\Amarok\Afile3 C:\Users\Aaron\AppData\Blender\alibrary.dll C:\Users\Aaron\AppData\Blender\and_so_on.txt

从这个排序中，我的自然反应是在进行缓慢的字符串比较之前，以某种方式将目录列表分成组。我真的不确定。我会感激任何想法。

编辑：如果可能的话，最好从上到下延迟加载此树。

- Abignale

---

你认为为什么会特别慢？如果有n行，每行最多有m个字符（因此有<= m个目录组件），这只需要O(nm)的时间。对于每一行，将其插入到深度最多为m的trie中。nm是输入数据的大小，因此它是线性的。 - p00ya

请参见以下链接：https://stackoverflow.com/questions/45687209/convert-file-path-list-to-tree - YonghanKim

你可能会在这里找到帮助，https://stackoverflow.com/questions/45687209/convert-file-path-list-to-tree - YonghanKim

Answer 1

你别无选择，只能进行完整的字符串比较，因为你无法保证字符串可能会有所不同。有一些技巧可以稍微加快速度：

• 如David所说，形成一棵树，但是从上一个插入点开始搜索新的插入点（也许可以借助某种matchingPrefix例程来告诉你新的插入点在哪里不同）。
• 如果可能有很多文件并且需要计算重复项，则对每个级别的树使用哈希表。（否则，将其附加到堆栈中就可以了。）

- Rex Kerr

Answer 2

如果可能的话，你可以使用tree命令生成你的树形结构，在这里。

- ghostdog74

Answer 3

为了利用输入数据的“通常排序”属性，从上次插入文件的目录开始遍历：将当前路径名的目录名称与上一个进行比较。如果它们匹配，您可以在此处插入，否则弹出一个级别并重试。

- David Gelhar