C # Ricerca di frammenti di documento rilevanti per la visualizzazione dei risultati della ricerca

Question

Nello sviluppo della ricerca di un sito che sto costruendo, ho deciso di andare nel modo più economico e rapido e utilizzare il motore di ricerca full text di Microsoft SQL Server invece di qualcosa di più robusto come Lucene.Net.

Una delle funzionalità che vorrei avere, tuttavia, è rappresentata dai frammenti di documenti pertinenti di Google. Ho rapidamente trovato determinante "pertinente" frammenti è più difficile di quanto pensassi.

Voglio scegliere frammenti in base alla densità dei termini di ricerca nel testo trovato. Quindi, essenzialmente, ho bisogno di trovare il termine più denso nel testo. Dove un passaggio è un numero arbitrario di personaggi (diciamo 200 - ma non importa davvero).

Il mio primo pensiero è di usare .IndexOf () in un ciclo e costruire un array di distanze di termini (sottrarre l'indice del termine trovato dal termine trovato in precedenza), quindi ... cosa? Aggiungi due, tre, quattro, cinque, cinque elementi di array sequenziali e usa quello con la somma più piccola (quindi, la distanza più piccola tra i termini di ricerca).

Sembra disordinato.

Esiste un modo stabilito, migliore o più ovvio per farlo rispetto a quello che ho escogitato?

Answer 1

Sebbene sia implementato in Java, puoi vedere un approccio per quel problema qui: http://rcrezende.blogspot.com/2010/08 /smallest-relevant-text-snippet-for.html

Answer 2

So che questo thread è molto vecchio, ma ho provato questa settimana scorsa ed è stato un dolore nella parte posteriore. Questo è tutt'altro che perfetto, ma questo è quello che mi è venuto in mente.

Il generatore di snippet:

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;

    }

La funzione che troverà l'indice di tutte le parole chiave nel testo di esempio

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

È un po 'goffo nella sua esecuzione. Il modo in cui funziona è trovare la posizione di tutte le parole chiave nella stringa. Quindi verificando che nessuna parola chiave sia più vicina tra loro della lunghezza dello snippet desiderata, in modo che gli snippet non si sovrappongano (è lì che è un po 'incerto ...). Quindi afferra sottostringhe della lunghezza desiderata centrata attorno alla posizione delle parole chiave e ricama il tutto insieme.

So che è in ritardo di anni, ma la pubblicazione nel caso in cui potrebbe aiutare qualcuno a trovare questa domanda.

Answer 3

Questo è un bel problema :)

Penso che creerei un vettore indice: per ogni parola, creare una voce 1 se il termine di ricerca o altrimenti 0. Quindi trovare i tale che la somma (indexvector [i: i + maxlength]) sia massimizzata.

Questo può effettivamente essere fatto in modo piuttosto efficiente. Inizia con il numero di termini di ricerca nelle prime parole di massima lunghezza. quindi, mentre vai avanti, diminuisci il tuo contatore se indexvector [i] = 1 (ovvero stai per perdere quel termine di ricerca mentre aumenti i) e aumentalo se indexvector [i + maxlength + 1] = 1. Mentre procedi, tieni traccia dell'i con il valore del contatore più alto.

Una volta ottenuto il tuo preferito i, puoi ancora fare la messa a punto come vedere se riesci a ridurre le dimensioni effettive senza compromettere il tuo contatore, ad es. per trovare limiti di frase o altro. O come scegliere l'i giusto di un numero di è con valori contatore equivalenti.

Non sono sicuro che si tratti di un approccio migliore del tuo - è diverso.

Potresti anche voler dare un'occhiata a questo documento sull'argomento, che viene fornito con l'ennesima baseline: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4357&rep=rep1&type=pdf

Answer 4

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

Esempio:

  

evidenzia " Il flusso ottico è definito come il cambiamento di luce strutturata nell'immagine, ad es. sulla retina o sul sensore della fotocamera, a causa di un movimento relativo tra il bulbo oculare o la fotocamera e la scena. Ulteriori definizioni dalla letteratura evidenziano diverse proprietà del flusso ottico " "flusso ottico"

Output:

[[HIGHLIGHT]] Il flusso ottico [[ENDHIGHTLIGHT]] è definito come il cambiamento di strutturato  luce nell'immagine, e ... Ulteriori definizioni dalla letteratura evidenziano diff proprietà attuali di [[HIGHLIGHT]] flusso ottico [[ENDHIGHTLIGHT]]

Answer 5

Bene, ecco la versione di hacking insieme che ho creato usando l'algoritmo che ho descritto sopra. Non penso sia così eccezionale. Usa tre loop (count em, three!) Un array e due liste. Ma, beh, è ??meglio di niente. Ho anche codificato la lunghezza massima invece di trasformarla in un parametro.

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

Alcuni miglioramenti che mi vengono in mente potrebbero essere la restituzione di più "frammenti". con una lunghezza inferiore che si aggiunge alla lunghezza più lunga, in questo modo è possibile campionare più parti del documento.

Answer 6

Ho adottato un altro approccio, forse aiuterà qualcuno ...

Per prima cosa cerca se nel mio caso appare la parola con IgnoreCase (tu lo cambi ovviamente tu stesso). Quindi creo un elenco di corrispondenze Regex su ciascun separatore e cerco la prima occorrenza della parola (consentendo corrispondenze senza distinzione tra maiuscole e minuscole). Da quell'indice, ottengo le 10 partite davanti e dietro la parola, il che rende lo snippet.

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

Se usi CONTAINSTABLE otterrai un RANK, questo è essenzialmente un valore di densità - più alto è il valore RANK, maggiore è la densità. In questo modo, è sufficiente eseguire una query per ottenere i risultati desiderati e non è necessario che i risultati vengano massaggiati al momento della loro restituzione.

Answer 8

Ha scritto una funzione per farlo proprio ora. Vuoi passare:

Ingressi:

Testo del documento
Questo è il testo completo del documento da cui stai prendendo uno snippet. Molto probabilmente vorrai eliminare qualsiasi BBCode / HTML da questo documento.

Query originale
La stringa immessa dall'utente come ricerca

Lunghezza frammento
Lunghezza dello snippet che desideri visualizzare.

Valore restituito:

Avvia l'indice del testo del documento da cui estrarre lo snippet. Per ottenere lo snippet è sufficiente fare documentText.Substring (returnValue, snippetLength) . Questo ha il vantaggio di sapere se lo snippet è preso dall'inizio / fine / medio, quindi puoi aggiungere qualche decorazione come ... se desideri all'inizio / fine dello snippet.

Prestazioni

Una risoluzione impostata su 1 troverà lo snippet migliore ma sposta la finestra di 1 carattere alla volta. Imposta questo valore su un valore più alto per accelerare l'esecuzione.

Tweaks

Puoi calcolare il score come vuoi. In questo esempio ho fatto Math.pow (wordLength, 2) per favorire parole più lunghe.

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

Molte altre cose che puoi aggiungere a questo, ad esempio invece di confrontare parole esatte, forse potresti provare a confrontare il SOUNDEX dove pesi soundex corrisponde a meno di corrispondenze esatte.