2

キーワードのリストとそれらを検索するテキストがあります。テキスト内で見つかった各キーワードの開始インデックスを取得する必要があり、一致は正確でなければなりません。例えば：

keywords=>cat,dog
text=> a catchy cat with a dogged dog

ここでは、'cat' と 'dog' のみを一致させますが、インデックスとの一致を返す必要があり、'catchy' や 'dogged' などの単語と一致させることはできません。

文字列の一致に Aho-Corasick Algorithm を試してみましたが、「キャッチー」と「ドッグジッド」にも一致します。キーワードを完全に一致させ、c# を使用してテキスト内のインデックス位置を返すにはどうすればよいですか?

4

4 に答える 4

1

Aho-Corasick Algorithm を使用して少し変更できます。すべてのキーワードについて、各キーワードの末尾に単語区切り文字 (スペース、ドット、改行など) を追加します。

したがって、m 個のキーワードがあり、テキストに n 種類のセパレータがある場合、n*m 個の単語からトライ ツリーを作成します。

セパレーターを追加した後、サンプルケースでは「キャッチー」と「ドッグ」に一致しません。

編集：

まず、AC アルゴリズムを理解しておく必要があります。

例：

キーワード=>猫、犬、テキスト=>キャッチーな猫と犬の犬

キーワードが変更されました =>'cat ','dog ', 'cat\n', 'dog\n' (スペースと改行区切りを追加するだけです)

変更されたテキスト=>「犬のようなキャッチーな猫\n」

次に、すべてのキーワードの各インデックスを検索する文字列に、標準の Aho-Corasick アルゴリズムを使用できます。

テキストの長さが n で、キーワードの合計の長さが m であると仮定すると、Aho-Corasick アルゴリズムの複雑さは O(n+m) であり、大きなテキストと大きなキーワード セットには十分です。

于 2013-10-24T11:16:42.207 に答える
0

以下の関数が各キーワードのインデックスのリストを返すことを願っています。

private List<int> GetIndexForKeyWord(string content,string key)
{
    int index = 0;
    List<int> indexes=new List<int>();
    while (index < content.Length && index >= 0)
    {
        index = content.IndexOf(key, index);
        if (index+key.Length==content.Length||index >= 0 && !char.IsLetter(content[index + key.Length]))
        {
            indexes.Add(index);
        }
        if(index!=-1)
            index++;
    }
    return indexes;
}
于 2013-10-24T11:21:12.803 に答える