討論區快速選單
知識庫快速選單
最紅的App開發語言:Kotlin 討論區最近新進100則主題 政府補助!學嵌入式+物聯網
[ 回上頁 ] [ 討論區發言規則 ]
[分享] Boyer-Moore 快速字串搜尋 
更改我的閱讀文章字型大小
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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;
 }


作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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;
 }
};
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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;
 }


作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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;
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/7/23 下午 08:31:35
執行結果

在 "123456abc7894abc56kkj" 字串裡
搜尋 "abc" 結果如下:

abc7894abc56kkj
abc56kkj
請按任意鍵繼續 . . .
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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;
  }


作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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;
  }
};
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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;
  }

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
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 是我所知最快的字串搜尋法,還有更快的嗎
 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 13050 
2 青衫 4760 
3 simula 4690 
4 coco 4030 
5 白老鼠(Gary) 3670 
6 ozzy 2540 
7 Ben 2250 
8 Anderson 1960 
9 windblown 1650 
10 Kenny 1560 
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/
0.1875