不会飞的鸟

2010年12月10日 ... 不鸟他们!!! 我要用自己开发的分布式文件系统、分布式调度系统、分布式检索系统, 做自己的搜索引擎!!!大鱼有大志!!! ---杨书童

2015年2月26日 #

[转]Win7下使用VS2010编译的Win32控制台应用程序在XP下运行报错:找不到msvcp100d.dll

//targetver.h

#pragma once

// 包括 SDKDDKVer.h 将定义可用的最高版本的 Windows 平台。

// 如果要为以前的 Windows 平台生成应用程序,请包括 WinSDKVer.h,并将
// WIN32_WINNT 宏设置为要支持的平台,然后再包括 SDKDDKVer.h。

#include <WinSDKVer.h>

#define _WIN32_WINNT _WIN32_WINNT_WINXP

#include <SDKDDKVer.h>

1、如上:在targetver.h中添加代码

2、如下:修改运行库



posted @ 2015-02-26 18:53 不会飞的鸟 阅读(351) | 评论 (0)编辑 收藏

2014年12月18日 #

[转]Linux下g++编译C++连接oracle(OCCI)出现的问题及解决方式

由于项目原因,开始学习C++,刚接触半个多月,今天参考网上例子,写了个简单的C++连接ORACLE的DEMO,可是使用g++编译时不顺利,不是报这个错就是那个,最后参考网上的解决方式和个人理解,终于调试好了,现把编译中出现的问题和解决方法总结出来。 

  源代码 
 
C++代码
  1. #include <iostream>  
  2. #include <string>  
  3. #include "occi.h"  
  4. using namespace oracle::occi;  
  5. using namespace std;  
  6.   
  7. int main()  
  8. {  
  9.         string usr="sys";  
  10.         string pwd="orcl";  
  11.         string SID="ORCL";  
  12.         string date;  
  13.   
  14.         Environment *env=Environment::createEnvironment(Environment::OBJECT);  
  15.         Connection *conn= env->createConnection(usr,pwd,SID);//all strings  
  16.         if(conn)  
  17.                 cout<<"success createConnection!"<<endl;  
  18.         else  
  19.                 cout<<"failure createConnection!"<<endl;  
  20.   
  21.         Statement *stmt = conn->createStatement();  
  22.         string sSQL = "select to_char(sysdate,'yyyy-mm-dd hh24:mi:ss') from dual";  
  23.         stmt->setSQL(sSQL);  
  24.   
  25.   
  26.         ResultSet *rs = stmt->executeQuery();  
  27.         if(rs->next())  
  28.         {  
  29.                 date = rs->getString(1);  
  30.         }  
  31.   
  32.         cout<<"now time :"<<date<<endl;  
  33.   
  34.         env->terminateConnection(conn);  
  35.         Environment::terminateEnvironment(env);  
  36.   
  37.         return 0;  
  38. }  
  39.     
  1. #include <iostream>  
  2. #include <string>  
  3. #include "occi.h"  
  4. using namespace oracle::occi;  
  5. using namespace std;  
  6.   
  7. int main()  
  8. {  
  9.         string usr="sys";  
  10.         string pwd="orcl";  
  11.         string SID="ORCL";  
  12.         string date;  
  13.   
  14.         Environment *env=Environment::createEnvironment(Environment::OBJECT);  
  15.         Connection *conn= env->createConnection(usr,pwd,SID);//all strings  
  16.         if(conn)  
  17.                 cout<<"success createConnection!"<<endl;  
  18.         else  
  19.                 cout<<"failure createConnection!"<<endl;  
  20.   
  21.         Statement *stmt = conn->createStatement();  
  22.         string sSQL = "select to_char(sysdate,'yyyy-mm-dd hh24:mi:ss') from dual";  
  23.         stmt->setSQL(sSQL);  
  24.   
  25.   
  26.         ResultSet *rs = stmt->executeQuery();  
  27.         if(rs->next())  
  28.         {  
  29.                 date = rs->getString(1);  
  30.         }  
  31.   
  32.         cout<<"now time :"<<date<<endl;  
  33.   
  34.         env->terminateConnection(conn);  
  35.         Environment::terminateEnvironment(env);  
  36.   
  37.         return 0;  
  38. }  
  39.     


  本人linux上安装oracle路径:/opt/app/oracle/product/10.2.0/db_1 

  编译命令:g++ -o conn -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib conn_db.cpp -g 

问题一:编译时报如下错误: 
    
