English Sentence Loading...

英语句子加载中...

1 | 2 | 3 | 4 | 5 | >

预览模式: 普通 | 列表

如何确定中文字符串的相似度

作者:admin 日期:2007-12-21

摘要

在数据挖掘的研究中，我们往往需要判断文章是否雷同,对类似文章或短句进行归类处理等，这其中就会遇到这样的问题：如何确定两个字符串之间的相似程度。

本文综合作者的实际工作经验和数据挖掘理论，结合中文字符串特性介绍一套相对完整的方法，以解决上述问题.。

分析

最简单的问题求解

字符串由一组不同含义的单词组成，它不同于数值型变量，可以用一个特定的数值来确定它的大小或位置，所以用何种方式来描述两个字符串之间的距离，成为了一个值得探讨的问题。

通常情况下，用于分析的数据类型有如下几种：区间标度遍历、二元变量、标称型变量、序数型变量、比例标度型变量、混合类型变量等。

综合这些变量类型，本文认为字符串变量更适合于归类于二元变量，我们可以利用分词技术将字符串分成若干个单词，每个独立的单词作为二元变量的一个属性。我们把所有单词设定为一个二元变量属性集合R，字符串1和字符串2的单词包含于这个集合R。设q是字符串1和字符串2中都存在的单词的总数，s是字符串1中存在，字符串2中不存在的单词总数，r是字符串2中存在，字符串1中不存在的单词总数，t是字符串1和字符串2中都不存在的单词总数。我们称 q,r,s,t为字符串比较中的4个状态分量。如图1所示：

由于两个字符串都不存在的单词对两个字符串的比较没有任何作用，所以忽略t，于是我们采用非恒定的相似度评价系数(Jaccard系数)来描述两个字符串见的相异度表示公式为

相异度 = r+s / (q+r+s)，不难推断，他们的形似度公式为

相似度=q/(q+r+s) 公式1

分类:MFC | 固定链接 | 评论: 0 | 引用: 19260 | 查看次数: 8384

字符串相似度的比较问题

作者:admin 日期:2007-12-21

字符串相似度的比较问题

比较两个字符串的相似程度问题，根据比较的标准常用的可以分为两个子问题：类似与DNA当中两个序列的比较问题和在两个字符串当中取出最长相同子串的问题。

一、DNA问题

DNA问题主要使用动态规划的方法来解决。

DNA问题是这样一个问题，有两个DNA片断d1,d2，为了比较两个DNA片断的相似性我们引进这样一种比较的规则，对于两个DNA片断上面的ATGC序列，我们通过比较从两个片断当中严格按顺序取得一个这样的最长片断，这个片断的每个元素都能够从两个被比较的元素上严格按顺序取下，通过比较这个取下的这个片断的长度来比较两个DNA片断的相似度。例如片断1为GTAGA片断二为GCCTA，那么被取下的片断为GTA，其相似度定义为3。

我们用计算机来解决这个问题的基本思路是，先从结果考虑：设我们取得的片断为r，那么假设r[len] = d1[len] = d2[len]那么就可以推断对于d1和d2这两个片断去掉最后一个元素以后得到的相似片断r'就是在r的基础上去掉最后一个元素；又假设如果d1[len] != d2[len]，那么片断r实质上是d1去掉最后一个元素与d2获得的相似片断和d1与d2去掉最后一个片断获得的相似片断两者之间的较长者。由上面的描述我们可以得到一个LCS函数，LCS函数需要两个片断的当中位置作为参数，其返回一个以两个位置分别作为两个片断的结束点的相似片断，用数学的方式我们可以如下表示：

LCS(i,j) = LCS(i-1,j-1) + 1 d1[i] == d2[j]

LCS(i,j) = max(LCS(i-1,j),LCS(i,j-1)) d1[i] != d2[j]

LCS(i,j) = 0 i == 0 || j == 0

从上面的描述我们可以看到我们所有的推断都是从两个片断的末尾开始的，但是在真正的计算时我们需要从两个片断的开头开始，这是因为从LCS函数我们看到，无论那种情况下如果需要计算必须要知道与i-1或者j-1相关的LCS函数的情况，而对于i == 0或者j == 0的情况我们可以知道LCS的值为0。在程序当中我们使用一张表来记录各个(i,j)组合表示的LCS值，并且用一种形象的方式来记录了最终取得的相似串当中的元素的走向。具体的程序如下：

enum {LEFT,UP,THIS};

struct Node
{
int subLen;
int Router;
};

