|
|
2017/7/23 下午 08:24:17
/*------------------------------------------------------------------------
BM_SEARCH.HPP v1.1.2
Copyright 楊志賢 CxxlMan, 2017
All Rights Reserved
採用 Boyer-Moore algorithm 的快速字串搜尋
BM_Search = 搜尋的字串編碼為 ANSI 或 UTF-8
BM_WSearch = 搜尋 wchar_t 形別的字串，以 Windows 作業系統作為優化的依據
可取出 Boyer-Moore 移位表加以保存，可用保存的移位表直接建構出
BM_Search 或 BM_WSearch 省去了建表的時間
------------------------------------------------------------------------*/
#if !defined(__BM_SEARCH_HPP_CxxlMan)
#define __BM_SEARCH_HPP_CxxlMan
#include <string>
#include <vector>
namespace CxxlMan2
{
// ANSI 或 UTF-8
class BM_Search
{
std::vector<size_t> BM_Table; // Boyer-Moore 移位表
std::string m_Pattern;
size_t m_PatternEndLen; // Pattern Length - 1
void SetPattern(const std::string &Pattern)
{
m_Pattern = Pattern;
}
void SetPattern(const std::string &&Pattern)
{
m_Pattern = std::move(Pattern);
}
void SetTable(const std::vector<size_t> &Table)
{
BM_Table = Table;
}
void SetTable(const std::vector<size_t> &&Table)
{
BM_Table = std::move(Table);
}
public:
// Constructor
// Pattern = 不可為 nullptr 也不能為空字串
BM_Search(const std::string &&Pattern)
:BM_Table(256, Pattern.size())
{
SetPattern(std::forward<decltype(Pattern)>(Pattern));
m_PatternEndLen = m_Pattern.size() - 1;
const unsigned char *p = (const unsigned char *)m_Pattern.c_str();
for (size_t i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
BM_Table[p[i]] = k;
}
// Constructor
// Pattern = 不可為 nullptr 也不能為空字串
// Table = 來自 GetTable()，且須和 Pattern 同一個來源
template <typename P, typename T>
BM_Search(P&& Pattern, T&& Table)
{
SetTable(std::forward<T>(Table));
SetPattern(std::forward<P>(Pattern));
m_PatternEndLen = m_Pattern.size() - 1;
}
|
|
|
|
2017/7/23 下午 08:24:49
// StrStart = 指向被搜尋字串開始位置，不可為 nullptr 也不能為空字串
// StrEnd = 指向被搜尋字串最後位置，須大於或等於 StrStart
// 回傳值為指向第一個符合搜尋字串的位置，若沒找到回覆 nullptr
const char* Serach(const char *StrStart, const char *StrEnd) const
{
auto BM_Table_Array = BM_Table.data();
for (const char *StrPatternEnd = StrStart + m_PatternEndLen;
StrPatternEnd <= StrEnd; StrPatternEnd = StrStart + m_PatternEndLen)
{
bool bfound = true;
for (const char *Start = StrStart, *Pattern = m_Pattern.c_str();
Start <= StrPatternEnd; ++Start, ++Pattern)
{
if (*Start != *Pattern)
{
const unsigned char Key = *(const char *)StrPatternEnd;
StrStart += BM_Table_Array[Key];
bfound = false;
break;
}
}
if(bfound)
return StrStart;
}
return nullptr;
}
// 取得搜尋字串
std::string GetPattern() const
{
return m_Pattern;
}
// 取得搜尋字串的長度
size_t GetPatternLength() const
{
return m_Pattern.size();
}
// 取得 Boyer-Moore 移位表
std::vector<size_t> GetTable() const
{
return BM_Table;
}
};
|
|
|
|
2017/7/23 下午 08:25:49
// wchar_t 形別的版本
class BM_WSearch
{
std::vector<size_t> BM_Table; // Boyer-Moore 移位表
std::wstring m_Pattern;
size_t m_PatternEndLen; // Pattern Length - 1
void SetPattern(const std::wstring &Pattern)
{
m_Pattern = Pattern;
}
void SetPattern(const std::wstring &&Pattern)
{
m_Pattern = std::move(Pattern);
}
void SetTable(const std::vector<size_t> &Table)
{
BM_Table = Table;
}
void SetTable(const std::vector<size_t> &&Table)
{
BM_Table = std::move(Table);
}
public:
// Constructor
// Pattern = 不可為 nullptr 也不能為空字串
BM_WSearch(const std::wstring &&Pattern)
:BM_Table(256, Pattern.size())
{
SetPattern(std::forward<decltype(Pattern)>(Pattern));
m_PatternEndLen = m_Pattern.size() - 1;
const wchar_t *p = (const wchar_t *)m_Pattern.c_str();
for (size_t i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
BM_Table[(const unsigned char)p[i]] = k;
}
// Constructor
// Pattern = 不可為 nullptr 也不能為空字串
// Table = 來自 GetTable()，且須和 Pattern 同一個來源
template <typename P, typename T>
BM_WSearch(P&& Pattern, T&& Table)
{
SetTable(std::forward<T>(Table));
SetPattern(std::forward<P>(Pattern));
m_PatternEndLen = m_Pattern.size() - 1;
}
|
|
|
|
2017/7/23 下午 08:26:16
// StrStart = 指向被搜尋字串開始位置，不可為 nullptr 也不能為空字串
// StrEnd = 指向被搜尋字串最後位置，須大於或等於 StrStart
// 回傳值為指向第一個符合搜尋字串的位置，若沒找到回覆 nullptr
const wchar_t* Serach(const wchar_t *StrStart, const wchar_t *StrEnd) const
{
auto BM_Table_Array = BM_Table.data();
for (const wchar_t *StrPatternEnd = StrStart + m_PatternEndLen;
StrPatternEnd <= StrEnd; StrPatternEnd = StrStart + m_PatternEndLen)
{
bool bfound = true;
for (const wchar_t *Start = StrStart, *Pattern = m_Pattern.c_str();
Start <= StrPatternEnd; ++Start, ++Pattern)
{
if (*Start != *Pattern)
{
const unsigned char Key = *(const unsigned char *)StrPatternEnd;
StrStart += BM_Table_Array[Key];
bfound = false;
break;
}
}
if (bfound)
return StrStart;
}
return nullptr;
}
// 取得搜尋字串
std::wstring GetPattern() const
{
return m_Pattern;
}
// 取得搜尋字串的長度
size_t GetPatternLength() const
{
return m_Pattern.size();
}
// 取得 Boyer-Moore 移位表
std::vector<size_t> GetTable() const
{
return BM_Table;
}
};
} /* namespace CxxlMan2 */
#endif
|
|
|
|
2017/7/23 下午 08:29:38
/*
** 測試碼
*/
#include <iostream>
#include "BM_SEARCH.HPP"
using namespace std;
using namespace CxxlMan2;
int main()
{
// 被搜尋的字串不可為 nullptr 也不能為空字串
char *Txt = u8"123456abc7894abc56kkj";
// 搜尋的字串不可為 nullptr 也不能為空字串
char *Pattern = u8"abc";
// 純粹只為建立 Boyer-Moore 移位表
BM_Search TxtCreateTable(Pattern);
auto Table = TxtCreateTable.GetTable(); // 保存 Boyer - Moore 移位表
// 用保存的 Boyer-Moore 移位表建立搜尋物件
BM_Search TxtFind(Pattern, std::move(Table));
const char *S = Txt;
// 被搜尋字串最後位置，須大於或等於開始的位置
const char *E = Txt + strlen(Txt) - 1;
cout << "在 \"" << Txt << "\" 字串裡" << endl
<< "搜尋 \"" << Pattern << "\" 結果如下：" << endl << endl;
// 循環搜尋整個字串
while ((S = TxtFind.Serach(S, E)) != nullptr)
{
cout << S << endl;
// 至少要移一個位址，這裡是跳過已找到的那一部份的意思
S += TxtFind.GetPatternLength();
}
return 0;
}
|
|
|
|
2017/7/23 下午 08:31:35
執行結果
在 "123456abc7894abc56kkj" 字串裡
搜尋 "abc" 結果如下：
abc7894abc56kkj
abc56kkj
請按任意鍵繼續 . . .
|
|
|
|
2017/7/26 下午 07:03:04
/*------------------------------------------------------------------------
BM_SEARCH.HPP v1.2.3
Copyright 楊志賢 CxxlMan, 2017
All Rights Reserved
採用 Boyer-Moore algorithm 的快速字串搜尋
BM_Search = 搜尋的字串編碼為 ANSI 或 UTF-8
BM_WSearch = 搜尋 wchar_t 形別的字串，以 Windows 作業系統作為優化的依據
可取出 Boyer-Moore 移位表加以保存，可用保存的移位表直接建構出
BM_Search 或 BM_WSearch 省去了建表的時間
------------------------------------------------------------------------*/
#if !defined(__BM_SEARCH_HPP_CxxlMan)
#define __BM_SEARCH_HPP_CxxlMan
#include <string>
#include <array>
namespace CxxlMan2
{
// ANSI 或 UTF-8
class BM_Search
{
std::array<size_t,256> BM_Table; // Boyer-Moore 移位表
std::string m_Pattern;
size_t m_PatternEndLen; // Pattern Length - 1
void SetPattern(const std::string &Pattern)
{
m_Pattern = Pattern;
}
void SetPattern(const std::string &&Pattern)
{
m_Pattern = std::move(Pattern);
}
void SetTable(const std::array<size_t,256> &Table)
{
BM_Table = Table;
}
void SetTable(const std::array<size_t, 256> &&Table)
{
BM_Table = std::move(Table);
}
public:
// Constructor
// Pattern = 不可為 nullptr 也不能為空字串
BM_Search(const std::string &&Pattern)
{
auto Len = Pattern.size();
BM_Table.fill(Len);
SetPattern(std::forward<decltype(Pattern)>(Pattern));
m_PatternEndLen = Len - 1;
const unsigned char *p = (const unsigned char *)m_Pattern.c_str();
for (size_t i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
BM_Table[p[i]] = k;
}
|
|
|
|
2017/7/26 下午 07:04:01
// Constructor
// Pattern = 不可為 nullptr 也不能為空字串
// Table = 來自 GetTable()，且須和 Pattern 同一個來源
template <typename P, typename T>
BM_Search(P&& Pattern, T&& Table)
{
SetTable(std::forward<T>(Table));
SetPattern(std::forward<P>(Pattern));
m_PatternEndLen = m_Pattern.size() - 1;
}
// Copy Constructor
BM_Search(const BM_Search &Src)
{
BM_Table = Src.BM_Table;
m_Pattern = Src.m_Pattern;
m_PatternEndLen = Src.m_PatternEndLen;
}
// 右值 Copy Constructor
BM_Search(const BM_Search &&Src)
{
BM_Table = std::move(Src.BM_Table);
m_Pattern = std::move(Src.m_Pattern);
m_PatternEndLen = Src.m_PatternEndLen;
}
// StrStart = 指向被搜尋字串開始位置，不可為 nullptr 也不能為空字串
// StrEnd = 指向被搜尋字串最後位置，須大於或等於 StrStart
// 回傳值為指向第一個符合搜尋字串的位置，若沒找到回覆 nullptr
const char* Serach(const char *StrStart, const char *StrEnd) const
{
auto BM_Table_Array = BM_Table.data();
for (const char *StrPatternEnd = StrStart + m_PatternEndLen;
StrPatternEnd <= StrEnd; StrPatternEnd = StrStart + m_PatternEndLen)
{
bool bfound = true;
for (const char *Start = StrStart, *Pattern = m_Pattern.c_str();
Start <= StrPatternEnd; ++Start, ++Pattern)
{
if (*Start != *Pattern)
{
const unsigned char Key = *(const char *)StrPatternEnd;
StrStart += BM_Table_Array[Key];
bfound = false;
break;
}
}
if(bfound)
return StrStart;
}
return nullptr;
}
// 取得搜尋字串
std::string GetPattern() const
{
return m_Pattern;
}
// 取得搜尋字串的長度
size_t GetPatternLength() const
{
return m_Pattern.size();
}
// 取得 Boyer-Moore 移位表
std::array<size_t,256> GetTable() const
{
return BM_Table;
}
};
|
|
|
|
2017/7/26 下午 07:05:02
// wchar_t 形別的版本
class BM_WSearch
{
std::array<size_t, 256> BM_Table; // Boyer-Moore 移位表
std::wstring m_Pattern;
size_t m_PatternEndLen; // Pattern Length - 1
void SetPattern(const std::wstring &Pattern)
{
m_Pattern = Pattern;
}
void SetPattern(const std::wstring &&Pattern)
{
m_Pattern = std::move(Pattern);
}
void SetTable(const std::array<size_t, 256> &Table)
{
BM_Table = Table;
}
void SetTable(const std::array<size_t, 256> &&Table)
{
BM_Table = std::move(Table);
}
public:
// Constructor
// Pattern = 不可為 nullptr 也不能為空字串
BM_WSearch(const std::wstring &&Pattern)
{
auto Len = Pattern.size();
BM_Table.fill(Len);
SetPattern(std::forward<decltype(Pattern)>(Pattern));
m_PatternEndLen = Len - 1;
const wchar_t *p = (const wchar_t *)m_Pattern.c_str();
for (size_t i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
BM_Table[(const unsigned char)p[i]] = k;
}
// Constructor
// Pattern = 不可為 nullptr 也不能為空字串
// Table = 來自 GetTable()，且須和 Pattern 同一個來源
template <typename P, typename T>
BM_WSearch(P&& Pattern, T&& Table)
{
SetTable(std::forward<T>(Table));
SetPattern(std::forward<P>(Pattern));
m_PatternEndLen = m_Pattern.size() - 1;
}
// Copy Constructor
BM_WSearch(const BM_WSearch &Src)
{
BM_Table = Src.BM_Table;
m_Pattern = Src.m_Pattern;
m_PatternEndLen = Src.m_PatternEndLen;
}
// 右值 Copy Constructor
BM_WSearch(const BM_WSearch &&Src)
{
BM_Table = std::move(Src.BM_Table);
m_Pattern = std::move(Src.m_Pattern);
m_PatternEndLen = Src.m_PatternEndLen;
}
|
|
|
|
2017/7/26 下午 07:05:36
// StrStart = 指向被搜尋字串開始位置，不可為 nullptr 也不能為空字串
// StrEnd = 指向被搜尋字串最後位置，須大於或等於 StrStart
// 回傳值為指向第一個符合搜尋字串的位置，若沒找到回覆 nullptr
const wchar_t* Serach(const wchar_t *StrStart, const wchar_t *StrEnd) const
{
auto BM_Table_Array = BM_Table.data();
for (const wchar_t *StrPatternEnd = StrStart + m_PatternEndLen;
StrPatternEnd <= StrEnd; StrPatternEnd = StrStart + m_PatternEndLen)
{
bool bfound = true;
for (const wchar_t *Start = StrStart, *Pattern = m_Pattern.c_str();
Start <= StrPatternEnd; ++Start, ++Pattern)
{
if (*Start != *Pattern)
{
const unsigned char Key = *(const unsigned char *)StrPatternEnd;
StrStart += BM_Table_Array[Key];
bfound = false;
break;
}
}
if (bfound)
return StrStart;
}
return nullptr;
}
// 取得搜尋字串
std::wstring GetPattern() const
{
return m_Pattern;
}
// 取得搜尋字串的長度
size_t GetPatternLength() const
{
return m_Pattern.size();
}
// 取得 Boyer-Moore 移位表
std::array<size_t, 256> GetTable() const
{
return BM_Table;
}
};
} /* namespace CxxlMan2 */
#endif
|
|
|
|
2017/7/26 下午 07:06:43
Boyer-Moore 移位表 BM_Table 在 1.1 版採用 std::vector，會用到 heap 比較花時間，所以 1.2 版改用 std::array，如此用保存的移位表建構只能整個陣列硬拷，不過仍保留右值參照的複製方式，因不確定所有編譯器實作方法。BM_Table 只有 256 bytes，硬拷應不會比 heap 花的時間多。
用保存的移位表建構的必要性取決於 Pattern 是不是大於 256 bytes，否則用 Pattern 建構就可以了。
1.2 版應是最後確定版，有什麼問題或意見請留言，謝謝
Boyer-Moore 是我所知最快的字串搜尋法，還有更快的嗎
|
|
|
|
|
|
|
|
| C++ |
 |
|
| |
專家等級 |
評價 |
|
| |
一代宗師 |
10000 |
|
| |
曠世奇才 |
5000 |
|
| |
頂尖高手 |
3000 |
|
| |
卓越專家 |
1500 |
|
| |
優秀好手 |
750 |
|
|
|
|
|
|
|
|
|
|
|
|
Microsoft Internet Explorer
6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2018 程式設計俱樂部 http://www.programmer-club.com.tw/ |
|
|
