多音字 搜索词纠错: 匹配简拼(汉字数≥5时才有效)  单字的拼音来自:这里(最全的多音字)...     

当搜索词中有错别字时,搜索引擎会尝试纠错

通过相似拼音纠错

搜索引擎把这些字还原成拼音,用一个拼音相同的已知的搜索词代替。

这是一种众所周知的纠错策略,但是,当输错的字是多音字,特别是有多个这样的错误输入时,所有的搜索引擎都尽量绕开这个问题,或者仅使用最常用的那些音去纠错。 因为要考虑所有可能的拼音组合,在极端情况下会导致指数爆炸! 例如某互联网大厂的实现(枚举多音字全排列)

基于自动机的算法可以完美解决这个指数爆炸问题

  • 这是自动机应用的又一个绝佳范例,作为演示,这个页面只收录了 800万搜索词+词频,数据也不太干净
  • 该算法全部在内存中运行,使用了 293M 内存,这个数据量,如果用传统方法暴力实现,并且达到这个性能,需要 几十G 的内存
  • 暴力方法是 Query 越长越可怕,该算法则是 Query 越长,优势越大
  • 纠错耗时仅供参考(单核虚拟云主机: Xeon E5-2430 2.20GHz + RAM:1G),如果你看到搜索耗时过长,很可能是 mmap 数据被 swap 到了硬盘上,再搜索一次会得到客观的搜索耗时

这个算法也可以用来解决用户输入预测(智能提示)功能

用户只输入Query开头部分,就自动提示出整个Query,例如用户输入举头望,就提示出举头望明月。就像现在各种搜索引擎做的那样。

基于编辑距离的纠错

在已知的搜索词中寻找编辑距离与用户 Query 最小的词,使用我的算法也可以高效解决(还没做演示页面)

高性能文件系统实现

阅读更多关于《高性能文件系统实现》
 

高性能文件系统-演示文档

PowerPoint下载

演示文档首页

Word Doc 文档下载

Fat 文件系统规格白皮书
文件系统的两种实现

标题

高性能文件系统 (该页文档描述)

最小实现

可扩展性

优良(基于虚拟文件系统构架)

时间性能

优良,接近硬件极限速度,
可用于驱动硬盘

差,仅可用于驱动存储卡片

空间性能

较大, Rom(Code)30K , Ram(RunTime) >= 32K

Rom(code) < 8KRam(RunTime) >=2K

支持

Fat12/Fat16/Fat32 ,长文件名

Fat12/Fat16 ,仅 8.3 文件名

可自定义路径解析

其它特点

对连续簇编组,不用 FatCache

FatCache

源码下载:

高性能文件系统( PowerPoint 文档描述)

最小实现
一个国外的Fat文件系统 (使用的是 FatCache ,不是对连续簇编组)

这些源码任何人可以自由下载,自由改动,
但我对此不提供技术支持,如果需要支持, 请联系我们!

C++使用模板进行的一种重构

阅读更多关于《C++使用模板进行的一种重构》

如果有一些遗留代码,里面有很多结构,定义了一些相同的成员,但在一些时候,需要取出这些成员,进行同样的处理。如下面这些代码的红色部分。

——原先的程序结构是使用类型码来区分实际的类型,客观地说,这些遗留代码是比较混乱的。

不想说太多,用简单的代码来说明问题吧。

typedef struct   _EVT_SWITCH : public EVT_HEAD {
 DWORD dwCategory;
 DWORD  dwSeverity;
 DWORD dwEvtSrcID;
 DWORD dwEvtSrcOffset;
 DWORD   dwSrcIp;
 DWORD   dwSrcPort;
 DWORD   dwDstIp;
 DWORD   dwDstPort;
 DWORD   dwProtocol;
 DWORD dwEvtUserOffset;
 DWORD   dwEvtUserIp;
 DWORD dwStatus;
 DWORD   dwOp;
 DWORD dwEvtNum;
 DWORD dwDetailOffset;
 CHAR szContent[0];
}EVT_SWITCH,*PEVT_SWITCH;

