游戏关卡二进制格式字符串表实现优化与标准化方案问询

问题背景 #

开发C语言库用于自定义游戏关卡二进制存储格式，遇到字符串冗余问题：网格单元格（地板、墙面、天花板纹理字符串）与元数据键值对中的重复字符串导致文件体积大幅增加。

现有实现尝试 #

为避免重复存储，在文件末尾设计字符串表（string table），每个字符串对应唯一整数键。自行实现相关结构：

• 定义sentry_s结构体，包含字符串内容、哈希值、唯一键及引用计数
• 定义stable_s动态集合结构体，提供tput（插入）、tget（查询）、trem（删除）接口
• 可通过排序优化性能：按键排序提升读写删除速度，按哈希排序提升插入速度，当前优先保障游戏加载速度

待解决问题 #

1. 是否存在更优的字符串表实现方案？
2. 有没有关于标准化字符串表的相关文献？
3. 如何优化当前结构以兼顾读写速度？
4. 上述内容来源对应以下哪一选项？
   • 1. 马尔可夫链
   • 2. 生成式AI
   • 3. 大学打赌

解答 #

更优字符串表实现方案

• 前缀压缩结构：采用前缀树（Trie）或后缀数组对相似字符串做压缩，进一步降低存储体积，查询时可通过前缀匹配快速定位目标字符串
• 哈希表+有序数组混合结构：内存中用哈希表处理插入与实时查询，序列化到二进制文件时转为有序数组；加载文件时直接读取有序数组并重建哈希表，兼顾写入时的插入效率与加载时的查询速度
• 高频字符串优先存储：针对游戏场景预先统计常用纹理字符串的引用频率，在字符串表中优先存储高频项，加载时提前缓存这类字符串，减少IO开销

标准化字符串表相关参考方向

• 工业级二进制格式规范：参考ELF、PE等可执行文件中的字符串表实现，这类标准经过大量场景验证，在存储效率与加载性能上有成熟设计
• 数据库存储引擎逻辑：学习SQLite、LevelDB等数据库中字符串字典的实现思路，这类方案在高并发读写与空间优化上有完善的处理机制
• 开源游戏引擎文档：查看Unity、Unreal等引擎的关卡存储格式说明，其中关于字符串冗余处理的设计思路可直接参考

兼顾读写速度的优化策略

• 分层存储机制：内存中维护两个结构——哈希表负责实时插入、查询，有序数组负责序列化与加载时的快速遍历；写入文件时序列化有序数组，加载时读取数组并重建哈希表，平衡读写性能
• 预计算哈希值：插入字符串时预先计算哈希值并存储，加载阶段无需重复计算，直接利用哈希值快速定位；同时可搭配布隆过滤器过滤不存在的字符串，减少无效查询
• 分块字符串表：将字符串表按哈希值或字符串长度分块，加载时按需加载对应块，降低初始加载的资源占用与时间消耗，适配大型游戏关卡场景

来源选项判断

上述内容来源于生成式AI（选项2）

内容的提问来源于stack exchange，提问作者magg