查找文本中出现的相邻子字符串

Question

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

">激活"是指贷款人以附件a的形式向银行发出的书面通知。

">激活通知"是指贷款人以附件a和激活的形式向银行发出的书面通知。

">营业日"是指银行对一般业务和激活通知开放的每一天(周六和周日除外(。

关键字数组看起来像

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

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

激活-4

激活通知-2

对于"激活说明"，这是正确的结果。但对于"激活"，正确的计数也应为2因为我不需要考虑相邻关键字"激活通知"内的事件。

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

Answer 1

我假设您是根据链接的示例得到结果的。

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. 候选者在活动范围之后开始。由于唯一的重叠是子集，并且这与活动范围重叠，因此它是一个稍后开始但仍在或之前结束的子集

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