typedef struct   _EVT_ROUTER : public EVT_HEAD {
 DWORD dwCategory;
 DWORD  dwSeverity;
 DWORD dwEvtSrcID;
 DWORD dwEvtSrcOffset;
 DWORD   dwSrcIp;
 DWORD   dwSrcPort;
 DWORD   dwDstIp;
 DWORD   dwDstPort;
 DWORD   dwProtocol;
 DWORD dwEvtUserOffset;
 DWORD   dwEvtUserIp;
 DWORD dwStatus;
 DWORD   dwOp;
 DWORD dwEvtNum;
 DWORD dwDetailOffset;
 CHAR szContent[0];
}EVT_ROUTER,*PEVT_ROUTER;

typedef struct  _EVT_NETWORK : public EVT_HEAD {
 DWORD dwCategoryOffset;
 DWORD  dwSeverity;
 DWORD dwEvtId;
 DWORD dwEvtSrcOffset;
 DWORD dwEvtUserOffset;
 DWORD dwEvtTypeOffset;
 DWORD dwSrcIp;
 DWORD dwSrcPort;
 DWORD dwDstIp;
 DWORD dwDstPort;
 DWORD dwProtocol;
 DWORD dwSmacOffset;
 DWORD dwDmacOffset;
 DWORD dwFlagOffset;
 DDWORD ddwInB,ddwOutB,ddwInPkt,ddwOutPkt;
 DDWORD ddwSessionId;
 DWORD dwRuleOffset;
 DWORD dwStatusOffset;
 DWORD dwOpOffset;
 DWORD dwReasonOffset;
 int tDuration;
 DWORD dwEvtNum;
 DWORD   dwArgOffset;
 DWORD dwMsgOffset;
 DWORD dwDetailOffset;
 CHAR szContent[0];
}EVT_FW,*PEVT_FW,EVT_NETWORK,*PEVT_NETWORK;

typedef struct  _EVT_VPN : public EVT_HEAD {
 int tDuration;
 DWORD dwCategoryOffset;
 DWORD  dwSeverity;
 DWORD dwEvtId;
 DWORD dwEvtSrcOffset;
 DWORD dwEvtUserOffset;
 DWORD dwEvtTypeOffset;
 DWORD   dwDevActionOffset;
 DWORD dwDevMoudleNameOffset;
 DWORD dwServiceOffset;
 DWORD dwSrcIp;
 DWORD dwSrcPort;
 DWORD dwDstIp;
 DWORD dwDstPort;
 DWORD dwProtocol;
 DWORD dwSmacOffset;
 DWORD dwDmacOffset;
 DWORD dwTargetUserIDOffset;
 DWORD dwTargetDomainOffset;
 DWORD dwMessageIDOffset;
 DWORD dwTunnelOffset;
 DWORD dwInterfaceOffset;
 DWORD   dwMmemonicOffset;
 DWORD dwFlagOffset;
 DDWORD ddwInB,ddwOutB,ddwInPkt,ddwOutPkt;
 DDWORD      ddwSessionId;
 DWORD dwStatusOffset;
 DWORD dwOpOffset;
 DWORD dwReasonOffset;
 DWORD dwEvtNum;
 DWORD   dwArgOffset;
 DWORD dwMsgOffset;
 DWORD dwDetailOffset;
 CHAR szContent[0];

}EVT_VPN,*PEVT_VPN;

typedef struct  _EVT_SECURE : public EVT_HEAD {
 DWORD dwCategoryOffset;
 DWORD dwSeverity;
 DWORD dwEvtTypeOffset;
 DWORD dwEvtSrcOffset;
 DWORD dwEvtUserOffset;
 DWORD dwSrcIp;
 DWORD dwSrcPort;
 DWORD dwDstIp;
 DWORD dwDstPort;
 DWORD dwProtocol;
 DWORD dwFlagOffset;
 DDWORD ddwInB,ddwOutB,ddwInPkt,ddwOutPkt;
 DDWORD ddwSessionId;
 DWORD dwRuleOffset;
 DWORD dwStatusOffset;
 DWORD dwOpOffset;
 DWORD dwReasonOffset;
 DWORD dwEvtId;
 DWORD dwEvtNum;
 DWORD   dwSignatureOffset;
 DWORD dwDetailOffset;
 CHAR    szContent[0];
}EVT_SECURE,*PEVT_SECURE;

这些类型实际上是同一类类型,实际上可以从同一个类派生,使用 PullUp Member 方法重构。但是这些结构已经发布,不可能施行这种重构。可以这样:

