10

私が構築しているサイトの検索を開発する際に、Lucene.Net のようなより堅牢なものではなく、Microsoft Sql Server の全文検索エンジンを使用することにしました。

私が欲しい機能の 1 つは、Google 風の関連ドキュメント スニペットです。「関連性の高い」スニペットを特定することは、思ったより難しいことにすぐに気付きました。

見つかったテキストの検索語密度に基づいてスニペットを選択したいと考えています。したがって、基本的には、テキスト内で最も検索用語が密集している箇所を見つける必要があります。パッセージは任意の数の文字です (たとえば 200 文字ですが、実際には問題ではありません)。

私の最初の考えは、ループで .IndexOf() を使用し、用語の距離の配列を作成することです (以前に見つかった用語から見つかった用語のインデックスを減算します)。任意の 2 つ、任意の 3 つ、任意の 4 つ、任意の 5 つの連続する配列要素を合計し、合計が最小の要素を使用します (したがって、検索語間の距離が最小になります)。

それは厄介なようです。

私が思いついた方法よりも、これを行うための確立された、より良い、またはより明白な方法はありますか?

4

8 に答える 8

6

これは Java で実装されていますが、この問題に対する 1 つのアプローチをここで見ることができます: http://rcrezende.blogspot.com/2010/08/smallest-relevant-text-snippet-for.html

于 2010-08-11T21:28:53.790 に答える
4

このスレッドがかなり古いことは知っていますが、先週試してみましたが、裏側が痛かったです。これは完璧にはほど遠いですが、これが私が思いついたものです。

スニペット ジェネレーター:

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

その実行には少し不器用です。それが機能する方法は、文字列内のすべてのキーワードの位置を見つけることです。次に、スニペットが重複しないように、目的のスニペットの長さよりも互いに近いキーワードがないことを確認します (これは少し不確実なところです...)。次に、キーワードの位置を中心に目的の長さの部分文字列を取得し、全体をつなぎ合わせます。

私はこれが何年も遅れていることを知っていますが、誰かがこの質問に出くわすのに役立つかもしれない場合に備えて投稿してください.

于 2011-06-24T01:46:09.070 に答える
2 
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]] は、画像内の構造化された光の変化として定義されます。[[HIGHLIGHT]] オプティック フロー [[ENDHIGHLIGHT]] のさまざまな特性を強調する文献からのさらなる定義

于 2013-09-14T00:33:43.497 に答える
1

さて、これが、上で説明したアルゴリズムを使用して作成したハッキン​​グされたバージョンです。私はそれがすべて素晴らしいとは思いません。配列と 2 つのリストを 3 つ (数えて、3 つ!) ループします。でもまあ、何もないよりはマシです。また、最大長をパラメーターに変換するのではなく、ハードコーディングしました。

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

私が考えることができるいくつかの改善は、より長い長さになる短い長さの複数の「スニペット」を返すことです。このようにして、ドキュメントの複数の部分をサンプリングできます。

于 2008-11-12T14:25:02.893 に答える
1

これはいい問題です:)

インデックス ベクトルを作成すると思います。単語ごとに、検索語の場合は 1、それ以外の場合は 0 のエントリを作成します。次に、sum(indexvector[i:i+maxlength]) が最大化されるような 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

于 2010-07-27T17:41:03.990 に答える
0

CONTAINSTABLEを使用すると、RANKが返されます。これは、本質的に密度値です。RANK値が高いほど、密度が高くなります。このように、クエリを実行して必要な結果を取得するだけで、データが返されたときにデータをマッサージする必要はありません。

于 2008-12-10T09:43:35.220 に答える