Ters Dizin: Belgeler kümesindeki bir ifadeyi bul

Question

Ben bir boğa sorguları ve sözcük düzeyinde tanecikliğe olanak sağlayan bir ters çevrilmiş dizin yapısını yapıyorum.

Geniş bir metin veritabanına sahibim ve her dosya için, hangi dosyada (IDdoc) olduğunu ve dosyanın (position) olduğu bir dizini saklıyorum. (Bir kelime çok dosya ve tek bir dosyada birçok yerde olabilir.)

Böylece her kelime için bir vektör tutmak:

vector<pair<IDdoc,position>> occurences_of_word; 

(vektör içinde, IDdoc tarafından ve daha sonra konuma göre sıralanır artan düzen.)

sözcükleri'dan yapılmış bir string nesnesine sahibim. Bu arıyorum ifade ifade ediyor. dolayısıyla IDdoc s bir vektör dönen, bu ifadeyi içeren belgeler bilmek istediğim ifade her kelime için

.

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; 
} 

Answer 1

Dizgeyle temsil edilen belirli bir Word'ü ararken, muhtemelen map gibi bir şeye bakmak istersiniz. Basit bir sonuç birliği oluşturmak için muhtemelen set. Bu uygulama, son derece istenen bir nihai uygulamadan ziyade bir gösteri olarak yazılmıştır (c.f.özensiz ifade ayrıştırma). bu bir

#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; 
} 

Çevrimiçi demo: http://ideone.com/Zlhfua

---

değişiklikleri ele almak Takip:

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" Diyelim biri olduğu anlamına gelir 1'dir vektörde eleman, eleman [0]. ID_doc_one 0'dır ve ID_doc_two sonra, geçersiz

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

1 ise. Bu tür kırık görünüyor,

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. 
    ... 
} 

İleri:

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; 
    } 

Ve senin de aynı belgeyi ancak birden pozisyonları varsa ne olur acaba Sen yineleyicinızı veya işaretçileri kullanarak daha iyi olabilir?

Bu gelecek sirke seçici, ancak ikinci kelime pozisyonundan sonra ise (" o bunu diyebilirsiniz bu yazmak için çok daha net görünüyor

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) 

ayrıştırmak için bana uzun bir zaman aldı birinci sözcük): Her iki maddeleri ortak içine parçası kaldırma için, mantıklı olurdu i ve j, ve güncelleme ID_doc_one ve iki artırmak için tasarlanmıştır ortaya çıktı çünkü

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) 

Bu, sonraki bir parçası, bir tür kafa karıştırıcı if bloğundan sonra bölüm, ancak yine else {} bunu yaptı aslında ne yaptığınızı söylemek zor. Her iki diziler maç ne zaman pos_two kullanırken neden ifade aslında pos_one yerinde bulundu beri

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; 
    } 

, her zaman, ben de emin değilim, i ve j hem bu şart değil artırmak istediğiniz?

Bu

bunu yazdım şekli şöyledir:

#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; 
} 

Canlı örnek: http://ideone.com/XRfhAI

Answer 2

bu en verimli olup olmadığını bilmiyorum, ama sen words[0] belgeleri/pozisyonları ile başlayabilir:

Burada bir çözüme benim girişimidir. Daha sonra words[1]'a gidin ve aynı belgeler için words[0].position + words[0].length + 1'a eşit olan kesişen belgeleri bulun. Sonra aynı şekilde words geri kalanı üzerinde yineleyin. Daha uzun ifadeler için oldukça hızlı bir şekilde daraltmalı mı? Wikipedia tarafından belirtildiği gibi belirtilmiştir gibi

Answer 3

, kullandığınız veri yapısı, aslında tam ters endeksidir:

ters endeksler iki ana varyantı bulunmaktadır: A kaydı seviyesi ters endeksi (veya ters dosya dizin veya sadece ters çevrilmiş dosya), her kelime için belgelere başvuruların bir listesini içerir. Sözcük düzeyi tersine çevrilmiş indeks (veya tam ters çevrilmiş indeks veya ters çevrilmiş liste), ek olarak, bir belgenin içindeki her kelimenin konumlarını içerir. [2] Son biçim, daha fazla işlevsellik (sıralı aramalar gibi) sunar, ancak oluşturulacak daha fazla zamana ve alana gereksinim duyar.

söyleniyor, ayrıca bir ifade dizini oluşturmak için deneyebilirsiniz:

http://ww2.cs.mu.oz.au/~jz/fulltext/acmtois04.pdf

(bir göstergesi olarak Bakınız Şekil 2).

Bir öbek dizini oluşturmuyorsanız, ne yapabileceğinizi (inanıyorum), yalnızca belirli bir sözcük içeren belgeleri almanız, kelimelerden gelen sorguyu büyütürken sahip olduğunuz belge kümesini kesiştirmeniz yeterli olacaktır. ifadelere sonra nihayet belgeye geri dönüp, sahip olduğunuz her iade edilen belgenin aslında "farklı konumlarda birbirlerini ayıran kelimeler" yerine "ifade" yi içerdiğini görün.