class CEventWrapper
{
public:
 CEventWrapper(PEVT_HEAD p) { m_p = p; }

 struct NetInfo
 {
  DWORD dwDstIp;
  DWORD dwDstPort;
  DWORD dwSrcIp;
  DWORD dwSrcPort;
  DWORD dwProtocol;
  TCHAR szDstMac[20];
  TCHAR szSrcMac[20];
 };
 BOOL GetNetInfo(NetInfo* p) const;
 template static void
  TemplateGetNetInfo(CEventWrapper::NetInfo* netInfo, const T& x)
 {
  netInfo->dwDstIp  = x.dwDstIp;
  netInfo->dwDstPort = x.dwDstPort;
  netInfo->dwSrcIp  = x.dwSrcIp;
  netInfo->dwSrcPort = x.dwSrcPort;
  netInfo->dwProtocol = x.dwProtocol;
 }

 BOOL   HasNetInfo() const;

private:
 PEVT_HEAD m_p;
};

BOOL CEventWrapper::HasNetInfo() const
{
 NetInfo ni;
 return GetNetInfo(&ni);
}

BOOL CEventWrapper::GetNetInfo(NetInfo* netInfo) const
{
 memset(netInfo, 0, sizeof(NetInfo));

 switch (m_p->dwLogFrt)
 {
 default:
  ASSERT(0);
  return FALSE;
 case DIAL_LOG:
 case WEBTRENDS_LOG:
 case SNORT_LOG:
 case SENDMAIL_LOG:
 case SYSLOG:
 case NETSCREEN_LOG:
 case WIN_FILE_LOG:
 case WIN_PROCESS_LOG:
 case APACHE_ERROR_LOG:
 case IP_MON_LOG:
 case IP_UP_LOG:
 case PROC_MON_LOG:
 case GENERAL_MON_LOG:
 case PERF_MON_LOG:
 case PORTMON_LOG:
  ASSERT(0);
  return FALSE;

 case EVENT_LOG:   return FALSE;

 case CP_LOG:
  TemplateGetNetInfo(netInfo, *(EVT_VIRUS*)(m_p + 1));
  return TRUE;
 case VPN_LOG:
  TemplateGetNetInfo(netInfo, *(EVT_VPN*)(m_p + 1));
  return TRUE;

 case SECEXPERT_LOG:  return FALSE;

 case IIS_FTP_LOG:  return FALSE;
 case EXCHANGE_LOG:  return FALSE;
 case FW_LOG:
  {
   EVT_FW* p = (EVT_FW*)(m_p + 1);
   TemplateGetNetInfo(netInfo, *p);
   if (p->dwDmacOffset)
    lstrcpyn(netInfo->szDstMac, p->dwDmacOffset + (char*)p,
     dimof(netInfo->szDstMac));
   if (p->dwSmacOffset)
    lstrcpyn(netInfo->szSrcMac, p->dwSmacOffset + (char*)p,
     dimof(netInfo->szSrcMac));
   return TRUE;
  }
 case DOMINO_HTTP_LOG:
 case APACHE_LOG:
 case IIS_HTTP_LOG:
  return FALSE;

 case CISCO_PIX_LOG:
 case CISCO_IOS_LOG:
 case CISCO_SWITCH_LOG:
 case HUAWEI_SWITCH_LOG:
 case NORTEL_SWITCH_LOG:
  TemplateGetNetInfo(netInfo, *(EVT_SWITCH*)(m_p + 1));
  return TRUE;

 case SQLSERVER_LOG:  
 case ORACLE_LOG:
 case MYSQL_LOG:
  return FALSE;

 case KIDS_LOG: case IDS_LOG:
  TemplateGetNetInfo(netInfo, *(EVT_SECURE*)(m_p + 1));
  return TRUE;
 }
 ASSERT(0);
 return FALSE;
}

C语言垃圾代码清除工具(含源码)

阅读更多关于《C语言垃圾代码清除工具(含源码)》

CodeClean 使用说明

 

1.      说明

工程中有许多垃圾代码,CodeClean能识别的垃圾代码指从入口不可达的垃圾函数和全局变量。CodeClean 可以扫描出所有这类代码,从扫描垃圾的角度,未对函数和全局变量未做区别。

