C＃検索結果表示用の関連ドキュメントスニペットの検索

https://stackoverflow.com/questions/282002

08-07-2019
|

質問

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

ただし、私が持ちたい機能の1つは、Google風の関連ドキュメントスニペットです。私はすぐに「関連」を決定しました。スニペットは私が思ったよりも難しいです。

見つかったテキストの検索語密度に基づいてスニペットを選択したい。したがって、本質的には、テキスト内で最も検索語が密集している箇所を見つける必要があります。パッセージが任意の数の文字である場合（たとえば、200-しかし、それは本当に重要ではありません）。

最初に考えたのは、ループ内で.IndexOf（）を使用して用語距離の配列を構築することです（以前に見つかった用語から見つかった用語のインデックスを減算します）。任意の2、3、4、5のシーケンシャル配列要素を合計し、最小の合計（したがって、検索語間の最小距離）を持つ要素を使用します。

それは面倒そうです。

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

解決

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

他のヒント

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

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

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

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

これは何年も遅れていることは知っていますが、念のため投稿すると、誰かがこの質問に出くわすのに役立つかもしれません。

これはいい問題です：）

インデックスベクトルを作成すると思います。単語ごとに、検索語またはその他の場合は0のエントリ1を作成します。次に、sum（indexvector [i：i + maxlength]）が最大化されるiを見つけます。

これは実際にはかなり効率的に行うことができます。最初のmaxlengthワードのsearchtermsの数から始めます。次に、先に進むにつれて、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

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＆quot;光の流れは、画像内の構造化された光の変化として定義されます。眼球またはカメラとシーンの間の相対的な動きのために、網膜またはカメラのセンサー上で。文献からのさらなる定義は、オプティックフローの異なる特性を強調しています。＆quot;オプティカルフロー＆quot;

出力：

[[HIGHLIGHT]]オプティックフロー[[ENDHIGHLIGHT]]は、構造化の変化として定義されます画像内の光、e ...文献からのさらなる定義は差分を強調する [[HIGHLIGHT]]オプティックフロー[[ENDHIGHLIGHT]]のさまざまな特性

まあ、これは上で説明したアルゴリズムを使用して作成した、ハッキングされたバージョンです。それほど素晴らしいとは思いません。配列と2つのリストの3つのループ（カウントem、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);
    }

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

別のアプローチをとりました。おそらく誰かを助けるでしょう...

まず、IgnoreCaseを使用して、私のケースに単語が含まれているかどうかを検索します（もちろん、これを自分で変更します）。次に、各セパレータで正規表現の一致のリストを作成し、単語の最初の出現を検索します（大文字と小文字を区別しない部分一致を許可します）。そのインデックスから、単語の前後に10個の一致を取得し、スニペットを作成します。

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

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

今これを行う関数を書きました。渡したい：

入力：

ドキュメントテキスト
これは、スニペットを取得しているドキュメントの全文です。ほとんどの場合、このドキュメントからBBCode / HTMLを削除する必要があります。

元のクエリ
ユーザーが検索として入力した文字列

スニペットの長さ
表示するスニペットの長さ。

戻り値：

スニペットを取得するドキュメントテキストのインデックスを開始します。スニペットを取得するには、 documentText.Substring（returnValue、snippetLength）を実行します。これには、スニペットが開始/終了/中間から取得されるかどうかを知っているという利点があるため、スニペットの開始/終了で必要な場合は、 ... のような装飾を追加できます。

パフォーマンス

resolution を 1 に設定すると、最適なスニペットが見つかりますが、一度に1文字に沿ってウィンドウが移動します。実行を高速化するには、この値を高く設定します。

微調整

必要に応じてスコアを実行できます。この例では、 Math.pow（wordLength、2）を実行して、長い単語を優先しています。

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

これに追加できることはたくさんあります。たとえば、正確な単語を比較する代わりに、soundexの一致を完全一致よりも小さくする SOUNDEX を比較してみてください。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow