C# 查找相关文档片段以显示搜索结果

Question

在为我正在构建的网站开发搜索时，我决定采用廉价且快速的方法，使用 Microsoft Sql Server 的全文搜索引擎，而不是像 Lucene.Net 这样更强大的引擎。

不过，我想要的功能之一是谷歌式的相关文档片段。 我很快发现确定“相关”片段比我意识到的更困难。

我想根据找到的文本中的搜索词密度来选择片段。 所以，本质上，我需要找到文本中搜索词最密集的段落。 其中一个段落是任意数量的字符（比如 200——但这并不重要）。

我的第一个想法是在循环中使用 .IndexOf() 并构建一个术语距离数组（从先前找到的术语中减去找到的术语的索引），然后......什么？ 将任意两个、任意三个、任意四个、任意五个连续数组元素相加，并使用总和最小的元素（因此，搜索项之间的距离最小）。

这看起来很混乱。

有没有比我想出的更成熟、更好或更明显的方法来做到这一点？

Answer 1

尽管它是用 Java 实现的，但您可以在此处查看解决该问题的一种方法：
http://rcrezende.blogspot.com/2010/08 /smallest-relevant-text-snippet-for.html

Answer 2

我知道这条线已经很老了，但我上周尝试过，但感觉很痛苦。 这远非完美，但这就是我想出的。

代码片段生成器：

public static string SelectKeywordSnippets(string StringToSnip, string[] Keywords, int SnippetLength)
    {
        string snippedString = "";
        List<int> keywordLocations = new List<int>();

        //Get the locations of all keywords
        for (int i = 0; i < Keywords.Count(); i++)
            keywordLocations.AddRange(SharedTools.IndexOfAll(StringToSnip, Keywords[i], StringComparison.CurrentCultureIgnoreCase));

        //Sort locations
        keywordLocations.Sort();

        //Remove locations which are closer to each other than the SnippetLength
        if (keywordLocations.Count > 1)
        {
            bool found = true;
            while (found)
            {
                found = false;
                for (int i = keywordLocations.Count - 1; i > 0; i--)
                    if (keywordLocations[i] - keywordLocations[i - 1] < SnippetLength / 2)
                    {
                        keywordLocations[i - 1] = (keywordLocations[i] + keywordLocations[i - 1]) / 2;

                        keywordLocations.RemoveAt(i);

                        found = true;
                    }
            }
        }

        //Make the snippets
        if (keywordLocations.Count > 0 && keywordLocations[0] - SnippetLength / 2 > 0)
            snippedString = "... ";
        foreach (int i in keywordLocations)
        {
            int stringStart = Math.Max(0, i - SnippetLength / 2);
            int stringEnd = Math.Min(i + SnippetLength / 2, StringToSnip.Length);
            int stringLength = Math.Min(stringEnd - stringStart, StringToSnip.Length - stringStart);
            snippedString += StringToSnip.Substring(stringStart, stringLength);
            if (stringEnd < StringToSnip.Length) snippedString += " ... ";
            if (snippedString.Length > 200) break;
        }

        return snippedString;

    }

该函数将查找示例文本中所有关键字的索引，

 private static List<int> IndexOfAll(string haystack, string needle, StringComparison Comparison)
    {
        int pos;
        int offset = 0;
        int length = needle.Length;
        List<int> positions = new List<int>();
        while ((pos = haystack.IndexOf(needle, offset, Comparison)) != -1)
        {
            positions.Add(pos);
            offset = pos + length;
        }
        return positions;
    }

其执行有点笨拙。 它的工作方式是找到字符串中所有关键字的位置。 然后检查没有关键字彼此之间的距离比所需的片段长度更近，这样片段就不会重叠（这就是有点不确定的地方......）。 然后抓取以关键字位置为中心的所需长度的子字符串，并将整个内容缝合在一起。

我知道这已经晚了好几年了，但发布只是为了防止有人遇到这个问题。

Answer 3

public class Highlighter
{        
    private class Packet
    {
        public string Sentence;
        public double Density;
        public int Offset;
    }

    public static string FindSnippet(string text, string query, int maxLength)
    {
        if (maxLength < 0)
        {
            throw new ArgumentException("maxLength");
        }
        var words = query.Split(' ').Where(w => !string.IsNullOrWhiteSpace(w)).Select(word => word.ToLower()).ToLookup(s => s);             
        var sentences = text.Split('.');
        var i = 0;
        var packets = sentences.Select(sentence => new Packet 
        { 
            Sentence = sentence, 
            Density = ComputeDensity(words, sentence),
            Offset = i++
        }).OrderByDescending(packet => packet.Density);
        var list = new SortedList<int, string>();            
        int length = 0;                
        foreach (var packet in packets)
        {
            if (length >= maxLength || packet.Density == 0)
            {
                break;
            }
            string sentence = packet.Sentence;
            list.Add(packet.Offset, sentence.Substring(0, Math.Min(sentence.Length, maxLength - length)));
            length += packet.Sentence.Length;
        }
        var sb = new List<string>();
        int previous = -1;
        foreach (var item in list)
        {
            var offset = item.Key;
            var sentence = item.Value;
            if (previous != -1 && offset - previous != 1)
            {
                sb.Add(".");
            }
            previous = offset;             
            sb.Add(Highlight(sentence, words));                
        }
        return String.Join(".", sb);
    }