char * GetSimilar(const char *str1,const char *str2)
{
//Get table
int len1 = strlen(str1);
int len2 = strlen(str2);
Node ** table;
table = new Node * [len1 + 1];
for (int i = 0;i <= len1;i++)
table[i] = new Node[len2 + 1];

//Init table
for (int i = 0;i <= len1;i++)
table[i][0].subLen = 0;
for (int i = 0;i <= len2;i++)
table[0][i].subLen = 0;

//Computer LCS&Router table
for (int i = 1;i <= len1;i++)
  for (int j = 1;j <= len2;j++)
  {
   if (str1[i - 1] == str2[j - 1])
   {
    table[i][j].subLen = table[i- 1][j - 1].subLen + 1;
    table[i][j].Router = THIS;
   }
   else if (table[i][j - 1].subLen < table[i - 1][j].subLen)
   {
    table[i][j].subLen = table[i - 1][j].subLen;
    table[i][j].Router = UP;
   }
   else
   {
    table[i][j].subLen = table[i][j - 1].subLen;
    table[i][j].Router = LEFT;
   }
  }

//use router in table to get similar string (it's inverster)
int minIncream = 50;
int IncreamTime = 0;
char *str = new char[minIncream];
for (int i = 0;i < minIncream;i++)
  str[i] = '\0';
int k = len1,j = len2,pos = 0;
while (k >= 1 && j >= 1)
{
  if (table[k][j].Router == THIS)
  {
   if (strlen(str) + 1 == (IncreamTime + 1) * minIncream)
   {
    IncreamTime++;
    char *t = new char[minIncream * (IncreamTime + 1)];
    for (int s = 0;s < minIncream * IncreamTime;s++)
     t[s] = str[s];
    for (int s = minIncream * IncreamTime;s < minIncream * (IncreamTime + 1);s++)
     t[s] = '\0';
    delete[] str;
    str = t;
   }
   str[pos++] = str1[k - 1];
   k--;
   j--;
  }
  else if (table[k][j].Router == LEFT)
   j--;
  else
   k--;
}

//inverster string
char *similarStr = new char[strlen(str) + 1];
for (int i = strlen(str) - 1,j = 0;i >= 0;i--,j++)
similarStr[j] = str[i];
similarStr[strlen(str)] = '\0';

//Clear
for (int i = 0;i <= len1;i++)
delete[] table[i];
delete[] table;
delete[] str;
return similarStr;
}

程序当中的原理可以按照下面的图形象的表示，图当中的一些箭头就是问题解决方案当中描述的解决方式，利用这些箭头我们可以方便的得到最终的相似串。

二、最长相同子串问题

最长相同子串问题如果使用枚举的方法从两个子串当中分别取出各种长度相同的子串并进行比较最后从一系列相同子串当中取得最长子串的办法来解决，就从两个字符串当中取子串的子问题就需要2的指数级别的操作，因此在字符串长度较长时性能不能被接受。我们在这里使用了一种类似于上面DNA问题当中的方法来解决这个问题。

首先我们从一个字符开始比较，从将字符串1当中和字符串2当中1个字符相同的两个位置配成位置对<i,j>并且记录当前已经相同的字符数放入一个链表当中，然后在第二次比较的时候我们根据链表当中已经存在的位置对来比较str1[i+1]和str[j+1]如果相同则把位置对修改为<i+1,j+1>并且将这个链表项当中记录的已经相同的字符数加1，当完成链表当中所有链表项的操作以后我们需要对整个链表进行整理，在链表当中仅仅保留相同字符数量最多的链表项其他链表项都删除，在比较的过程当中如果我们发现所有的链表项当中str1[i+1] != str2[j+1]那么我们可以断定链表当中与保存的信息相关的子串已经是两个字符串之间最长的相同子串，这时比较结束，开始输出这些最长子串，具体算法如下：

struct Node
{
int pos1;
int pos2;
int len;
Node *next;
};

struct Queue
{
Node *front;
Node *rear;
int maxLen;
};

void InitQueue(Queue &q);
void InsertQueue(Queue &q,int len,int pos1,int pos2);
void DeleteQueue(Queue &q);
void orderQueue(Queue &q);
void EmptyQueue(Queue &q);

char *GetMaxSub(const char *str1,const char *str2);

void InitQueue(Queue &q)
{
q.front = q.rear = 0;
q.maxLen = -1;
}

void InsertQueue(Queue &q,int len,int pos1,int pos2)
{
Node *node = new Node;
node->pos1 = pos1;
node->pos2 = pos2;
node->len = len;
node->next = 0;
if (len > q.maxLen)
  q.maxLen = len;
if (q.front == 0)
  q.front = node;
else
  q.rear->next = node;
q.rear = node;
}

