精简内存字典

• 下载源 - 7.2 KB
• 下载演示项目 - 43.0 KB

引言

你是否遇到过需要存储大量字符串字典，却发现将其保留在内存中是一场噩梦的情况？如果是这样，这可能是解决您问题的最佳方案之一。在本文中，我将描述一种将字典中的所有内容都保留在磁盘上的实现方式。在您的代码中使用它的优点是：

1. 内存占用非常低（仅几字节），无论字典大小如何。
2. 磁盘访问对用户（使用代码的开发人员）来说是透明的，因此他们可以像访问内存一样访问它。
3. 虽然存储在磁盘上，但由于基于 B 树的实现，访问速度相当快。
4. 无需单独的机制即可将字典写入磁盘和从磁盘读取。
5. 字符串的单位是字符串而不是字符，因此应用程序开发人员可以控制 trie（用于实现字典）的深度。
6. 也可以存储字典中单词的相对频率。

背景

我正在对我母语僧伽罗语进行自然语言处理研究。为此，我需要在内存中同时存储几个大型字典（短语、单词和发音字典）。然而，我意识到这些字典占用了大量内存（数百兆字节），导致程序性能急剧下降。我不得不采用一种实现方式，使字典能够存储在磁盘上并直接从磁盘访问。

为什么字典占用了大量内存？

假设我们要存储一个包含 100,000 个单词的字典。如果平均单词长度为 6 个字符，并且我们将单词的相对频率（出现可能性）存储为整数。那么整个字典只需要 10 字节/单词，总共才 1MB！！这是一个很小的数量，为什么我们还需要采用磁盘方法呢？嗯，只有当我们顺序存储单词时才会是这样。这将需要线性搜索来查找单词，这对于大型字典来说（在性能方面）是完全不切实际的。因此，我们肯定需要一种结构化的方式来存储字典。Trie 是一种基于树的数据结构，是对此最常见的解决方案。在 trie 中，查找单词只需要像单词在树中的深度一样少的步骤。

现在的问题是我们存储 trie 需要多少内存。它会比顺序方法所需的内存显着高吗？我们来看看。trie 中的叶节点数量等于字典中的单词数量，即 100,000 个。此外，还有内部（非叶）节点。在我的工作中，我发现当存储单词时，这个数量接近叶节点数量的两倍。所以，总节点数约为 300,000。每个节点需要多少内存？一个节点将需要：（i）ID：4 字节（ii）一个标志，指示它是否是叶节点：1 字节（iii）从节点进行的转换映射，如果节点是内部节点 - 转换是字符串（请注意，单位是字符串）和整数的关联。假设每个节点的平均转换数为 5（5 字节 * 5 = 25 字节）。映射数据结构本身会占用一些内存。如果我们假设是 10 字节，则映射占用的内存为 35 字节。所以，每个节点占用的内存为 40 字节，整个字典需要 40 * 300,000 = 12MB。这比我们为顺序方法预测的要多得多。当存储的字符串更长时（例如短语），情况会变得更糟。节点数量会更多，内存需求会增长到数百兆字节。

它如何在磁盘上存储

您无需理解甚至阅读本节即可使用代码。本节仅供对内部机制感兴趣的人阅读。我在磁盘存储字典时使用了 B 树方法，这在数据库实现中非常常见。如果您不熟悉 B 树，最好在阅读本节之前阅读一本好的教程（有很多）。

在此实现中，有三种结构构成了磁盘文件。

1. 节点 - 代表一个节点，包含节点属性，如节点 ID、结束标志、计数等。
2. 转换页 - 这是一组转换，其中一个转换由一个字符串和一个目标节点 ID 组成。
3. 转换里程碑页 (TMP) - 这是从 B 树架构继承的结构。我们对节点的转换集进行排序，并将它们分成页面。我们将转换页的第一个转换称为转换里程碑。转换里程碑页是节点转换里程碑的集合。给定节点可以有一个或多个转换里程碑页。

我们的磁盘文件由这些结构的顺序排列的实例组成。让我们看看节点结构。

节点

请注意，一个节点在其内部包含其第一个 TMP。然后它拥有指向其下一个 TMP 的偏移量（如果有）；否则，它被设置为无效偏移量。转换页结构看起来就像由红色边框包围的部分，而在 TMP 中，开头有一个额外的整数字段，指示下一个 TMP 的偏移量（如果有）。

磁盘文件有一个头，其中包含字典的一些属性和统计信息。

头部的最前面两个字节是字符 "DL"，代表 "Dictionary Lite"。如果您在文本编辑器中打开字典文件，您会在开头看到这两个字符。紧随头部的是 trie 的根节点。

使用代码

使用此代码非常简单。首先，在您的项目中包含 "Dictionary.h"。您可以创建一个 CDictionaryLite 对象，并按照以下指南中的函数进行操作。

