编程与调试 C++ -- 字符串快速检索

// 用正则进行二进制匹配
std::regex* reg = new std::regex(regex);
std::string tempstr(str, datasize);
# match_any 若多于一个匹配可行，则任何匹配都是可接受的结果。
bool result = std::regex_search(tempstr, *reg, std::regex_constants::match_any);

typedef unsigned char BYTE;
typedef unsigned int UINT32;

typedef std::map<BYTE, struct Node*> CHILDREN;
typedef std::vector<int> WORDS;
typedef std::queue<Node*> NODEQUEUE;

#define CONTAINS(children, value) (children.find(value) != children.end())

struct Node {
    Node* fail;
    CHILDREN children;
    int count; // 是否为该单词的最后一个节点
    WORDS wordsizes; // 每个单词的长度
    WORDS wordids; // 每个单词的 ID

    Node() {
        fail = NULL;
        count = 0;
    }
};

class Automaton {
public:
    Automaton() {
        m_root = new Node();
        m_bPrintId = false;
        m_nMaxWordSize = 0;
        m_bDebug = false;
        m_bIgnoreCase = false;
    }
    ~Automaton() {
        release(m_root);
    }

public:
    void insert(BYTE* data, int size, int id);
    void build();
    int query(BYTE* data, int size);
    int query(BYTE* data, int offset, int size);
    void output(BYTE* data, int offset, const WORDS& wordsizes, const WORDS& wordids);
    void insert(const char* data, int id);
    BOOL buildfromfile(const wchar_t* fpath);

    void setPrintId(BOOL flag) {
        m_bPrintId = flag;
    }
    void setIgnoreCase(BOOL ignore) {
        m_bIgnoreCase = ignore;
    }
    void setDebug(BOOL flag) {
        m_bDebug = flag;
    }
    int getMaxWordSize() {
        return m_nMaxWordSize;
    }

private:
    void release(Node* node);

private:
    Node* m_root;
    BOOL m_bPrintId;
    BOOL m_bIgnoreCase; // 对于二进制检索，可能不准确，因为各种编码的原因。
    BOOL m_bDebug;
    int m_nMaxWordSize;
    Locker m_locker;
    std::set<__int64> m_resultset;
};

void Automaton::insert(BYTE* data, int size, int id) {
    Node* p = m_root;
    for (int i = 0; i < size; i++) {
        BYTE key = data[i];
        if (m_bIgnoreCase) {
            if (key >= 'A' && key <= 'Z') {
                key = key - 'A' + 'a';
            }
        }
        if (!CONTAINS(p->children, key)) {
            Node* temp = new Node();
            p->children[key] = temp;
            p = temp;
        } else {
            p = p->children[key];
        }
    }
    p->count++;
    p->wordsizes.push_back(size);
    p->wordids.push_back(id);
    m_nMaxWordSize = max(m_nMaxWordSize, size);
}

void Automaton::build() {
    m_root->fail = NULL;
    NODEQUEUE queue;
    queue.push(m_root);

    while (!queue.empty()) {
        Node* temp = queue.front();
        queue.pop();

        CHILDREN::iterator iter = temp->children.begin();

        for (; iter != temp->children.end(); iter++) {
            BYTE key = iter->first;
            Node* subnode = iter->second;

            if (temp == m_root) {
                subnode->fail = m_root;
            } else {
                Node* p = temp->fail;
                while (p != NULL) {
                    if (CONTAINS(p->children, key)) {
                        subnode->fail = p->children[key];
                        break;
                    }
                    p = p->fail;
                }
                if (p == NULL) {
                    subnode->fail = m_root;
                }
            }
            queue.push(subnode);
        }
    }
}

int Automaton::query(BYTE* data, int offset, int size) {
    Node* p = m_root;
    int cnt = 0;
    for (int i = offset; i < offset+size; i++) {
        BYTE key = data[i];
        if (m_bIgnoreCase) {
            if (key >= 'A' && key <= 'Z') {
                key = key - 'A' + 'a';
            }
        }

        while (!CONTAINS(p->children, key) && p != m_root) {
            p = p->fail;
        }

        if (CONTAINS(p->children, key)) {
            p = p->children[key];
        } else {
            p = m_root;
        }

        Node* temp = p;
        while (temp != m_root && temp->count != -1) {
            cnt += temp->count;
#ifndef TOY_VERSION
            temp->count = -1; // 如果已经统计进去了。
#else
            if (temp->count) {
                output(data, i, temp->wordsizes, temp->wordids);
            }
#endif
            temp = temp->fail;
        }
    }
    return cnt;
}

void Automaton::output(BYTE* data, int offset, //
                       const WORDS& wordsizes, const WORDS& wordids) //
{
    AutoLocker temp(m_locker);

    int size = wordsizes.size();
    for (int i = 0; i < size; i++) {
        int wordsizesize = wordsizes[i];
        int start = offset - wordsizesize + 1;

        __int64 hash = start;
        hash = (hash << 32) + wordsizesize;
        if (m_resultset.find(hash) != m_resultset.end()) {
            continue;
        }
        m_resultset.insert(hash);

        if (m_bPrintId) {
            printf("%d %d %d\n", start, wordsizesize, wordids[i]);
        } else {
            char* buffer = new char[wordsizesize + 1];
            memcpy(buffer, &data[start], wordsizesize);
            buffer[wordsizesize] = 0;
            printf("%d %d %s\n", start, wordsizesize, buffer);
            delete[] buffer;
        }
    }
}

struct ThreadData {
    Automaton* automaton;
    BYTE* data;
    int offset;
    int size;
};

DWORD WINAPI ThreadFun(LPVOID pm) {
    ThreadData* data = (ThreadData*) pm;
    data->automaton->query((BYTE*)data->data, data->offset, data->size);
    return 0;
}

int testz(int argcz, wchar_t* argvz[]) {

    if (!automaton.buildfromfile(keyfile)) {
        return -1;
    }
    automaton.setPrintId(true);

    long length = 0;
    char* fdata = readfile(inputfile, length);

    if (length < 1024 || threadcount == 1) {
        automaton.query((BYTE*)fdata, length);
    } else {

        int piece = length / threadcount;

        HANDLE* hThread = new HANDLE[threadcount];
        ThreadData* hThreadData = new ThreadData[threadcount];
        for(int i = 0; i < threadcount; i++) {
            ThreadData& data = hThreadData[i];
            data.automaton = &automaton;
            data.data = (BYTE*)fdata;
            data.offset = piece * i;

            // 重叠部分，避免误差。
            data.size = piece + automaton.getMaxWordSize() + 1;
            if (data.offset + data.size > length) {
                data.size = length - data.offset;
            }

            LPVOID lpParameter = &hThreadData[i];
            hThread[i] = CreateThread(NULL, 0, ThreadFun, lpParameter, 0, NULL);
        }

        WaitForMultipleObjects(threadcount, hThread, TRUE, INFINITE);
        for (int i = 0; i < threadcount; i++) {
            CloseHandle(hThread[i]); // 关闭线程
        }
        delete[] hThread;
        delete[] hThreadData;
    }
    delete[] fdata;
    return 0;
}