存储和检索DAWG数据结构以实现快速加载的最佳方法

Question

我有一个加载到DAWG数据结构中的500k+词表。我的应用程序是针对手机的。我当然不想每次都重复所有的转换步骤来加载这个单词列表到DAWG中，因为在手机上有单词列表需要很大的存储空间，每次加载到DAWG中需要很长的时间。因此，我正在寻找一种方法来将我的DAWG中的数据以一种既节省空间又允许我快速将其加载回我的DAWG数据结构的格式存储到文件或DB中。

我收到一个建议，建议我可以将每个节点存储在SQLite DB中，但我不确定这到底是如何工作的，如果我这样做了，我将如何快速检索它。我当然不想运行太多的查询。其他类型的存储方法会更好吗？我还收到了创建序列化文件或将其存储为位图的建议。

Answer 1

基本上可以进行内存转储，只需使用偏移量而不是指针(在Java术语中，将所有节点放入数组中，并使用数组索引来引用节点)。

对于现代手机来说，500k似乎不是问题，特别是DAWG已经相当高效了。如果对文件进行mmap，即使数据结构不适合内存，也可以使用它。

Answer 2

你有没有试着减少词汇表？如果您的应用程序可能的话，您是否只保存单词stam？

另一方面:你永远不应该重新构建数据结构，因为词表是恒定的。尝试使用像suggusted这样的内存转储。使用mmap for the file、java序列化或pickle pickle技术将现成的数据结构加载到内存中。

Answer 3

我猜，您正在使用DAWG在字典中快速搜索某个单词。DAWG有O(LEN)搜索的复杂性。

很多年前，我开发过J2ME应用程序，也遇到过同样的问题。但在那个时候，手机绝对不能提供如此大的内存容量来存储500K+字符串)，我使用的解决方案如下：

1. 读取所有单词，对它们进行排序，逐行放入一些文件中，并为每个单词预先计算skipBytes。-此字之前的字节数。计算skipBytes是微不足道的。伪代码是skipBytes[0]=words[0].bytesLen; for i=1 to n skipBytes[i]=skipBytes[i-1]+words[i].getBytesLength
2. When应用程序开始读取500k skipBytes到某个整型数组。它比字典二分搜索中500K strings)
3. Searching字要小得多。想象一下，您正在对排序数组执行它，但是，您没有生成array[i]，而是生成了类似于RandomAccessFile.read(skipBytes[i])的东西。谷歌Java随机存取文件我的伪代码当然是错的，这只是方向。

复杂度- O(LEN*LOG(N)) =二进制搜索和比较字符串的对数是线性复杂度。LOG(500000)~19，LEN ~最坏情况下的平均字长为50 (奇妙的上界)，因此搜索操作仍然非常快，只有~1000次操作将在微秒内完成。优点-内存使用量小。

值得一提的是，在web应用程序中，当许多用户执行搜索时，LOG(N)变得很重要，但如果您的应用程序只为一个人提供服务，则如果它不在循环内执行，则不会有太大变化(500000)