algorithm - 计算倒排索引中的词接近度

Question

作为搜索引擎的一部分，我开发了一个倒排索引。

所以我有一个列表，其中包含以下类型的元素

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

现在这个记录是针对一个词的。 hitLocation 包含在文档中找到特定单词的位置。

现在我想要的是计算 List<int> hitLocation 中元素的接近度到另一个List<int> hitLocation然后如果List中的元素相邻则增加两条记录的权重。

我遇到的问题是为此目的找到合适的算法。感谢任何帮助

Answer 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 子句中进行类似的检查。