2

我有一个关键字列表和一个要搜索的文本。我需要获取文本中每个找到的关键字的起始索引，并且匹配必须准确。例如：

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

此处虽然只匹配 'cat' 和 'dog' 必须返回与索引匹配，并且匹配不应与诸如 'catchy' 和 'dogged' 之类的词匹配

我尝试过使用Aho-Corasick 算法进行字符串匹配，但它也匹配 'catchy' 和 'dogged'。如何使用 c# 对关键字进行精确匹配并返回文本中的索引位置

4

4 回答 4

3

使用带边界的正则表达式..

var results= keywords.Select(x=>
                               new
                               {
                                word=x,
                                indexes=Regex.Matches(input,@"\b"+x+@"\b")
                                             .Cast<Match>().Select(y=>y.Index)
                                             .ToList()    
                               }
                            );

您现在可以迭代结果

foreach(var match in results)
{
    match.word;
    foreach(int index in match.indexes)//index
}
于 2013-10-24T10:36:22.860 回答
1

您可以使用 Aho-Corasick 算法进行一些修改。对于所有关键字，在每个关键字的末尾附加单词分隔符（如空格、点、换行符等）。

因此，如果您有 m 个关键字并且文本有 n 种分隔符，您将从 n*m 个单词构建 trie 树。

附加分隔符后，它将与您的示例案例中的“catchy”和“dogged”不匹配。

编辑：

首先你最好对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 回答
0

按单词拆分文本并将所有单词推入Dictionary<word, index>并查找每个关键字的字典。

于 2013-10-24T12:26:25.550 回答