テキスト内の25 000語を検索

https://stackoverflow.com/questions/154365

03-07-2019
|

質問

テキスト内で〜25 000単語の出現を見つける必要があります。この目的に最も適したアルゴリズム/ライブラリは何ですか？

ターゲット言語はC ++

解決

worldテーブルで各単語を検索するために、単語を含むハッシュテーブルを作成し、テキストをスキャンして、必要な情報を詰め込みます（カウントを増やし、位置リストに追加します）。

他のヒント

かつてボイヤー・ムーアアルゴリズムを使用しましたが、非常に高速でした。

Boyer-Mooreは、多くの単語を効率的に検索するのに適していません。実際には、Wu-Manberアルゴリズムと呼ばれる非常に効率的なアルゴリズムがあります。リファレンス実装を投稿します。ただし、これは先ほど教育目的でのみ行ったことに注意してください。したがって、実装は実際には直接使用するのに適しておらず、より効率的にすることもできます。

Dinkumware STLの stdext :: hash_map も使用します。 std :: tr1 :: unordered_map または適切な実装で置き換えます。

Knut Reinertが開催したFreie Universit＆＃228; t Berlinでの講義の講義スクリプト。

元の論文もオンラインになっていますが（再び見つかったばかりですが）特にそこに提示された擬似コードが好きです。

#ifndef FINDER_HPP
#define FINDER_HPP

#include <string>

namespace thru { namespace matching {

class Finder {
public:
    virtual bool find() = 0;

    virtual std::size_t position() const = 0;

    virtual ~Finder() = 0;

protected:
    static size_t code_from_chr(char c) {
        return static_cast<size_t>(static_cast<unsigned char>(c));
    }
};

inline Finder::~Finder() { }

} } // namespace thru::matching

#endif // !defined(FINDER_HPP)

#include <vector>
#include <hash_map>

#include "finder.hpp"

#ifndef WUMANBER_HPP
#define WUMANBER_HPP

namespace thru { namespace matching {

class WuManberFinder : public Finder {
public:

    WuManberFinder(std::string const& text, std::vector<std::string> const& patterns);

    bool find();

    std::size_t position() const;

    std::size_t pattern_index() const;

private:

    template <typename K, typename V>
    struct HashMap {
        typedef stdext::hash_map<K, V> Type;
    };

    typedef HashMap<std::string, std::size_t>::Type shift_type;
    typedef HashMap<std::string, std::vector<std::size_t> >::Type hash_type;

    std::string const& m_text;
    std::vector<std::string> const& m_patterns;
    shift_type m_shift;
    hash_type m_hash;
    std::size_t m_pos;
    std::size_t m_find_pos;
    std::size_t m_find_pattern_index;
    std::size_t m_lmin;
    std::size_t m_lmax;
    std::size_t m_B;
};

} } // namespace thru::matching

#endif // !defined(WUMANBER_HPP)

#include <cmath>
#include <iostream>

#include "wumanber.hpp"

using namespace std;

namespace thru { namespace matching {

WuManberFinder::WuManberFinder(string const& text, vector<string> const& patterns)
    : m_text(text)
    , m_patterns(patterns)
    , m_shift()
    , m_hash()
    , m_pos()
    , m_find_pos(0)
    , m_find_pattern_index(0)
    , m_lmin(m_patterns[0].size())
    , m_lmax(m_patterns[0].size())
    , m_B()
{
    for (size_t i = 0; i < m_patterns.size(); ++i) {
        if (m_patterns[i].size() < m_lmin)
            m_lmin = m_patterns[i].size();
        else if (m_patterns[i].size() > m_lmax)
            m_lmax = m_patterns[i].size();
    }

    m_pos = m_lmin;
    m_B = static_cast<size_t>(ceil(log(2.0 * m_lmin * m_patterns.size()) / log(256.0)));

    for (size_t i = 0; i < m_patterns.size(); ++i)
        m_hash[m_patterns[i].substr(m_patterns[i].size() - m_B)].push_back(i);

    for (size_t i = 0; i < m_patterns.size(); ++i) {
        for (size_t j = 0; j < m_patterns[i].size() - m_B + 1; ++j) {
            string bgram = m_patterns[i].substr(j, m_B);
            size_t pos = m_patterns[i].size() - j - m_B;

            shift_type::iterator old = m_shift.find(bgram);
            if (old == m_shift.end())
                m_shift[bgram] = pos;
            else
                old->second = min(old->second, pos);
        }
    }
}

bool WuManberFinder::find() {
    while (m_pos <= m_text.size()) {
        string bgram = m_text.substr(m_pos - m_B, m_B);
        shift_type::iterator i = m_shift.find(bgram);
        if (i == m_shift.end())
            m_pos += m_lmin - m_B + 1;
        else {
            if (i->second == 0) {
                vector<size_t>& list = m_hash[bgram];
                // Verify all patterns in list against the text.
                ++m_pos;
                for (size_t j = 0; j < list.size(); ++j) {
                    string const& str = m_patterns[list[j]];
                    m_find_pos = m_pos - str.size() - 1;
                    size_t k = 0;

                    for (; k < str.size(); ++k)
                        if (str[k] != m_text[m_find_pos + k])
                            break;

                    if (k == str.size()) {
                        m_find_pattern_index = list[j];
                        return true;
                    }
                }
            }
            else
                m_pos += i->second;
        }
    }

    return false;
}

size_t WuManberFinder::position() const {
    return m_find_pos;
}

size_t WuManberFinder::pattern_index() const {
    return m_find_pattern_index;
}

} } // namespace thru::matching

