实现词典设计方法
目录
1 设计目标
2 设计思路
3 数据结构
3.1 后缀树结构
3.2 查找算法
4 实现
4.1 后缀树结构的生成及保存
4.1.1 数据结构
4.1.2 词典保存
4.2 利用后缀树结构进行词条查询
4.3 测试程序
4.4 下载
5 后记
1 设计目标
实现类似于金山词霸的词典查询系统，本文主要讨论其中词典的组织和查询，关于屏幕取词等相关问题另文叙述。
主要设计目标：
l 要求能够在海量词典中快速查询，基本要求：词条数500,000以上，数据量80MB以上，每次查询时间应在毫秒级（通过千次查询统计性能）
l 要求支持基于前缀的查询，比如输入“中”，要求能够查询处所有以“中”打头的词条。对前缀查询有同样的性能要求
l 主要针对中文词典，但要求能方便扩充到英文词典
l 运行时内存占用不可过大（不超过100MB）
2 设计思路
该问题主要在于词典数据结构的组织问题，简单的说，它可以归为查询问题，可能的几种思路如下：
l 直接搜索，复杂度为O(N)，对于500,000以上的词条不适用
l 二分搜索，复杂度为O(log2N)，对于500,000以上的词条，每次查询约需要19次左右的字符串比较，单次查询效率应该说基本可以满足要求，但当N变得更大时，效率可能会成为问题，而且，对于二分搜索最大的问题在于：无法有效支持基于前缀的查询。
l Hash查询，优秀的Hash查询能够使得复杂度降低到O(1)。
因此，我们主要希望找到一个好的Hash查询算法，能够将查询复杂度降低到常数级，而且针对前缀查询有很好的支持。
3 数据结构
我们采用的数据结构和算法如下：
3.1 后缀树结构
图1后缀树结构示意图
我们采用的数据结构见上图。
上图中通过一个树形结构表示出如下的词条：
u 中
u 中国
u 中间
u 中国人
u 中国人民
u 中国共产党
u 中华
u 中华文明
u 中华人民
u 中华人民共和国
u 中秋
u 中秋节
u 华夏
u …
（图中红色标出的字表示不成词）
采用这样的数据结构，可以使得查询词条的复杂度降到常数级。
3.2 查找算法
当我们采用这样的数据结构后，查找算法就显得很显而易见了。
输入： 带检索词条Word
是否前缀查询IsFuzzy
输出： 查询结果词条列表及释义
算法：
1. 通过Word的第一个字符定位到森林中对应字符的根结点（为了提高效率，采用数组定位）
2. 在对应树中，按Word的字符依次向下查找，直到找到全部匹配的词条对应结点
3. 如果前缀查询，则输出对应结点下所有的成词词条，否则仅输出该节点对应的词条。
算法1词典查找算法
4 实现
我们采用Delphi对上述算法进行了实现。
实现包括两部分：
4.1 后缀树结构的生成及保存
我们定义如下的接口，用于后缀树结构维护：
class TDictionary
public
// 增加新词条
procedure AddWord(DictItem: TDictItem);
// 保存词典
procedure SaveDictionary;
end;
4.1.1 数据结构
我们采用类TDictItem表示每个词条及其含义：
TDictItem = class
private
FOffset: LongInt;
FSuffixTree: TSuffixTree; // 指向关联该词条的后缀树节点
end;
我们看到，该类中实际有意义的数据仅为FOffset，而并没有任何词条的释义，之所以采用这样的结构是为了避免将所有词条全部载入到内存中（对于大词典将耗费过多的内存），这里的FOffset仅仅是文件中的偏移量，在需要获得对应词条的释义时，再通过该偏移量到文件中读取出词条。
既然该类中只有一个FOffset数据成员，我们其实完全可以取消这个类，而将该偏移量直接存放在每个节点上，这样可以减少一定的内存消耗。不过我们出于简单，没有再进行这样的优化。
为了表示后缀树，我们采用了类TSuffixTree：
TSuffixTree = class
private
FParent: TSuffixTree; // 指向父节点，如果是根则为nil
FLevel: Byte; // 节点在树中的层次
Ch: WideString; // 该节点的检索字
DictItem: TDictItem; // 该节点对应的词条
FCount: Word; // 子节点数目
FCapacity: Word; // 子节点数组容量
FChilds: TSuffixTreeList; // 子节点数组
end;
我们看到，该类中成员Ch不是保存的一个WideChar，而是WideString，这是和上文描述的数据结构不一致的。我们采用这样的结构也是出于优化的考虑。比如图1的数据结构优化后可以存储为：
图2优化后的数据结构
在优化后的数据结构中，所有的未成词字符（共产、共和）会被合并存放到一个节点上。因此在类TSuffixTree中的Ch类型为WideString。
4.1.2 词典保存
既然词典的词条部分会被表示为后缀树结构，而释义部分直接关联在后缀树节点上。因此我们将词典保存为两部分：
l 索引部分（dict.idx）：保存由词条构成的后缀树结构
l 词典部分（dict.dat）：保存所有词条及其释义
索引部分采用简单的对象序列化方法进行保存。
4.2 利用后缀树结构进行词条查询
我们定义如下的接口用于词条的查询：
TDictionary = class
public
// 加载词条索引
procedure LoadIndex;
// 查询（如果IsFuzzy=True，则进行前缀查询）
function Search(Word: WideString; IsFuzzy: Boolean = false): TDictItemList;
end;
具体的实现请参看示例代码。
词典库接口：
TSuffixTree = class;
TDictItem = class
private
FOffset: LongInt;
public
FSuffixTree: TSuffixTree;
Word: WideString;
Meaning: WideString;
procedure SaveContent(Stream: TStream);
procedure SaveIndex(Stream: TStream);
procedure LoadIndex(Stream: TStream);
function GetMeaning: WideString;
function GetWord: WideString;
end;
TOnProcessItem = procedure (DictItem: TDictItem) of object;
TDictItemList = array of TDictItem;
TSuffixTreeList = array of TSuffixTree;
TSuffixTree = class
private
FParent: TSuffixTree;
FLevel: Byte;
Ch: WideString;
DictItem: TDictItem;
FCount: Word;
FCapacity: Word;
FChilds: TSuffixTreeList;
procedure ProcessAllItem(OnProcessItem: TOnProcessItem = nil);
function GetIsWord: Boolean;
function Compact: Boolean;
function GetChild(Index: Integer): TSuffixTree;
function GetChildByChar(Ch: WideChar): TSuffixTreeList;
function GetChildByString(str: WideString): TSuffixTreeList;
function AddChild(SuffixTree: TSuffixTree): TSuffixTree; overload;
procedure DelChild(SuffixTree: TSuffixTree);
public
property ChildCount: Word read FCount;
property Parent: TSuffixTree read FParent;
property IsWord: Boolean read GetIsWord;
function Locate(Word: WideString; Index: Integer = 1): TSuffixTreeList;
constructor Create(Parent: TSuffixTree; InitCapacity: Integer = 10); overload;
constructor Create(Ch: WideString; DictItem: TDictItem; Parent: TSuffixTree; InitCapacity: Integer = 10); overload;
destructor Destroy; override;
procedure SaveToStream(Stream: TStream);
procedure LoadFromStream(Stream: TStream);
end;
TDictionary = class
private
FSuffixTree: array [$0..$FFFF] of TSuffixTreeList;
FStream: TStream;
function Locate(Word: WideString): TSuffixTreeList;
procedure OnProcessItem_SaveContent(DictItem: TDictItem);
procedure ProcessAllItem(OnProcessItem: TOnProcessItem = nil);
procedure SaveIndex;
procedure SaveContent;
public
constructor Create;
destructor Destroy; override;
function Search(Word: WideString; IsFuzzy: Boolean = false): TDictItemList; overload;
procedure AddWord(DictItem: TDictItem);
procedure SaveDictionary;
procedure LoadIndex;
procedure Compact;
end;
4.3 测试程序
本文所附的示例里包含了一个测试程序，他包括两个部分：
l DictMgr.exe
用于词典维护的程序。要求用户指定一个词典文件，将该词典文件转换为后缀树结构并保存。
词典文件的格式为：
【词条1】
释义1
【词条2】
释义2
…
l DictDemo.exe
用于在生成的词典中查询：
4.1 下载
需要的请联系作者
5 后记
本文给出一种高效的词典组织和查询的数据结构和算法，并给出对该算法的实现和示例程序，出于简单，没有进行太多的优化处理，主要只是演示该算法的可行性，希望有读者能够对该实现进一步改进。
如果有任何意见或建议，请联系作者！
本文地址：http://www.45fan.com/a/question/72201.html