    private static string Highlight(string sentence, ILookup<string, string> words)
    {
        var sb = new List<string>();
        var ff = true;
        foreach (var word in sentence.Split(' '))
        {
            var token = word.ToLower();
            if (ff && words.Contains(token))
            {
                sb.Add("[[HIGHLIGHT]]");
                ff = !ff;
            }
            if (!ff && !string.IsNullOrWhiteSpace(token) && !words.Contains(token))
            {
                sb.Add("[[ENDHIGHLIGHT]]");
                ff = !ff;
            }
            sb.Add(word);
        }
        if (!ff)
        {
            sb.Add("[[ENDHIGHLIGHT]]");
        }
        return String.Join(" ", sb);
    }

    private static double ComputeDensity(ILookup<string, string> words, string sentence)
    {            
        if (string.IsNullOrEmpty(sentence) || words.Count == 0)
        {
            return 0;
        }
        int numerator = 0;
        int denominator = 0;
        foreach(var word in sentence.Split(' ').Select(w => w.ToLower()))
        {
            if (words.Contains(word))
            {
                numerator++;
            }
            denominator++;
        }
        if (denominator != 0)
        {
            return (double)numerator / denominator;
        }
        else
        {
            return 0;
        }
    }
}

例子：

highlight “光流被定义为图像中结构光的变化，例如由于眼球或相机与场景之间的相对运动而在视网膜或相机传感器上发生的变化。文献中的进一步定义强调了不同的属性光流”“光流”

输出：

[[HIGHLIGHT]] 光流 [[ENDHIGHLIGHT]] 被定义为结构的变化
图像中的光，e...文献中的进一步定义突出显示差异
[[HIGHLIGHT]] 光流 [[ENDHIGHLIGHT]] 的其他属性

Answer 4

好吧，这是我使用上面描述的算法制作的破解版本。 我不认为这一切都那么好。 它使用三个（数一下，三个！）循环一个数组和两个列表。 但是，好吧，有总比没有好。 我还硬编码了最大长度，而不是把它变成一个参数。

private static string FindRelevantSnippets(string infoText, string[] searchTerms)
    {
        List<int> termLocations = new List<int>();
        foreach (string term in searchTerms)
        {
            int termStart = infoText.IndexOf(term);
            while (termStart > 0)
            {
                termLocations.Add(termStart);
                termStart = infoText.IndexOf(term, termStart + 1);
            }
        }

        if (termLocations.Count == 0)
        {
            if (infoText.Length > 250)
                return infoText.Substring(0, 250);
            else
                return infoText;
        }

        termLocations.Sort();

        List<int> termDistances = new List<int>();
        for (int i = 0; i < termLocations.Count; i++)
        {
            if (i == 0)
            {
                termDistances.Add(0);
                continue;
            }
            termDistances.Add(termLocations[i] - termLocations[i - 1]);
        }

        int smallestSum = int.MaxValue;
        int smallestSumIndex = 0;
        for (int i = 0; i < termDistances.Count; i++)
        {
            int sum = termDistances.Skip(i).Take(5).Sum();
            if (sum < smallestSum)
            {
                smallestSum = sum;
                smallestSumIndex = i;
            }
        }
        int start = Math.Max(termLocations[smallestSumIndex] - 128, 0);
        int len = Math.Min(smallestSum, infoText.Length - start);
        len = Math.Min(len, 250);
        return infoText.Substring(start, len);
    }

我能想到的一些改进是返回多个长度较短的“片段”，加起来长度较长——这样可以对文档的多个部分进行采样。

Answer 5

这是一个很好的问题:)

我想我会创建一个索引向量：对于每个单词，创建一个条目 1 如果搜索词或其他 0 。然后找到 i 使得 sum(indexvector[i:i+maxlength]) 为最大化。

这实际上可以相当有效地完成。 从第一个 maxlength 单词中的搜索词数量开始。 然后，当您继续前进时，如果indexvector[i]=1（即，当您增加i时您将失去该搜索词），则减少计数器；如果indexvector[i+maxlength+1]=1，则增加计数器。 在此过程中，跟踪具有最高计数器值的 i。

