📄 pattree.c
字号:
/*******************************************************************************************************************************************************/
/**********************************************What's new***********************************************************************************************/
/*05.07.26 1.加入一个函数long NEXTAP_GetKernelVersion(void);用于读取核心版本 */
/* 2.更改一个函数long NEXTAP_GetDicInfo(void *pDicBuffer, int nTag); 加入一个参数用于读取字典版本 */
/* 目前核心版本号为十六进制数XX057261H(XX表示UNICODE等信息)，中文字典版本号为XX057212，英文字典版本号为XX057211 */
/* 3.更改Bug: 自定义词"阿啊"（全拼与简拼相同）后候选中出现两个 */
/* 4.加入输出分词有冲突的所有词表的功能int PATTREE_DumpConflictedWords(void *pDicBuffer, const TCHAR* strFilename ); */
/* 目前700K词典有50多处词表冲突，暂时的解决办法是对于这50多处冲突此表，可以用左键修改第一个字。例如：输入“一场”时显示“下岗”， */
/* 那么用左键移到“下”时再按左键则候选中可以修改为“一”。但是目前这种选择后优化仍有问题，将继续改进优化方法。 */
/*05.07.27 目前核心版本号: XX057272(XX表示UNICODE等信息)，中文字典版本号: XX057212，英文字典版本号: XX057211 */
/* 1.完善05.07.26中功能的修改 */
/*05.07.28 目前核心版本号: XX057282(XX表示UNICODE等信息)，中文字典版本号: XX057212，英文字典版本号: XX057211 */
/* 1.英文中MACRO格式书写上略微修改。 */
/*05.08.01 目前核心版本号: XX058011(XX表示UNICODE等信息)，中文字典版本号: XX058011，英文字典版本号: XX057211 */
/* 1.中文字典中加入30个偏旁的比划编码。 */
/* 2.笔画输入时结果中不再填入拼音。 */
/*05.08.04 目前核心版本号: XX058041(XX表示UNICODE等信息)，中文字典版本号: XX058011，英文字典版本号: XX057211 */
/* 1.Debug:加入用户词典时判断是否有冲突时可能在Release版时会有堆栈溢出的Bug。 */
/*05.08.09 目前核心版本号: XX058091(XX表示UNICODE等信息)，中文字典版本号: XX058011，英文字典版本号: XX057211 */
/* 1.左右键修改时当前词的拼音也随之变化。 */
/*05.08.10 目前核心版本号: XX058091(XX表示UNICODE等信息)，中文字典版本号: XX058091，英文字典版本号: XX057211 */
/* 1.IND_T 结构压缩为6字节，TYPE_PROB目前为BYTE。 */
/*05.08.11 目前核心版本号: XX058112(XX表示UNICODE等信息)，中文字典版本号: XX058091，英文字典版本号: XX057211 */
/* 1.Debug有冲突词时可能在Release版时左右键修改时有内存越界(CheckPreWord中)。 */
/*05.08.15 目前核心版本号: XX058151(XX表示UNICODE等信息)，中文字典版本号: XX058091，英文字典版本号: XX057211 */
/* 1.Debug:添加用户词典时用户词典空间剩余大小计算错误，调整了添加，删除用户词典时词典偏移量的计算。 */
/*05.08.17 目前核心版本号: XX058171(XX表示UNICODE等信息)，中文字典版本号: XX058091，英文字典版本号: XX057211 */
/* 1.Debug:FreezePreWord时对于改变成TYPE_PROB的词性词频类型没有设置正确。 */
/*******************************************************************************************************************************************************/
/*******************************************************************************************************************************************************/
/* NOTES: */
/* 1.外部接口函数一般以NEXTAP_打头，分为三类：以EN为后缀，用于英文输入法；以HW为后缀，用于手写输入法，暂时不用；其余是中文键盘输入法 */
/* 2.StaticDic 和 StaticLexicon对应的是输入法中应用的结构，不需要动态分配内存；相应的动态部分用于生成字典时用 */
/* 3.所有的结构由于要用在嵌入式系统中，因此需要至少2字节对齐，参见字典生成过程中ALIGN(n)和ALIGN2(n)，不排除今后可能做成4字节或8字节对齐 */
/* 4.UnifiedCand实际上是后来根据需求加入的Candidates和Predictions的混合体，因此不直接存储结果，而只是存储对应的Candidates和Predictions的结果 */
/* 5.由于屏幕大小不一，因此候选的排列个数会根据屏幕大小调整，具体计算参见CalculateMaxCandPredictNum */
/* 6.生成字典部分需要在PC上执行。所需文件举例如下： */
/* "lex_full.txt" 词表主文件，包括词，词频，拼音，词性及词性分布 */
/* "single_pinyin_jp.txt" 单字拼音表，包括所有单字拼音及其简拼 */
/* "chs_part_new.txt" 单字笔划表，包括至少前4笔 */
/* "pos_rmrb.txt" 2元词性统计文件，包括单元和双元词性统计，从人民日报表记语料中统计得出 */
/* "WTPenPDA_GB2312_Set_Unicode.lib" 第3方提供的手写字典 */
/* 所需的这些文件在Debug目录中都有，不同版本的字典主要是词表主文件不同 */
/* 7.简拼目前只作用于用户自定义词典。但是只要把简拼加入原词典，应该也支持 */
/* 8.在字典结构中，词条有2类排序后的索引：一类是原始索引，称为Word Index，为词条按字的编码排序的索引；一类为按对应数字串排序后的索引，例如按拼音数字串 */
/* 排序后的索引，称为WordID,其排序原则为 数字串>同数字串的词频，WordID索引为2级索引，需要到相应的WordID数组中找到相应的WordIndex */
/* 9.由于做过很多更改，因此目前版本只针对Unicode和词性Bigram做过测试，其他版本可能会有Bug */
/* 10.用户自定义词典目前用GetList按钮响应函数实现，因此与Build字典的功能重叠，需要更改void CEasyT9Dlg::OnBnClickedButtonGetlist()函数体来切换这2种功能 */
/*******************************************************************************************************************************************************/
#ifdef __SYMBIAN32__
#include <e32def.h>
#endif
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>
#ifndef __SYMBIAN32__
#include <tchar.h>
#else
#ifdef _UNICODE
#define _tfopen wfopen
#define _T(x) L ## x
#define _tcscpy wcscpy
#define _tcscat wcscat
#define _tcslen wcslen
#define _tcscmp wcscmp
#else
#define _tfopen fopen
#define _T(x) x
#define _tcscpy strcpy
#define strcat wcscat
#define _tcslen strlen
#define _tcscmp strcmp
#endif
#define _tcsclen _tcslen
#define __min(a,b) (a<b?a:b)
#define __max(a,b) (a>b?a:b)
#endif
#include "PatTree.h"
#ifdef PATTREE_HANDWRITING
#include "wtpen\v4\wtpen.h"
#endif
#define PATTREE_KERNEL_VERSION 0x00058171 /* kernel version */
#define PATTREE_BIN_VERSION 0x00058091 /* dictionary file version */
#define PATTREE_BIN_EN_VERSION 0x00057211 /* english dictionary file version */
#define PATTREE_DIC_STATIC 0x01000000
#define PATTREE_DIC_UNICODE 0x02000000
#define PATTREE_DIC_POSBIGRAM 0x04000000
//#define PATTREE_DIC_TYPE_PROB_CHAR 0x00000000
//#define TYPE_PROB unsigned short
//#define PATTREE_MAXLOGPROB 0x00FF00
//#define PATTREE_MAXLOGPROB_INC 0x200000
//#define PATTREE_MAXLOGPROB_FULL 0x00FFD0
//#define PATTREE_MAXLOGPROB_FULL_INC 0x000020
#define PATTREE_DIC_TYPE_PROB_CHAR 0x08000000
#define TYPE_PROB unsigned char
#define PATTREE_MAXLOGPROB 0x00F0
#define PATTREE_MAXLOGPROB_INC 0x1000
#define PATTREE_MAXLOGPROB_FULL 0x00FD
#define PATTREE_MAXLOGPROB_FULL_INC 0x0002
#define PATTREE_USER_DIC_LEN 10240 //10K
#define PATTREE_USER_DIC_MAX_ENTRY 100
#define USER_LEXICON_ENTRY_SPACE 102 //( sizeof(STATIC_LEXICON_ENTRY_T) + 16*(sizeof(wchar_t) + sizeof(unsigned short)) + 8*4 )
#define USER_LEXICON_ENTRY_IND_SPACE 180 //( sizeof(IND_T)*PATTREE_MAX_IND_LEN )
#define PATTREE_MAXLOGPROB_EN 245
#define PATTREE_ZEROTON_COUNT 0.8
// POS bigram
#define PATTREE_ZEROTON_POS_BIGRAM 0.8
#define PATTREE_ZEROTON_POS 0.8
#define PATTREE_WEIGHT_POS_WORD 1
#define PATTREE_WEIGHT_POS_BIGRAM 1
#define PATTREE_PUNCTUATION_POSINDEX 22
#define PATTREE_COMPOUND_POSINDEX 13 // as noun，任何一个用户自定义词认为其词性为noun
#define PATTREE_MAX_CHARPOSNUM 16
#define PATTREE_MAX_POSTYPE 39
#define PATTREE_MAX_COMMON_SINGLE_CHAR 16
#define PATTREE_MAX_SYMBOL_NUM 16
#define PATTREE_MAX_WORD_LEN 30 /* maximum word length */
#define PATTREE_MAX_IND_LEN PATTREE_MAX_WORD_LEN /* maximum index of the dictionary */
#define PATTREE_MAX_CODE_NUM 8 /* maximum code types number */
#define PATTREE_MAX_LEXICON_ENTRY 65530 /* maximum lexicon entries number */
#define PATTREE_MAX_CHARSTROKENUM 4
#define PATTREE_MAX_PREDICTION_NUM 40
#define PATTREE_MAX_CAND_NUM 256
#define PATTREE_MAX_UNIFIED_CAND_NUM (PATTREE_MAX_CAND_NUM+PATTREE_MAX_PREDICTION_NUM)
#define PATTREE_MAX_WORDCH_LEN 8
#define PATTREE_MAX_EN_ENTRY 128
#define PATTREE_MAX_WORDEN_LEN 48
#define PATTREE_MAX_UNIFIED_CAND_NUM_EN (PATTREE_MAX_EN_ENTRY+PATTREE_MAX_PREDICTION_NUM)
#define PATTREE_UNIFY_FIRST_CAND_NUM 2
#define PATTREE_CHAR_SPACE_RATIO 4
#define PATTREE_MAX_TRACE_LEN 2048
#define PATTREE_MAX_HW_BUFFER_LEN 2048
#define PATTREE_MAX_HW_CAND_LEN 10
#define PATTREE_MAX_INDEXINLEXICON_NUM PATTREE_MAX_PREDICTION_NUM
#define PATTREE_NULL_WORDINDEX 65535
#define PATTREE_NULL_WORDINDEX_EN 0x000FFFFF
#define ALIGN(n) ( ( ((n) + 3) >> 2) << 2 )
#define ALIGN2(n) ( ( ((n) + 1) >> 1) << 1 )
/*********************************************************************************************/
#pragma pack( push, BEFORE_PATTREE_T ) /* the struct is packed to 1 byte aligned */
#pragma pack( PATTREE_ALIGNBYTES )
/***************************************basic datastructure*********************************************/
// 静态字典中词条的存储结构
typedef struct tagSTATIC_LEXICON_ENTRY
{
//TYPE_PROB wLogProb;
// 词频，已做log变换以及换算成整形数。实际的词频log数值为 (wLogProb - pDic->ReadOnlyHead.nLogProbOffset) * pDic->fLogProbScale
// 由于浮点运算费时，因此在后面的运算中不涉及 * pDic->fLogProbScale 的运算
// 改到词典中统一的一个数组中
char cPinyinNum;
// 拼音数目。如果为0，则只有一个拼音，而且所有组成的单字的拼音只有一个，可以从单字拼音表中（静态字典中awCharPinyinCode）中查到；否则，从
// 下面的awPinyinCode中查找拼音码。
char cPinyinCodeOffset;
// 拼音码在动态数据中的存储偏移量（针对本结构的起始地址）
#ifdef PATTREE_POSBIGRAM
char cPOSNum; // 词性数目
char cPOSOffset; // 词性偏移量
#endif
wchar_t wszWord[1]; // 动态数据存储区，除了开始的词条之外，具体内容参见下面的数组
// unsigned short awPinyinCode[]; // 存储顺序为：第一个词拼音的n个拼音（n为字数），第二个词拼音的n个拼音...
// TYPE_PROB aPOSLogProb[];
// unsigned char abyPOSType[];
} STATIC_LEXICON_ENTRY_T;
/* struct of a index in dictionary, it correspond to a char in the dictionary tree */
typedef struct tagIND_T
{
/* code of the char represented by this node, if it is a lexicon but not a part of it
then the code is OR with 0x80 */
char cCode;
unsigned char byWordIDNum;
/* the index of the next sequence char of a word, PATTREE_NULL_WORDINDEX if no other char stored, that means
the lexicon is actually end, no lexicon exist which include this sequence chars as
a prefix part */
unsigned short nIndex;
/* the word ID of this word which is really existing */
unsigned short wWordIDFirst;
/* the maximal count of this word and all the words with this prefix */
//TYPE_PROB probMaxSeriesLogProb; // moved to dictionary vector
//unsigned short wReserved;
}
#ifdef __SYMBIAN32__
#ifdef __GCC32__
__attribute__ ((__aligned__(PATTREE_ALIGNBYTES), __packed__))
#endif
#endif
IND_T;
typedef struct tagSTATIC_DIC_HEAD_T
{
long nVersion;
long nTotalLen;
short nLanguage;
short nReservedShort[3];
long nOffset_RewritableBegin;
long nOffset_DataEnd; // 字典结尾处的偏移量
long nReservedLong[8];
} STATIC_DIC_HEAD_T;
typedef struct tagSTATIC_USER_DIC_HEAD_T
{
long nOffset_aLexiconLogprob;
long nOffset_awWordIndex_Pinyin;
// awWordIndex_Pinyin[nWordIndexNum_Pinyin]的偏移量，awWordIndex_Pinyin是所有词条按拼音数字编码排序后的索引
// 原始词条按STATIC_LEXICON_ENTRY_T结构存储，按字的编码排序，但是针对数字键盘，需要对词条对相应拼音数字排序以加快查找速度
// 其存储的称为WordID
long nOffset_aMaxSeriesLogProb_Pinyin;
// awMaxSeriesLogProb_Pinyin[nWordIndexNum_Pinyin]的偏移量，awMaxSeriesLogProb_Pinyin是所有词条按拼音数字编码排序后的
// 所建索引后在Patricia树中的分支的最大LogProb（原来存储在IND_T结构中，后来为了分离Rewritable部分单独提出）
long nOffset_awWordIndex_Stroke;
long nOffset_aMaxSeriesLogProb_Stroke;
// user lexicon,用户自定义词典
long nLexiconNum_User;
long nOffset_anlexiconsOffset_User;
long nOffset_aLexiconLogprob_User;
// user pinyin，用户自定义词典的拼音索引部分
long nActualDigiNum_Pinyin_User;
long nWordIndexNum_Pinyin_User;
//存储初始值为nWordIndexNum_Pinyin
long nOffset_awWordIndex_Pinyin_User;
long nOffset_aMaxSeriesLogProb_Pinyin_User;
long nOffset_awIndNum_Pinyin_User;
long nOffset_anIndOffset_Pinyin_User;
// user stroke，用户自定义词典的笔画索引部分
long nActualDigiNum_Stroke_User;
long nWordIndexNum_Stroke_User;
long nOffset_awWordIndex_Stroke_User;
long nOffset_aMaxSeriesLogProb_Stroke_User;
long nOffset_awIndNum_Stroke_User;
long nOffset_anIndOffset_Stroke_User;
long nUSER_DIC_MAX_ENTRY;
long nOffset_anUserDicDynamicBegin; // aLexicons_User[] 的起始偏移
long nReserved1[2];
} STATIC_USER_DIC_HEAD_T;
typedef struct tagSTATIC_READONLY_DIC_HEAD_T
{
short nReserved[1];
// pinyin
short nMaxIndLen_Pinyin; // 拼音索引的最大长度,最大不超过PATTREE_MAX_IND_LEN
// stroke
short nMaxIndLen_Stroke; // 笔画索引的最大长度，最大不超过PATTREE_MAX_IND_LEN
// char and single pinyin
unsigned short wCharCodeOffset;
// 单字的拼音，笔画码按数组存储，数组排列按单字编码顺序（UNICODE或GB2312），其中数组中起始字的编码即为此值。
long nCharNum;
// 单字数目
long nOffset_awCharPinyinCode;
// 单字拼音码的起始偏移地址，对于多音字，虽然也存储其首拼音，但无用。注意：所有偏移地址以abData算起（与Lexicon中不同）
long nOffset_awCharStrokeCode;
// 单字笔画码的起始偏移地址。单字笔画码最多存储单字的前4笔，每一笔编码占4个bits，总共占一个WORD
long nPinyinNum;
// 单字拼音的数目。此处单字拼音包括所有可能的单字拼音，包括简拼，大概400多个
long nOffset_anPinyinListOffset;
// 单字拼音偏移量数组的偏移量，也就是通过此偏移量定位到拼音偏移量数组anPinyinListOffset[nPinyinNum]，再通过此数组定位各拼音。
long nSymbolNum;
// lexicon
long nTotalCount;
// 字典中词频总数。
long nLogProbOffset;
// 整型变换量，参见STATIC_LEXICON_ENTRY_T的说明
double fLogProbScale;
long nLexiconNum;
// 词条数目
long nOffset_anlexiconsOffset;
// 词条偏移量数组的偏移量，词条按STATIC_LEXICON_ENTRY_T结构存储。
// pinyin
long nActualDigiNum_Pinyin;
// 所有词条拼音按数字编码后的独立数字串数
long nWordIndexNum_Pinyin;
// 所有词条按拼音数字编码排列后的词条数目。（>nLexiconNum, 由于多音的原因）
long nOffset_awIndNum_Pinyin;
// awIndNum_Pinyin[nMaxIndLen_Pinyin]的偏移，awIndNum_Pinyin[nMaxIndLen_Pinyin]存储各级（每一级即从前到后的拼音数字）IND_T结构的个数
long nOffset_anIndOffset_Pinyin;
// anIndOffset_Pinyin[nMaxIndLen_Pinyin]的偏移，anIndOffset_Pinyin[nMaxIndLen_Pinyin]存储各级IND_T结构数组的偏移量
// 请参阅DIC_IND_T结构对上述三个成员做理解。理论上是Patricia Tree.
// stroke
long nActualDigiNum_Stroke;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -