Перевернутый указатель: поиск фразы в наборе документов
Я реализую перевернутый индекс структура, в частности такая, которая допускает логические запросы, и гранулярность на уровне слов.
У меня большая база данных текста, и я держу индекс, который говорит мне, для каждого слова, в каком файле это (IDdoc) и где в файле это находится (position). (Слово может быть во многих файлах и во многих местах в одном файле.)
Таким образом я сохраняю вектор для каждого слова:
vector<pair<IDdoc,position>> occurences_of_word;
(Вектор сортируется по IDdoc, а затем по позиции в порядке возрастания.)
у меня есть string объект сделан из слова. Это фраза Я ищу.
Для каждого слово в фраза Я хотел бы знать, какие документы содержат эту фразу, следовательно, возвращая вектор IDdocs.
Вот моя попытка решения:
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;
}
Решение
Для поиска определенного Word из строкового представления вы, вероятно, захотите посмотреть на что-то вроде карта. Для создания простого объединения результатов вы, вероятно, хотите задавать. Эта реализация написана скорее как демонстрация, чем как крайне желательная финальная реализация (например, небрежный разбор фраз).
#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. Это означает, что в векторе есть один элемент, 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)
кажется, гораздо яснее написать это так, как вы могли бы сказать «(если второе слово находится в позиции после первого слова):
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_two, так как фраза была фактически найдена в pos_one?
Вот как бы я написал это:
#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
Другие решения
Я не знаю, является ли это наиболее эффективным, но вы могли бы начать с документов / должностей words[0], Затем перейдите к words[1] и найти пересекающиеся документы с позициями, равными words[0].position + words[0].length + 1 по тем же документам. Затем аналогичным образом переберите остальную часть words, Это должно сузиться довольно быстро для более длинных фраз?
Как вы заявили, структура данных, которую вы используете, на самом деле является полностью инвертированным индексом, как заявлено в Википедии:
Существует два основных варианта инвертированных индексов: Инвертированный индекс уровня записи (или инвертированный индекс файла или просто инвертированный файл) содержит список ссылок на документы для каждого слова. Инвертированный индекс уровня слова (или полностью инвертированный индекс или инвертированный список) дополнительно содержит позиции каждого слова в документе. [2] Последняя форма предлагает больше функциональности (например, поиск по фразам), но требует больше времени и места для создания.
При этом вы также можете попытаться создать словосочетание:
http://ww2.cs.mu.oz.au/~jz/fulltext/acmtois04.pdf
(См. Рисунок 2 в качестве демонстрации).
Если вы не создаете словосочетание, то, что вы можете сделать (я полагаю), это просто извлечь документы, содержащие определенное слово, пересечь имеющийся у вас набор документов при увеличении запроса от слов к фразам, а затем наконец, вернитесь к документу и посмотрите, содержит ли каждый возвращаемый документ фактически «фразу» вместо «слова, разделяющие друг друга в разных позициях».