有很多函数和全局变量被其它的函数或全局变量引用到,但引用它的函数(或全局变量)从入口是不可达的,这样的函数(或全局变量)称它为 Island

本程序仅扫描C语言(不包括C++)的垃圾代码。本程序不对C语言程序进行预处理(忽略了#”开头的行),对宏调用不做特别处理,将它看作是一个普通的函数调用。

对于已知的未使用的变量,或函数(如这些变量或函数在汇编语言程序中使用)。为防止他们被清除掉,可以定义一个哑宏,如:

#define  DUMMY_REFER(X)

在某个(已知的)从入口可达的函数(非垃圾函数)中引用该变量(或函数)即可。如:

Void main()

{

   …..

   DUMMY_REFER(MyPredefinedFunction);

   …..

}

2.      命令行

        CodeClean options

 

        options: /Fxxx option default is output file name

        island object is an object which is not reachable by ‘main’,

        but was refered by another object.

 

/Fmake [make file name(input file, list of input source file names)]

/Fgarbage [garbage object list file name]

/Fisland [island object file name]

/Ferror [error message output file name]

/Fcall [call graph file name]

/Dcall [max call graph depth (default is 32)]

/Ncall [max callees number each object’s call graph (default is 32)]

/Fcaller [caller graph file name]

/Dcaller [max caller graph depth (default is 32)]

/entry [entry point name (default is ‘main’)]

 

/allcaller (list all callers of each object, in spite of found ‘main’ or not)

/cleancode (generate clean code)

/onlyzero (only list zero refered object to garbage object file)

/tomain (list any callers of each object until found ‘main’ function)

/entrystop (same as ‘tomain’)

/? or /H or /h (show this help message)

3.      命令行详解

[ ] 括起来的地方,表示这里必须要有一个参数――如果有前面的 /xxxx 选项。

 

/Fmake [输入文件名,其中包含 *.C文件名列表,每行一个文件]

/Fgarbage [输出文件名,扫描出的垃圾对象列表]

/Fisland [输出文件名,扫描出的“island”对象列表]

/Ferror [输出文件名,扫描过程中的显示信息,默认是Consol屏幕]

/Fcall [对象调用图(从上往下)]

/Dcall [每个对象调用图的最大深度(默认是 32)]

/Ncall [每个对象调用图的最多只列出的调用对象的数目,默认列出全部]

/Fcaller [对象被调图(从下往上)]

/Dcaller [每个对象被调图的最大深度(默认是 32)]

/entry [入口函数的名字,默认是”main”]

/allcaller (列出每个对象的所有调用者,不管是否搜索已到入口)

/cleancode (生成干净代码,生成的干净代码与原代码在同一目录下,以 .cxx 为后缀名)

/onlyzero (仅列出未被使用的对象,不列出 “island”对象)

/tomain (被调图碰到入口函数就停止)

/entrystop (‘tomain’相同)

/? or /H or /h (显示这个帮助信息)

 

例:

CodeClean /tomain /entry MyMain /Fmake make.mak /Fgarbage garbage.txt /Fcaller caller.txt /Fcall call.txt

生成垃圾对象列表和被调图及调用图,其中MyMain是入口函数名, make.mak 是输入文件名,其中包含要扫描的文件名列表...

 

一个可能的 Mak 文件内容如下:

 

kernel/oss/kernel.c

kernel/oss/osinit.c

kernel/oss/os_err.c

kernel/oss/os_msg.c

kernel/oss/os_oem.c

kernel/oss/os_stat.c

kernel/oss/os_synch.c

kernel/oss/schtmr.c

 

 

4.      程序

如果您的VC(或其它编译环境)安装了STLPort,您可以定义__USE_HASP_MAP宏以便编译出最快的代码。

使用__USE_HASP_MAP,在Windows2000P42.8512M内存环境下,扫描2M代码只需要5!如果再生成去除垃圾后的干净代码,也只需要10钟。连我自己都对这个速度感到惊异!

 

源码下载

程序下载(该程序未使用__USE_HASP_MAP,速度不是最快

 

 

 

 

使用 C 语言的“准元程序”设计

阅读更多关于《使用 C 语言的“准元程序”设计》

将 C 语言的预编译语言看成是“元语言”,使用该元语言进行程序设计

但为什么叫“准元程序”?

因为 C 语言的预编译语言没有迭代结构,所以C 语言的元程序语言不是图灵完备的。举个简单的例子,我们无法用 C 语言的“元语言”写出一个计算 factorial(x)——x 的阶乘的程序;而用 C++的模板就可以(使用模板特化)。因为这需要语言的迭代结构。C预编译语言没有迭代结构的原因是宏替换仅发生在源语言的宏调用中,预编译中的宏调用是不会发生替换的(除了条件编译中条件中对宏的调用)如:

但是,在条件编译中:

因此,象这样的程序是错误的:

适应它,Play With Preprocessor

虽然如此,用 C 语言的预编译能力,在很多时候还是可以写出很好的程序,可以尽可能地减少代码冗余,增强程序性能。程序的可读性,也许增加了,也许减少了;但是在这个探索的过程中,很可能对问题的认识更深刻了,问题得到了更高程度的抽象。

元程序使用的几个重要重要指令:

CAT_TOKEN是一个核心的基本构造块。

总体上讲,C++的元程序设计是函数式语言(类似 lisp),而C语言的元程序设计有点类似汇编语言,试看:

 

实例,实现函数

      a)  这是一个性能要求相当高基本图像位传送函数,同时又有许多种位操作:
          (1)  not,and,or,xor,…完备的布尔代数,共16种布尔操作,去掉全真和全假,是14种操作
          (2)  许多种象素位数(1,2,4,8,16,24,32),甚至更多。
          (3)  这些情况组合起来,共有 686种(7×7×14)这显然是一个“过于完备”)的集合。
          (4)  如果按普通的方式编码,要写 686多个不同的函数,或者 switch…case中686种不同的 case。而这些代码都是非常相似的,如果把相同部分提取出来,把不同部分使用“模板”替换掉…..

          (5)  详细内容见代码,代码是非常短的(同时还有另外一个函数mergeblt,原型与bitblt相同,其中仅实现了16,24,32位象素),这些代码如果使用预编译器输出处理结果,有 6000 多行!: 

