C # Encontrar trechos de documentos relevantes para a apresentação de resultados de pesquisa

Question

No desenvolvimento de pesquisa para um site que estou construindo, eu decidi ir para o mais barato e maneira rápida e usar texto Motor de busca completa do Microsoft SQL Server em vez de algo mais robusto como Lucene.Net.

Uma das características que eu gostaria de ter, porém, é google-esque trechos de documentos relevantes. Eu encontrei rapidamente determinar trechos "relevantes" é mais difícil do que eu imaginava.

Eu quero escolher trechos com base na densidade termo de pesquisa no texto encontrado. Então, basicamente, eu preciso encontrar o mais passagem densa termo de pesquisa no texto. Quando uma passagem é algum número arbitrário de caracteres (digamos 200 - mas realmente não importa).

Meu primeiro pensamento é usar .IndexOf () em um loop e construir uma matriz de distâncias prazo (subtrair o índice do termo encontrado a partir do termo anteriormente encontrado), então ... o quê? Adicionar-se quaisquer dois, três qualquer, qualquer quatro, cinco, quaisquer elementos da matriz sequenciais e usar a um com a menor soma (portanto, a menor distância entre os termos de pesquisa).

Isso parece confuso.

Existe uma melhor, ou forma estabelecida, mais óbvia de fazer isso do que o que eu tenho chegar a?

Answer 1

Embora ele é implementado em Java, você pode ver uma abordagem para o problema aqui: http://rcrezende.blogspot.com/2010/08 /smallest-relevant-text-snippet-for.html

Answer 2

Eu sei que esta discussão é velha maneira, mas eu dei isto uma tentativa na semana passada e foi uma dor no lado de trás. Isto está longe de ser perfeito, mas é isso que eu vim acima com.

O gerador trecho:

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;

    }

A função que irá encontrar o índice de todas as palavras-chave no texto de exemplo

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

É um desajeitado pouco na sua execução. O modo como funciona é encontrar a posição de todas as palavras-chave na cadeia. Em seguida, verificar se há palavras-chave são mais próximas entre si do que o comprimento trecho desejado, de modo que trechos não vai sobreposição (que é onde ele é um pouco duvidoso ...). E então pega substrings de comprimento desejado centrado em torno da posição das palavras-chave e pontos a coisa toda em conjunto.

Eu sei que isso é anos de atraso, mas postagem apenas no caso que pode ajudar alguém entrar em toda esta questão.

Answer 3

Este é um problema bom:)

Eu acho que criar um vetor de índice: Para cada palavra, criar uma entrada de 1 se termo de pesquisa ou caso contrário, 0. Em seguida, localize o i tal que soma (indexvector [i: i + maxlength]) é maximizada.

Isso pode realmente ser feito, em vez de forma eficiente. Comece com o número de searchterms nas primeiras palavras maxlength. então, como você seguir em frente, diminuir o seu contador se indexvector [i] = 1 (ou seja, o seu ponto de perder esse termo de pesquisa à medida que aumenta i) e aumentá-la se indexvector [i + maxlength + 1] = 1. Como você vai, faixa de manter o i com o maior valor do contador.

Uma vez que você tem o seu i favorito, você pode ainda fazer ajustes finos como ver se você pode reduzir o tamanho real sem comprometer seu contador, por exemplo, a fim de encontrar limites da frase ou qualquer outra coisa. Ou como escolher o i direito de um número de é com valores de contador equivalentes.

Não sei se isso é uma abordagem melhor do que o seu. - É um diferente

Você também pode querer verificar para fora este artigo sobre o tema, que vem com ainda sem outra linha de base: 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;
        }
    }
}

Exemplo:

destaque "fluxo óptico é definido como a mudança de luz estruturada na imagem, por exemplo, sobre a retina ou sensor da câmera, devido a um movimento relativo entre o globo ocular ou câmera ea cena. Outras definições da literatura destacar propriedades diferentes de fluxo óptico" 'fluxo óptico'

Output:

[[REALCE]] fluxo óptico [[ENDHIGHLIGHT]] é definida como a mudança de estruturada a luz da imagem, e ... Outras definições do diff literatura destaque Propriedades erent de [[REALCE]] fluxo óptico [[ENDHIGHLIGHT]]

Answer 5

Bem, aqui está a versão hackeada juntos que eu fiz usando o algoritmo que eu descrevi acima. Eu não acho que isso é tudo o que ótimo. Ele usa três (contagem em, três!) Loops de uma matriz e duas listas. Mas, bem, é melhor do que nada. Eu também codificado o comprimento máximo em vez de transformá-lo em um 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);
    }

Algumas melhorias que eu poderia pensar seria para retornar vários "snippets" com um comprimento mais curto que somar o maior comprimento -. Desta forma várias partes do documento podem ser amostrados

Answer 6

Eu levei uma outra abordagem, talvez ele vai ajudar alguém ...

Primeiro ele procura se ele aparecer palavra no meu caso com IgnoreCase (você mudar isso, claro, você mesmo). Então eu criar uma lista de partidas Regex em cada separadores e procurar a primeira ocorrência da palavra (permitindo caso parcial partidas insensíveis). A partir desse índice, fico com os 10 partidas na frente e por trás da palavra, o que torna o trecho.

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 você usa CONTAINSTABLE você receberá uma volta RANK, isto é, em essência, um valor de densidade - quanto maior o valor de classificação, maior a densidade. Desta forma, você acabou de executar uma consulta para obter os resultados que você quer e não tem que resultar em massageando os dados quando o seu devolvidos.

Answer 8

escreveu uma função para fazer isso agora. Você quer passar em:

Entradas:

Texto do documento
Este é o texto completo do documento que você está tomando um trecho. Muito provavelmente você vai querer retirar qualquer BBCode / HTML a partir deste documento.

consulta Original
A cadeia de caracteres que o usuário entrou como sua pesquisa

comprimento de trechos
Comprimento do trecho que você deseja exibir.

Valor de retorno:

índice inicial do texto do documento para levar o trecho. Para obter o trecho simplesmente fazer documentText.Substring(returnValue, snippetLength). Isto tem a vantagem de que você sabe se o trecho é tomar a partir do início / fim / meio para que você pode adicionar alguma decoração como ... se desejar no trecho de início / fim.

Desempenho

Um conjunto resolution para 1 irá encontrar o melhor trecho , mas move a janela junto 1 caractere de cada vez. Definir esse valor mais alto para acelerar a execução.

Ajustes

Você pode trabalhar score como quiser. Neste exemplo eu fiz Math.pow(wordLength, 2) para favorecer palavras mais longas.

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

Muito mais você pode acrescentar a isto, por exemplo, em vez de comparar palavras exatas, talvez, você pode querer tentar comparar o SOUNDEX onde partidas peso soundex menos de correspondências exatas.