8

逆インデックス構造、特にブールクエリと単語レベルの粒度を可能にする構造を実装しています。

私はテキストの大規模なデータベースを持っており、すべての単語について、それがどのファイルにあるのか ( IDdoc)、ファイルのどこにあるのか( ) を示すインデックスを保持していますposition。(単語は、多くのファイルに存在する場合もあれば、1 つのファイルの多くの場所に存在する場合もあります。)

したがって、各単語のベクトルを保持します。

vector<pair<IDdoc,position>> occurences_of_word;

(ベクトルは IDdoc で並べ替えられ、次に位置で昇順で並べ替えられます。)

私は言葉stringでできたオブジェを持っています。これが私が探している言葉です。

フレーズ内の各単語について、どのドキュメントにこのフレーズが含まれているかを知りたいので、s のベクトルを返します。IDdoc

これが私の解決策の試みです：

typedef std::string     Word_t;
typedef unsigned int    WordPosition_t;
typedef unsigned int    IDdocument_t;

vector<pair<IDdocument_t,WordPosition_t> > IndiceInvertidoBooleanoConPosicion::_interseccion_dos_listas
    (const vector<pair<IDdocument_t,WordPosition_t>> & v1,
    const vector<pair<IDdocument_t,WordPosition_t>> & v2)
{
vector<pair<IDdocument_t,WordPosition_t> > intersection;

IDdocument_t ID_doc_one, ID_doc_two;

int i = 0;
int j = 0;
const int MAX_INDEX_V1 = v1.size() -1;
const int MAX_INDEX_V2 = v2.size() -1;

while(i <= MAX_INDEX_V1  && j <= MAX_INDEX_V2)
{
    ID_doc_one = v1[i].first;
    ID_doc_two = v2[j].first;
    if (ID_doc_one < ID_doc_two)
        i++;
    else if (ID_doc_one > ID_doc_two)
        j++;
    else // The words were found in the same document!
    {
        WordPosition_t pos_word_one = v1[i].second;
        WordPosition_t pos_word_two = v2[j].second;

        // The words make a phrase!  Return pos_two for the next intersection finding step
        if (pos_word_one + 1 == pos_word_two)
        {
            intersection.push_back(make_pair(ID_doc_one,pos_word_two));
            i++;
            j++;
        }

        // Phrase not found
        else
        {
            if (pos_word_one < pos_word_two)
                i++;
            else
                j++;
        }

    }
}

return intersection;
}

int find_phrase(const string phrase, vector<IDdocument_t> & id_docs)
{
Word_t word;
id_docs.clear();
Text parsed_phrase;
// Extract the relevant words from the phrase
parsed_phrase.parse(phrase); 

vector<pair<IDdocument_t,WordPosition_t> > intersection;
vector<pair<IDdocument_t,WordPosition_t> > second_vector;

while (parsed_phrase.get_next_word(word) != RES_END)
{
    _find_vector_words(word,intersection);

    while (parsed_phrase.get_next_word(word) != RES_END)
    {
        _find_vector_words(word,second_vector);

        intersection = _intersect_two_words(intersection,second_vector);

    }
}

for (unsigned int i = 0; i < intersection.size(); i ++)
{
    IDdocument_t id_doc = intersection[i].first;
    if(std::find(id_docs.begin(), id_docs.end(), id_doc) == id_docs.end())
        id_docs.push_back(id_doc);
}

return RES_OK;
}
4

3 に答える 3

2

文字列表現から特定の Word を検索するには、おそらくmapのようなものを見たいと思うでしょう。結果の単純な結合を作成するには、おそらくsetが必要です。この実装は、非常に望ましい最終的な実装というよりは、デモンストレーションとして書かれています (ずさんなフレーズの解析を参照)。

#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <string>

typedef std::string IDdoc;
typedef int position;

typedef std::pair<IDdoc,position> Occurrence;
typedef std::vector<Occurrence> OccurrencesOfWord;
typedef std::map<std::string /*word*/, OccurrencesOfWord> Dictionary;
typedef std::set<IDdoc> Matches;

