2

我有一个 500k+ 的词表，我将它加载到DAWG数据结构中。我的应用程序适用于手机。我当然不想每次都重复所有的转换步骤来将此单词表加载到 DAWG 中，因为在手机上保存单词表会占用大量存储空间，并且每次将其加载到 DAWG 中都需要很多时间. 因此，我正在寻找一种方法将我的 DAWG 中的数据以一种既可以节省空间又可以让我快速将其加载回我的 DAWG 数据结构的格式存储到文件或数据库中。

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

4

3 回答 3

2

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

对于现代手机来说，500k 似乎不是问题，尤其是 DAWG 已经非常高效了。如果您映射文件，即使它不适合内存，您也可以使用数据结构。

于 2010-12-13T13:58:49.393 回答
1

你试过减少单词表吗？如果可能的话，您是否只为您的应用程序保存单词 stam？

另一方面：你永远不应该重建数据结构，因为 wordlist 是不变的。尝试使用建议的内存转储。使用 mmap 文件、java 序列化或 pickle pickle 技术将现成的数据结构加载到您的内存中。

于 2011-03-20T13:37:27.607 回答
0

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

许多年前，我开发了 J2ME 应用程序并面临同样的问题。但在那个时候，手机肯定无法提供如此多的 RAM 内存来存储 500K+ 字符串）我使用的解决方案如下：

  1. 阅读所有单词，对它们进行排序，逐行放入某个文件中，并为每个单词 precompute skipBytes。- 该字之前的字节数。计算 skipBytes 是微不足道的。伪代码是 skipBytes[0]=words[0].bytesLen; for i=1 to n skipBytes[i]=skipBytes[i-1]+words[i].getBytesLength
  2. 当应用程序启动时，将 500k skipBytes 读取到某个 int 数组。比 500K 字符串小得多）
  3. 在字典中搜索单词 - 二进制搜索。想象一下，您正在排序数组上执行它，而不是让array[i]您制作类似RandomAccessFile.read(skipBytes[i]). Google Java Random Access Files 我的伪代码当然错了，这只是方向。

复杂度 - O(LEN*LOG(N))= 二进制搜索和比较字符串的 LOG 是线性复杂度。LOG(500000)~19, LEN ~ 最坏情况下的平均单词长度为 50（神奇的上限），所以搜索操作仍然非常快，只需约 1000 次操作即可在微秒内完成。优点 - 内存使用量小。

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

于 2014-09-11T05:54:36.277 回答