Shell代码
  1.       [oracle@localhost demo]$ g++ g++ -o conn -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib -lclntsh -locci /usr/lib/libstdc++.so.5 conn_db.cpp -g  
  2. g++: g++: No such file or directory  
  3. conn_db.cpp:3:18: error: occi.h: No such file or directory  
  4. conn_db.cpp:4: error: 'oracle' has not been declared  
  5. conn_db.cpp:4: error: 'occi' is not a namespace-name  
  6. conn_db.cpp:4: error: expected namespace-name before ';' token  
  7. conn_db.cpp: In function 'int main()':  
  8. conn_db.cpp:14: error: 'Environment' was not declared in this scope  
  9. conn_db.cpp:14: error: 'env' was not declared in this scope  
  10. conn_db.cpp:14: error: 'Environment' is not a class or namespace  
  11. conn_db.cpp:14: error: 'Environment' is not a class or namespace  
  12. conn_db.cpp:15: error: 'Connection' was not declared in this scope  
  13. conn_db.cpp:15: error: 'conn' was not declared in this scope  
  14. conn_db.cpp:21: error: 'Statement' was not declared in this scope  
  15. conn_db.cpp:21: error: 'stmt' was not declared in this scope  
  16. conn_db.cpp:26: error: 'ResultSet' was not declared in this scope  
  17. conn_db.cpp:26: error: 'rs' was not declared in this scope  
  18. conn_db.cpp:35: error: 'Environment' is not a class or namespace  
  19.        

   
    解决:编译时没有引入OCCI头文件,如果没有,先下载对应的 ORACLE client安装,比如我的是oracle10g,下载了oracle-instantclient-basic- 10.2.0.4-1.i386.zip,解压到一个目录下(/home/oracle/oracle/include),然后在编译文件的时候引进这个解压目录 

   编译命令增加OCCI目录:g++ -o conn -I/home/oracle/oracle/include -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib conn_db.cpp -g 


问题2:找不到对应函数 
 