代码(附件中有完整代码)

C 语言几个绝招

阅读更多关于《C 语言几个绝招》

符号展开连接

CAT_TOKEN_1 将 t1 t2 连接成 t1t2 ,不预先将 t1 和 t2 展开,而

CAT_TOKEN_2 将 t1 和 t2 展开后再连接,如:

0转化为0,而将非零转化为 1,可以转化指针

编译时断言

定义 Handle类型

将 Handle 定义为函数指针主要有一个好处:就是禁止了对 Handle 的加减,防止了一些小错误的发生。

定义union中的匿名 struct

 

一个脚本语言编译器

阅读更多关于《一个脚本语言编译器》
 

  该编译器及运行环境采用虚拟机执行方式,即将源文件编译为中间代码(类似 Java 字节码),而中间代码在虚拟机(不是堆栈机,Java虚拟机是“准堆栈机”,大部分指令是堆栈式的,但为了效率,也有小部分指令不是堆栈式的)上执行。 可用于编译原理学习。

代码下载:http://febird.nease.net/OtherProduct/ScriptCompiler/ScriptEngine.rar

语言描述:http://febird.nease.net/OtherProduct/ScriptCompiler/Specification.htm

我的原文:http://febird.nease.net/OtherProduct/ScriptCompiler/ScriptCompiler.htm

按序号索引二叉树

阅读更多关于《按序号索引二叉树》

  理论上,一个平衡的二叉树,可以在 O(logn)时间内,按中序遍历的顺序号(或者说下标)完成对结点的搜索。不过,这需要在每个结点上存储以该结点为根的子树的大小,通过增加存储的途径,来改善性能。

  如果这是一棵排序树,那么这个序号就是按大小排列的顺序号。

  但是如果这颗树在程序运行过程中有对结点的动态插入和删除(插入和删除时,以及调整平衡性时,都需要调整插入/删除结点路径上的Node.count,时间复杂度为O(logn)),那么每个结点的序号就是变化的。

  因此,不能把序号存储在某个地方,然后又企图根据这一序号,重新找到该序号先前对应的那个结点。可能时因为这个原因,在很多时候,没有对这种计算的需求。我目前还没有在什么地方看到过这方面的文章。自己苦思冥想,竟也完成了。

