Um ein bestimmtes Wort aus der Zeichenfolgendarstellung nachzuschlagen, möchten Sie wahrscheinlich etwas wie map betrachten. Zum Erstellen einer einfachen Vereinigung von Ergebnissen möchten Sie wahrscheinlich set. Diese Implementierung ist mehr als Demonstration als als äußerst wünschenswerte endgültige Implementierung geschrieben (vgl.schlampige Phrasenparsing).
#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;
}
Online-Demo von diesem an: http://ideone.com/Zlhfua
Follow-up, um Ihre Änderungen Adresse:
while(i < SIZE_VECTOR_ONE && j < SIZE_VECTOR_TWO)
{
if (ID_doc_one < ID_doc_two)
{
ID_doc_one = v1[++i].first;
Lassen Sie uns sagen "SIZE_VECTOR 1" ist 1. Das bedeutet, dass es einen gibt Element im Vektor, Element [0]. Wenn ID_doc_one gleich 0 ist und ID_doc_two gleich 1 ist, dann
, was ungültig ist. Vielleicht haben Sie besser dran Iteratoren oder Zeiger verwendet werden:
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.
...
}
Next, das sieht irgendwie gebrochen:
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;
}
Und ich frage mich, was passiert, wenn Sie das gleiche Dokument aber mehrere Positionen haben?
Die nächste ist nit-wählerisch, aber es dauerte eine lange Zeit
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)
scheint es wesentlich deutlicher zu analysieren, dies zu schreiben, wie Sie es sagen könnten „(wenn das zweite Wort in der Lage ist, nach das erste Wort):
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)
Dieser nächste Teil war etwas verwirrend, da beide Klauseln bestimmt erschien i und j und Update ID_doc_one und zwei zu erhöhen, wäre es sinnvoll gewesen, dass ein Teil in einen gemeinsamen hissen Abschnitt nach dem if-Block, aber wieder die else {} hat es geschafft schwer zu sagen, was du eigentlich gemacht hast.
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;
}
Wenn Sie beide Arrays entsprechen, möchten Sie immer beide erhöhen i und j, es ist nicht Bedingung, ich bin auch nicht sicher, warum Sie pos_two verwenden, da der Begriff tatsächlich bei pos_one gefunden wurde?
Dies ist, wie ich es geschrieben hätte:
#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;
}
anschauliches Beispiel: http://ideone.com/XRfhAI
Nicht sicher, was Sie fordern genau - fragen Sie, wie man welche Ihrer Dokumente enthalten „eine Nummer identifizieren Philips-Schraubendreher ", oder welche Dokumente enthalten die Wörter" A "," Nummer "" eins "," Philips "oder" Schraubenzieher ". Wenn die ersteren, müssen sie aufeinander folgen oder werden "die Anzahl der Griffe auf einem Schraubendreher ist eine sowohl für Philips und Pozidrive" ein Match sein? –
@MatsPetersson, sie müssen aufeinander folgen. –
Related: http://stackoverflow.com/questions/2659120/how-to-search-phrase-queries-in-inverted-index-struktur – jogojapan