创建字典

字典的文件名应在构造函数中给出。您可以使用任何扩展名。有两种构造函数。

CDictionaryLite(CString sFilename);
CDictionaryLite(CString sFilename, bool bKeepFile,
   int iStrLen = DICTIONARY_LITE_DEFAULT_STR_LEN,
   int iNoOfStrInNode = DICTIONARY_LITE_DEFAULT_NO_OF_STR_IN_NODE,
   int iNoOfStrInTransition = DICTIONARY_LITE_DEFAULT_NO_OF_STR_IN_TRANSITION);

首次创建字典时使用第二个构造函数。第二个参数指示销毁后是否保留字典文件。如果您在程序中创建了大量字典，并且在程序终止后不需要它们，请将此参数设置为 false。还有其他与字典相关的参数（可选），您可以根据需要进行指定。例如，如果您将字符用作字符串单元，可以将 iStrLen 设置为 2（请记住为 null 终止符保留一个字节）。iNoOfStrInNode 是节点或 TMP 中的字符串数量。iNoOfStrInTransition 是转换页中的字符串数量。如果未指定，这些参数将分配默认值。但是，最好输入这些值以最小化字典的空间和时间复杂度。

使用已存在的字典文件创建字典对象时，应使用第一个构造函数。只需要给出文件名，因为字典文件在其头部包含了所有其他参数。

向字典添加单词（字符串）

创建字典对象后，您可以通过以下函数向其添加单词：

void AddString(CStrList& oStrList, int iCount = 1);

请注意，您输入的是字符串列表而不是单个字符串作为单词。这是因为字典中使用的字符串单位也是字符串。这样做是为了使其更通用。CStrList 是一个派生自 std::list<CString> 的类，所以您所要做的就是将单元字符串推入其中。如果这一点不清楚，请参考下面的示例。可以选择给出字符串的计数。如果单词已存在于字典中，其计数将增加此数字。

检索字典中的单词

1. 可以通过以下函数验证字典中是否存在某个单词：

   int GetStringCount(CStrList& oStrList);

   如果单词存在于字典中，输出将是其计数，否则为零。

2. 可以使用以下两个函数顺序检索字典中的所有单词：

   bool GetFirstWord(CStrList& oStrList, int& iCount);
   bool GetNextWord(CStrList& oStrList, int& iCount);
   

函数名不言自明。字典中的单词以深度优先左递归方式遍历。即，如果 A 和 B 是两个兄弟节点（具有相同的父节点），并且 A 在树中位于 B 的左侧，则在访问 B 之前，A 及其所有后代都会被访问。

使用完字典对象后，只需删除它。就这么简单！字典文件将保留在磁盘上（除非您在构造函数中将 bKeepFile 参数设置为 false），您可以再次使用它。

以下代码片段说明了这些基本操作：

// create dictionary
CDictionaryLite* pDicLite = new CDictionaryLite
            ("MyDic.ldic", true, 3, 5, 6);
// add three words to the dictionary


CStrList oStr1, oStr2, oStr3;
oStr1.push_back("a");
oStr1.push_back("pp");
oStr1.push_back("le");
// "apple"

oStr2.push_back("m");
oStr2.push_back("a");
oStr2.push_back("n");
// "man"

oStr3.push_back("ca");
oStr3.push_back("t");
// "cat"

pDicLite->AddString(oStr1); // count = 1
pDicLite->AddString(oStr2, 4); // count = 4
pDicLite->AddString(oStr3, 2); // count = 2

//check whether "cat" is in the dictionary
bool bIsInDictionary = (pDicLite->GetStringCount(oStr3) > 0);
// result : true
oStr3.push_back("s");
//check whether "cats" is in the dictionary
bIsInDictionary = (pDicLite->GetStringCount(oStr3) > 0); 
// result : false

//retrieve first two words in the dictionary
CStrList oWord;
int iCount;
pDicLite->GetFirstWord(oWord, iCount); 
// oWord = "apple" iCount = 1
pDicLite->GetNextWord(oWord, iCount); 
// oWord = "cat" iCount = 2

// destroy the dictionary object
delete pDicLite;

关注点

字典对象所需的内存以字节为单位，甚至不足以达到千字节！这不取决于字典的实际大小。在我的 2.8 GHz 机器上，访问一个单词（查找单词的计数）不到 1 毫秒。通过添加内存缓存，肯定可以使其更快。有人可以试试吗？

通过实现可变大小的页面，可以减小字典占用的磁盘空间，因为在此实现中，页面大小（页面中的字符串数量）是固定的，并且并非页面中的所有条目（转换页或 TMP）都被使用。在这种情况下，页面大小可以存储在页面本身中的某个位置。如果有人能尝试一下，将不胜感激。

历史

2007 年 3 月 10 日：初始发布