0

検索エンジンの一部として、逆索引を開発しました。

だから私は次のタイプの要素を含むリストを持っています

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

現在、この記録は単一の単語に対してです。hitLocation には、ドキュメント内で特定の単語が見つかった場所が含まれます。

今私が欲しいのは、要素の近さList<int> hitLocationを別の要素と計算List<int> hitLocationし、リスト内の要素が隣接している場合は、両方のレコードの重みを増やすことです。

私が抱えている問題は、この目的に適したアルゴリズムを見つけることです。どんな助けでも大歓迎です

4

2 に答える 2

1

hitLocationリストがソートされている場合、これは最も簡単です。だから始めてください：

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

ただし、検索エンジンに対してこれを行う場合は、おそらくそれらのリストを逆インデックスで事前に並べ替えたいと思うでしょう。

いずれにせよ、リストを並べ替えると、一致するものを見つけるのは非常に簡単です。

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

これにより、word1 の後に word2 が続く箇所が検索されます。word2 の後に word1 も必要な場合は、else句に同様のチェックを入れることができます。

于 2013-09-25T21:21:25.563 に答える
0 
#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;
}

コードを参照して、2 つの並べ替えられたリストのマージ スキャンですべての隣接するヒット位置を出力してください。

于 2015-03-06T11:24:19.267 に答える