class Node
{
public:
 Node* getByIndex(int index)
 {
  Node* p = this;
  while (p)
  {
   Node* q = p->left;
   while (q && q->count > index)
   {
    p = q;
    q = q->left;
   }
   if (0 == q || q->count == index) return p;

   p = p->right;
   index–;
   if (q) index -= q->count;
  }
  return 0;
 }
private:
 Node *left, *right;
 int count; // node count of ‘this’ and its subtree
};

 

软件加密技术及实现-续-01

阅读更多关于《软件加密技术及实现-续-01》

两年前,我曾在毕业设计:《软件加密技术及实现》中设想使用“代码转移”来实现更强大的反破解功能。

直到前不久,在朋友的鼓励下,我在多个方面增强了原先的软件SoftProtector,并改为图形界面,改名为《秦赢甲胄》(可在各搜索引擎搜索),开始尝试商业化。

为了实现更强大的反破解功能,前不久我开始思考实现“代码转移”,不想实现根设想完全两码事,太复杂了:需要对 x86 进行反汇编,代码分析,甚至虚拟执行(虚拟机),来完善《秦赢甲胄》。

在参考了很多资料之后,我终于深有体会,我需要更多的。

希望大家支持!

 

目前我的参考资料:

1.         《虚拟机设计与实现》,说实话,该书深度不够,不过它提到了不少好的参考资料。

2.         Java KVM 虚拟机源代码:http://www.sun.com

3.         IA-32 Intel® Architecture Software Developer’s Manual, http://www.intel.com

 

 

在 C 语言中实现模板函数的方法(续)

阅读更多关于《在 C 语言中实现模板函数的方法(续)》

C 语言中实现模板函数的方法(续):

 

/* 定义一个宏,用来连接两个标识符:*/

#define  MAKE_NAME(className, methodName)    calssName##__##methodName

 

/* 模板源文件:template.c

 * 必须重定义的宏:TheClass

 * 其它需要重定义的宏(如对一个搜索树的实现,需要比较元素或键值大小的宏)

 *

 */

 

Int MAKE_NAME(TheClass, Method1) (int param1, int param2)

{

       ….

       Return 0;

}

 

Int MAKE_NAME(TheClass, Method2) (int param1, int param2)

{

       ….

       Return 0;

}

 

Int MAKE_NAME(TheClass, Method3) (int param1, int param2)

{

       ….

       Return 0;

}

…..

 

/* 引用该模板的文件:samp1.c */

 

#undef  TheClass

#define TheClass  Class1

 

#include template.c

 

/* end samp1.c */

 

 

 

在 C 语言中实现模板函数的方法

阅读更多关于《在 C 语言中实现模板函数的方法》

现以一个求和函数 Sum 为例,用 C++ Template 可写如下:

如果不是内置类型,该模板隐式地需要 R R::operator+=(T)运算符可用。

三种使用 C 语言模拟C++的模板的方法

1.    使用函数指针作为 Functor 替换者

2.    用宏作为Functor的替换者

3.    所有可替换参数均为宏

至少需要一个额外的文件(实现文件) impsum.c

总结:

第一种方法,易于跟踪调试,但是效率低下,适用于对可变函数(函数指针)的效率要求不高,但程序出错的可能性较大(复杂),模板函数(Sum)本身很复杂,模板参数也比较复杂(add)的场合。

第二种方法,效率高,但很难跟踪调试,在模板函数和模板参数本身都很复杂的时候更是如此。

第三种方法,是我最近几天才想出的,我认为是最好的,在模板参数(Add)比较复杂时可以用函数(第二种也可以如此),简单时可以用宏,并且,易于调试。在模板函数本身很复杂,而模板参数比较简单时更为优越。但是,可能有点繁琐。

 

一般情况下,没有必要做如此劳心的工作,一切交给编译器去做就行了。但是本人在开发一个文件系统时,由于是基于一种少见的平台,没有可用的C++编译器,有几个函数,除了其中的类型不同(uint16uint32),和几个可参数化的宏不同,其它地方完全相同,而函数本身很复杂(两百多行代码)。Copy出几个完全类似的函数副本,维护起来特别烦人。非常需要如此的编程模式,故此,分享出来,大家共同探讨。