1

我有一个 Word 文档的文本和一个字符串数组。目标是查找文档文本中这些字符串的所有匹配项。我尝试在 Aho-Corasick 算法的 C# 实现中使用 Aho-Corasick 字符串匹配，但默认实现不适合我。文本的典型部分看起来像

“<strong>启动”是指贷款人以附件 A 的形式向银行发出的书面通知。

“<strong>启动通知”是指贷款人以附件 A 和启动的形式向银行发出的书面通知。

“<strong>工作日”是指银行开放进行一般业务和激活通知的每一天（周六和周日除外）。

关键字的数组看起来像

var keywords = new[] {"Activation", "Activation Notice"};

Aho-Corasick 算法的默认实现返回以下出现次数

激活 - 4

激活通知 - 2

对于“激活说明”，这是正确的结果。但是对于“激活”，正确的计数也应该是 2，因为我不需要考虑相邻关键字“激活通知”中的出现次数。

这种情况有合适的算法吗？

4

1 回答 1

0

我会假设你根据你链接的例子得到你的结果。

StringSearchResult[] results = searchAlg.FindAll(textToSearch);

有了这些results，如果您假设唯一的重叠是子集，您可以按索引排序并一次性收集您想要的结果。

public class SearchResultComparer : IComparer<StringSearchResult> { 
    public int StringSearchResult(StringSearchResult x, StringSearchResult y) 
    { 
        // Try ordering by the start index.
        int compare = x.Index.CompareTo(y.Index);
        if (compare == 0)
        {
            // In case of ties, reverse order by keyword length.
            compare = y.Keyword.Length.CompareTo(x.Keyword.Length);
        }
        return compare;
    } 
} 

// ...


IComparer searchResultComparer = new SearchResultComparer();
Array.Sort(results, searchResultComparer); 

int activeEndIndex = -1;
List<StringSearchResult> nonOverlappingResults = new List<StringSearchResult>();
foreach(StringSearchResult r in results)
{
    if (r.Index < activeEndIndex)
    {
        // This range starts before the active range ends.
        // Since it's an overlap, skip it.
        continue;
    }

    // Save this result, track when it ends.
    nonOverlappingResults.Add(r);
    activeEndIndex = r.Index + r.Keyword.Length;
}

由于索引排序，循环保证只保留不重叠的范围。但是有些范围会被拒绝。发生这种情况只有两个原因。

  1. 候选从与活动范围相同的索引开始。由于排序打破了这些联系，所以最长的先行，候选必须比活动范围短并且可以跳过。
  2. 候选人在活动范围之后开始。由于唯一的重叠是子集，并且这与活动范围重叠，因此它是一个子集，开始较晚，但仍结束于或之前。

因此，唯一被拒绝的候选将是子集，并且必须在活动范围之前结束。所以活动范围仍然是唯一需要担心重叠的事情。

于 2020-04-15T07:38:53.867 回答