使用例：

vector<string> patterns;
patterns.push_back("announce");
patterns.push_back("annual");
patterns.push_back("annually");

WuManberFinder wmf("CPM_annual_conference_announce", patterns);

while (wmf.find())
    cout << "Pattern \"" << patterns[wmf.pattern_index()] <<
        "\" found at position " << wmf.position() << endl;

A ブルームフィルターが最善の策です。検索語でフィルターを初期化し、コーパスを読んでいる間、各作品がフィルター内にあるかどうかをすばやく確認できます。

これは非常にスペース効率が高く、各単語をハッシュするよりもはるかに優れています。1％の誤検出率では、要素ごとに9.6ビットしか必要ありません。偽陽性率は、要素ごとに4.8ビットが追加されるごとに10分の1ずつ減少します。これとは対照的に、通常要素ごとにsizeof（int）== 32ビットを必要とするプレーンハッシュとは対照的です。

C＃の実装は次のとおりです： http://www.codeplex.com/bloomfilter

文字列での使用を示す例です：

int capacity = 2000000; // the number of items you expect to add to the filter
Filter<string> filter = new Filter<string>(capacity);
filter.Add("Lorem");
filter.Add("Ipsum");
if (filter.Contains("Lorem"))
    Console.WriteLine("Match!");

コーパスが非常に大きい場合は、次の方法で最適化します：

チェックする必要のある各単語のハッシュを計算し、各charに整数の素数を割り当ててから、各数値を乗算します。各数値を格納します->単語をマルチマップに格納します（単一のキーで複数の値を許可する必要があります））

ワードリストをスキャンしながら、各ワードについて同じ方法でハッシュを計算し、ハッシュマップ上の計算されたキーに関連付けられたワードを取得します。整数をキーとして使用すると、O（1）を取得できます。これにより、処理された単語にアナグラム（文字を乗算したもの）がマップ内に含まれている場合、非常に迅速に見つけることができます。

覚えておいてください。同じハッシュを持つ単語のセットをマルチマップに保存したため、この大幅に削減されたセットで一致を見つける必要があります。マップ上の整数の単純な存在は、関連セット内の単語の存在と同等ではないため、この追加チェックが必要です。ここではハッシュを使用して問題の計算スペースを削減していますが、これにより衝突が発生し、識別された各アナグラムを明確に確認します。

Aho-Corasickアルゴリズムを使用します。このアプリケーション用に作成されました。検索テキストの各文字を読む必要があるのは一度だけです。私は最近、それを実装して使用し、素晴らしい結果を得ました。

Javierが言うように、おそらく最も簡単な解決策はハッシュテーブルです。

C ++では、これはSTLセットを使用して実装できます。最初に25,000個のテストワードをセットに追加し、次にset.find（current_word）を使用してテキスト内の各ワードをスキャンして、そのワードが25,000個のテストワードに含まれるかどうかを評価します。

set.findは対数的に高速であるため、25,000個のテストワードが大きすぎてはなりません。アルゴリズムは、テキスト内の単語数において明らかに線形です。

検索しているテキストが巨大な場合、25,000語をTRIEにまとめる前処理を行う価値があります。

テキストの最初の単語の先頭までスキャンし、単語の文字を読みながらTRIEを歩き始めます。 TRIEに遷移がない場合は、次の単語の先頭にスキップして、TRIEのルートに戻ります。単語の最後に到達し、TRIEの単語終了ノードにいる場合は、一致が見つかりました。テキスト内の単語ごとに繰り返します。

テキストが（巨大ではなく）単に大きい場合は、ハッシュテーブルで各単語を検索するだけで十分です。

viceBergのコメント：

かつてボイヤー・ムーア・アルゴリズムを使用しましたそれは非常に高速でした。

ボイヤー・ムーアでは、通常、テキストブロックで単一文字列を検索しませんか？

実装を簡単にするために、Javierが提案したハッシュテーブルアプローチを使用します。 FatCat1111が提案するブルームフィルターも機能するはずです...目標に応じて。

最初の辞書（25000ワード）をディスク上のberkeley dbハッシュテーブルに格納し、おそらくc / c ++から直接使用できます（perlから実行できることを知っています）。テキスト、データベースに存在するかどうかを照会します。

テキストと単語リストをアルファベット順に並べ替えることもできます。 2つの並べ替えられた配列がある場合、線形時間で簡単に一致を見つけることができます。

3項検索ツリーが必要です。適切な実装は、こちらで見つけることができます。

Aho-Corasickアルゴリズムは、その目的のために特別に構築されています：一度に多くの単語を検索します。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow