C# Znajdowanie odpowiednich fragmentów dokumentów do wyświetlania wyników wyszukiwania

Question

Szukając witryny, którą buduję, zdecydowałem się przejść tanią i szybką drogę i użyć silnika wyszukiwania Microsoft SQL Server zamiast czegoś bardziej niezawodnego, takiego jak Lucene.Net.

Jedną z funkcji, które chciałbym mieć, są fragmenty dokumentów dotyczące google-esque. Szybko stwierdziłem, że określenie "istotnych" fragmentów jest trudniejsze, niż sobie uświadomiłem.

Chcę wybrać fragmenty na podstawie gęstości wyszukiwanego hasła w znalezionym tekście. Tak więc, w zasadzie, muszę znaleźć w tekście najbardziej poszukiwany termin gęsty. Gdzie fragment jest dowolną liczbą znaków (powiedzmy 200 - ale to naprawdę nie ma znaczenia).

Moją pierwszą myślą jest użyć .IndexOf() w pętli i zbudować tablicę odległości (odjąć indeks znalezionego terminu od poprzednio znalezionego terminu), a następnie ... co? Dodaj dowolne dwa, dowolne trzy, dowolne cztery, dowolne pięć, kolejne elementy tablicy i użyj tego z najmniejszą sumą (stąd najmniejsza odległość między wyszukiwanymi terminami).

To wydaje się nieporządne.

Czy istnieje ustalony, lepszy lub bardziej oczywisty sposób na zrobienie tego niż to, co wymyśliłem?

Answer 1

Chociaż jest zaimplementowana w języku Java, można zobaczyć jedno podejście do tego problemu tutaj: http://rcrezende.blogspot.com/2010/08/smallest-relevant-text-snippet-for.html

Answer 2

Oto zhakowana wersja, którą zrobiłem przy użyciu algorytmu opisanego powyżej. Nie sądzę, że to wszystko jest wspaniałe. Używa trzech (count em, three!) Pętli tablicy i dwóch list. Ale cóż, to lepsze niż nic. Również zakodowałem maksymalną długość zamiast zamienić ją w parametr.

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

Niektóre ulepszenia mogłem pomyśleć byłoby powrócić wiele „fragmentów” o krótszej długości, które sumują się do dłuższej długości - ten sposób wiele części dokumentu mogą być próbą.

Answer 3

Jeśli użyjesz CONTAINSTABLE, otrzymasz RANK z powrotem, jest to w istocie wartość gęstości - im wyższa wartość RANK, tym wyższa gęstość. W ten sposób wystarczy uruchomić kwerendę, aby uzyskać pożądane wyniki i nie trzeba wykonywać masowania danych po ich zwróceniu.

Answer 4

Jest to miłe problemem :)

myślę, że tworzą wektor index: Dla każdego słowa, utworzyć wpis 1, jeżeli szukany termin lub inaczej 0. Następnie znajdź I takie, że suma (indexvector [ i: i + maxlength]) jest zmaksymalizowany.

Można to zrobić dość sprawnie. Zacznij od liczby wyszukiwań w pierwszych słowach o maksymalnej długości. następnie, gdy będziesz poruszał się, zmniejsz swój licznik, jeśli indexvector [i] = 1 (tzn. stracisz ten termin wyszukiwania w miarę wzrostu i) i zwiększ go, jeśli indexvector [i + maxlength + 1] = 1. Kiedy jedziesz, śledź i o najwyższej wartości licznika.

Po uzyskaniu ulubionego elementu i, można nadal robić finetuning, jak sprawdzić, czy można zmniejszyć rzeczywisty rozmiar bez narażania swojego licznika, np. w celu znalezienia granic zdań lub cokolwiek innego. Lub jak wybranie prawej i liczby jest z odpowiednimi wartościami licznika.

Nie jestem pewien, czy to jest lepsze podejście od twojego - to jest inne.

Warto również sprawdzić ten dokument na ten temat, która pochodzi z przecie innym bazowej: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4357&rep=rep1&type=pdf

Answer 5

Wiem, że ten wątek jest bardzo stary, ale spróbowałem w zeszłym tygodniu i był to problem z tyłu. To daleki od doskonałości, ale właśnie to wymyśliłem.

Generator urywek:

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; 

    } 

Funkcja który znajdzie indeks wszystkich słów kluczowych w tekście próbki

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

To trochę niezdarny w jego realizacji. Sposób działania polega na znalezieniu pozycji wszystkich słów kluczowych w łańcuchu. Następnie sprawdź, czy żadne słowa kluczowe nie są sobie bliższe niż żądana długość fragmentu, więc fragmenty nie będą się nakładać (to tam jest trochę niepewnie ...). A następnie chwyta podciągi o pożądanej długości, skupione wokół pozycji słów kluczowych i łączy wszystko razem.

Wiem, że to spóźnia się o wiele lat, ale zamieszczam na wszelki wypadek, może to pomóc komuś przejść przez to pytanie.

Answer 6

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

przykład:

Highlight „przepływ optyczna jest określona jako zmiany strukturalnej światło w obrazie, na przykład w siatkówce lub czujnik aparatu, w wyniku względnego ruchu pomiędzy gałki ocznej lub aparatu . a scena Kolejne definicje z literatury wyróżnić różne właściwości przepływu nerwu”«przepływu nerwu»

wyjściowa:

[[HIGHLIGHT]] Strumień optyczny [[ENDHIGHLIGHT]] jest zdefiniowany jako zmiana strukturyzowanego światła na obrazie, e ... Dalsze definicje z literatury wskazują, że różnice w przepływie optycznym [[HIGHLIGHT]] [[ ENDHIGHIGHT]]

Answer 7

Napisano funkcję, aby zrobić to właśnie teraz. Chcesz przekazać w:

wejść:

tekst dokumentu
Jest to pełny tekst dokumentu ty bierzesz fragment z. Najprawdopodobniej z tego dokumentu chcesz usunąć dowolny kod BBCode/HTML.

zapytanie Original
Ciąg użytkownik wszedł jako poszukiwaniu

długości

Snippet
Długość fragmentu, który chcesz wyświetlić.

Wartość zwracana: indeks

Początek tekstu dokumentu wziąć fragment z.Aby uzyskać krótki opis, po prostu wykonaj documentText.Substring(returnValue, snippetLength). Ma to tę zaletę, że wiesz, czy fragment jest pobierany od początku/końca/środka, aby dodać trochę dekoracji, np. ..., jeśli chcesz na początku/końcu snippet.

Wydajność

resolution zestaw do 1znajdzie najlepszy fragment ale przesuwa okno po 1 char naraz. Ustaw wyższą wartość, aby przyspieszyć wykonanie.

Wariacje

Możesz poćwiczyć score jednak chcesz. W tym przykładzie zrobiłem Math.pow(wordLength, 2), aby faworyzować dłuższe słowa.

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

Dużo więcej można dodać do tego, na przykład zamiast porównując dokładnych słów, być może chcesz spróbować porównując SOUNDEX gdzie waga Soundex mecze mniej niż dokładnych dopasowań.