存储大前缀树的最佳方法

本文关键字：最佳 方法 前缀 存储 | 更新日期: 2023-09-27 17:57:10

我将编写代表AI的程序，用于与玩家玩棋盘游戏。我想将每个玩过的游戏都保留在前缀树中，以搜索类似的游戏。但我担心这棵树会变得太大而无法保存在记忆中。那么存储它的最佳方法是什么。并且能够快速搜索它。我不认为将其写入文件是好的解决方案。可能在某个DB之王？

存储大前缀树的最佳方法

您要查找的是嵌入式数据库，其中大多数都是用C++编写的，但也有一些具有 C# 包装器。我推荐Berkeley DB for .NET（它是Oracle的Berkeley DB的包装器）。

我建议为每个前缀树

生成一个唯一的哈希，其中生成的哈希将具有正确表示相似前缀树的位置：换句话说，两个相似前缀树的哈希应该非常接近。您所指的游戏被称为井字游戏，因此散列类似的井字游戏应该很容易，这里有一些参考资料（我并没有真正阅读它们，我只是快速搜索了"散列井字游戏"，这就是结果）：

  • 我认为这可能是java示例
  • TicTacToe战略削减
  • http://cg.scs.carleton.ca/~luc/1997notes/topic14/

然后，哈希存储在伯克利数据库中，前缀树存储在辅助文件中，或者如果需要，也可以将其存储在值中。由于 Berkeley DB 存储键值对，因此您可以将哈希设置为键，并将值设置为任何内容（即前缀树或包含前缀树的 aux 文件的路径）。然后，您要做的就是查找类似的哈希并从 aux 文件中检索相应的树。

Berkeley DB 按顺序存储类似的密钥，因此您可以依靠它不会移动密钥并破坏哈希的位置这一事实。由于局部性不会被破坏，因此您可以进行额外的优化并检索大页的键值对，并减少在磁盘上进行的查找和查找次数。

相关文章：