一旦你得到了你最喜欢的 i，你仍然可以进行微调，比如看看你是否可以在不影响计数器的情况下减小实际大小，例如为了找到句子边界或其他什么。 或者就像从具有相同计数器值的多个 is 中选择正确的 i 一样。

不确定这是否是比你更好的方法 - 这是一种不同的方法。

您可能还想查看有关该主题的这篇论文，其中还有另一个基线：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4357&rep=rep1&type=pdf

Answer 6

我采取了另一种方法，也许它会对某人有所帮助...

首先，它会使用 IgnoreCase 搜索该单词是否出现在我的案例中（当然您自己可以更改它）。
然后，我在每个分隔符上创建一个正则表达式匹配列表，并搜索该单词的第一次出现（允许部分不区分大小写的匹配）。
从该索引中，我获得了该单词前后的 10 个匹配项，从而生成了该片段。

public static string GetSnippet(string text, string word)
{
    if (text.IndexOf(word, StringComparison.InvariantCultureIgnoreCase) == -1)
    {
        return "";
    }

    var matches = new Regex(@"\b(\S+)\s?", RegexOptions.Singleline | RegexOptions.Compiled).Matches(text);

    var p = -1;
    for (var i = 0; i < matches.Count; i++)
    {
        if (matches[i].Value.IndexOf(word, StringComparison.InvariantCultureIgnoreCase) != -1)
        {
            p = i;
            break;
        }
    }

    if (p == -1) return "";
    var snippet = "";
    for (var x = Math.Max(p - 10, 0); x < p + 10; x++)
    {
        snippet += matches[x].Value + " ";
    }
    return snippet;
}

Answer 7

如果你使用 CONTAINSTABLE 你会得到一个 RANK 返回，这本质上是一个密度值 - RANK 值越高，密度越高。 这样，您只需运行查询即可获取所需的结果，而不必在返回数据时对其进行修改。

Answer 8

刚才写了一个函数来做到这一点。 您要传入：

输入：

文档文本
这是您从中截取片段的文档的全文。 您很可能想要从此文档中删除任何 BBCode/HTML。

原始查询
用户输入的字符串作为搜索

代码段长度
您想要显示的片段的长度。

返回值：

从中获取片段的文档文本的起始索引。 要获取代码片段，只需执行 documentText.Substring(returnValue, snippetLength) 即可。 这样做的优点是您知道片段是否是从开始/结束/中间获取的，因此如果您愿意，您可以在片段开始/结束处添加一些装饰，例如 ... 。

性能

将分辨率设置为1将找到最佳片段，但一次会沿1个字符移动窗口。 将此值设置得较高可加快执行速度。

调整

您可以根据需要计算出分数。 在此示例中，我执行了 Math.pow(wordLength, 2) 以支持较长的单词。

private static int GetSnippetStartPoint(string documentText, string originalQuery, int snippetLength)
{
    // Normalise document text
    documentText = documentText.Trim();
    if (string.IsNullOrWhiteSpace(documentText)) return 0;

    // Return 0 if entire doc fits in snippet
    if (documentText.Length <= snippetLength) return 0;

    // Break query down into words
    var wordsInQuery = new HashSet<string>();
    {
        var queryWords = originalQuery.Split(' ');
        foreach (var word in queryWords)
        {
            var normalisedWord = word.Trim().ToLower();
            if (string.IsNullOrWhiteSpace(normalisedWord)) continue;
            if (wordsInQuery.Contains(normalisedWord)) continue;
            wordsInQuery.Add(normalisedWord);
        }
    }

    // Create moving window to get maximum trues
    var windowStart = 0;
    double maxScore = 0;
    var maxWindowStart = 0;

    // Higher number less accurate but faster
    const int resolution = 5;

    while (true)
    {
        var text = documentText.Substring(windowStart, snippetLength);

        // Get score of this chunk
        // This isn't perfect, as window moves in steps of resolution first and last words will be partial.
        // Could probably be improved to iterate words and not characters.
        var words = text.Split(' ').Select(c => c.Trim().ToLower());
        double score = 0;
        foreach (var word in words)
        {
            if (wordsInQuery.Contains(word))
            {
                // The longer the word, the more important.
                // Can simply replace with score += 1 for simpler model.
                score += Math.Pow(word.Length, 2);
            }                   
        }
        if (score > maxScore)
        {
            maxScore = score;
            maxWindowStart = windowStart;
        }

        // Setup next iteration
        windowStart += resolution;

        // Window end passed document end
        if (windowStart + snippetLength >= documentText.Length)
        {
            break;
        }
    }

    return maxWindowStart;
}

您还可以添加更多内容，例如，您可能不想比较确切的单词，而是尝试比较 SOUNDEX，其中您对 soundex 匹配的权重小于精确匹配的权重。