一种基于路径节点标识的文件检索方法和装置与流程

摘要: 本发明涉及嵌入式系统,具体涉及一种基于路径节点标识的文件检索方法和装置。背景技术:1、在嵌入式系统领域,只读文件系统(如romfs、cramfs、squashf...
一种基于路径节点标识的文件检索方法和装置与流程

本发明涉及嵌入式系统,具体涉及一种基于路径节点标识的文件检索方法和装置。

背景技术:

1、在嵌入式系统领域,只读文件系统(如romfs、cramfs、squashfs等)被广泛用于系统资源与固件文件的统一管理。当前主流的文件检索方法普遍采用基于字符串路径的访问机制,即用户或系统通过提供完整的路径字符串来定位目标文件。为实现快速检索,现有技术通常采用以下三种方式:其一,直接存储完整路径字符串,在访问时逐级进行字符串比较以匹配目标路径;其二,基于路径字符串计算哈希值构建哈希索引表,通过哈希查找加速文件定位;其三,在系统启动阶段将全部索引结构加载至ram中,以空间换时间提升访问速度。

2、现有技术中,文件路径以完整字符串形式存储于索引结构中,随着文件数量增多,路径字符串累积占用大量存储空间,对rom和ram资源造成显著负担;文件检索过程依赖逐级字符串比较或路径字符串的哈希计算,字符串比较的时间复杂度随路径深度和名称长度线性增长,哈希计算亦需遍历整个路径字符串,cpu开销较大,不利于嵌入式设备的低功耗运行。此外,基于哈希的索引方式存在哈希冲突问题,冲突处理机制进一步增加了检索的复杂性和不确定性,且哈希值与路径层级结构之间缺乏天然的绑定关系,无法利用目录层级特性优化检索路径。再者,启动阶段全量加载索引至ram的方式虽可提升访问速度,但对于中等规模文件系统而言,索引结构可能达到数百kb甚至数mb级别,严重挤占本已紧张的运行内存。

3、综上,亟需一种能够在嵌入式环境下减少字符串依赖、轻量级且与路径层级结构强绑定的文件索引构建与检索方案。

技术实现思路

1、有鉴于此,本发明实施例提供一种基于路径节点标识的文件检索方法和装置,以至少解决现有的嵌入式文件检索字符串依赖强、内存算力开销高的问题。

2、本发明实施例提供以下技术方案:

3、本发明实施例提供一种基于路径节点标识的文件检索方法,包括:

4、对原始文件路径进行规范化处理和层级拆分,以得到有序路径元素序列,所述有序路径元素序列包括若干层级路径元素;

5、将根目录定义为根节点并设定根节点标识,通过确定性映射函数递推计算各所述层级路径元素对应的定长路径节点标识,以生成路径pni序列;

6、以所述根节点为图起点,根据所述路径pni序列的层级顺序逐级插入pni节点并建立父子关系边,以构建得到有向图索引结构,其中,对应路径末端的所述pni节点关联有文件条目指针;

7、根据所述有向图索引结构,在文件访问时按照目标路径对应的所述路径pni序列逐级匹配所述pni节点,匹配至目标pni节点后获取其关联的所述文件条目指针,依据所述文件条目指针完成文件内容读取。

8、优选地,对所述原始文件路径进行规范化处理包括去除冗余信息和歧义结构。

9、优选地,所述去除冗余信息和歧义结构具体包括:去除路径中的重复路径分隔符,解析路径中的当前目录符号与上级目录符号,将路径统一转换为标准层级结构。

10、优选地,所述将根目录定义为根节点并设定根节点标识,通过确定性映射函数递推计算各所述层级路径元素对应的定长路径节点标识,以生成路径pni序列包括:

11、以所述根节点标识作为递推初始参考值;

12、对于当前所述层级路径元素,获取其上一层级对应的父节点pni值,将所述父节点pni值与当前所述层级路径元素名称共同输入所述确定性映射函数,计算得到当前所述层级路径元素对应的定长路径节点标识;

13、将当前所述层级路径元素对应的所述定长路径节点标识作为下一层级的所述层级路径元素递推计算的所述父节点pni值,并重复上述计算步骤,直至所有层级路径元素均被处理完成;

14、将各所述层级路径元素对应的定长路径节点标识按路径顺序组合,生成所述路径pni序列。

15、优选地,所述确定性映射函数为crc32、fnv或自定义混合哈希函数中的任意一种,其输出为固定长度整数或定长编码值;和/或

16、对于同一父节点下的相同层级路径元素,所述确定性映射函数生成唯一且确定的定长路径节点标识。

17、优选地,所述有向图索引结构的构建方式为:

18、以所述根节点为图起点,将所述路径pni序列中的每个定长路径节点标识作为pni节点,并按路径层级顺序依次插入,并在相邻层级的pni节点之间建立父子关系边;

19、每个所述pni节点至少包含pni标识值、子节点索引列表、节点类型标识以及文件条目指针;其中对应路径末端的所述pni节点,其文件条目指针关联至对应文件元数据。

20、优选地,所述按路径层级顺序依次插入pni节点的过程具体包括:

21、从所述根节点开始,按照所述路径pni序列的层级顺序逐级检查对应的所述pni节点是否已存在;

22、若对应的所述pni节点不存在,则创建新的所述pni节点,并在新的pni节点与上一层级的所述pni节点之间建立父子关系边;若对应的所述pni节点已存在,则复用已有的pni节点,维持原有父子关系边。

23、优选地,按照目标路径对应的所述路径pni序列逐级匹配所述pni节点的过程具体包括:

24、以所述根节点作为遍历起始节点,按照所述路径pni序列的层级顺序,依次在当前节点的子节点索引列表中查找匹配的pni节点;

25、当前层级匹配成功后,进入对应的所述子节点并继续匹配下一层级的所述pni节点;

26、直至所述路径pni序列中的全部节点均匹配完成,得到目标pni节点。

27、优选地,所述依据所述文件条目指针完成文件内容读取的过程具体包括:

28、通过所述文件条目指针定位至文件条目区中的对应文件元数据记录,获取所述文件元数据的存储位置信息;

29、根据所述存储位置信息访问文件内容存储区,读取对应文件数据并输出。

30、本发明实施例还提供了一种基于路径节点标识的文件检索装置,包括路径规范化模块、路径分割模块、pni生成模块、pni图构建模块、图遍历匹配模块、文件定位模块和数据读取模块;

31、所述路径规范化模块,用于对原始文件路径进行规范化处理;

32、所述路径分割模块,用于对规范化处理后的文件路径进行层级拆分,得到有序路径元素序列,所述有序路径元素序列包括若干层级路径元素;

33、所述pni生成模块,用于将根目录定义为根节点并设定根节点标识,通过确定性映射函数递推计算各所述层级路径元素对应的定长路径节点标识,以生成路径pni序列;

34、所述pni图构建模块,用于以所述根节点为图起点,根据所述路径pni序列的层级顺序逐级插入pni节点并建立父子关系边,以构建得到有向图索引结构,其中对应路径末端的所述pni节点关联有文件条目指针;

35、所述图遍历匹配模块,用于在文件访问时,按照目标路径对应的所述路径pni序列在所述有向图索引结构中逐级匹配所述pni节点,得到目标pni节点;

36、所述文件定位模块,用于获取所述目标pni节点关联的文件条目指针;

37、所述数据读取模块,用于依据所述文件条目指针完成文件内容读取。

38、与现有技术相比,本发明实施例采用的上述至少一个技术方案能够达到的技术效果至少包括:

39、本发明的基于路径节点标识的文件检索方法,通过对文件路径进行规范化拆分与层级递推式路径节点标识生成,将传统字符串路径转换为定长路径节点标识序列,并以此构建与路径层级强绑定的有向图索引结构,在文件访问时依托标识序列逐级匹配完成文件定位读取,既彻底消除了运行阶段对路径字符串的存储、比较及哈希计算依赖,规避了哈希冲突带来的处理开销与不确定性,又使文件检索复杂度仅与路径深度相关、不受文件总量影响,同时有效降低了运行内存占用与cpu运算负荷,形成了轻量、确定且低资源消耗的文件检索机制,能够良好适配资源受限的嵌入式应用场景。