Найти вхождения смежных подстрок в тексте - PullRequest
Новая
       40

Найти вхождения смежных подстрок в тексте

1 голос
/ 15 апреля 2020

У меня есть текст документа Word и массив строк. Цель состоит в том, чтобы найти все вхождения для этих строк в тексте документа. Я пытался использовать совпадение строк Aho-Corasick в C# реализации алгоритма Aho-Corasick, но реализация по умолчанию мне не подходит. Типичная часть текста выглядит следующим образом:

« Активация » означает письменное уведомление от Кредитора Банку в основном в форме Приложения A.

« Уведомление об активации ”означает письменное уведомление от Кредитора Банку в основном в форме Приложения А и Активации.

« Рабочий день »означает каждый день (кроме субботы) и воскресенья), когда банки открыты для общего бизнеса и уведомления об активации.

Массив ключевых слов выглядит как 

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

Возвращает реализация алгоритма Aho-Corasick по умолчанию следующее количество вхождений

Активация - 4

Уведомление об активации - 2

Для «Примечаний к активации» это правильный результат. Но для « Активация 'правильный счет должен быть также равен 2, потому что мне не нужно рассматривать вхождения внутри смежного ключевого слова' Уведомление об активации '.

Существует ли подходящий алгоритм для этого случая?

1 Ответ

0 голосов
/ 15 апреля 2020

Я предполагаю, что вы получили свои результаты в соответствии с примером, который вы связали. 

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

Благодаря сортировке индекса l oop гарантирует, что будут сохраняться только непересекающиеся диапазоны. Но некоторые диапазоны будут отклонены. Это может произойти только по двум причинам.

  1. Кандидат начинает с того же индекса, что и активный диапазон. Так как сортировка разрывает эти связи, поэтому самый длинный идет первым, кандидат должен быть короче активного диапазона и может быть пропущен.
  2. Кандидат стартует после активного диапазона. Поскольку единственными перекрытиями являются подмножества, и это перекрывается с активным диапазоном, это подмножество, которое начинается позже, но все еще заканчивается в или раньше.

Поэтому единственными отклоненными кандидатами будут подмножества, и они должны заканчиваться до активного диапазона. Таким образом, активный диапазон остается единственным, о чем нужно беспокоиться при перекрытии.

...