bool findMatchesForPhrase(const std::string& phrase, const Dictionary& dictionary, Matches& matches)
{
    size_t pos = 0;
    size_t len = 0;
    while (pos < phrase.length()) {
        size_t end = phrase.find(' ', pos);
        size_t len = ((end == phrase.npos) ? phrase.length() : end) - pos;
        std::string word(phrase, pos, len);
        pos += len + 1; // to skip the space.

        // ignore words not in the dictionary.
        auto dictIt = dictionary.find(word);
        if (dictIt == dictionary.end())
            continue;

        auto& occurrences = dictIt->second; // shortcut/alias,.
        for (auto& occurIt : occurrences) {
            // Add all the IDdoc's of this occurence to the set.
            matches.insert(occurIt.first);
        }
    }

    return !matches.empty();
}

void addToDictionary(Dictionary& dict, const char* word, const char* doc, int position)
{
    dict[word].push_back(std::make_pair(std::string(doc), position));
}

int main(int argc, const char** argv)
{
    std::string phrase("pizza is life");
    Dictionary dict;

    addToDictionary(dict, "pizza", "book1", 10);
    addToDictionary(dict, "pizza", "book2", 30);
    addToDictionary(dict, "life", "book1", 1);
    addToDictionary(dict, "life", "book3", 1);
    addToDictionary(dict, "goat", "book4", 99);

    Matches matches;
    bool result = findMatchesForPhrase(phrase, dict, matches);

    std::cout << "result = " << result << std::endl;
    for (auto& ent : matches) {
        std::cout << ent << std::endl;
    }

    return 0;
}

これのオンライン デモ: http://ideone.com/Zlhfua

フォローアップして変更に対処します。

