HorspoolアルゴリズムC++11実装(中国語と英語の混合検索をサポート)

要約:
本論文ではhorspoolアルゴリズムの実装を示し,使用例を示し,非常に使いやすいUTF 8文字トランスコードプロジェクトを紹介し,簡単なテストレポートなどを与えた.
アルゴリズムの実装:

#include <iostream>
#include <unordered_map>
//#include <codecvt>
#include <fstream>
#include <iterator>
#include <sstream>
#include <bitset>
#include "utf8.h"
using namespace std;

template <typename Key,typename Value>
class ShiftTable{

  public:
        ShiftTable(const std::u32string& pattern){
            index_=pattern.size();
            auto end=pattern.rbegin();
            auto head=pattern.rend();
            auto cur=end+1;
            while(cur!=head){
              shiftTable_.emplace(make_pair(*cur,cur-end));
              ++cur;
            }
        }
        Value operator [](const Key& key){
            auto cur=shiftTable_.find(key);
            if(cur!=shiftTable_.end())
              return cur->second;
             else
              return index_;
        }
    private:
        unordered_map<Key,Value> shiftTable_;
        size_t index_;
};


int HorspoolMatching(const std::u32string & pattern,const std::u32string & text){
    if(pattern.empty()||text.empty())return -1;
    ShiftTable<char32_t,size_t> table(pattern);
    auto m=pattern.size();
    auto n=text.size();
    auto i=m-1;
    while(i<=n-1){
        int k=0;
        while(k<=m-1&&pattern[m-1-k]==text[i-k]) k++;
        if(k==m)
            return i-m+1;
        else
            i+=table[text[i]];
    }
    return -1;
}

ここではhorspoolアルゴリズムについては述べず,1つの実装のみを共有する.
実装ではstd::u 32 stringを使用し、任意の国建文字の検索をサポートするためにunicode 32を使用する必要があります.
ここでは、軽量オープンソースのutf 8トランスコード実装に注目することを強くお勧めします.これはプロジェクトのホームページutf 8です.
使用例:

int main()
{

    //      ， C++          
    ifstream filestream("/home/ron/input.in");//      utf8    （       ）
    stringstream ss;
    ss<<filestream.rdbuf();
    
    string text(ss.str());
    string pattern="  ";//  "  " utf8   ，     ubuntu  utf8  

    std::u32string  text32;
    std::u32string  pattern32;
    utf8::utf8to32(text.begin(), text.end() , back_inserter(text32));
    utf8::utf8to32(pattern.begin(), pattern.end() , back_inserter(pattern32));
    
    string repWord=" ";//  " " utf8   ，     ubuntu  utf8  
    std::u32string repWord32;
    utf8::utf8to32(repWord.begin(), repWord.end() , back_inserter(repWord32));

    //      "  "
    auto index=HorspoolMatching(pattern32,text32);
    if( index!=-1 )
    {
        cout<<"found it,at index "<<index<<endl;
        text32.replace(index,1,repWord32);
         //     ，  "  " "  "
        ofstream ofilestream("/home/ron/input.in");
        ostream_iterator<char> out(ofilestream);
        utf8::utf32to8(text32.begin(),text32.end(),out);
    }
    else
    {
        cout<<"not found"<<endl;
    }


    return 0;
}

 
 上述代码，是一个使用示例，它可以跨平台（操作系统支不支持utf8无所谓，我们程序支持utf8/16/32 任意转码），所以只要求输入文件和模式字符串是采用utf8编码即可。我们知道utf8是网络传输采用的标准，并且大多数系统均支持utf8。 
  
 
我们可以做支持任何编码的查找，那样问题就复杂化了，谁愿意无穷尽的陷入到字符编码中，相信只有这个领域的专家吧。
 
 
 
 
codecvt：
 
  
 
#include <codecvt>
  
このヘッダーファイルは何ですか.C++11が導入した文字トランスコードの実現について、残念ながらgccはまだ実現していません.vc 2010以降のバージョンはサポートされるはずです.興味のある学生は自分で理解することができます.私のコンパイル環境はubuntu gccなのでcodecvtは使えません.他にもICUなどの文字コードライブラリがありますが、彼らは大きすぎて、使うのも面倒です.やっとutf 8軽量級プロジェクトが見つかり、copyソースコードがすぐに使用され、ubuntuの下で非常によく表現されています.もちろんwindowの下でも同じです.欠点はutfのみをサポートすることにほかならない.
テスト:
このインプリメンテーションと標準ライブラリのインプリメンテーションをいくつかのテキストで比較したところ、時間パフォーマンスの効率はほぼ同じです(標準ライブラリは少し良いです).Boyer−Mooreアルゴリズムを用いてfindを実現することを望むgcc issueがある.だから私はgccがfindの実現に対してhorspoolアルゴリズムを採用する可能性が高いと推測して、速くて簡単で、ただ最悪の複雑さは保証できません.
KMP:  
どうしてKMPが見えないのか、KMPは複雑すぎる.アルゴリズムに夢中になっていない限り、同じ効率を選択するプログラマーはいませんが、より複雑なアルゴリズムを実現します.しかし、KMPアルゴリズムの考え方は確かに後続の他のアルゴリズムに影響を及ぼした.
本人のレベルに限って、皆さんの批判と指摘を歓迎します.転載は出典を表明してください.ありがとうございます.