#pragma once
// 鍖呮嫭 SDKDDKVer.h 灝嗗畾涔夊彲鐢ㄧ殑鏈楂樼増鏈殑 Windows 騫沖彴銆?br />
// 濡傛灉瑕佷負(fù)浠ュ墠鐨?nbsp;Windows 騫沖彴鐢熸垚搴旂敤紼嬪簭錛岃鍖呮嫭 WinSDKVer.h錛屽茍灝?br />// WIN32_WINNT 瀹忚緗負(fù)瑕佹敮鎸佺殑騫沖彴錛岀劧鍚庡啀鍖呮嫭 SDKDDKVer.h銆?/span>
#include <WinSDKVer.h>
#define _WIN32_WINNT _WIN32_WINNT_WINXP
#include <SDKDDKVer.h>
1銆佸涓婏細(xì)鍦╰argetver.h涓坊鍔犱唬鐮?/p>
2銆佸涓嬶細(xì)淇敼榪愯搴?/p>
甯哥敤鐨勫瓧絎︿覆Hash鍑芥暟榪樻湁ELFHash錛孉PHash絳夌瓑錛岄兘鏄崄鍒嗙畝鍗曟湁鏁堢殑鏂規(guī)硶銆傝繖浜涘嚱鏁頒嬌鐢ㄤ綅榪愮畻浣垮緱姣忎竴涓瓧絎﹂兘瀵規(guī)渶鍚庣殑鍑芥暟鍊間駭鐢熷獎(jiǎng)鍝嶃傚彟澶栬繕鏈変互MD5鍜孲HA1涓轟唬琛ㄧ殑鏉傚噾鍑芥暟錛岃繖浜涘嚱鏁板嚑涔庝笉鍙兘鎵懼埌紕版挒銆?/p>
甯哥敤瀛楃涓插搱甯屽嚱鏁版湁BKDRHash錛孉PHash錛孌JBHash錛孞SHash錛孯SHash錛孲DBMHash錛孭JWHash錛孍LFHash絳夌瓑銆傚浜庝互涓婂嚑縐嶅搱甯屽嚱鏁幫紝鎴戝鍏惰繘琛屼簡(jiǎn)涓涓皬灝忕殑璇勬祴銆?br />
| Hash鍑芥暟 | 鏁版嵁1 | 鏁版嵁2 | 鏁版嵁3 | 鏁版嵁4 | 鏁版嵁1寰楀垎 | 鏁版嵁2寰楀垎 | 鏁版嵁3寰楀垎 | 鏁版嵁4寰楀垎 | 騫沖潎鍒?/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涓瓧姣嶅拰鏁板瓧緇勬垚鐨勯殢鏈轟覆鍝堝笇鍐茬獊涓暟銆傛暟鎹?涓?00000涓湁鎰忎箟鐨勮嫳鏂囧彞瀛愬搱甯屽啿紿佷釜鏁般傛暟鎹?涓烘暟鎹?鐨勫搱甯屽間笌1000003(澶х礌鏁?姹傛ā鍚庡瓨鍌ㄥ埌綰挎ц〃涓啿紿佺殑涓暟銆傛暟鎹?涓烘暟鎹?鐨勫搱甯屽間笌10000019(鏇村ぇ绱犳暟)姹傛ā鍚庡瓨鍌ㄥ埌綰挎ц〃涓啿紿佺殑涓暟銆?/p>
緇忚繃姣旇緝錛屽緱鍑轟互涓婂鉤鍧囧緱鍒嗐傚鉤鍧囨暟涓哄鉤鏂瑰鉤鍧囨暟銆傚彲浠ュ彂鐜幫紝BKDRHash鏃犺鏄湪瀹為檯鏁堟灉榪樻槸緙栫爜瀹炵幇涓紝鏁堟灉閮芥槸鏈紿佸嚭鐨勩侫PHash涔熸槸杈冧負(fù)浼樼鐨勭畻娉曘侱JBHash,JSHash,RSHash涓嶴DBMHash鍚勬湁鍗冪銆侾JWHash涓嶦LFHash鏁堟灉鏈宸紝浣嗗緱鍒嗙浉浼鹼紝鍏剁畻娉曟湰璐ㄦ槸鐩鎬技鐨勩?/p>
鍦ㄤ俊鎭慨绔炶禌涓紝瑕佹湰鐫鏄撲簬緙栫爜璋冭瘯鐨勫師鍒欙紝涓漢璁や負(fù)BKDRHash鏄渶閫傚悎璁板繂鍜屼嬌鐢ㄧ殑銆?/p>
BYVoid鍘熷垱錛屾榪庡緩璁佷氦嫻併佹壒璇勫拰鎸囨銆?/p>闄勶細(xì)鍚勭鍝堝笇鍑芥暟鐨凜璇█紼嬪簭浠ｇ爜
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鏄釜璺ㄥ鉤鍙扮殑寮婧愬簱錛岄鍏堜粠http://jsoncpp.sourceforge.net/涓婁笅杞絡(luò)soncpp搴撴簮鐮侊紝鎴戜笅杞界殑鏄痸0.5.0錛屽帇緙╁寘澶х害107K錛岃В鍘嬶紝鍦╦soncpp-src-0.5.0/makefiles/vs71鐩綍閲屾壘鍒癹soncpp.sln錛岀敤VS2003鍙?qiáng)浠ヤ笂鐗堟湰缂栬瘧锛岄粯璁ょ敓鎴愰潤(rùn)鎬侀摼鎺ュ簱銆?鍦ㄥ伐紼嬩腑寮曠敤錛屽彧闇瑕乮nclude/json鍙?lib鏂囦歡鍗沖彲銆?/span>
浣跨敤JsonCpp鍓嶅厛鏉ョ啛鎮(zhèn)夊嚑涓富瑕佺殑綾伙細(xì)
Json::Value 鍙互琛ㄧず閲屾墍鏈夌殑綾誨瀷錛屾瘮濡俰nt,string,object,array絳夛紝鍏蜂綋搴旂敤灝嗕細(xì)鍦ㄥ悗杈圭ず渚嬩腑浠嬬粛銆?/span>
Json::Reader 灝唈son鏂囦歡嫻佹垨瀛楃涓茶В鏋愬埌Json::Value, 涓昏鍑芥暟鏈塒arse銆?/span>
Json::Writer 涓嶫son::Reader鐩稿弽錛屽皢Json::Value杞寲鎴愬瓧絎︿覆嫻侊紝娉ㄦ剰瀹冪殑涓や釜瀛愮被錛欽son::FastWriter鍜孞son::StyleWriter錛屽垎鍒緭鍑轟笉甯︽牸寮忕殑json鍜屽甫鏍煎紡鐨刯son銆?/span>
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灝咼son瀛楃涓茶В鏋愬埌root錛宺oot灝嗗寘鍚獼son閲屾墍鏈夊瓙鍏冪礌
{
std::string upload_id = root["uploadid"].asString(); // 璁塊棶鑺傜偣錛寀pload_id = "UP000000"
int code = root["code"].asInt(); // 璁塊棶鑺傜偣錛宑ode = 100
}
return 0;
}
{
const char* str = "{\"uploadid\": \"UP000000\",\"code\": 100,\"msg\": \"\",\"files\": \"\"}";
Json::Reader reader;
Json::Value root;
if (reader.parse(str, root)) // reader灝咼son瀛楃涓茶В鏋愬埌root錛宺oot灝嗗寘鍚獼son閲屾墍鏈夊瓙鍏冪礌
{
std::string upload_id = root["uploadid"].asString(); // 璁塊棶鑺傜偣錛寀pload_id = "UP000000"
int code = root["code"].asInt(); // 璁塊棶鑺傜偣錛宑ode = 100
}
return 0;
}
2. 浠庢枃浠惰В鏋恓son
{
"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"
}
]
}
]
}
瑙ｆ瀽浠ｇ爜錛?br />
int ParseJsonFromFile(const char* filename)
{
// 瑙ｆ瀽json鐢↗son::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()) // 璁塊棶鑺傜偣錛孉ccess an object value by name, create a null member if it does not exist.
code = root["uploadid"].asString();
// 璁塊棶鑺傜偣錛孯eturn the member named key if it exist, defaultValue otherwise.
code = root.get("uploadid", "null").asString();
// 寰楀埌"files"鐨勬暟緇勪釜鏁?/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鐢↗son::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()) // 璁塊棶鑺傜偣錛孉ccess an object value by name, create a null member if it does not exist.
code = root["uploadid"].asString();
// 璁塊棶鑺傜偣錛孯eturn the member named key if it exist, defaultValue otherwise.
code = root.get("uploadid", "null").asString();
// 寰楀埌"files"鐨勬暟緇勪釜鏁?/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. 鍦╦son緇撴瀯涓彃鍏son
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; // 鎻掑叆鍘焜son涓?/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; // 鎻掑叆鍘焜son涓?/span>
4. 杈撳嚭json
// 杞崲涓哄瓧絎︿覆錛堝甫鏍煎紡錛?/span>
std::string out = root.toStyledString();
// 杈撳嚭鏃犳牸寮廽son瀛楃涓?/span>
Json::FastWriter writer;
std::string out2 = writer.write(root);
std::string out = root.toStyledString();
// 杈撳嚭鏃犳牸寮廽son瀛楃涓?/span>
Json::FastWriter writer;
std::string out2 = writer.write(root);
浜? 浣跨敤Boost property_tree瑙ｆ瀽json
property_tree鍙互瑙ｆ瀽xml錛宩son錛宨ni錛宨nfo絳夋牸寮忕殑鏁版嵁錛岀敤property_tree瑙ｆ瀽榪欏嚑縐嶆牸寮忎嬌鐢ㄦ柟娉曞緢鐩鎬技銆?/p>
瑙ｆ瀽json寰堢畝鍗曪紝鍛藉悕絀洪棿涓?span id="4KSFindDIV">boost::property_tree錛宺eson_json鍑芥暟灝嗘枃浠舵祦銆佸瓧絎︿覆瑙ｆ瀽鍒皃tree錛寃rite_json灝唒tree杈撳嚭涓哄瓧絎︿覆鎴栨枃浠舵祦銆傚叾浣欑殑閮芥槸瀵筽tree鐨勬搷浣溿?/p>
瑙ｆ瀽json闇瑕佸姞澶存枃浠訛細(xì)
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>
1. 瑙ｆ瀽json
瑙ｆ瀽涓孌典笅闈㈢殑鏁版嵁錛?/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"鐨剉alue
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"鐨剉alue
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. 鏋勯爅son
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;
}
// 淇敼/澧炲姞涓涓猭ey-value錛宬ey涓嶅瓨鍦ㄥ垯澧炲姞
pt.put("upid", "00001");
// 鎻掑叆涓涓暟緇?/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;
}
// 淇敼/澧炲姞涓涓猭ey-value錛宬ey涓嶅瓨鍦ㄥ垯澧炲姞
pt.put("upid", "00001");
// 鎻掑叆涓涓暟緇?/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;
}
涓? 涓ょ瑙ｆ瀽搴撶殑浣跨敤緇忛獙
1. 鐢?span id="15KSFindDIV">boost::property_tree瑙ｆ瀽瀛楃涓查亣鍒?\/"鏃惰В鏋愬け璐ワ紝鑰宩soncpp鍙互瑙ｆ瀽鎴愬姛錛岃鐭ラ亾'/'鍓嶉潰鍔犱竴涓?\'鏄疛SON鏍囧噯鏍煎紡銆?/p>
2. boost::property_tree鐨剅ead_json鍜寃rite_json鍦ㄥ綰跨▼涓嬌鐢ㄤ細(xì)寮曡搗宕╂簝銆?/p>
閽堝1錛屽彲浠ュ湪浣跨敤boost::property_tree瑙ｆ瀽鍓嶅啓涓嚱鏁板幓鎺?\/"涓殑'\'錛岄拡瀵?錛屽湪澶氱嚎紼嬩腑鍚屾涓涓嬪彲浠ヨВ鍐熾?/p>
鎴戠殑浣跨敤蹇?jī)寰楀Q氫嬌鐢?span id="18KSFindDIV">boost::property_tree涓嶄粎鍙互瑙ｆ瀽json錛岃繕鍙互瑙ｆ瀽xml錛宨nfo絳夋牸寮忕殑鏁版嵁銆傚浜庤В鏋恓son錛屼嬌鐢?span id="19KSFindDIV">boost::property_tree瑙ｆ瀽榪樺彲浠ュ繊鍙楋紝浣嗚В鏋恱ml錛岀敱浜庨亣鍒伴棶棰樺お澶氬彧鑳芥崲鍏跺畠搴撲簡(jiǎn)銆?/p>
浣嗘槸錛屽畠騫朵笉鏄晥鐜囨渶楂樼殑綆楁硶錛屽疄闄呴噰鐢ㄥ茍涓嶅銆傚悇縐嶆枃鏈紪杈戝櫒鐨?鏌ユ壘"鍔熻兘錛圕trl+F錛夛紝澶у閲囩敤Boyer-Moore綆楁硶銆?/p>
Boyer-Moore綆楁硶涓嶄粎鏁堢巼楂橈紝鑰屼笖鏋勬濆閥濡欙紝瀹規(guī)槗鐞嗚В銆?977騫達(dá)紝寰峰厠钀ㄦ柉澶у鐨凴obert S. Boyer鏁欐巿鍜孞 Strother Moore鏁欐巿鍙戞槑浜?jiǎn)杩櫩U嶇畻娉曘?/p>
涓嬮潰錛屾垜鏍規(guī)嵁Moore鏁欐巿鑷繁鐨?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">渚嬪瓙鏉ヨВ閲婅繖縐嶇畻娉曘?/p>
1.
鍋囧畾瀛楃涓蹭負(fù)"HERE IS A SIMPLE EXAMPLE"錛屾悳绱㈣瘝涓?EXAMPLE"銆?/p>
2.
棣栧厛錛?瀛楃涓?涓?鎼滅儲(chǔ)璇?澶撮儴瀵歸綈錛屼粠灝鵑儴寮濮嬫瘮杈冦?/p>
榪欐槸涓涓緢鑱槑鐨勬兂娉曪紝鍥犱負(fù)濡傛灉灝鵑儴瀛楃涓嶅尮閰嶏紝閭ｄ箞鍙涓嬈℃瘮杈冿紝灝卞彲浠ョ煡閬撳墠7涓瓧絎︼紙鏁翠綋涓婏級(jí)鑲畾涓嶆槸瑕佹壘鐨勭粨鏋溿?/p>
鎴戜滑鐪嬪埌錛?S"涓?E"涓嶅尮閰嶃傝繖鏃訛紝"S"灝辮縐頒負(fù)"鍧忓瓧絎?錛坆ad character錛夛紝鍗充笉鍖歸厤鐨勫瓧絎︺?/span>鎴戜滑榪樺彂鐜幫紝"S"涓嶅寘鍚湪鎼滅儲(chǔ)璇?EXAMPLE"涔嬩腑錛岃繖鎰忓懗鐫鍙互鎶婃悳绱㈣瘝鐩存帴縐誨埌"S"鐨勫悗涓浣嶃?/p> 3. 渚濈劧浠庡熬閮ㄥ紑濮嬫瘮杈冿紝鍙戠幇"P"涓?E"涓嶅尮閰嶏紝鎵浠?P"鏄?鍧忓瓧絎?銆備絾鏄紝"P"鍖呭惈鍦ㄦ悳绱㈣瘝"EXAMPLE"涔嬩腑銆傛墍浠ワ紝灝嗘悳绱㈣瘝鍚庣Щ涓や綅錛屼袱涓?P"瀵歸綈銆?/p> 4. 鎴戜滑鐢辨鎬葷粨鍑?span style="font-weight: 800;">"鍧忓瓧絎﹁鍒?
銆銆鍚庣Щ浣嶆暟 = 鍧忓瓧絎︾殑浣嶇疆 - 鎼滅儲(chǔ)璇嶄腑鐨勪笂涓嬈″嚭鐜頒綅緗?/p>
濡傛灉"鍧忓瓧絎?涓嶅寘鍚湪鎼滅儲(chǔ)璇嶄箣涓紝鍒欎笂涓嬈″嚭鐜頒綅緗負(fù) -1銆?/p>
浠?P"涓轟緥錛屽畠浣滀負(fù)"鍧忓瓧絎?錛屽嚭鐜板湪鎼滅儲(chǔ)璇嶇殑絎?浣嶏紙浠?寮濮嬬紪鍙鳳級(jí)錛屽湪鎼滅儲(chǔ)璇嶄腑鐨勪笂涓嬈″嚭鐜頒綅緗負(fù)4錛屾墍浠ュ悗縐?6 - 4 = 2浣嶃傚啀浠ュ墠闈㈢浜屾鐨?S"涓轟緥錛屽畠鍑虹幇鍦ㄧ6浣嶏紝涓婁竴嬈″嚭鐜頒綅緗槸 -1錛堝嵆鏈嚭鐜幫級(jí)錛屽垯鏁翠釜鎼滅儲(chǔ)璇嶅悗縐?6 - (-1) = 7浣嶃?/p>
5.
渚濈劧浠庡熬閮ㄥ紑濮嬫瘮杈冿紝"E"涓?E"鍖歸厤銆?/p>
6.
姣旇緝鍓嶉潰涓浣嶏紝"LE"涓?LE"鍖歸厤銆?/p>
7.
姣旇緝鍓嶉潰涓浣嶏紝"PLE"涓?PLE"鍖歸厤銆?/p>
8.
姣旇緝鍓嶉潰涓浣嶏紝"MPLE"涓?MPLE"鍖歸厤銆?span style="font-weight: 800;">鎴戜滑鎶婅繖縐嶆儏鍐電О涓?濂藉悗緙"錛坓ood suffix錛夛紝鍗蟲墍鏈夊熬閮ㄥ尮閰嶇殑瀛楃涓層?/span>娉ㄦ剰錛?MPLE"銆?PLE"銆?LE"銆?E"閮芥槸濂藉悗緙銆?/p>
9.
姣旇緝鍓嶄竴浣嶏紝鍙戠幇"I"涓?A"涓嶅尮閰嶃傛墍浠ワ紝"I"鏄?鍧忓瓧絎?銆?/p>
10.
鏍規(guī)嵁"鍧忓瓧絎﹁鍒?錛屾鏃舵悳绱㈣瘝搴旇鍚庣Щ 2 - 錛?1錛? 3 浣嶃傞棶棰樻槸錛屾鏃舵湁娌℃湁鏇村ソ鐨勭Щ娉曪紵
11.
鎴戜滑鐭ラ亾錛屾鏃跺瓨鍦?濂藉悗緙"銆傛墍浠ワ紝鍙互閲囩敤"濂藉悗緙瑙勫垯"錛?/p>
銆銆鍚庣Щ浣嶆暟 = 濂藉悗緙鐨勪綅緗?- 鎼滅儲(chǔ)璇嶄腑鐨勪笂涓嬈″嚭鐜頒綅緗?/p>
涓句緥鏉ヨ錛屽鏋滃瓧絎︿覆"ABCDAB"鐨勫悗涓涓?AB"鏄?濂藉悗緙"銆傞偅涔堝畠鐨勪綅緗槸5錛堜粠0寮濮嬭綆楋紝鍙栨渶鍚庣殑"B"鐨勫鹼級(jí)錛屽湪"鎼滅儲(chǔ)璇嶄腑鐨勪笂涓嬈″嚭鐜頒綅緗?鏄?錛堢涓涓?B"鐨勪綅緗級(jí)錛屾墍浠ュ悗縐?5 - 1 = 4浣嶏紝鍓嶄竴涓?AB"縐誨埌鍚庝竴涓?AB"鐨勪綅緗?/p>
鍐嶄婦涓涓緥瀛愶紝濡傛灉瀛楃涓?ABCDEF"鐨?EF"鏄ソ鍚庣紑錛屽垯"EF"鐨勪綅緗槸5 錛屼笂涓嬈″嚭鐜扮殑浣嶇疆鏄?-1錛堝嵆鏈嚭鐜幫級(jí)錛屾墍浠ュ悗縐?5 - (-1) = 6浣嶏紝鍗蟲暣涓瓧絎︿覆縐誨埌"F"鐨勫悗涓浣嶃?/p>
榪欎釜瑙勫垯鏈変笁涓敞鎰忕偣錛?/p>
銆銆錛?錛?濂藉悗緙"鐨勪綅緗互鏈鍚庝竴涓瓧絎︿負(fù)鍑嗐傚亣瀹?ABCDEF"鐨?EF"鏄ソ鍚庣紑錛屽垯瀹冪殑浣嶇疆浠?F"涓哄噯錛屽嵆5錛堜粠0寮濮嬭綆楋級(jí)銆?/p>
銆銆錛?錛夊鏋?濂藉悗緙"鍦ㄦ悳绱㈣瘝涓彧鍑虹幇涓嬈★紝鍒欏畠鐨勪笂涓嬈″嚭鐜頒綅緗負(fù) -1銆傛瘮濡傦紝"EF"鍦?ABCDEF"涔嬩腑鍙嚭鐜頒竴嬈★紝鍒欏畠鐨勪笂涓嬈″嚭鐜頒綅緗負(fù)-1錛堝嵆鏈嚭鐜幫級(jí)銆?/p>
銆銆錛?錛夊鏋?濂藉悗緙"鏈夊涓紝鍒欓櫎浜?jiǎn)鏈闀跨殑閭ｄ釜"濂藉悗緙"錛屽叾浠?濂藉悗緙"鐨勪笂涓嬈″嚭鐜頒綅緗繀欏誨湪澶撮儴銆傛瘮濡傦紝鍋囧畾"BABCDAB"鐨?濂藉悗緙"鏄?DAB"銆?AB"銆?B"錛岃闂繖鏃?濂藉悗緙"鐨勪笂涓嬈″嚭鐜頒綅緗槸浠涔堬紵鍥炵瓟鏄紝姝ゆ椂閲囩敤鐨勫ソ鍚庣紑鏄?B"錛屽畠鐨勪笂涓嬈″嚭鐜頒綅緗槸澶撮儴錛屽嵆絎?浣嶃傝繖涓鍒欎篃鍙互榪欐牱琛ㄨ揪錛氬鏋滄渶闀跨殑閭ｄ釜"濂藉悗緙"鍙嚭鐜頒竴嬈★紝鍒欏彲浠ユ妸鎼滅儲(chǔ)璇嶆敼鍐欐垚濡備笅褰㈠紡榪涜浣嶇疆璁＄畻"(DA)BABCDAB"錛屽嵆铏氭嫙鍔犲叆鏈鍓嶉潰鐨?DA"銆?/p>
鍥炲埌涓婃枃鐨勮繖涓緥瀛愩傛鏃訛紝鎵鏈夌殑"濂藉悗緙"錛圡PLE銆丳LE銆丩E銆丒錛変箣涓紝鍙湁"E"鍦?EXAMPLE"榪樺嚭鐜板湪澶撮儴錛屾墍浠ュ悗縐?6 - 0 = 6浣嶃?/p>
12.
鍙互鐪嬪埌錛?鍧忓瓧絎﹁鍒?鍙兘縐?浣嶏紝"濂藉悗緙瑙勫垯"鍙互縐?浣嶃傛墍浠ワ紝Boyer-Moore綆楁硶鐨勫熀鏈濇兂鏄紝姣忔鍚庣Щ榪欎袱涓鍒欎箣涓殑杈冨ぇ鍊箋?/span>
鏇村閥濡欑殑鏄紝榪欎袱涓鍒欑殑縐誨姩浣嶆暟錛屽彧涓庢悳绱㈣瘝鏈夊叧錛屼笌鍘熷瓧絎︿覆鏃犲叧銆傚洜姝わ紝鍙互棰勫厛璁＄畻鐢熸垚銆婂潖瀛楃瑙勫垯琛ㄣ嬪拰銆婂ソ鍚庣紑瑙勫垯琛ㄣ嬨備嬌鐢ㄦ椂錛屽彧瑕佹煡琛ㄦ瘮杈冧竴涓嬪氨鍙互浜?jiǎn)銆?/p>
13.
緇х畫浠庡熬閮ㄥ紑濮嬫瘮杈冿紝"P"涓?E"涓嶅尮閰嶏紝鍥犳"P"鏄?鍧忓瓧絎?銆傛牴鎹?鍧忓瓧絎﹁鍒?錛屽悗縐?6 - 4 = 2浣嶃?/p>
14.
浠庡熬閮ㄥ紑濮嬮愪綅姣旇緝錛屽彂鐜板叏閮ㄥ尮閰嶏紝浜庢槸鎼滅儲(chǔ)緇撴潫銆傚鏋滆繕瑕佺戶緇煡鎵撅紙鍗蟲壘鍑哄叏閮ㄥ尮閰嶏級(jí)錛屽垯鏍規(guī)嵁"濂藉悗緙瑙勫垯"錛屽悗縐?6 - 0 = 6浣嶏紝鍗沖ご閮ㄧ殑"E"縐誨埌灝鵑儴鐨?E"鐨勪綅緗?/p>
涓句緥鏉ヨ錛屾湁涓涓瓧絎︿覆"BBC ABCDAB ABCDABCDABDE"錛屾垜鎯崇煡閬擄紝閲岄潰鏄惁鍖呭惈鍙︿竴涓瓧絎︿覆"ABCDABD"錛?/p>
璁稿綆楁硶鍙互瀹屾垚榪欎釜浠誨姟錛?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">Knuth-Morris-Pratt綆楁硶
錛堢畝縐癒MP錛夋槸鏈甯哥敤鐨勪箣涓銆傚畠浠ヤ笁涓彂鏄庤呭懡鍚嶏紝璧峰ご鐨勯偅涓狵灝辨槸钁楀悕縐戝瀹禗onald Knuth銆?/p>
榪欑綆楁硶涓嶅お瀹規(guī)槗鐞嗚В錛岀綉涓婃湁寰堝瑙ｉ噴錛屼絾璇昏搗鏉ラ兘寰堣垂鍔層傜洿鍒拌鍒?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">Jake Boxer鐨勬枃绔狅紝鎴戞墠鐪熸鐞嗚В榪欑綆楁硶銆備笅闈紝鎴戠敤鑷繁鐨勮璦錛岃瘯鍥懼啓涓綃囨瘮杈冨ソ鎳傜殑KMP綆楁硶瑙ｉ噴銆?/p>
1.
棣栧厛錛屽瓧絎︿覆"BBC ABCDAB ABCDABCDABDE"鐨勭涓涓瓧絎︿笌鎼滅儲(chǔ)璇?ABCDABD"鐨勭涓涓瓧絎︼紝榪涜姣旇緝銆傚洜涓築涓嶢涓嶅尮閰嶏紝鎵浠ユ悳绱㈣瘝鍚庣Щ涓浣嶃?/p>
2.
鍥犱負(fù)B涓嶢涓嶅尮閰嶏紝鎼滅儲(chǔ)璇嶅啀寰鍚庣Щ銆?/p>
3.
灝辮繖鏍鳳紝鐩村埌瀛楃涓叉湁涓涓瓧絎︼紝涓庢悳绱㈣瘝鐨勭涓涓瓧絎︾浉鍚屼負(fù)姝€?/p>
4.
鎺ョ潃姣旇緝瀛楃涓插拰鎼滅儲(chǔ)璇嶇殑涓嬩竴涓瓧絎︼紝榪樻槸鐩稿悓銆?/p>
5.
鐩村埌瀛楃涓叉湁涓涓瓧絎︼紝涓庢悳绱㈣瘝瀵瑰簲鐨勫瓧絎︿笉鐩稿悓涓烘銆?/p>
6.
榪欐椂錛屾渶鑷劧鐨勫弽搴旀槸錛屽皢鎼滅儲(chǔ)璇嶆暣涓悗縐諱竴浣嶏紝鍐嶄粠澶撮愪釜姣旇緝銆傝繖鏍峰仛铏界劧鍙錛屼絾鏄晥鐜囧緢宸紝鍥犱負(fù)浣犺鎶?鎼滅儲(chǔ)浣嶇疆"縐誨埌宸茬粡姣旇緝榪囩殑浣嶇疆錛岄噸姣斾竴閬嶃?/p>
7.
涓涓熀鏈簨瀹炴槸錛屽綋絀烘牸涓嶥涓嶅尮閰嶆椂錛屼綘鍏跺疄鐭ラ亾鍓嶉潰鍏釜瀛楃鏄?ABCDAB"銆侹MP綆楁硶鐨勬兂娉曟槸錛岃娉曞埄鐢ㄨ繖涓凡鐭ヤ俊鎭紝涓嶈鎶?鎼滅儲(chǔ)浣嶇疆"縐誨洖宸茬粡姣旇緝榪囩殑浣嶇疆錛岀戶緇妸瀹冨悜鍚庣Щ錛岃繖鏍峰氨鎻愰珮浜?jiǎn)鏁堢巼銆?/p>
8.
鎬庝箞鍋氬埌榪欎竴鐐瑰憿錛熷彲浠ラ拡瀵規(guī)悳绱㈣瘝錛岀畻鍑轟竴寮犮婇儴鍒嗗尮閰嶈〃銆嬶紙Partial Match Table錛夈傝繖寮犺〃鏄浣曚駭鐢熺殑錛屽悗闈㈠啀浠嬬粛錛岃繖閲屽彧瑕佷細(xì)鐢ㄥ氨鍙互浜?jiǎn)銆?/p>
9.
宸茬煡絀烘牸涓嶥涓嶅尮閰嶆椂錛屽墠闈㈠叚涓瓧絎?ABCDAB"鏄尮閰嶇殑銆傛煡琛ㄥ彲鐭ワ紝鏈鍚庝竴涓尮閰嶅瓧絎瀵瑰簲鐨?閮ㄥ垎鍖歸厤鍊?涓?錛屽洜姝ゆ寜鐓т笅闈㈢殑鍏紡綆楀嚭鍚戝悗縐誨姩鐨勪綅鏁幫細(xì)
銆銆縐誨姩浣嶆暟 = 宸插尮閰嶇殑瀛楃鏁?- 瀵瑰簲鐨勯儴鍒嗗尮閰嶅?/p>
鍥犱負(fù) 6 - 2 絳変簬4錛屾墍浠ュ皢鎼滅儲(chǔ)璇嶅悜鍚庣Щ鍔?浣嶃?/p>
10.
鍥犱負(fù)絀烘牸涓庯跡涓嶅尮閰嶏紝鎼滅儲(chǔ)璇嶈繕瑕佺戶緇線鍚庣Щ銆傝繖鏃訛紝宸插尮閰嶇殑瀛楃鏁頒負(fù)2錛?AB"錛夛紝瀵瑰簲鐨?閮ㄥ垎鍖歸厤鍊?涓?銆傛墍浠ワ紝縐誨姩浣嶆暟 = 2 - 0錛岀粨鏋滀負(fù) 2錛屼簬鏄皢鎼滅儲(chǔ)璇嶅悜鍚庣Щ2浣嶃?/p>
11.
鍥犱負(fù)絀烘牸涓嶢涓嶅尮閰嶏紝緇х畫鍚庣Щ涓浣嶃?/p>
12.
閫愪綅姣旇緝錛岀洿鍒板彂鐜癈涓嶥涓嶅尮閰嶃備簬鏄紝縐誨姩浣嶆暟 = 6 - 2錛岀戶緇皢鎼滅儲(chǔ)璇嶅悜鍚庣Щ鍔?浣嶃?/p>
13.
閫愪綅姣旇緝錛岀洿鍒版悳绱㈣瘝鐨勬渶鍚庝竴浣嶏紝鍙戠幇瀹屽叏鍖歸厤錛屼簬鏄悳绱㈠畬鎴愩傚鏋滆繕瑕佺戶緇悳绱紙鍗蟲壘鍑哄叏閮ㄥ尮閰嶏級(jí)錛岀Щ鍔ㄤ綅鏁?= 7 - 0錛屽啀灝嗘悳绱㈣瘝鍚戝悗縐誨姩7浣嶏紝榪欓噷灝變笉鍐嶉噸澶嶄簡(jiǎn)銆?/p>
14.
涓嬮潰浠嬬粛銆婇儴鍒嗗尮閰嶈〃銆嬫槸濡備綍浜х敓鐨勩?/p>
棣栧厛錛岃浜?jiǎn)瑙ｄ袱涓蹇靛Q?鍓嶇紑"鍜?鍚庣紑"銆?"鍓嶇紑"鎸囬櫎浜?jiǎn)鏈鍚庝竴涓瓧絎︿互澶栵紝涓涓瓧絎︿覆鐨勫叏閮ㄥご閮ㄧ粍鍚堬紱"鍚庣紑"鎸囬櫎浜?jiǎn)绗竴涓瓧絎︿互澶栵紝涓涓瓧絎︿覆鐨勫叏閮ㄥ熬閮ㄧ粍鍚堛?/p>
15.
"閮ㄥ垎鍖歸厤鍊?灝辨槸"鍓嶇紑"鍜?鍚庣紑"鐨勬渶闀跨殑鍏辨湁鍏冪礌鐨勯暱搴︺備互"ABCDABD"涓轟緥錛?/p>
銆銆錛嶃"A"鐨勫墠緙鍜屽悗緙閮戒負(fù)絀洪泦錛屽叡鏈夊厓绱犵殑闀垮害涓?錛?/p>
銆銆錛嶃"AB"鐨勫墠緙涓篬A]錛屽悗緙涓篬B]錛屽叡鏈夊厓绱犵殑闀垮害涓?錛?/p>
銆銆錛嶃"ABC"鐨勫墠緙涓篬A, AB]錛屽悗緙涓篬BC, C]錛屽叡鏈夊厓绱犵殑闀垮害0錛?/p>
銆銆錛嶃"ABCD"鐨勫墠緙涓篬A, AB, ABC]錛屽悗緙涓篬BCD, CD, D]錛屽叡鏈夊厓绱犵殑闀垮害涓?錛?/p>
銆銆錛嶃"ABCDA"鐨勫墠緙涓篬A, AB, ABC, ABCD]錛屽悗緙涓篬BCDA, CDA, DA, A]錛屽叡鏈夊厓绱犱負(fù)"A"錛岄暱搴︿負(fù)1錛?/p>
銆銆錛嶃"ABCDAB"鐨勫墠緙涓篬A, AB, ABC, ABCD, ABCDA]錛屽悗緙涓篬BCDAB, CDAB, DAB, AB, B]錛屽叡鏈夊厓绱犱負(fù)"AB"錛岄暱搴︿負(fù)2錛?/p>
銆銆錛嶃"ABCDABD"鐨勫墠緙涓篬A, AB, ABC, ABCD, ABCDA, ABCDAB]錛屽悗緙涓篬BCDABD, CDABD, DABD, ABD, BD, D]錛屽叡鏈夊厓绱犵殑闀垮害涓?銆?/p>
16.
"閮ㄥ垎鍖歸厤"鐨勫疄璐ㄦ槸錛屾湁鏃跺欙紝瀛楃涓插ご閮ㄥ拰灝鵑儴浼?xì)鏈夐噸澶嶃傛瘮濡傦紝"ABCDAB"涔嬩腑鏈変袱涓?AB"錛岄偅涔堝畠鐨?閮ㄥ垎鍖歸厤鍊?灝辨槸2錛?AB"鐨勯暱搴︼級(jí)銆傛悳绱㈣瘝縐誨姩鐨勬椂鍊欙紝絎竴涓?AB"鍚戝悗縐誨姩4浣嶏紙瀛楃涓查暱搴?閮ㄥ垎鍖歸厤鍊鹼級(jí)錛屽氨鍙互鏉ュ埌絎簩涓?AB"鐨勪綅緗?/p>
涓銆侀鑹插垎甯冩硶
姣忓紶鍥劇墖閮藉彲浠ョ敓鎴?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">棰滆壊鍒嗗竷鐨勭洿鏂瑰浘錛坈olor histogram錛夈傚鏋滀袱寮犲浘鐗囩殑鐩存柟鍥懼緢鎺ヨ繎錛屽氨鍙互璁や負(fù)瀹冧滑寰堢浉浼箋?/p>
浠諱綍涓縐嶉鑹查兘鏄敱綰㈢豢钃濅笁鍘熻壊錛圧GB錛夋瀯鎴愮殑錛屾墍浠ヤ笂鍥懼叡鏈?寮犵洿鏂瑰浘錛堜笁鍘熻壊鐩存柟鍥?+ 鏈鍚庡悎鎴愮殑鐩存柟鍥撅級(jí)銆?/p>
濡傛灉姣忕鍘熻壊閮藉彲浠ュ彇256涓鹼紝閭ｄ箞鏁翠釜棰滆壊絀洪棿鍏辨湁1600涓囩棰滆壊錛?56鐨勪笁嬈℃柟錛夈傞拡瀵硅繖1600涓囩棰滆壊姣旇緝鐩存柟鍥撅紝璁＄畻閲忓疄鍦ㄥお澶т簡(jiǎn)錛屽洜姝ら渶瑕侀噰鐢ㄧ畝鍖栨柟娉曘傚彲浠ュ皢0锝?55鍒嗘垚鍥涗釜鍖猴細(xì)0锝?3涓虹0鍖猴紝64锝?27涓虹1鍖猴紝128锝?91涓虹2鍖猴紝192锝?55涓虹3鍖恒傝繖鎰忓懗鐫綰㈢豢钃濆垎鍒湁4涓尯錛屾誨叡鍙互鏋勬垚64縐嶇粍鍚堬紙4鐨?嬈℃柟錛夈?/p>
浠諱綍涓縐嶉鑹插繀鐒跺睘浜庤繖64縐嶇粍鍚堜腑鐨勪竴縐嶏紝榪欐牱灝卞彲浠ョ粺璁℃瘡涓縐嶇粍鍚堝寘鍚殑鍍忕礌鏁伴噺銆?/p>
涓婂浘鏄煇寮犲浘鐗囩殑棰滆壊鍒嗗竷琛紝灝嗚〃涓渶鍚庝竴鏍忔彁鍙栧嚭鏉ワ紝緇勬垚涓涓?4緇村悜閲?7414, 230, 0, 0, 8, ..., 109, 0, 0, 3415, 53929)銆傝繖涓悜閲忓氨鏄繖寮犲浘鐗囩殑鐗瑰緛鍊兼垨鑰呭彨"鎸囩汗"銆?/p>
浜庢槸錛屽鎵劇浉浼煎浘鐗囧氨鍙樻垚浜?jiǎn)鎵惧囖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;">浣欏雞鐩鎬技搴?/a>綆楀嚭銆?/p>
浜屻佸唴瀹圭壒寰佹硶
闄や簡(jiǎn)棰滆壊鏋勬垚錛岃繕鍙互浠庢瘮杈冨浘鐗囧唴瀹圭殑鐩鎬技鎬у叆鎵嬨?/p>
棣栧厛錛屽皢鍘熷浘杞垚涓寮犺緝?yōu)畯鐨勭伆搴﹀泟囧Q屽亣瀹氫負(fù)50x50鍍忕礌銆傜劧鍚庯紝紜畾涓涓槇鍊鹼紝灝嗙伆搴﹀浘鐗囪漿鎴愰粦鐧藉浘鐗囥?/p>
濡傛灉涓ゅ紶鍥劇墖寰堢浉浼鹼紝瀹冧滑鐨勯粦鐧借疆寤撳簲璇ユ槸鐩歌繎鐨勩備簬鏄紝闂灝卞彉鎴愪簡(jiǎn)錛岀涓姝ュ浣曠‘瀹氫竴涓悎鐞嗙殑闃堝鹼紝姝ｇ‘鍛堢幇鐓х墖涓殑杞粨錛?/p>
鏄劇劧錛屽墠鏅壊涓庤儗鏅壊鍙嶅樊瓚婂ぇ錛岃疆寤撳氨瓚婃槑鏄俱傝繖鎰忓懗鐫錛屽鏋滄垜浠壘鍒頒竴涓鹼紝鍙互浣垮緱鍓嶆櫙鑹插拰鑳屾櫙鑹插悇鑷殑"綾誨唴宸紓鏈灝?錛坢inimizing the intra-class variance錛夛紝鎴栬?綾婚棿宸紓鏈澶?錛坢aximizing the inter-class variance錛夛紝閭ｄ箞榪欎釜鍊煎氨鏄悊鎯崇殑闃堝箋?/p>
1979騫達(dá)紝鏃ユ湰瀛﹁呭ぇ媧ュ睍涔嬭瘉鏄庝簡(jiǎn)錛?綾誨唴宸紓鏈灝?涓?綾婚棿宸紓鏈澶?鏄悓涓浠朵簨錛屽嵆瀵瑰簲鍚屼竴涓槇鍊箋備粬鎻愬嚭涓縐嶇畝鍗曠殑綆楁硶錛屽彲浠ユ眰鍑?guó)櫩欎釜闃堝鹼紝榪欒縐頒負(fù)"澶ф觸娉?錛圤tsu's method錛夈備笅闈㈠氨鏄粬鐨勮綆楁柟娉曘?/p>
鍋囧畾涓寮犲浘鐗囧叡鏈塶涓儚绱狅紝鍏朵腑鐏板害鍊煎皬浜庨槇鍊肩殑鍍忕礌涓?n1 涓紝澶т簬絳変簬闃堝肩殑鍍忕礌涓?n2 涓紙 n1 + n2 = n 錛夈倃1 鍜?w2 琛ㄧず榪欎袱縐嶅儚绱犲悇鑷殑姣旈噸銆?/p>
銆銆w1 = n1 / n
銆銆w2 = n2 / n
鍐嶅亣瀹氾紝鎵鏈夌伆搴﹀煎皬浜庨槇鍊肩殑鍍忕礌鐨勫鉤鍧囧煎拰鏂瑰樊鍒嗗埆涓?μ1 鍜?σ1錛屾墍鏈夌伆搴﹀煎ぇ浜庣瓑浜庨槇鍊肩殑鍍忕礌鐨勫鉤鍧囧煎拰鏂瑰樊鍒嗗埆涓?μ2 鍜?σ2銆備簬鏄紝鍙互寰楀埌
銆銆綾誨唴宸紓 = w1(σ1鐨勫鉤鏂? + w2(σ2鐨勫鉤鏂?
銆銆綾婚棿宸紓 = w1w2(μ1-μ2)^2
鍙互璇佹槑錛岃繖涓や釜寮忓瓙鏄瓑浠風(fēng)殑錛氬緱鍒?綾誨唴宸紓"鐨勬渶灝忓鹼紝絳夊悓浜庡緱鍒?綾婚棿宸紓"鐨勬渶澶у箋備笉榪囷紝浠庤綆楅毦搴︾湅錛屽悗鑰呯殑璁＄畻瑕佸鏄撲竴浜涖?/p>
涓嬩竴姝ョ敤"絀蜂婦娉?錛屽皢闃堝間粠鐏板害鐨勬渶浣庡煎埌鏈楂樺鹼紝渚濇鍙栦竴閬嶏紝鍒嗗埆浠ｅ叆涓婇潰鐨勭畻寮忋備嬌寰?綾誨唴宸紓鏈灝?鎴?綾婚棿宸紓鏈澶?鐨勯偅涓鹼紝灝辨槸鏈緇堢殑闃堝箋傚叿浣撶殑瀹炰緥鍜孞ava綆楁硶錛岃鐪?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">榪欓噷銆?/p>
鏈変簡(jiǎn)50x50鍍忕礌鐨勯粦鐧界緝鐣ュ浘錛屽氨絳変簬鏈変簡(jiǎn)涓涓?0x50鐨?-1鐭╅樀銆傜煩闃電殑姣忎釜鍊煎搴斿師鍥劇殑涓涓儚绱狅紝0琛ㄧず榛戣壊錛?琛ㄧず鐧借壊銆傝繖涓煩闃靛氨鏄竴寮犲浘鐗囩殑鐗瑰緛鐭╅樀銆?/p>
涓や釜鐗瑰緛鐭╅樀鐨勪笉鍚屼箣澶勮秺灝戯紝灝變唬琛ㄤ袱寮犲浘鐗囪秺鐩鎬技銆傝繖鍙互鐢?寮傛垨榪愮畻"瀹炵幇錛堝嵆涓や釜鍊間箣涓彧鏈変竴涓負(fù)1錛屽垯榪愮畻緇撴灉涓?錛屽惁鍒欒繍綆楃粨鏋滀負(fù)0錛夈傚涓嶅悓鍥劇墖鐨勭壒寰佺煩闃佃繘琛?寮傛垨榪愮畻"錛岀粨鏋滀腑鐨?瓚婂皯錛屽氨鏄秺鐩鎬技鐨勫浘鐗囥?/p>
榪欎釜緋誨垪鐨勫墠涓ら儴鍒嗗氨鏄緢濂界殑渚嬪瓙銆備粎浠呬緷闈犵粺璁¤瘝棰戯紝灝辮兘鎵懼嚭鍏抽敭璇?/a>鍜?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">鐩鎬技鏂囩珷銆傝櫧鐒跺畠浠畻涓嶄笂鏁堟灉鏈濂界殑鏂規(guī)硶錛屼絾鑲畾鏄渶綆渚挎槗琛岀殑鏂規(guī)硶銆?/p>
浠婂ぉ錛屼緷鐒剁戶緇繖涓富棰樸傝璁哄浣曢氳繃璇嶉錛屽鏂囩珷榪涜鑷姩鎽樿錛圓utomatic summarization錛夈?/p>
濡傛灉鑳戒粠3000瀛楃殑鏂囩珷錛屾彁鐐煎嚭150瀛楃殑鎽樿錛屽氨鍙互涓鴻鑰呰妭鐪佸ぇ閲忛槄璇繪椂闂淬傜敱浜哄畬鎴愮殑鎽樿鍙?浜哄伐鎽樿"錛岀敱鏈哄櫒瀹屾垚鐨勫氨鍙?鑷姩鎽樿"銆傝澶氱綉绔欓兘闇瑕佸畠錛屾瘮濡傝鏂囩綉绔欍佹柊闂葷綉绔欍佹悳绱㈠紩鎿庣瓑絳夈?007騫達(dá)紝緹庡浗瀛﹁呯殑璁烘枃銆夾 Survey on Automatic Text Summarization銆?/a>錛圖ipanjan Das, Andre F.T. Martins, 2007錛夋葷粨浜?jiǎn)鐩墠鐨勮嚜鍔ㄦ憳瑕伣帡娉曘傚叾涓紝寰堥噸瑕佺殑涓縐嶅氨鏄瘝棰戠粺璁°?/p> 榪欑鏂規(guī)硶鏈鏃╁嚭鑷?958騫寸殑IBM鍏徃縐戝瀹?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">H.P. Luhn
Luhn鍗氬＋璁や負(fù)錛屾枃绔犵殑淇℃伅閮藉寘鍚湪鍙ュ瓙涓紝鏈変簺鍙ュ瓙鍖呭惈鐨勪俊鎭錛屾湁浜涘彞瀛愬寘鍚殑淇℃伅灝戙?鑷姩鎽樿"灝辨槸瑕佹壘鍑洪偅浜涘寘鍚俊鎭渶澶氱殑鍙ュ瓙銆?/p>
鍙ュ瓙鐨勪俊鎭噺鐢?鍏抽敭璇?鏉ヨ 閲忋傚鏋滃寘鍚殑鍏抽敭璇嶈秺澶氾紝灝辮鏄庤繖涓彞瀛愯秺閲嶈銆侺uhn鎻愬嚭鐢?綈?錛坈luster錛夎〃紺哄叧閿瘝鐨勮仛闆嗐傛墍璋?綈?灝辨槸鍖呭惈澶氫釜鍏抽敭璇嶇殑鍙ュ瓙鐗囨銆?/p>
涓婂浘灝辨槸Luhn鍘熷璁烘枃鐨勬彃鍥撅紝琚璧鋒潵鐨勯儴鍒嗗氨鏄竴涓?綈?銆傚彧瑕佸叧閿瘝涔嬮棿鐨勮窛紱誨皬浜?闂ㄦ鍊?錛屽畠浠氨琚涓哄浜庡悓涓涓皣涔嬩腑銆侺uhn寤鴻鐨勯棬妲涘兼槸4鎴?銆備篃灝辨槸璇達(dá)紝濡傛灉涓や釜鍏抽敭璇嶄箣闂存湁5涓互涓婄殑鍏朵粬璇嶏紝灝卞彲浠ユ妸榪欎袱涓叧閿瘝鍒嗗湪涓や釜綈囥?/p>
涓嬩竴姝ワ紝瀵逛簬姣忎釜綈囷紝閮借綆楀畠鐨勯噸瑕佹у垎鍊箋?/p>
浠ュ墠鍥句負(fù)渚嬶紝鍏朵腑鐨勭皣涓鍏辨湁7涓瘝錛屽叾涓?涓槸鍏抽敭璇嶃傚洜姝わ紝瀹冪殑閲嶈鎬у垎鍊肩瓑浜?( 4 x 4 ) / 7 = 2.3銆?/p>
鐒跺悗錛屾壘鍑哄寘鍚垎鍊兼渶楂樼殑綈囩殑鍙ュ瓙錛堟瘮濡?鍙ワ級(jí)錛屾妸瀹冧滑鍚堝湪涓璧鳳紝灝辨瀯鎴愪簡(jiǎn)榪欑瘒鏂囩珷鐨勮嚜鍔ㄦ憳瑕併傚叿浣撳疄鐜板彲浠ュ弬瑙?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">銆奙ining the Social Web: Analyzing Data from Facebook, Twitter, LinkedIn, and Other Social Media Sites銆?/a>錛圤'Reilly, 2011錛変竴涔︾殑絎?绔狅紝python浠ｇ爜瑙?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">github銆?/p>
Luhn鐨勮繖縐嶇畻娉曞悗鏉ヨ綆鍖栵紝涓嶅啀鍖哄垎"綈?錛屽彧鑰冭檻鍙ュ瓙鍖呭惈鐨勫叧閿瘝銆備笅闈㈠氨鏄竴涓緥瀛愶紙閲囩敤浼爜琛ㄧず錛夛紝鍙冭檻鍏抽敭璇嶉鍏堝嚭鐜扮殑鍙ュ瓙銆?/p>
銆銆Summarizer(originalText, maxSummarySize):
銆銆銆銆// 璁＄畻鍘熷鏂囨湰鐨勮瘝棰戯紝鐢熸垚涓涓暟緇勶紝姣斿[(10,'the'), (3,'language'), (8,'code')...]
銆銆銆銆wordFrequences = getWordCounts(originalText)銆銆銆銆// 榪囨護(hù)鎺夊仠鐢ㄨ瘝錛屾暟緇勫彉鎴怺(3, 'language'), (8, 'code')...]
銆銆銆銆contentWordFrequences = filtStopWords(wordFrequences)銆銆銆銆// 鎸夌収璇嶉榪涜鎺掑簭錛屾暟緇勫彉鎴怺'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銆銆銆銆// 灝嗛変腑鐨勫彞瀛愭寜鐓у嚭鐜伴『搴忥紝緇勬垚鎽樿
銆銆銆銆summary = ""
銆銆銆銆foreach sentence in sentences:
銆銆銆銆銆銆if sentence in setSummarySentences:
銆銆銆銆銆銆銆銆summary = summary + " " + sentence銆銆銆銆return summary
綾諱技鐨勭畻娉曞凡緇忚鍐欐垚浜?jiǎn)宸ュ咗P紝姣斿鍩轟簬Java鐨?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">Classifier4J搴撶殑SimpleSummariser妯″潡銆佸熀浜嶤璇█鐨?a target="_blank" style="margin: 0px; padding: 0px; list-style-type: none; border: none; color: #112233;">OTS搴撱佷互鍙?qiáng)鍩轰簬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>