Calculating Word Proximity in an inverted Index

问题:

As part of search engine i have developed an inverted index.

So i have a list which contains elements of the following type

public struct ForwardBarrelRecord
{
    public string DocId;
    public int hits { get; set; }
    public List<int> hitLocation;
}

Now this record is against a single word. The hitLocation contains the locations where a particular word has been found in a document.

Now what i want is to calculate the closeness of elements in List<int> hitLocation to another List<int> hitLocation and then if the elements in the List are adjacent then to increase the weight of both records.

Problem that i am having is finding a suitable algorithm for this purpose. Any Help is appreciated

回答1:

This is easiest if the hitLocation lists are in sorted order. So start with:

var word1List = word1.hitLocation.Orderby(s => s).ToList();
var word2List = word2.hitLocation.Orderby(s => s).ToList();

Although if you're doing this for a search engine then you'll probably want those lists to be pre-sorted in your inverted index.

In any case, once you have the lists sorted, finding matches is pretty easy.

int ix1 = 0;
int ix2 = 0;
while (ix1 < word1List.Count && ix2 < word2List.Count)
{
    int hit1 = word1List[ix1];
    int hit2 = word2List[ix2];
    if (hit1 < hit2)
    {
        if ((hit2 - hit1) == 1)
        {
            Console.WriteLine("Match at {0} and {1}", hit1, hit2);
        }
        ix1++;
    }
    else
    {
        ix2++;
    }
}          

That will locate occurrences of word1 followed by word2. If you also want word2 followed by word1, you could put a similar check in the else clause.

回答2:

#include <iostream>
#include <list>
#include <string>
using namespace std;

struct ForwardBarrelRecord
{
    string DocId;
    int hits;
    list<int> hitLocation;
};

void merge(struct ForwardBarrelRecord& fa, struct ForwardBarrelRecord& fb)
{
    list<int>& la = fa.hitLocation;
    list<int>& lb = fb.hitLocation;
    la.sort();
    lb.sort();
    std::list<int>::iterator ita = la.begin(); 
    std::list<int>::iterator itb = lb.begin();
    while(ita != la.end() && itb != lb.end())
    {
        int loc_a = *ita;
        int loc_b = *itb;
        if (loc_a < loc_b)
        {
            if (loc_a + 1 == loc_b)
            {
                cout << "adjacent pair (" << loc_a << ", " << loc_b << ")" << endl;
            }
            ita++;
        }
        else if (loc_a > loc_b)
        {
            if (loc_b + 1 == loc_a)
            {
                cout << "adjacent pair (" << loc_a << ", " << loc_b << ")" << endl;
            }
            itb++;
        }
        else
        {
            ita++;
            itb++;
            if (ita != la.end() && *ita == loc_b + 1)
            {
                cout << "adjacent pair (" << *ita << ", " << loc_b << ")" << endl;
            }
            if (itb != lb.end() && *itb == loc_a + 1)
            {
                cout << "adjacent pair (" << loc_a << ", " << *itb << ")" << endl;
            }
        }
    }
}

int main() {
    struct ForwardBarrelRecord fa;
    fa.hitLocation.push_back(1);
    fa.hitLocation.push_back(2);
    fa.hitLocation.push_back(3);
    struct ForwardBarrelRecord fb;
    fb.hitLocation.push_back(2);
    fb.hitLocation.push_back(3);
    merge(fa, fb);
    return 0;
}

please refer to the code to output all adjacent hit locations in a merge-scan of 2 sorted lists.