C # Поиск релевантных фрагментов документа для отображения результатов поиска
https://stackoverflow.com/questions/282002
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Разрабатывая поиск для сайта, который я создаю, я решил пойти дешевым и быстрым путем и использовать полнотекстовую поисковую систему Microsoft Sql Server вместо чего-то более надежного, такого как Lucene.Net.
Однако одна из функций, которую я хотел бы иметь, - это соответствующие фрагменты документов в стиле Google.Я быстро обнаружил, что определить "релевантные" фрагменты сложнее, чем я предполагал.
Я хочу выбирать фрагменты на основе плотности поисковых запросов в найденном тексте.Итак, по сути, мне нужно найти наиболее насыщенный поисковыми запросами отрывок в тексте.Где отрывок представляет собой некоторое произвольное количество символов (скажем, 200 - но на самом деле это не имеет значения).
Моя первая мысль - использовать .indexOf() в цикле и построить массив расстояний между терминами (затем вычтите индекс найденного термина из ранее найденного термина) ...что?Сложите любые два, любые три, любые четыре, любые пять последовательных элементов массива и используйте тот, у которого наименьшая сумма (следовательно, наименьшее расстояние между поисковыми терминами).
Это кажется грязным.
Есть ли устоявшийся, лучший или более очевидный способ сделать это, чем тот, который я придумал?
Решение
Хотя это реализовано в Java, вы можете увидеть один подход к этой проблеме здесь: http://rcrezende.blogspot.com/2010/08 /smallest-relevant-text-snippet-for.html
Другие советы
Я знаю, что этой ветке уже много лет, но я попробовал на прошлой неделе, и это была боль в задней части. Это далеко не идеально, но это то, что я придумал.
Генератор фрагментов:
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;
}
Это немного неуклюже в своем исполнении. Это работает путем поиска позиции всех ключевых слов в строке. Затем проверьте, что никакие ключевые слова не ближе друг к другу, чем желаемая длина фрагмента, чтобы фрагменты не перекрывались (вот где это немного ненадежно ...). А затем берет подстроки нужной длины, центрированные вокруг позиции ключевых слов, и сшивает все вместе.
Я знаю, что это на несколько лет позже, но публикация на всякий случай может помочь кому-нибудь натолкнуться на этот вопрос.
Это хорошая проблема:)
Я думаю, я бы создал индексный вектор: для каждого слова создайте запись 1, если поисковый термин или иначе 0. Затем найдите i такой, что сумма (indexvector [i: i + maxlength]) максимизируется.
На самом деле это можно сделать довольно эффективно. Начните с количества поисковых терминов в первых словах максимальной длины. затем, двигаясь дальше, уменьшите свой счетчик, если indexvector [i] = 1 (т.е. вы собираетесь потерять этот поисковый термин при увеличении i), и увеличьте его, если indexvector [i + maxlength + 1] = 1. На ходу следите за i с наибольшим значением счетчика.
Как только вы получили свой любимый i, вы все равно можете выполнить тонкую настройку, как, например, посмотреть, можете ли вы уменьшить реальный размер без ущерба для счетчика, например, чтобы найти границы предложения или что-то еще. Или как выбор правильного значения i из числа с эквивалентными значениями счетчика.
Не уверен, что это лучший подход, чем у вас, - он другой.
Возможно, вы также захотите ознакомиться с этим документом по этой теме, который содержит еще одну базовую информацию: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4357&rep=rep1&type=pdf
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]] Оптический поток [[ENDHIGHLIGHT]] определяется как изменение структурированного света в изображении, т.е...В дальнейшем определениями из литературы выделить различия различные свойства [[выделить]] оптического потока [[ENDHIGHLIGHT]]
Хорошо, вот взломанная версия, которую я сделал, используя алгоритм, описанный выше. Я не думаю, что это все так здорово. Он использует три (считайте их, три!) Цикла и два списка. Но это лучше, чем ничего. Я также жестко прописал максимальную длину вместо того, чтобы превращать ее в параметр.
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;
}
Если вы используете CONTAINSTABLE, вы получите RANK обратно, по сути это значение плотности - чем выше значение RANK, тем выше плотность. Таким образом, вы просто запускаете запрос, чтобы получить желаемые результаты, и вам не нужно выполнять массивацию данных при их возврате.
Написал функцию, чтобы сделать это только сейчас. Вы хотите пройти:
Входы:
Текст документа
Это полный текст документа, из которого вы берете фрагмент. Скорее всего, вы захотите удалить любой BBCode / HTML из этого документа.
Исходный запрос
Строка, введенная пользователем для поиска
Длина фрагмента
Длина фрагмента, который вы хотите отобразить.
Возвращаемое значение:
Начальный индекс текста документа, из которого будет взят фрагмент. Чтобы получить фрагмент, просто выполните documentText.Substring (returnValue, snippetLength) . Преимущество этого в том, что вы знаете, что фрагмент взят из начала / конца / середины, поэтому вы можете добавить некоторые украшения, например, ... , если хотите в начале / конце фрагмента.
Производительность
resolution , для которого установлено значение 1 , найдет лучший фрагмент , но перемещает окно на 1 символ за раз. Установите это значение выше, чтобы ускорить выполнение.
Tweaks
Вы можете работать Score так, как вы хотите. В этом примере я сделал 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 меньше, чем точное совпадение.
