在开发我正在构建的网站的搜索功能时，我决定采用廉价快捷的方式，使用Microsoft Sql Server的全文搜索引擎，而不是像Lucene.Net这样更强大的工具。
然而，我想要实现类似于Google的相关文档片段的功能。我很快发现，确定“相关”片段比我预想的要困难。
我希望根据所找到的文本中搜索词的密度来选择片段。因此，本质上，我需要找到文本中搜索词最密集的部分。其中一段是任意数量的字符（比如200个字符 - 但实际上并不重要）。
我的第一个想法是在循环中使用.IndexOf()方法，并构建一个术语距离数组（从先前找到的项的索引中减去找到的项的索引），然后...然后呢？添加任意两个、任意三个、任意四个、任意五个连续的数组元素并使用具有最小和（因此，搜索词之间距离最小）的那个。
这看起来很混乱。
除了我提出的方法，是否有已经确定的、更好的或更明显的方法来完成这件事呢？
我知道这个帖子很老，但是上周我尝试了一下，结果非常麻烦。虽然这远非完美，但这就是我想出来的。
代码片段生成器：
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;
}
它的执行有点笨拙。它的工作方式是找到字符串中所有关键字的位置。然后检查没有关键字比所需的片段长度更接近彼此，以便片段不重叠（这就是它有点问题的地方...）。然后抓取关键字周围所需长度的子字符串，并将整个字符串拼接在一起。
我知道这已经晚了几年，但发帖只是为了帮助可能遇到这个问题的人。
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]]是指在眼球或相机与场景之间相对运动的情况下，图像中结构化光的变化，例如在视网膜或相机传感器上。来自文献的进一步定义强调了[[HIGHLIGHT]]光流[[ENDHIGHLIGHT]]的不同特性。
这是一个不错的问题 :)
我认为我会创建一个索引向量：对于每个单词，如果是搜索词则创建一个条目1，否则为0。然后找到i，使得sum（indexvector [i：i + maxlength]）最大化。
这实际上可以相当高效地完成。从第一个maxlength单词中的搜索术语数量开始。然后，随着您的移动，如果indexvector [i] = 1（即，您将要失去该搜索术语，因为您增加了i），则减少计数器，并在indexvector [i + maxlength +1] = 1时增加它。当您前进时，保持具有最高计数器值的i的跟踪。
一旦您得到了最喜欢的i，您仍然可以进行微调，例如查看是否可以缩小实际大小而不影响计数器，例如为了找到句子边界或其他内容。或者像从具有等效计数器值的多个i中选择正确的i一样。
不确定这是否比您的方法更好-这是另一种方法。
你可能还想查看这篇关于该主题的论文，其中包含另一个基准：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4357&rep=rep1&type=pdf
好的，这是我使用上述算法制作的拼凑版本。我认为它并不是很好。它使用了三个（数一数，三个！）循环、一个数组和两个列表。但是，嗯，总比没有强。我还将最大长度硬编码而不是将其转换为参数。
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);
}
我采取了另一种方法，也许会对某些人有所帮助...
首先，它使用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;
}
刚刚编写了一个函数来执行此操作。 您需要传入：
文本文档
这是您要从中获取片段的文档的完整文本。 最可能您希望从该文档中剥离掉任何BBCode / HTML。
原始查询
用户输入的搜索字符串
片段长度
您希望显示的片段长度。
从文档文本中获取片段的起始索引。 要获取片段，只需执行 documentText.Substring(returnValue, snippetLength)。 这有一个优点，即您可以知道片段是从开始/结束/中间获取的，因此如果希望在片段开头/结尾添加一些装饰符号，例如...，则可以这样做。
resolution设置为1意味着将每次沿着1个字符的窗口移动，以找到最佳片段。 将此值设置更高以加快执行速度。
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匹配的权重降低到低于精确匹配。