void DeleteQueue(Queue &q)
{
if (q.front)
{
  Node *temp = q.front;
  q.front = q.front->next;
  if (temp == q.rear)
   q.rear = 0;
  delete temp;
}
}

void orderQueue(Queue &q)
{
Node *node = q.front;
Node *preNode = 0;
while (node)
{
  if (node->len > q.maxLen)
   q.maxLen = node->len;
  node = node->next;
}

node = q.front;
while (node)
  if (node->len < q.maxLen)
  {
   if (preNode == 0)
   {
    DeleteQueue(q);
    node = q.front;
   }
   else
   {
    preNode->next = node->next;
    if (node == q.rear)
     q.rear = preNode;
    Node *temp = node;
    node = node->next;
    delete temp;
   }

  }
  else
  {
   preNode = node;
   node = node->next;
  }
}

void EmptyQueue(Queue &q)
{
while (q.front)
DeleteQueue(q);
}

char * GetMaxSub(const char *str1,const char *str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
Queue q;
InitQueue(q);
for (int i = 0;i < len1;i++)
  for (int j = 0;j < len2;j++)
   if (str1[i] == str2[j])
    InsertQueue(q,0,i,j);
int curLen;
do
{
  curLen = q.maxLen;
  Node *node = q.front;
  while (node)
  {
   if (node->pos1 + node->len + 1 < len1 && node->pos2 + node->len + 1 < len2 && str1[node->pos1 + node->len + 1] == str2[node->pos2 + node->len + 1])
    node->len++;
   node = node->next;
  }
  OrderQueue(q);
}while (curLen < q.maxLen);

char *returnValue = 0;
if (q.front)
{
  returnValue = new char[q.maxLen + 2];
  strncpy(returnValue,&str1[q.front->pos1],q.front->len + 1);
  returnValue[q.front->len + 1] = '\0';
}
EmptyQueue(q);
return returnValue;
}

分类:MFC | 固定链接 | 评论: 0 | 引用: 13712 | 查看次数: 8079

VC中编写COM供ASP使用时的注意问题...

作者:admin 日期:2007-12-20

1。对象创建

<%
Set cls = Server.CreateObject("Simplealt.first_alt")
b = cls.funsum3(5)

分类:MFC | 固定链接 | 评论: 0 | 引用: 23007 | 查看次数: 10844

Request...

