#pragma once
// 包括 SDKDDKVer.h 定义可用的最高版本的 Windows q_?br />
// 如果要ؓ以前?nbsp;Windows q_生成应用E序Q请包括 WinSDKVer.hQƈ?br />// WIN32_WINNT 宏设|ؓ要支持的q_Q然后再包括 SDKDDKVer.h?/span>
#include <WinSDKVer.h>
#define _WIN32_WINNT _WIN32_WINNT_WINXP
#include <SDKDDKVer.h>
1、如上：在targetver.h中添加代?/p>
2、如下：修改q行?/p>
常用的字W串Hash函数q有ELFHashQAPHash{等Q都是十分简单有效的Ҏ。这些函C用位q算使得每一个字W都Ҏ后的函数g生媄响。另外还有以MD5和SHA1Z表的杂凑函数Q这些函数几乎不可能扑ֈ撞?/p>
常用字符串哈希函数有BKDRHashQAPHashQDJBHashQJSHashQRSHashQSDBMHashQPJWHashQELFHash{等。对于以上几U哈希函敎ͼ我对其进行了一个小的评测?br />
| Hash函数 | 数据1 | 数据2 | 数据3 | 数据4 | 数据1得分 | 数据2得分 | 数据3得分 | 数据4得分 | q_?/td> |
| BKDRHash | 2 | 0 | 4774 | 481 | 96.55 | 100 | 90.95 | 82.05 | 92.64 |
| APHash | 2 | 3 | 4754 | 493 | 96.55 | 88.46 | 100 | 51.28 | 86.28 |
| DJBHash | 2 | 2 | 4975 | 474 | 96.55 | 92.31 | 0 | 100 | 83.43 |
| JSHash | 1 | 4 | 4761 | 506 | 100 | 84.62 | 96.83 | 17.95 | 81.94 |
| RSHash | 1 | 0 | 4861 | 505 | 100 | 100 | 51.58 | 20.51 | 75.96 |
| SDBMHash | 3 | 2 | 4849 | 504 | 93.1 | 92.31 | 57.01 | 23.08 | 72.41 |
| PJWHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
| ELFHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
其中数据1?00000个字母和数字l成的随Z哈希冲突个数。数??00000个有意义的英文句子哈希冲H个数。数?为数?的哈希g1000003(大素?求模后存储到U性表中冲H的个数。数?为数?的哈希g10000019(更大素数)求模后存储到U性表中冲H的个数?/p>
l过比较Q得Z上^均得分。^均数为^方^均数。可以发玎ͼBKDRHash无论是在实际效果q是~码实现中，效果都是最H出的。APHash也是较ؓ优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相|其算法本质是怼的?/p>
在信息修竞赛中，要本着易于~码调试的原则，个h认ؓBKDRHash是最适合记忆和用的?/p>
BYVoid原创Q欢q徏议、交、批评和指正?/p>附：各种哈希函数的C语言E序代码
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);
}
]]>
一. 使用jsoncpp解析json
Jsoncpp是个跨^台的开源库Q首先从http://jsoncpp.sourceforge.net/上下载jsoncpp库源码，我下载的是v0.5.0Q压~包大约107KQ解压，在jsoncpp-src-0.5.0/makefiles/vs71目录里找到jsoncpp.slnQ用VS2003及以上版本编译，默认生成静态链接库?在工E中引用Q只需要include/json?lib文g卛_?/span>
使用JsonCpp前先来熟悉几个主要的c：
Json::Value 可以表示里所有的cdQ比如int,string,object,array{，具体应用会在后边示例中介绍?/span>
Json::Reader json文g或字符串解析到Json::Value, 主要函数有Parse?/span>
Json::Writer 与Json::Reader相反Q将Json::Value转化成字W串，注意它的两个子类QJson::FastWriter和Json::StyleWriterQ分别输Z带格式的json和带格式的json?/span>
1. 从字W串解析json
int ParseJsonFromString()
{
const char* str = "{\"uploadid\": \"UP000000\",\"code\": 100,\"msg\": \"\",\"files\": \"\"}";
Json::Reader reader;
Json::Value root;
if (reader.parse(str, root)) // readerJson字符串解析到rootQroot包含Json里所有子元素
{
std::string upload_id = root["uploadid"].asString(); // 讉K节点Qupload_id = "UP000000"
int code = root["code"].asInt(); // 讉K节点Qcode = 100
}
return 0;
}
{
const char* str = "{\"uploadid\": \"UP000000\",\"code\": 100,\"msg\": \"\",\"files\": \"\"}";
Json::Reader reader;
Json::Value root;
if (reader.parse(str, root)) // readerJson字符串解析到rootQroot包含Json里所有子元素
{
std::string upload_id = root["uploadid"].asString(); // 讉K节点Qupload_id = "UP000000"
int code = root["code"].asInt(); // 讉K节点Qcode = 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"
}
]
}
]
}
"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"
}
]
}
]
}
解析代码Q?br />
int ParseJsonFromFile(const char* filename)
{
// 解析json用Json::Reader
Json::Reader reader;
// Json::Value是一U很重要的类型，可以代表Lcd。如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()) // 讉K节点QAccess an object value by name, create a null member if it does not exist.
code = root["uploadid"].asString();
// 讉K节点QReturn the member named key if it exist, defaultValue otherwise.
code = root.get("uploadid", "null").asString();
// 得到"files"的数l个?/span>
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;
}
{
// 解析json用Json::Reader
Json::Reader reader;
// Json::Value是一U很重要的类型，可以代表Lcd。如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()) // 讉K节点QAccess an object value by name, create a null member if it does not exist.
code = root["uploadid"].asString();
// 讉K节点QReturn the member named key if it exist, defaultValue otherwise.
code = root.get("uploadid", "null").asString();
// 得到"files"的数l个?/span>
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. 在jsonl构中插入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?/span>
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?/span>
4. 输出json
// 转换为字W串Q带格式Q?/span>
std::string out = root.toStyledString();
// 输出无格式json字符?/span>
Json::FastWriter writer;
std::string out2 = writer.write(root);
std::string out = root.toStyledString();
// 输出无格式json字符?/span>
Json::FastWriter writer;
std::string out2 = writer.write(root);
? 使用Boost property_tree解析json
property_tree可以解析xmlQjsonQiniQinfo{格式的数据Q用property_tree解析q几U格式用方法很怼?/p>
解析json很简单，命名I间?span id="4KSFindDIV">boost::property_treeQreson_json函数文件流、字W串解析到ptreeQwrite_jsonptree输出为字W串或文件流。其余的都是对ptree的操作?/p>
解析json需要加头文Ӟ
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>
1. 解析json
解析一D下面的数据Q?/p>
{
"code": 0,
"images":
[
{
"url": "fmn057/20111221/1130/head_kJoO_05d9000251de125c.jpg"
},
{
"url": "fmn057/20111221/1130/original_kJoO_05d9000251de125c.jpg"
}
]
}
"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;
}
{
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-valueQkey不存在则增加
pt.put("upid", "00001");
// 插入一个数l?/span>
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;
}
{
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-valueQkey不存在则增加
pt.put("upid", "00001");
// 插入一个数l?/span>
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;
}
? 两种解析库的使用l验
1. ?span id="15KSFindDIV">boost::property_tree解析字符串遇?\/"时解析失败，而jsoncpp可以解析成功Q要知道'/'前面加一?\'是JSON标准格式?/p>
2. boost::property_tree的read_json和write_json在多U程中用会引v崩溃?/p>
针对1Q可以在使用boost::property_tree解析前写个函数去?\/"中的'\'Q针?Q在多线E中同步一下可以解冟?/p>
我的使用心得Q?span id="18KSFindDIV">boost::property_tree不仅可以解析jsonQ还可以解析xmlQinfo{格式的数据。对于解析jsonQ?span id="19KSFindDIV">boost::property_tree解析q可以忍受，但解析xmlQ由于遇到问题太多只能换其它库了?/p>
但是Q它q不是效率最高的法Q实际采用ƈ不多。各U文本编辑器?查找"功能QCtrl+FQ，大多采用Boyer-Moore法?/p>
Boyer-Moore法不仅效率高，而且构思y妙，Ҏ理解?977q_德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这U算法?/p>
下面Q我ҎMoore教授自己?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">例子来解释这U算法?/p>
1.
假定字符串ؓ"HERE IS A SIMPLE EXAMPLE"Q搜索词?EXAMPLE"?/p>
2.
首先Q?字符??搜烦?头部寚wQ从N开始比较?/p>
q是一个很聪明的想法，因ؓ如果N字符不匹配，那么只要一ơ比较，可以知道前7个字W（整体上）肯定不是要找的结果?/p>
我们看到Q?S"?E"不匹配。这Ӟ"S"pUCؓ"坏字W?Qbad characterQ，即不匚w的字W?/span>我们q发玎ͼ"S"不包含在搜烦?EXAMPLE"之中Q这意味着可以把搜索词直接Ud"S"的后一位?/p> 3. 依然从尾部开始比较，发现"P"?E"不匹配，所?P"?坏字W?。但是，"P"包含在搜索词"EXAMPLE"之中。所以，搜索词后移两位Q两?P"寚w?/p> 4. 我们由此ȝ?span style="font-weight: 800;">"坏字W规?
后移位数 = 坏字W的位置 - 搜烦词中的上一ơ出C|?/p>
如果"坏字W?不包含在搜烦词之中，则上一ơ出C|ؓ -1?/p>
?P"ZQ它作ؓ"坏字W?Q出现在搜烦词的W?位（?开始编PQ在搜烦词中的上一ơ出C|ؓ4Q所以后U?6 - 4 = 2位。再以前面第二步?S"ZQ它出现在第6位，上一ơ出C|是 -1Q即未出玎ͼQ则整个搜烦词后U?6 - (-1) = 7位?/p>
5.
依然从尾部开始比较，"E"?E"匚w?/p>
6.
比较前面一位，"LE"?LE"匚w?/p>
7.
比较前面一位，"PLE"?PLE"匚w?/p>
8.
比较前面一位，"MPLE"?MPLE"匚w?span style="font-weight: 800;">我们把这U情늧?好后~"Qgood suffixQ，x有尾部匹配的字符丌Ӏ?/span>注意Q?MPLE"?PLE"?LE"?E"都是好后~?/p>
9.
比较前一位，发现"I"?A"不匹配。所以，"I"?坏字W??/p>
10.
Ҏ"坏字W规?Q此时搜索词应该后移 2 - Q?1Q? 3 位。问题是Q此时有没有更好的移法？
11.
我们知道Q此时存?好后~"。所以，可以采用"好后~规则"Q?/p>
后移位数 = 好后~的位|?- 搜烦词中的上一ơ出C|?/p>
举例来说Q如果字W串"ABCDAB"的后一?AB"?好后~"。那么它的位|是5Q从0开始计，取最后的"B"的|Q在"搜烦词中的上一ơ出C|??Q第一?B"的位|）Q所以后U?5 - 1 = 4位，前一?AB"Ud后一?AB"的位|?/p>
再D一个例子，如果字符?ABCDEF"?EF"是好后缀Q则"EF"的位|是5 Q上一ơ出现的位置?-1Q即未出玎ͼQ所以后U?5 - (-1) = 6位，x个字W串Ud"F"的后一位?/p>
q个规则有三个注意点Q?/p>
Q?Q?好后~"的位|以最后一个字Wؓ准。假?ABCDEF"?EF"是好后缀Q则它的位置?F"为准Q即5Q从0开始计）?/p>
Q?Q如?好后~"在搜索词中只出现一ơ，则它的上一ơ出C|ؓ -1。比如，"EF"?ABCDEF"之中只出Cơ，则它的上一ơ出C|ؓ-1Q即未出玎ͼ?/p>
Q?Q如?好后~"有多个，则除了最长的那个"好后~"Q其?好后~"的上一ơ出C|必d头部。比如，假定"BABCDAB"?好后~"?DAB"?AB"?B"Q请问这?好后~"的上一ơ出C|是什么？回答是，此时采用的好后缀?B"Q它的上一ơ出C|是头部Q即W?位。这个规则也可以q样表达Q如果最长的那个"好后~"只出Cơ，则可以把搜烦词改写成如下形式q行位置计算"(DA)BABCDAB"Q即虚拟加入最前面?DA"?/p>
回到上文的这个例子。此Ӟ所有的"好后~"QMPLE、PLE、LE、EQ之中，只有"E"?EXAMPLE"q出现在头部Q所以后U?6 - 0 = 6位?/p>
12.
可以看到Q?坏字W规?只能U?位，"好后~规则"可以U?位。所以，Boyer-Moore法的基本思想是，每次后移q两个规则之中的较大倹{?/span>
更y妙的是，q两个规则的Ud位数Q只与搜索词有关Q与原字W串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。用时Q只要查表比较一下就可以了?/p>
13.
l箋从尾部开始比较，"P"?E"不匹配，因此"P"?坏字W?。根?坏字W规?Q后U?6 - 4 = 2位?/p>
14.
从尾部开始逐位比较Q发现全部匹配，于是搜烦l束。如果还要l查找（x出全部匹配）Q则Ҏ"好后~规则"Q后U?6 - 0 = 6位，卛_部的"E"UdN?E"的位|?/p>
举例来说Q有一个字W串"BBC ABCDAB ABCDABCDABDE"Q我想知道，里面是否包含另一个字W串"ABCDABD"Q?/p>
许多法可以完成q个dQ?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">Knuth-Morris-Pratt法
Q简UKMPQ是最常用的之一。它以三个发明者命名，起头的那个K是著名U学家Donald Knuth?/p>
q种法不太Ҏ理解Q网上有很多解释Q但读v来都很费劌Ӏ直到读?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">Jake Boxer的文章，我才真正理解q种法。下面，我用自己的语aQ试囑ֆ一比较好懂的KMP法解释?/p>
1.
首先Q字W串"BBC ABCDAB ABCDABCDABDE"的第一个字W与搜烦?ABCDABD"的第一个字W，q行比较。因为B与A不匹配，所以搜索词后移一位?/p>
2.
因ؓB与A不匹配，搜烦词再往后移?/p>
3.
pP直到字符串有一个字W，与搜索词的第一个字W相同ؓ止?/p>
4.
接着比较字符串和搜烦词的下一个字W，q是相同?/p>
5.
直到字符串有一个字W，与搜索词对应的字W不相同为止?/p>
6.
q时Q最自然的反应是Q将搜烦词整个后UM位，再从头逐个比较。这样做虽然可行Q但是效率很差，因ؓ你要?搜烦位置"Ud已经比较q的位置Q重比一遍?/p>
7.
一个基本事实是Q当I格与D不匹配时Q你其实知道前面六个字符?ABCDAB"。KMP法的想法是Q设法利用这个已知信息，不要?搜烦位置"Ud已经比较q的位置Ql把它向后移Q这样就提高了效率?/p>
8.
怎么做到q一点呢Q可以针Ҏ索词Q算Z张《部分匹配表》（Partial Match TableQ。这张表是如何生的Q后面再介绍Q这里只要会用就可以了?/p>
9.
已知I格与D不匹配时Q前面六个字W?ABCDAB"是匹配的。查表可知，最后一个匹配字WB对应?部分匚w??Q因此按照下面的公式出向后Ud的位敎ͼ
Ud位数 = 已匹配的字符?- 对应的部分匹配?/p>
因ؓ 6 - 2 {于4Q所以将搜烦词向后移?位?/p>
10.
因ؓI格与E不匹配，搜烦词还要l往后移。这Ӟ已匹配的字符Cؓ2Q?AB"Q，对应?部分匚w??。所以，Ud位数 = 2 - 0Q结果ؓ 2Q于是将搜烦词向后移2位?/p>
11.
因ؓI格与A不匹配，l箋后移一位?/p>
12.
逐位比较Q直到发现C与D不匹配。于是，Ud位数 = 6 - 2Ql将搜烦词向后移?位?/p>
13.
逐位比较Q直到搜索词的最后一位，发现完全匚wQ于是搜索完成。如果还要l搜索（x出全部匹配）Q移动位?= 7 - 0Q再搜索词向后Ud7位，q里׃再重复了?/p>
14.
下面介绍《部分匹配表》是如何产生的?/p>
首先Q要了解两个概念Q?前缀"?后缀"?"前缀"指除了最后一个字W以外，一个字W串的全部头部组合；"后缀"指除了第一个字W以外，一个字W串的全部尾部组合?/p>
15.
"部分匚w?是"前缀"?后缀"的最长的共有元素的长度。以"ABCDABD"ZQ?/p>
Q "A"的前~和后~都ؓI集Q共有元素的长度?Q?/p>
Q "AB"的前~为[A]Q后~为[B]Q共有元素的长度?Q?/p>
Q "ABC"的前~为[A, AB]Q后~为[BC, C]Q共有元素的长度0Q?/p>
Q "ABCD"的前~为[A, AB, ABC]Q后~为[BCD, CD, D]Q共有元素的长度?Q?/p>
Q "ABCDA"的前~为[A, AB, ABC, ABCD]Q后~为[BCDA, CDA, DA, A]Q共有元素ؓ"A"Q长度ؓ1Q?/p>
Q "ABCDAB"的前~为[A, AB, ABC, ABCD, ABCDA]Q后~为[BCDAB, CDAB, DAB, AB, B]Q共有元素ؓ"AB"Q长度ؓ2Q?/p>
Q "ABCDABD"的前~为[A, AB, ABC, ABCD, ABCDA, ABCDAB]Q后~为[BCDABD, CDABD, DABD, ABD, BD, D]Q共有元素的长度??/p>
16.
"部分匚w"的实质是Q有时候，字符串头部和N会有重复。比如，"ABCDAB"之中有两?AB"Q那么它?部分匚w?是2Q?AB"的长度）。搜索词Ud的时候，W一?AB"向后Ud4位（字符串长?部分匚w|Q就可以来到W二?AB"的位|?/p>
一、颜色分布法
每张囄都可以生?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">颜色分布的直方图Qcolor histogramQ。如果两张图片的直方囑־接近Q就可以认ؓ它们很相伹{?/p>
M一U颜色都是由U绿蓝三原色QRGBQ构成的Q所以上囑օ?张直方图Q三原色直方?+ 最后合成的直方图）?/p>
如果每种原色都可以取256个|那么整个颜色I间共有1600万种颜色Q?56的三ơ方Q。针对这1600万种颜色比较直方图，计算量实在太大了Q因此需要采用简化方法。可以将0?55分成四个区：0?3为第0区，64?27为第1区，128?91为第2区，192?55为第3区。这意味着U绿蓝分别有4个区Qd可以构成64U组合（4?ơ方Q?/p>
M一U颜色必然属于这64U组合中的一U，q样可以统计每一U组合包含的像素数量?/p>
上图是某张图片的颜色分布表，表中最后一栏提取出来，l成一?4l向?7414, 230, 0, 0, 8, ..., 109, 0, 0, 3415, 53929)。这个向量就是这张图片的特征值或者叫"指纹"?/p>
于是Q寻扄似图片就变成了找Z其最怼的向量。这可以?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">皮尔逊相关系?/a>或?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">余u怼?/a>出?/p>
二、内容特征法
除了颜色构成Q还可以从比较图片内容的怼性入手?/p>
首先Q将原图转成一张较的灰度囄Q假定ؓ50x50像素。然后，定一个阈|灰度图片{成黑白图片?/p>
如果两张囄很相|它们的黑白轮廓应该是相近的。于是，问题变成了Q第一步如何确定一个合理的阈|正确呈现照片中的轮廓Q?/p>
昄Q前景色与背景色反差大Q轮廓就明显。这意味着Q如果我们找C个|可以使得前景色和背景色各自的"cd差异最?Qminimizing the intra-class varianceQ，或?c间差异最?Qmaximizing the inter-class varianceQ，那么q个值就是理想的阈倹{?/p>
1979q_日本学者大z展之证明了Q?cd差异最??c间差异最?是同一件事Q即对应同一个阈倹{他提出一U简单的法Q可以求个阈|q被UCؓ"大|?QOtsu's methodQ。下面就是他的计方法?/p>
假定一张图片共有n个像素，其中灰度值小于阈值的像素?n1 个，大于{于阈值的像素?n2 个（ n1 + n2 = n Q。w1 ?w2 表示q两U像素各自的比重?/p>
w1 = n1 / n
w2 = n2 / n
再假定，所有灰度值小于阈值的像素的^均值和方差分别?μ1 ?σ1Q所有灰度值大于等于阈值的像素的^均值和方差分别?μ2 ?σ2。于是，可以得到
cd差异 = w1(σ1的^? + w2(σ2的^?
c间差异 = w1w2(μ1-μ2)^2
可以证明Q这两个式子是等LQ得?cd差异"的最|{同于得?c间差异"的最大倹{不q，从计难度看Q后者的计算要容易一些?/p>
下一步用"ID?Q将阈g灰度的最低值到最高|依次取一遍，分别代入上面的算式。?cd差异最??c间差异最?的那个|是最l的阈倹{具体的实例和Java法Q请?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">q里?/p>
有了50x50像素的黑白羃略图Q就{于有了一?0x50?-1矩阵。矩늚每个值对应原囄一个像素，0表示黑色Q?表示白色。这个矩阵就是一张图片的特征矩阵?/p>
两个特征矩阵的不同之处越，׃表两张图片越怼。这可以?异或q算"实现Q即两个g中只有一个ؓ1Q则q算l果?Q否则运结果ؓ0Q。对不同囄的特征矩阵进?异或q算"Q结果中?少Q就是越怼的图片?/p>
q个pd的前两部分就是很好的例子。仅仅依靠统计词频，p扑և关键?/a>?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">怼文章。虽然它们算不上效果最好的ҎQ但肯定是最便易行的Ҏ?/p>
今天Q依然l这个主题。讨论如何通过词频Q对文章q行自动摘要QAutomatic summarizationQ?/p>
如果能从3000字的文章Q提炼出150字的摘要Q就可以者节省大量阅L间。由人完成的摘要?人工摘要"Q由机器完成的就?自动摘要"。许多网站都需要它Q比如论文网站、新ȝ站、搜索引擎等{?007q_国学者的论文《A Survey on Automatic Text Summarization?/a>QDipanjan Das, Andre F.T. Martins, 2007Qȝ了目前的自动摘要法。其中，很重要的一U就是词频统计?/p> q种Ҏ最早出?958q的IBM公司U学?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">H.P. Luhn
Luhn博士认ؓQ文章的信息都包含在句子中，有些句子包含的信息多Q有些句子包含的信息?自动摘要"是要找出那些包含信息最多的句子?/p>
句子的信息量?关键?来衡量。如果包含的关键词越多，p明这个句子越重要。Luhn提出??QclusterQ表C关键词的聚集。所??是包含多个关键词的句子片段?/p>
上图是Luhn原始论文的插图，被框h的部分就是一??。只要关键词之间的距d?门槛?Q它们就被认为处于同一个簇之中。Luhn的门槛值是4?。也是_如果两个关键词之间有5个以上的其他词，可以把q两个关键词分在两个?/p>
下一步，对于每个，都计它的重要性分倹{?/p>
以前图ؓ例，其中的簇一共有7个词Q其?个是关键词。因此，它的重要性分值等?( 4 x 4 ) / 7 = 2.3?/p>
然后Q找出包含分值最高的的句子Q比?句）Q把它们合在一P构成了q篇文章的自动摘要。具体实现可以参?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">《Mining the Social Web: Analyzing Data from Facebook, Twitter, LinkedIn, and Other Social Media Sites?/a>QO'Reilly, 2011Q一书的W?章，python代码?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">github?/p>
Luhn的这U算法后来被化，不再区分"?Q只考虑句子包含的关键词。下面就是一个例子（采用伪码表示Q，只考虑关键词首先出现的句子?/p>
Summarizer(originalText, maxSummarySize):
// 计算原始文本的词频，生成一个数l，比如[(10,'the'), (3,'language'), (8,'code')...]
wordFrequences = getWordCounts(originalText)// qo掉停用词Q数l变成[(3, 'language'), (8, 'code')...]
contentWordFrequences = filtStopWords(wordFrequences)// 按照词频q行排序Q数l变成['code', 'language'...]
contentWordsSortbyFreq = sortByFreqThenDropFreq(contentWordFrequences)// 文章分成句?br /> sentences = getSentences(originalText)
// 选择关键词首先出现的句子
setSummarySentences = {}
foreach word in contentWordsSortbyFreq:
firstMatchingSentence = search(sentences, word)
setSummarySentences.add(firstMatchingSentence)
if setSummarySentences.size() = maxSummarySize:
break// 选中的句子按照出现顺序，l成摘要
summary = ""
foreach sentence in sentences:
if sentence in setSummarySentences:
summary = summary + " " + sentencereturn summary
cM的算法已l被写成了工P比如ZJava?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">Classifier4J库的SimpleSummariser模块、基于C语言?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">OTS库、以及基于classifier4J?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">C#实现?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">python实现?/p>