c# - para - metadescripciones

C#Encontrar fragmentos de documentos relevantes para la visualización de resultados de búsqueda

Question

Al desarrollar la búsqueda de un sitio que estoy construyendo, decidí ir de una manera barata y rápida y utilizar el motor de búsqueda de texto completo del servidor Microsoft Sql en lugar de utilizar algo más sólido como Lucene.Net.

Una de las características que me gustaría tener, sin embargo, son los fragmentos de documentos relevantes de google-esque. Rápidamente descubrí que la determinación de fragmentos "relevantes" es más difícil de lo que creía.

Quiero elegir fragmentos basados ​​en la densidad del término de búsqueda en el texto encontrado. Entonces, esencialmente, necesito encontrar el pasaje más denso del término de búsqueda en el texto. Donde un pasaje es una cantidad arbitraria de caracteres (digamos 200, pero realmente no importa).

Mi primer pensamiento es usar .IndexOf () en un bucle y construir una matriz de distancias de términos (restar el índice del término encontrado del término encontrado previamente), entonces ... ¿qué? Agregue dos, tres, cuatro o cinco elementos de matriz secuencial y utilice el que tenga la suma más pequeña (por lo tanto, la distancia más pequeña entre los términos de búsqueda).

Eso parece desordenado.

¿Existe una manera establecida, mejor o más obvia de hacer esto que lo que se me ocurrió?

Answer 1

Bueno, aquí está la versión pirateada que hice usando el algoritmo que describí arriba. No creo que sea tan genial. Utiliza tres (¡cuenta em, tres!) Bucles una matriz y dos listas. Pero, bueno, es mejor que nada. También codifiqué la longitud máxima en lugar de convertirla en un parámetro.

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

Algunas mejoras que podría pensar serían devolver varios "fragmentos" con una longitud más corta que se suman a la longitud más larga, de esta manera se pueden muestrear varias partes del documento.

Answer 2

Si usa CONTAINSTABLE obtendrá un RANGO, este es esencialmente un valor de densidad, cuanto mayor sea el valor de RANK, mayor será la densidad. De esta manera, solo ejecuta una consulta para obtener los resultados que desea y no tiene que dar como resultado el masaje de los datos cuando se devuelve.

Answer 3

Este es un lindo problema :)

Creo que crearía un vector de índice: para cada palabra, cree una entrada 1 si es un término de búsqueda o de otra manera 0. Luego encuentre el i tal que la suma (vector de índice [i: i + maxlength]) se maximice.

Esto realmente se puede hacer de manera bastante eficiente. Comience con el número de términos de búsqueda en las primeras palabras de longitud máxima. luego, a medida que avanza, disminuya su contador si indexvector [i] = 1 (es decir, está a punto de perder ese término de búsqueda a medida que aumenta i) y aumente si el vector de índice [i + maxlength + 1] = 1. A medida que avanza, realice un seguimiento de la i con el valor de contador más alto.

Una vez que haya obtenido su i favorito, puede seguir afinando, como ver si puede reducir el tamaño real sin comprometer su contador, por ejemplo, para encontrar límites de oraciones o lo que sea. O como elegir el derecho i de cierto número con valores de contador equivalentes.

No estoy seguro si este es un enfoque mejor que el tuyo, es diferente.

También es posible que desee consultar este documento sobre el tema, que viene con otra base: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4357&rep=rep1&type=pdf

Answer 4

A pesar de que se implementa en Java, puede ver un enfoque para ese problema aquí: http://rcrezende.blogspot.com/2010/08/spanish-relevant-text-snippet-for.html

Answer 5

Sé que este hilo es muy antiguo, pero lo probé la semana pasada y fue un dolor en la parte posterior. Esto está lejos de ser perfecto, pero esto es lo que se me ocurrió.

El generador de fragmentos:

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 función que encontrará el índice de todas las palabras clave en el texto de muestra

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

Es un poco torpe en su ejecución. La forma en que funciona es encontrar la posición de todas las palabras clave en la cadena. Luego, verifica que no haya palabras clave más cercanas entre sí que la longitud del fragmento deseado, para que los fragmentos no se superpongan (es por eso que es un poco dudoso ...). Y luego toma subcadenas de la longitud deseada centradas alrededor de la posición de las palabras clave y las une todo.

Sé que esto es años tarde, pero publicando solo en caso de que pueda ayudar a alguien a encontrar esta pregunta.

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

Ejemplo:

"El flujo óptico se define como el cambio de luz estructurada en la imagen, por ejemplo, en la retina o el sensor de la cámara, debido a un movimiento relativo entre el globo ocular o la cámara y la escena. Otras definiciones de la literatura resaltan diferentes propiedades del flujo óptico "flujo óptico"

Salida:

[[HIGHLIGHT]] Flujo óptico [[ENDHIGHLIGHT]] se define como el cambio de luz estructurada en la imagen, e ... Otras definiciones de la literatura resaltan las diferentes propiedades de [[HIGHLIGHT]] flujo óptico [[ENDHIGHLIGHT]]

Answer 7

Escribió una función para hacer esto ahora. Quieres pasar:

Insumos:

Texto del documento
Este es el texto completo del documento del que está sacando un fragmento. Lo más probable es que desee quitar cualquier BBCode / HTML de este documento.

Consulta original
La cadena que el usuario ingresó como su búsqueda

Longitud de fragmento
Longitud del fragmento que desea visualizar.

Valor de retorno:

Inicie el índice del texto del documento para tomar el fragmento. Para obtener el fragmento simplemente haga documentText.Substring(returnValue, snippetLength) . Esto tiene la ventaja de que usted sabe si el fragmento se toma desde el inicio / final / medio para que pueda agregar algo de decoración como ... si lo desea en el inicio / final del fragmento.

Actuación

Una resolution establecida en 1 encontrará el mejor fragmento pero moverá la ventana a lo largo de 1 char a la vez. Establezca este valor más alto para acelerar la ejecución.

Ajustes

Puedes calcular tu score como quieras. En este ejemplo he hecho Math.pow(wordLength, 2) para favorecer palabras más largas.

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

Puede agregar muchas más SOUNDEX a esto, por ejemplo, en lugar de comparar palabras exactas, quizás le SOUNDEX comparar el SOUNDEX donde pesa soundex y que no coincide con las coincidencias exactas.