作者:admin 日期:2007-09-22

   1. CookieContainer myCookieContainer = new CookieContainer();
   2.
   3. private string PostHtml(string url,string postData,Encoding enc)
   4.         {
   5.             string result = "";

分类:.NET | 固定链接 | 评论: 0 | 引用: 27384 | 查看次数: 11575

DDE数据交换

作者:admin 日期:2007-09-16

DDE是一种动态数据交换机制（Dynamic Data Exchange，DDE）。使用DDE通讯需要两个Windows应用程序，其中一个作为服务器处理信息，另外一个作为客户机从服务器获得信息。客户机应用程序向当前所激活的服务器应用程序发送一条消息请求信息，服务器应用程序根据该信息作出应答，从而实现两个程序之间的数据交换。

DDE（Dynamic data exchange）的工作原理是：
甲方申请一块全局内存，然后把内存指针postmessage到乙方，
乙方根据收到的指针访问那块全局内存。

分类:Other | 固定链接 | 评论: 0 | 引用: 29629 | 查看次数: 9282

Win32程序模型

作者:admin 日期:2007-09-08

关于Windows程序模型的最重要之处在于，程序是在Windows面向对象的体系结构中运行的。

在WinMain()函数中，程序所进行的最重要工作是注册窗口类，从而把自定义的窗口过程提供给Windows。然后程序调用Windows创建和显示窗口，由此启动同用户的交互过程。在消息循环中，程序不断取得消息，但并不进行处理，而是将其发回Windows，由Windows将消息发给相应的窗口过程。消息循环的作用在于控制生命期，如果没有消息循环，进程将立即结束。

在较高层次上来看，一个可扩展的系统会给模块提供资源和自由，而模块应当配合系统的整体结构。程序执行时，Windows会为其创建进程，分配资源，并调用WinMain()。WinMain()是进程入口，也是进程出口，在此期间进程可以做任何事情，但是为了使用Windows提供的各种便利，它必须符合Windows程序模型，将自己的运行结合到Windows环境中。作为进程出口， WinMain()决定着程序生命期。一个提供窗口过程而等待Windows调用的程序如何维持和结束自己的生命期呢，应该由消息来决定。当进程没有要处理的消息时，它应该等待，所以WinMain()必须知道有没有消息，Windows发给窗口过程的消息不能绕过WinMain()；当进程收到特定的消息时，它结束生命期，所以WinMain()还应该了解消息的内容。这正是GetMessage()所做的，如果取不到消息就阻塞，如果取到 WM_QUIT消息就返回0，结束消息循环。那么如果取到普通的消息呢，由WinMain()直接调用窗口过程不可以吗？这种做法有悖于程序由 Windows调用的基本思想，而实际上也会出现问题。一个窗口程序可能有很多窗口类，一些窗口类及其窗口过程是程序自定义的，另一些则是在 Windows内部定义的，程序看不到其窗口过程，比如各种控件窗口。窗口程序运行起来以后，这些窗口类互相配合，它们通信的方式就是消息。由于消息指向的窗口过程可能是自定义的，也可能是Windows内部的，只有Windows才能把它们都送到目的地，并保持发送方式的一致性。所以WinMain() 取到消息后，通过DispatchMessage()将其发回Windows，由Windows为其调用适当的窗口过程，直到窗口过程调用后返回 Windows，DispatchMessage()才返回。(Windows调用窗口过程之后控制首先返回Windows，由WinMain()调用窗口过程之后控制保持在程序中，这种区别是否也有作用？不过经我试验，在一个Win32 SDK的Hello程序中改由WinMain()调用窗口过程，没有发现什么问题)

分类:SDK | 固定链接 | 评论: 0 | 引用: 22112 | 查看次数: 10119

MVC模式和MFC文档/视图结构

作者:admin 日期:2007-09-08

MVC(Model-View-Controller)模式的基本思想是数据，显示和处理相分离。模型(Model)负责数据管理，视图(View)负责数据显示，控制器(Controller)负责业务逻辑和响应策略。

从MVC的形成过程来看，最初只有模型和视图两个元素。模型封装了数据并提供操作接口，视图用来表现数据和接收用户请求。模型是独立的，而视图依赖于模型：从模型获取数据进行显示；向模型发送用户请求，并根据返回结果刷新自己。

需要用多个视图表现同一模型时，情况发生了变化：一个视图修改数据以后，不但本身要刷新，其他所有视图也要刷新。如果由该视图通知其他视图，它就需要知道其他所有视图，由于每个视图都可能发出修改，每个视图都要知道其他所有视图，这种关联过于复杂，不但难以维护，而且不便于增加新的视图。如果让模型通知所有视图更新，可能会影响模型的独立性。用观察者(Observer)模式可以解决上述矛盾，从而实现：由模型通知视图，而模型不依赖于具体的视图，具体视图之间相互独立。

分类:MFC | 固定链接 | 评论: 0 | 引用: 23698 | 查看次数: 10769

Form窗体的KeyPreview属性的妙用

作者:admin 日期:2007-08-31

在使用.Net Framework编写窗体应用程序的时候，有时有需要响应窗体的按键消息。

当窗体上没有任何其他控件的时候，窗体是可以直接响应这些消息的。

但是当窗体上有其他控件时，会发现窗体再也不会响应这些消息了，因为这些消息都由其上的控件所处理掉并且不再发给父窗体。

分类:.NET | 固定链接 | 评论: 0 | 引用: 30259 | 查看次数: 12308

GDI+图像处理初级系列—灰度图像处理

作者:admin 日期:2007-08-29

数字图像在计算机上以位图(bitmap)的形式存在,位图是一个矩形点阵，其中每一点称为像素(pixel)，像素是数字图像中的基本单位。一幅m×n大小的图像，是由m×n个明暗度不等的像素组成的。数字图像中各个像素所具有的明暗程度由灰度值(gray level)所标识。一般将白色的灰度值定义为255，黑色灰度值定义为0，而由黑到白之间的明暗度均匀地划分为256个等级。对于黑白图像，每个像素用一个字节数据来表示，而在彩色图像中，每个像素需用三个字节数据来表述。彩色图像可以分解成红(R)、绿(G)、蓝(B)三个单色图像，任何一种颜色都可以由这三种颜色混合构成。在图像处理中，彩色图像的处理通常是通过对其三个单色图像分别处理而得到的。对于位图的相关概念这里就不再详细讲述。

如果要将彩色图像转换为灰度图像，只要将图像中的每个像素取出来，然后取像素的R、G、B颜色分量，利用如下公式计算灰度值：

int gray = r＊0.3 ＋ g＊0.59 ＋ b＊0.11;

分类:.NET | 固定链接 | 评论: 0 | 引用: 25152 | 查看次数: 10692