|
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-2019 程式設計俱樂部 http://www.programmer-club.com.tw/ |
|
|