windows - 压缩的文件路径数组和随机访问

Question

我正在开发文件管理 Windows 应用程序。该程序应保留磁盘上所有文件和文件夹的路径数组。例如:

0 "C:"  
1 "C:\abc"  
2 "C:\abc\def"  
3 "C:\ghi"  
4 "C:\ghi\readme.txt"  

“原样”的数组将非常大，因此应该将其压缩并存储在磁盘上。但是，我想随机访问它:

1. 通过索引检索数组中的任何路径(例如，RetrievePath(2) = "C:\abc\def")
2. 查找数组中任何路径的索引(例如，IndexOf("C:\ghi") = 3)
3. 向数组添加新路径(任何现有路径的索引不应更改)，例如，AddPath("C:\ghi\xyz\file.dat")
4. 重命名数据库中的一些文件或文件夹；
5. 删除现有路径(同样，任何其他索引不应更改)。
   例如，从数据库中删除路径 1 "C:\abc" 并且仍然有 4 "C:\ghi\readme.txt"。

有人可以建议一些好的算法/数据结构/想法来做这些事情吗？

编辑:
目前我想出了以下解决方案:

0 "C:"
1 "[0]\abc"
2 "[1]\def"
3 "[0]\ghi"
4 "[3]\readme.txt"

即公共(public)前缀被压缩。

1. RetrievePath(2) = "[1]\def"= RetrievePath(1) + "\def"= "[0]\abc\def"= RetrievePath(0) + "\abc\def"= "C:\abc\def"

2. IndexOf() 也可以迭代工作，类似这样:

   IndexOf("C:") = 0
   IndexOf("C:\abc") = IndexOf("[0]\abc") = 1
   IndexOf("C:\abc\def") = IndexOf("[1]\def") = 2
   

3. 要添加新路径，比如 AddPath("C:\ghi\xyz\file.dat")，首先应该添加其前缀:

   5 [3]\xyz
   6 [5]\file.dat
   

4. 重命名/移动文件/文件夹仅涉及一次替换(例如，将 [0]\ghi 替换为 [1]\klm 将重命名目录 "ghi" 到 "klm" 并将其移动到目录 "C:\abc")

5. DeletePath() 涉及将其(以及所有子路径)设置为空字符串。将来，它们可以被替换为新的路径。
   在 DeletePath("C:\abc") 之后，数组将是:

   0 "C:"
   1 ""
   2 ""
   3 "[0]\ghi"
   4 "[3]\readme.txt"
   

整个数组仍然需要加载到 RAM 中才能执行快速操作。例如，总共有 1000000 个文件和文件夹，平均文件名长度为 10，则该数组将占用超过 10 MB。
此外，函数 IndexOf() 被迫按顺序扫描数组。

编辑 (2):我刚刚意识到我的问题可以重新表述:
我如何为磁盘上的每个文件和每个文件夹分配唯一的整数索引，以便我能够通过索引快速找到文件/文件夹，已知文件/文件夹的索引，并执行基本的文件操作而无需更改许多索引？

编辑 (3): Here是一个关于类似但与 Linux 相关的问题。建议使用文件名和内容哈希来识别文件。是否有一些特定于 Windows 的改进？

Answer 1

您的解决方案似乎不错。您还可以尝试使用临时技巧来压缩更多内容，例如仅对常见字符(如“\”)、驱动器号、可能是常见文件扩展名等使用一些位。您还可以查看尝试 ( http://en.wikipedia.org/wiki/Trie)。

关于您的第二次编辑，这似乎符合哈希表的特征，但这是用于索引，而不是压缩存储。