Shell代码
  1.    [oracle@localhost demo]$ g++ -o conn -I/home/oracle/oracle/include -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib conn_db.cpp -Wall -O -g  
  2. /tmp/cclFs9xq.o: In function `main':  
  3. /home/oracle/oracle/demo/conn_db.cpp:14: undefined reference to `oracle::occi::Environment::createEnvironment(oracle::occi::Environment::Mode, void*, void* (*)(void*, unsigned int), void* (*)(void*, void*, unsigned int), void (*)(void*, void*))'  
  4. /home/oracle/oracle/demo/conn_db.cpp:35: undefined reference to `oracle::occi::Environment::terminateEnvironment(oracle::occi::Environment*)'  
  5. collect2: ld returned 1 exit status   
  6.    

解决:增加libocci.so和libclntsh.so指定编译 
  
  修改后的编译命令: g++ -o conn -I/home/oracle/oracle/include -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib conn_db.cpp -lclntsh -locci -Wall -O -g 

  另外可能在引入-lclntsh -locci编译时可能会报找不到以下错误: 
    
Shell代码
  1.      [oracle@localhost demo]$ g++ -o conn -I/home/oracle/oracle/include -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib conn_db.cpp -lclntsh -locci /usr/lib/libstdc++.so.5 -Wall -O -g  
  2. /usr/bin/ld: cannot find -lclntsh  
  3. collect2: ld returned 1 exit status  
  4. [oracle@localhost demo]$   
  5.        

     解决:这是因为没有找到libclntsh.so和libocci.so链接库,你在可以把oracle client安装目录下把这两个文件拷贝到$ORACLE_HOME/lib目录下,或加到/usr/lib目录下就可以了 

问题三:occi在linux编译运行时报libstdc++.so.6冲突的问题 
   
Java代码
  1. [oracle@localhost demo]$ g++ -o conn -I/home/oracle/oracle/include -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib conn_db.cpp -lclntsh -locci -Wall -O -g  
  2. /usr/bin/ld: warning: libstdc++.so.5, needed by /opt/app/oracle/product/10.2.0/db_1/lib/libocci.so, may conflict with libstdc++.so.6  
  1. [oracle@localhost demo]$ g++ -o conn -I/home/oracle/oracle/include -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib conn_db.cpp -lclntsh -locci -Wall -O -g  
  2. /usr/bin/ld: warning: libstdc++.so.5, needed by /opt/app/oracle/product/10.2.0/db_1/lib/libocci.so, may conflict with libstdc++.so.6  

  解决:OCCI库在linux编译的时候,由于linux版本太高,会提示以上情况,实际上,在大多数linux系统上,还保留有libstdc++5的库,自己手工在编译的时候加上去就好了 

  修改后的编译命令:g++ -o conn -I/home/oracle/oracle/include -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib -lclntsh -locci /usr/lib/libstdc++.so.5 conn_db.cpp -g 

  编译通过后执行结果输出: 
  
Shell代码
  1. [oracle@localhost demo]$ g++ -o conn -I/home/oracle/oracle/include -L/opt/app/oracle/product/10.2.0/db_1/lib -L/opt/oracle/product/10.2.0/db_1/rdbms/lib conn_db.cpp -lclntsh -locci /usr/lib/libstdc++.so.5 -Wall -O -g  
  2. [oracle@localhost demo]$ ./conn  
  3. success createConnection!  
  4. now time :2010-11-14 22:49:24  
  5. [oracle@localhost demo]$  


posted @ 2014-12-18 13:04 不会飞的鸟 阅读(403) | 评论 (0)编辑 收藏

2014年11月10日 #

各种字符串Hash函数比较

常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。

常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。对于以上几种哈希函数,我对其进行了一个小小的评测。

Hash函数数据1数据2数据3数据4数据1得分数据2得分数据3得分数据4得分平均分
BKDRHash20477448196.5510090.9582.0592.64
APHash23475449396.5588.4610051.2886.28
DJBHash22497547496.5592.31010083.43
JSHash14476150610084.6296.8317.9581.94
RSHash10486150510010051.5820.5175.96
SDBMHash32484950493.192.3157.0123.0872.41
PJWHash302648785130043.89021.95
ELFHash302648785130043.89021.95

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

经过比较,得出以上平均得分。平均数为平方平均数。可以发现,BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。

在信息修竞赛中,要本着易于编码调试的原则,个人认为BKDRHash是最适合记忆和使用的。

BYVoid原创,欢迎建议、交流、批评和指正。

附:各种哈希函数的C语言程序代码

unsigned int SDBMHash(char *str)
{
    unsigned 
int hash = 0;

    
while (*str)
    {
        
// equivalent to: hash = 65599*hash + (*str++);
        hash = (*str+++ (hash << 6+ (hash << 16- hash;
    }

    
return (hash & 0x7FFFFFFF);
}

// RS Hash Function
unsigned int RSHash(char *str)
{
    unsigned 
int b = 378551;
    unsigned 
int a = 63689;
    unsigned 
int hash = 0;

    
while (*str)
    {
        hash 
= hash * a + (*str++);
        a 
*= b;
    }

    
return (hash & 0x7FFFFFFF);
}

// JS Hash Function
unsigned int JSHash(char *str)
{
    unsigned 
int hash = 1315423911;

    
while (*str)
    {
        hash 
^= ((hash << 5+ (*str+++ (hash >> 2));
    }

    
return (hash & 0x7FFFFFFF);
}

// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
    unsigned 
int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int* 8);
    unsigned 
int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3/ 4);
    unsigned 
int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
    unsigned 
int HighBits         = (unsigned int)(0xFFFFFFFF<< (BitsInUnignedInt - OneEighth);
    unsigned 
int hash             = 0;
    unsigned 
int test             = 0;

    
while (*str)
    {
        hash 
= (hash << OneEighth) + (*str++);
        
if ((test = hash & HighBits) != 0)
        {
            hash 
= ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }

    
return (hash & 0x7FFFFFFF);
}

// ELF Hash Function
unsigned int ELFHash(char *str)
{
    unsigned 
int hash = 0;
    unsigned 
int x    = 0;

    
while (*str)
    {
        hash 
= (hash << 4+ (*str++);
        
if ((x = hash & 0xF0000000L!= 0)
        {
            hash 
^= (x >> 24);
            hash 
&= ~x;
        }
    }

    
return (hash & 0x7FFFFFFF);
}

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned 
int seed = 131// 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;

    
while (*str)
    {
        hash 
= hash * seed + (*str++);
    }

    
return (hash & 0x7FFFFFFF);
}

// DJB Hash Function
unsigned int DJBHash(char *str)
{
    unsigned 
int hash = 5381;

    
while (*str)
    {
        hash 
+= (hash << 5+ (*str++);
    }

    
return (hash & 0x7FFFFFFF);
}

// AP Hash Function
unsigned int APHash(char *str)
{
    unsigned 
int hash = 0;
    
int i;

    
for (i=0*str; i++)
    {
        
if ((i & 1== 0)
        {
            hash 
^= ((hash << 7^ (*str++^ (hash >> 3));
        }
        
else
        {
            hash 
^= (~((hash << 11^ (*str++^ (hash >> 5)));
        }
    }

    
return (hash & 0x7FFFFFFF);
}

posted @ 2014-11-10 19:53 不会飞的鸟 阅读(263) | 评论 (0)编辑 收藏

2014年5月26日 #

[转]C++的Json解析库:jsoncpp和boost

JSON(JavaScript Object Notation)跟xml一样也是一种数据交换格式,了解json请参考其官网http://json.org/,本文不再对json做介绍,将重点介绍c++的json解析库的使用方法。json官网上列出了各种语言对应的json解析库,作者仅介绍自己使用过的两种C++的json解析库:jsoncpp(v0.5.0)和Boost(v1.34.0)。

一. 使用jsoncpp解析json

Jsoncpp是个跨平台的开源库,首先从http://jsoncpp.sourceforge.net/上下载jsoncpp库源码,我下载的是v0.5.0,压缩包大约107K,解压,在jsoncpp-src-0.5.0/makefiles/vs71目录里找到jsoncpp.sln,用VS2003及以上版本编译,默认生成静态链接库。 在工程中引用,只需要include/json及.lib文件即可。

使用JsonCpp前先来熟悉几个主要的类:

Json::Value 可以表示里所有的类型,比如int,string,object,array等,具体应用将会在后边示例中介绍。

Json::Reader 将json文件流或字符串解析到Json::Value, 主要函数有Parse。

Json::Writer 与Json::Reader相反,将Json::Value转化成字符串流,注意它的两个子类:Json::FastWriter和Json::StyleWriter,分别输出不带格式的json和带格式的json。

1. 从字符串解析json

int ParseJsonFromString()
{
  const char* str = "{\"uploadid\": \"UP000000\",\"code\": 100,\"msg\": \"\",\"files\": \"\"}";

  Json::Reader reader;
  Json::Value root;
  if (reader.parse(str, root))  // reader将Json字符串解析到root,root将包含Json里所有子元素
  {
    std::string upload_id = root["uploadid"].asString();  // 访问节点,upload_id = "UP000000"
    int code = root["code"].asInt();    // 访问节点,code = 100
  }
  return 0;
}

2. 从文件解析json

{
    "uploadid": "UP000000",
    "code": "0",
    "msg": "",
    "files":
    [
        {
            "code": "0",
            "msg": "",
            "filename": "1D_16-35_1.jpg",
            "filesize": "196690",
            "width": "1024",
            "height": "682",
            "images":
            [
                {
                    "url": "fmn061/20111118",
                    "type": "large",
                    "width": "720",
                    "height": "479"
                },
                {
                    "url": "fmn061/20111118",
                    "type": "main",
                    "width": "200",
                    "height": "133"
                }
            ]
        }
    ]
}
解析代码:
int ParseJsonFromFile(const char* filename)
{
  // 解析json用Json::Reader
  Json::Reader reader;
  // Json::Value是一种很重要的类型,可以代表任意类型。如int, string, object, array
  Json::Value root;       

  std::ifstream is;
  is.open (filename, std::ios::binary );  
  if (reader.parse(is, root))
  {
    std::string code;
    if (!root["files"].isNull())  // 访问节点,Access an object value by name, create a null member if it does not exist.
      code = root["uploadid"].asString();
    
    // 访问节点,Return the member named key if it exist, defaultValue otherwise.
    code = root.get("uploadid", "null").asString();

    // 得到"files"的数组个数
    int file_size = root["files"].size();

    // 遍历数组
    for(int i = 0; i < file_size; ++i)
    {
      Json::Value val_image = root["files"][i]["images"];
      int image_size = val_image.size();
      for(int j = 0; j < image_size; ++j)
      {
        std::string type = val_image[j]["type"].asString();
        std::string url = val_image[j]["url"].asString();
      }
    }
  }
  is.close();
  return 0;
}

3. 在json结构中插入json

    Json::Value arrayObj;   // 构建对象
    Json::Value new_item, new_item1;
    new_item["date"] = "2011-12-28";
    new_item1["time"] = "22:30:36";
    arrayObj.append(new_item);  // 插入数组成员
    arrayObj.append(new_item1); // 插入数组成员
    int file_size = root["files"].size();
    for(int i = 0; i < file_size; ++i)
      root["files"][i]["exifs"] = arrayObj;   // 插入原json中

4. 输出json

// 转换为字符串(带格式)
std::string out = root.toStyledString();
// 输出无格式json字符串
Json::FastWriter writer;
std::string out2 = writer.write(root);

二. 使用Boost property_tree解析json

property_tree可以解析xml,json,ini,info等格式的数据,用property_tree解析这几种格式使用方法很相似。

解析json很简单,命名空间为boost::property_tree,reson_json函数将文件流、字符串解析到ptree,write_json将ptree输出为字符串或文件流。其余的都是对ptree的操作。

解析json需要加头文件:

#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>

1. 解析json

解析一段下面的数据:

{
  "code": 0,
  "images":
  [
    {
      "url": "fmn057/20111221/1130/head_kJoO_05d9000251de125c.jpg"
    },
    {
      "url": "fmn057/20111221/1130/original_kJoO_05d9000251de125c.jpg"
    }
  ]
}
int ParseJson()
{
  std::string str = "{\"code\":0,\"images\":[{\"url\":\"fmn057/20111221/1130/head_kJoO_05d9000251de125c.jpg\"},{\"url\":\"fmn057/20111221/1130/original_kJoO_05d9000251de125c.jpg\"}]}";
  using namespace boost::property_tree;

  std::stringstream ss(str);
  ptree pt;
  try{    
    read_json(ss, pt);
  }
  catch(ptree_error & e) {
    return 1; 
  }

  try{
    int code = pt.get<int>("code");   // 得到"code"的value
    ptree image_array = pt.get_child("images");  // get_child得到数组对象
    
    
// 遍历数组
    BOOST_FOREACH(boost::property_tree::ptree::value_type &v, image_array)
    {
      std::stringstream s;
      write_json(s, v.second);
      std::string image_item = s.str();
    }
  }
  catch (ptree_error & e)
  {
    return 2;
  }
  return 0;
}

2. 构造json

int InsertJson()
{
  std::string str = "{\"code\":0,\"images\":[{\"url\":\"fmn057/20111221/1130/head_kJoO_05d9000251de125c.jpg\"},{\"url\":\"fmn057/20111221/1130/original_kJoO_05d9000251de125c.jpg\"}]}";
  using namespace boost::property_tree;

  std::stringstream ss(str);
  ptree pt;
  try{    
    read_json(ss, pt);
  }
  catch(ptree_error & e) {
    return 1; 
  }

  // 修改/增加一个key-value,key不存在则增加
  pt.put("upid", "00001");

  // 插入一个数组
  ptree exif_array;
  ptree array1, array2, array3;
  array1.put("Make", "NIKON");
  array2.put("DateTime", "2011:05:31 06:47:09");
  array3.put("Software", "Ver.1.01");
  exif_array.push_back(std::make_pair("", array1));
  exif_array.push_back(std::make_pair("", array2));
  exif_array.push_back(std::make_pair("", array3));

//   exif_array.push_back(std::make_pair("Make", "NIKON"));
//   exif_array.push_back(std::make_pair("DateTime", "2011:05:31 06:47:09"));
//   exif_array.push_back(std::make_pair("Software", "Ver.1.01"));

  pt.put_child("exifs", exif_array);
  std::stringstream s2;
  write_json(s2, pt);
  std::string outstr = s2.str();

  return 0;
}

三. 两种解析库的使用经验

1. 用boost::property_tree解析字符串遇到"\/"时解析失败,而jsoncpp可以解析成功,要知道'/'前面加一个'\'是JSON标准格式。

2. boost::property_tree的read_json和write_json在多线程中使用会引起崩溃。

针对1,可以在使用boost::property_tree解析前写个函数去掉"\/"中的'\',针对2,在多线程中同步一下可以解决。

我的使用心得:使用boost::property_tree不仅可以解析json,还可以解析xml,info等格式的数据。对于解析json,使用boost::property_tree解析还可以忍受,但解析xml,由于遇到问题太多只能换其它库了。

posted @ 2014-05-26 00:36 不会飞的鸟 阅读(348) | 评论 (0)编辑 收藏

2014年3月6日 #

[转]字符串匹配的Boyer-Moore算法

上一篇文章,我介绍了KMP算法

但是,它并不是效率最高的算法,实际采用并不多。各种文本编辑器的"查找"功能(Ctrl+F),大多采用Boyer-Moore算法

Boyer-Moore算法不仅效率高,而且构思巧妙,容易理解。1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。

下面,我根据Moore教授自己的例子来解释这种算法。

1.

假定字符串为"HERE IS A SIMPLE EXAMPLE",搜索词为"EXAMPLE"。

2.

首先,"字符串"与"搜索词"头部对齐,从尾部开始比较。

这是一个很聪明的想法,因为如果尾部字符不匹配,那么只要一次比较,就可以知道前7个字符(整体上)肯定不是要找的结果。

我们看到,"S"与"E"不匹配。这时,"S"就被称为"坏字符"(bad character),即不匹配的字符。我们还发现,"S"不包含在搜索词"EXAMPLE"之中,这意味着可以把搜索词直接移到"S"的后一位。

3.

依然从尾部开始比较,发现"P"与"E"不匹配,所以"P"是"坏字符"。但是,"P"包含在搜索词"EXAMPLE"之中。所以,将搜索词后移两位,两个"P"对齐。

4.

我们由此总结出"坏字符规则"

  后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置

如果"坏字符"不包含在搜索词之中,则上一次出现位置为 -1。

以"P"为例,它作为"坏字符",出现在搜索词的第6位(从0开始编号),在搜索词中的上一次出现位置为4,所以后移 6 - 4 = 2位。再以前面第二步的"S"为例,它出现在第6位,上一次出现位置是 -1(即未出现),则整个搜索词后移 6 - (-1) = 7位。

5.

依然从尾部开始比较,"E"与"E"匹配。

6.

比较前面一位,"LE"与"LE"匹配。

7.

比较前面一位,"PLE"与"PLE"匹配。

8.

比较前面一位,"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"(good suffix),即所有尾部匹配的字符串。注意,"MPLE"、"PLE"、"LE"、"E"都是好后缀。

9.

比较前一位,发现"I"与"A"不匹配。所以,"I"是"坏字符"。

10.

根据"坏字符规则",此时搜索词应该后移 2 - (-1)= 3 位。问题是,此时有没有更好的移法?

11.

我们知道,此时存在"好后缀"。所以,可以采用"好后缀规则"

  后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置

举例来说,如果字符串"ABCDAB"的后一个"AB"是"好后缀"。那么它的位置是5(从0开始计算,取最后的"B"的值),在"搜索词中的上一次出现位置"是1(第一个"B"的位置),所以后移 5 - 1 = 4位,前一个"AB"移到后一个"AB"的位置。

再举一个例子,如果字符串"ABCDEF"的"EF"是好后缀,则"EF"的位置是5 ,上一次出现的位置是 -1(即未出现),所以后移 5 - (-1) = 6位,即整个字符串移到"F"的后一位。

这个规则有三个注意点:

  (1)"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀,则它的位置以"F"为准,即5(从0开始计算)。

  (2)如果"好后缀"在搜索词中只出现一次,则它的上一次出现位置为 -1。比如,"EF"在"ABCDEF"之中只出现一次,则它的上一次出现位置为-1(即未出现)。

  (3)如果"好后缀"有多个,则除了最长的那个"好后缀",其他"好后缀"的上一次出现位置必须在头部。比如,假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B",请问这时"好后缀"的上一次出现位置是什么?回答是,此时采用的好后缀是"B",它的上一次出现位置是头部,即第0位。这个规则也可以这样表达:如果最长的那个"好后缀"只出现一次,则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB",即虚拟加入最前面的"DA"。

回到上文的这个例子。此时,所有的"好后缀"(MPLE、PLE、LE、E)之中,只有"E"在"EXAMPLE"还出现在头部,所以后移 6 - 0 = 6位。

12.

可以看到,"坏字符规则"只能移3位,"好后缀规则"可以移6位。所以,Boyer-Moore算法的基本思想是,每次后移这两个规则之中的较大值。

更巧妙的是,这两个规则的移动位数,只与搜索词有关,与原字符串无关。因此,可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时,只要查表比较一下就可以了。

13.

继续从尾部开始比较,"P"与"E"不匹配,因此"P"是"坏字符"。根据"坏字符规则",后移 6 - 4 = 2位。

14.

从尾部开始逐位比较,发现全部匹配,于是搜索结束。如果还要继续查找(即找出全部匹配),则根据"好后缀规则",后移 6 - 0 = 6位,即头部的"E"移到尾部的"E"的位置。

posted @ 2014-03-06 21:47 不会飞的鸟 阅读(245) | 评论 (0)编辑 收藏

[转]字符串匹配的KMP算法

字符串匹配是计算机的基本任务之一。

举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?

许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。

这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。

1.

首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

2.

因为B与A不匹配,搜索词再往后移。

3.

就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

4.

接着比较字符串和搜索词的下一个字符,还是相同。

5.

直到字符串有一个字符,与搜索词对应的字符不相同为止。

6.

这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。

7.

一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

8.

怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

9.

已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:

  移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4,所以将搜索词向后移动4位。

10.

因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。

11.

因为空格与A不匹配,继续后移一位。

12.

逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。

13.

逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。

14.

下面介绍《部分匹配表》是如何产生的。

首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

15.

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,

  - "A"的前缀和后缀都为空集,共有元素的长度为0;

  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

16.

"部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

posted @ 2014-03-06 21:46 不会飞的鸟 阅读(165) | 评论 (0)编辑 收藏

[转]进程与线程的一个简单解释

进程(process)和线程(thread)是操作系统的基本概念,但是它们比较抽象,不容易掌握。

最近,我读到一篇材料,发现有一个很好的类比,可以把它们解释地清晰易懂。

1.

计算机的核心是CPU,它承担了所有的计算任务。它就像一座工厂,时刻在运行。

2.

假定工厂的电力有限,一次只能供给一个车间使用。也就是说,一个车间开工的时候,其他车间都必须停工。背后的含义就是,单个CPU一次只能运行一个任务。

3.

进程就好比工厂的车间,它代表CPU所能处理的单个任务。任一时刻,CPU总是运行一个进程,其他进程处于非运行状态。

4.

一个车间里,可以有很多工人。他们协同完成一个任务。

5.

线程就好比车间里的工人。一个进程可以包括多个线程。

6.

车间的空间是工人们共享的,比如许多房间是每个工人都可以进出的。这象征一个进程的内存空间是共享的,每个线程都可以使用这些共享内存。

7.

可是,每间房间的大小不同,有些房间最多只能容纳一个人,比如厕所。里面有人的时候,其他人就不能进去了。这代表一个线程使用某些共享内存时,其他线程必须等它结束,才能使用这一块内存。

8.

一个防止他人进入的简单方法,就是门口加一把锁。先到的人锁上门,后到的人看到上锁,就在门口排队,等锁打开再进去。这就叫"互斥锁"(Mutual exclusion,缩写 Mutex),防止多个线程同时读写某一块内存区域。

9.

还有些房间,可以同时容纳n个人,比如厨房。也就是说,如果人数大于n,多出来的人只能在外面等着。这好比某些内存区域,只能供给固定数目的线程使用。

10.

这时的解决方法,就是在门口挂n把钥匙。进去的人就取一把钥匙,出来时再把钥匙挂回原处。后到的人发现钥匙架空了,就知道必须在门口排队等着了。这种做法叫做"信号量"(Semaphore),用来保证多个线程不会互相冲突。

不难看出,mutex是semaphore的一种特殊情况(n=1时)。也就是说,完全可以用后者替代前者。但是,因为mutex较为简单,且效率高,所以在必须保证资源独占的情况下,还是采用这种设计。

11.

操作系统的设计,因此可以归结为三点:

(1)以多进程形式,允许多个任务同时运行;

(2)以多线程形式,允许单个任务分成不同的部分运行;

(3)提供协调机制,一方面防止进程之间和线程之间产生冲突,另一方面允许进程之间和线程之间共享资源。

posted @ 2014-03-06 21:44 不会飞的鸟 阅读(130) | 评论 (0)编辑 收藏

[转]相似图片搜索的原理(二)

昨天,我在isnowfy的网站看到,还有其他两种方法也很简单,这里做一些笔记。

一、颜色分布法

每张图片都可以生成颜色分布的直方图(color histogram)。如果两张图片的直方图很接近,就可以认为它们很相似。

任何一种颜色都是由红绿蓝三原色(RGB)构成的,所以上图共有4张直方图(三原色直方图 + 最后合成的直方图)。

如果每种原色都可以取256个值,那么整个颜色空间共有1600万种颜色(256的三次方)。针对这1600万种颜色比较直方图,计算量实在太大了,因此需要采用简化方法。可以将0~255分成四个区:0~63为第0区,64~127为第1区,128~191为第2区,192~255为第3区。这意味着红绿蓝分别有4个区,总共可以构成64种组合(4的3次方)。

任何一种颜色必然属于这64种组合中的一种,这样就可以统计每一种组合包含的像素数量。

上图是某张图片的颜色分布表,将表中最后一栏提取出来,组成一个64维向量(7414, 230, 0, 0, 8, ..., 109, 0, 0, 3415, 53929)。这个向量就是这张图片的特征值或者叫"指纹"。

于是,寻找相似图片就变成了找出与其最相似的向量。这可以用皮尔逊相关系数或者余弦相似度算出。

二、内容特征法

除了颜色构成,还可以从比较图片内容的相似性入手。

首先,将原图转成一张较小的灰度图片,假定为50x50像素。然后,确定一个阈值,将灰度图片转成黑白图片。

  

如果两张图片很相似,它们的黑白轮廓应该是相近的。于是,问题就变成了,第一步如何确定一个合理的阈值,正确呈现照片中的轮廓?

显然,前景色与背景色反差越大,轮廓就越明显。这意味着,如果我们找到一个值,可以使得前景色和背景色各自的"类内差异最小"(minimizing the intra-class variance),或者"类间差异最大"(maximizing the inter-class variance),那么这个值就是理想的阈值。

1979年,日本学者大津展之证明了,"类内差异最小"与"类间差异最大"是同一件事,即对应同一个阈值。他提出一种简单的算法,可以求出这个阈值,这被称为"大津法"(Otsu's method)。下面就是他的计算方法。

假定一张图片共有n个像素,其中灰度值小于阈值的像素为 n1 个,大于等于阈值的像素为 n2 个( n1 + n2 = n )。w1 和 w2 表示这两种像素各自的比重。

  w1 = n1 / n

  w2 = n2 / n

再假定,所有灰度值小于阈值的像素的平均值和方差分别为 μ1 和 σ1,所有灰度值大于等于阈值的像素的平均值和方差分别为 μ2 和 σ2。于是,可以得到

  类内差异 = w1(σ1的平方) + w2(σ2的平方)

  类间差异 = w1w2(μ1-μ2)^2

可以证明,这两个式子是等价的:得到"类内差异"的最小值,等同于得到"类间差异"的最大值。不过,从计算难度看,后者的计算要容易一些。

下一步用"穷举法",将阈值从灰度的最低值到最高值,依次取一遍,分别代入上面的算式。使得"类内差异最小"或"类间差异最大"的那个值,就是最终的阈值。具体的实例和Java算法,请看这里

有了50x50像素的黑白缩略图,就等于有了一个50x50的0-1矩阵。矩阵的每个值对应原图的一个像素,0表示黑色,1表示白色。这个矩阵就是一张图片的特征矩阵。

两个特征矩阵的不同之处越少,就代表两张图片越相似。这可以用"异或运算"实现(即两个值之中只有一个为1,则运算结果为1,否则运算结果为0)。对不同图片的特征矩阵进行"异或运算",结果中的1越少,就是越相似的图片。

posted @ 2014-03-06 21:42 不会飞的鸟 阅读(205) | 评论 (0)编辑 收藏

[转]相似图片搜索的原理(一)

上个月,Google把"相似图片搜索"正式放上了首页。

你可以用一张图片,搜索互联网上所有与它相似的图片。点击搜索框中照相机的图标。

一个对话框会出现。

你输入网片的网址,或者直接上传图片,Google就会找出与其相似的图片。下面这张图片是美国女演员Alyson Hannigan。

上传后,Google返回如下结果:

类似的"相似图片搜索引擎"还有不少,TinEye甚至可以找出照片的拍摄背景。

==========================================================

这种技术的原理是什么?计算机怎么知道两张图片相似呢?

根据Neal Krawetz博士的解释,原理非常简单易懂。我们可以用一个快速算法,就达到基本的效果。

这里的关键技术叫做"感知哈希算法"(Perceptual hash algorithm),它的作用是对每张图片生成一个"指纹"(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。

下面是一个最简单的实现:

第一步,缩小尺寸。

将图片缩小到8x8的尺寸,总共64个像素。这一步的作用是去除图片的细节,只保留结构、明暗等基本信息,摒弃不同尺寸、比例带来的图片差异。

 

第二步,简化色彩。

将缩小后的图片,转为64级灰度。也就是说,所有像素点总共只有64种颜色。

第三步,计算平均值。

计算所有64个像素的灰度平均值。

第四步,比较像素的灰度。

将每个像素的灰度,与平均值进行比较。大于或等于平均值,记为1;小于平均值,记为0。

第五步,计算哈希值。

将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了。

 =  = 8f373714acfcf4d0

得到指纹以后,就可以对比不同的图片,看看64位中有多少位是不一样的。在理论上,这等同于计算"汉明距离"(Hamming distance)。如果不相同的数据位不超过5,就说明两张图片很相似;如果大于10,就说明这是两张不同的图片。

具体的代码实现,可以参见Wote用python语言写的imgHash.py。代码很短,只有53行。使用的时候,第一个参数是基准图片,第二个参数是用来比较的其他图片所在的目录,返回结果是两张图片之间不相同的数据位数量(汉明距离)。

这种算法的优点是简单快速,不受图片大小缩放的影响,缺点是图片的内容不能变更。如果在图片上加几个文字,它就认不出来了。所以,它的最佳用途是根据缩略图,找出原图。

实际应用中,往往采用更强大的pHash算法和SIFT算法,它们能够识别图片的变形。只要变形程度不超过25%,它们就能匹配原图。这些算法虽然更复杂,但是原理与上面的简便算法是一样的,就是先将图片转化成Hash字符串,然后再进行比较。

posted @ 2014-03-06 21:42 不会飞的鸟 阅读(198) | 评论 (0)编辑 收藏

[转]TF-IDF与余弦相似性的应用(三):自动摘要

有时候,很简单的数学方法,就可以完成很复杂的任务。

这个系列的前两部分就是很好的例子。仅仅依靠统计词频,就能找出关键词相似文章。虽然它们算不上效果最好的方法,但肯定是最简便易行的方法。

今天,依然继续这个主题。讨论如何通过词频,对文章进行自动摘要(Automatic summarization)。

如果能从3000字的文章,提炼出150字的摘要,就可以为读者节省大量阅读时间。由人完成的摘要叫"人工摘要",由机器完成的就叫"自动摘要"。许多网站都需要它,比如论文网站、新闻网站、搜索引擎等等。2007年,美国学者的论文《A Survey on Automatic Text Summarization》(Dipanjan Das, Andre F.T. Martins, 2007)总结了目前的自动摘要算法。其中,很重要的一种就是词频统计。

这种方法最早出自1958年的IBM公司科学家H.P. Luhn的论文《The Automatic Creation of Literature Abstracts》

Luhn博士认为,文章的信息都包含在句子中,有些句子包含的信息多,有些句子包含的信息少。"自动摘要"就是要找出那些包含信息最多的句子。

句子的信息量用"关键词"来衡量。如果包含的关键词越多,就说明这个句子越重要。Luhn提出用"簇"(cluster)表示关键词的聚集。所谓"簇"就是包含多个关键词的句子片段。

上图就是Luhn原始论文的插图,被框起来的部分就是一个"簇"。只要关键词之间的距离小于"门槛值",它们就被认为处于同一个簇之中。Luhn建议的门槛值是4或5。也就是说,如果两个关键词之间有5个以上的其他词,就可以把这两个关键词分在两个簇。

下一步,对于每个簇,都计算它的重要性分值。

以前图为例,其中的簇一共有7个词,其中4个是关键词。因此,它的重要性分值等于 ( 4 x 4 ) / 7 = 2.3。

然后,找出包含分值最高的簇的句子(比如5句),把它们合在一起,就构成了这篇文章的自动摘要。具体实现可以参见《Mining the Social Web: Analyzing Data from Facebook, Twitter, LinkedIn, and Other Social Media Sites》(O'Reilly, 2011)一书的第8章,python代码见github

Luhn的这种算法后来被简化,不再区分"簇",只考虑句子包含的关键词。下面就是一个例子(采用伪码表示),只考虑关键词首先出现的句子。

  Summarizer(originalText, maxSummarySize):

    // 计算原始文本的词频,生成一个数组,比如[(10,'the'), (3,'language'), (8,'code')...]
    wordFrequences = getWordCounts(originalText)

    // 过滤掉停用词,数组变成[(3, 'language'), (8, 'code')...]
    contentWordFrequences = filtStopWords(wordFrequences)

    // 按照词频进行排序,数组变成['code', 'language'...]
    contentWordsSortbyFreq = sortByFreqThenDropFreq(contentWordFrequences)

    // 将文章分成句子
    sentences = getSentences(originalText)

    // 选择关键词首先出现的句子
    setSummarySentences = {}
    foreach word in contentWordsSortbyFreq:
      firstMatchingSentence = search(sentences, word)
      setSummarySentences.add(firstMatchingSentence)
      if setSummarySentences.size() = maxSummarySize:
        break

    // 将选中的句子按照出现顺序,组成摘要
    summary = ""
    foreach sentence in sentences:
      if sentence in setSummarySentences:
        summary = summary + " " + sentence

    return summary

类似的算法已经被写成了工具,比如基于Java的Classifier4J库的SimpleSummariser模块、基于C语言的OTS库、以及基于classifier4J的C#实现python实现

posted @ 2014-03-06 21:37 不会飞的鸟 阅读(146) | 评论 (0)编辑 收藏

仅列出标题  下一页