while(i < SIZE_VECTOR_ONE  && j < SIZE_VECTOR_TWO)
{
    if (ID_doc_one < ID_doc_two)
    {
        ID_doc_one = v1[++i].first;

「SIZE_VECTOR 1」が 1 だとしましょう。これは、ベクトルに 1 つの要素 element[0] があることを意味します。ID_doc_one が 0 で ID_doc_two が 1 の場合、

if (0 < 1) {
    ID_doc_one = v1[1].first;

これは無効です。イテレータまたはポインタを使用する方がよい場合があります。

while (oneIt != v1.end() && twoIt != v2.end()) {
    if (oneIt->first < twoIt->first) {
        ++oneIt;
        continue;
    } else if (*twoIt < *oneIt) {
        ++twoIt;
        continue;
    }
    // same documentId in both lists, snag positions.
    ...
}

次に、これはちょっと壊れているように見えます:

    else {
    }   // To avoid "out of range" errors <-- but also ends the "else"
        if (i < SIZE_VECTOR_ONE - 1)
            ID_doc_one = v1[++i].first;
        if (j < SIZE_VECTOR_TWO - 1)
            ID_doc_two = v2[++j].first;
    }

また、同じドキュメントで複数のポジションがある場合はどうなるでしょうか?

この次は気まぐれですが、解析するのに長い時間がかかりました

    WordPosition_t pos_one = v1[i].second;
    WordPosition_t pos_two = v2[j].second;

    // The words make a phrase!  Return pos_two for the next intersection finding step
    if (pos_one + 1 == pos_two)

「(2 番目の単語が最初の単語の後の位置にある場合):

    WordPosition_t posFirstWord = v1[i].second;
    WordPosition_t posSecondWord = v2[j].second;

    // The words make a phrase!  Return pos_two for the next intersection finding step
    if (posSecondWord == posFirstWord + 1)

この次の部分は、どちらの句も i と j をインクリメントし、ID_doc_one と two を更新することを意図しているように見えたので、ちょっとややこしかったです。その部分を if ブロックの後に共通のセクションに引き上げるのは理にかなっていたでしょうが、これelse {}も難しくなりました。あなたが実際に何をしていたかを伝えるために。

    if (pos_one + 1 == pos_two)
    {
        intersection.push_back(make_pair(ID_doc_one,pos_two));
        ID_doc_one = v1[++i].first;
        ID_doc_two = v2[++j].first;
    }

    else {
    }   // To avoid "out of range" errors
        if (i < SIZE_VECTOR_ONE - 1)
            ID_doc_one = v1[++i].first;
        if (j < SIZE_VECTOR_TWO - 1)
            ID_doc_two = v2[++j].first;
    }

両方の配列を一致させる場合、常に i と j の両方をインクリメントする必要があります。これは条件ではありません。フレーズが実際に pos_one で見つかったため、pos_two を使用している理由もわかりません。

これは私がそれを書いた方法です：

#include<iostream>
#include<map>
#include<vector>
#include<string>

typedef std::string         Word_t;
typedef unsigned int        WordPosition_t;
typedef unsigned int        IDdocument_t;

typedef std::pair<IDdocument_t, WordPosition_t> DocumentPosition_t;
typedef std::vector<DocumentPosition_t> WordReferences_t;

WordReferences_t _intersect_two_words(const WordReferences_t& v1, const WordReferences_t& v2)
{
    // all the locations where the words occur one after the other.
    WordReferences_t intersection;

    auto firstIt = v1.begin();
    auto secondIt = v2.begin();
    while (firstIt != v1.end() && secondIt != v2.end())
    {
        if (firstIt->first < secondIt->first)
        {
            ++firstIt;
            continue;
        }
        // find the second word in the same document and AFTER the first word.
        if (secondIt->first < firstIt->first || secondIt->second < firstIt->second + 1)
        {
            ++secondIt;
            continue;
        }
        // first word wasn't just before the second, it's not a phrase.
        if (secondIt->second > firstIt->second + 1)
        {
            ++firstIt;
            continue;
        }
        // We found a phrase.
        intersection.emplace_back(*firstIt);
        ++firstIt;
        ++secondIt;
    }

    return intersection;
}

int main()
{
    WordReferences_t v1, v2;
    v1.push_back(std::make_pair(10, 5));
    v1.push_back(std::make_pair(10, 25));
    v1.push_back(std::make_pair(11, 10));
    v1.push_back(std::make_pair(12, 1));
    v1.push_back(std::make_pair(12, 11));
    v1.push_back(std::make_pair(12, 21));
    v1.push_back(std::make_pair(12, 31));
    v1.push_back(std::make_pair(15, 11));
    v1.push_back(std::make_pair(100, 1));
    v1.push_back(std::make_pair(100, 11));
    v1.push_back(std::make_pair(100, 21));
    v1.push_back(std::make_pair(101, 11));
    v1.push_back(std::make_pair(102, 11));
    v1.push_back(std::make_pair(102, 13));
    v1.push_back(std::make_pair(102, 14));
    v1.push_back(std::make_pair(103, 11));
    v1.push_back(std::make_pair(103, 13));

    v2.push_back(std::make_pair(10, 11));
    v2.push_back(std::make_pair(12, 10));
    v2.push_back(std::make_pair(12, 40));
    v2.push_back(std::make_pair(16, 11));
    v2.push_back(std::make_pair(100, 12)); // match
    v2.push_back(std::make_pair(101, 12)); // match
    v2.push_back(std::make_pair(101, 13));
    v2.push_back(std::make_pair(101, 14));
    v2.push_back(std::make_pair(102, 12)); //match
    v2.push_back(std::make_pair(103, 1));
    v2.push_back(std::make_pair(103, 10));
    v2.push_back(std::make_pair(103, 12)); // match
    v2.push_back(std::make_pair(103, 15));

    auto intersection = _intersect_two_words(v1, v2);
    for (auto entry : intersection)
    {
        std::cout << entry.first << ", " << entry.second << "+" << (entry.second + 1) << std::endl;
    }

    return 0;
}

実際の例: http://ideone.com/XRfhAI

于 2013-06-28T02:54:00.763 に答える
0

これが最も効率的かどうかはわかりませんが、 のドキュメント/位置から始めることができますwords[0]。次に、 に移動して、同じドキュメントに対してwords[1]と等しい位置で交差するドキュメントを見つけwords[0].position + words[0].length + 1ます。次に、同様に の残りの部分を繰り返しwordsます。長いフレーズの場合、かなり迅速に絞り込む必要がありますか?

于 2013-06-27T23:06:55.270 に答える