Лучший способ проверить существующую строку с большим списком сопоставимых

Question

Предположим, у вас есть список аббревиатур, которые определяют значение (например, AB1, DE2, CC3), и вам нужно проверить строковое значение (например, "Happy: DE2 | 234"), чтобы увидеть, находится ли аббревиатура в строка. Для краткого списка аббревиатур я обычно создавал бы простой RegEx, который использовал разделитель (например, (AB1 | DE2 | CC3)) и просто искал совпадение.

Но как бы я справился с этим, если есть более 30 акронимов для сравнения? Имеет ли смысл использовать ту же технику (безобразно), или есть более эффективный и элегантный способ выполнить эту задачу?

Имейте в виду, что список примеров аббревиатур и строка примеров - это не фактический формат данных, с которым я работаю, а просто способ выразить свою проблему.

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

РЕДАКТИРОВАТЬ: я забыл включить мою потребность захватить совпадающее значение, отсюда и выбор использования регулярных выражений ...

Answer 1

Лично я не думаю, что 30 является особенно большим для регулярного выражения, поэтому я не буду слишком спешить, чтобы исключить это. Вы можете создать регулярное выражение с одной строкой кода:

var acronyms = new[] { "AB", "BC", "CD", "ZZAB" };
var regex = new Regex(string.Join("|", acronyms), RegexOptions.Compiled);
for (var match = regex.Match("ZZZABCDZZZ"); match.Success; match = match.NextMatch())
    Console.WriteLine(match.Value);
// returns AB and CD

Таким образом, код относительно элегантен и удобен в обслуживании. Если вы знаете верхнюю границу для количества сокращений, я бы провел некоторое тестирование, которое знает, какие оптимизации там уже встроены в движок регулярных выражений. Вы также сможете бесплатно получить выгоду от будущих оптимизаций движка regex. Если у вас нет оснований полагать, что производительность будет проблемой, делайте это просто.

С другой стороны, регулярное выражение может иметь другие ограничения, например, по умолчанию, если у вас есть аббревиатуры AB, BC и CD, в «ABCD» он вернет только два из них как совпадение. Поэтому хорошо сказать, что есть аббревиатура, но вы должны быть осторожны, чтобы поймать несколько совпадений.

Когда производительность стала для меня проблемой (> 10000 элементов), я поместил «сокращения» в HashSet, а затем искал каждую подстроку текста (от минимальной длины акронима до максимальной длины акронима). Это было хорошо для меня, потому что исходный текст был очень коротким. Я не слышал об этом раньше, но на первый взгляд алгоритм Aho-Corasick, упомянутый в вопросе, на который вы ссылаетесь, кажется лучшим общим решением этой проблемы.

Answer 2

Вот что я придумал. Буду признателен за любую конструктивную критику, которую вы можете предложить ...

Сначала создайте перечисление, которое будет содержать каждое из моих сокращений:

enum acronym
{ AB1,DE2,CC3 }

Далее я создаю строковый массив перечисления:

string[] acronyms = Enum.GetNames(typeof(acronym));

Наконец, я перебираю строковый массив и выполняю метод regex.match:

foreach (string a in acronyms)
{
    Match aMatch = Regex.Match(input, a.ToString(), RegexOptions.None);
    if (aMatch.Success)
    {
        ...<do something>...
        break;
    }
}

Видите что-нибудь не так с этим?

Answer 3

Почему бы просто не разбить строку и сравнить возвращаемый список? В этом случае кажется ненужным использовать REGEX. Я знаю, что ваш формат может отличаться, но может показаться, что вы могли бы:

• Разделить строку на основе «разделителя заголовков», в вашем случае двоеточие:
• Возьмите вторую половину результата, строку аббревиатуры, и разделите ее на основе разделителя акроним, в данном случае это труба |
• Наконец, переберите новый разделенный список сокращений и сравните каждое со списком кандидатов с помощью вложенного цикла for

РЕДАКТИРОВАТЬ: Если вам нужно только знать, существует ли конкретная аббревиатура или набор акронимов внутри строки, используйте метод .Search () вместо .Match ().

Answer 4

Подход regex кажется достаточно эффективным и элегантным. Конечно, вам придется следить за неэкранированными символами при построении выражения или за невозможностью его компилировать из-за сложности или ограничений по размеру.

Другим способом сделать это было бы создание структуры данных trie для представления всех сокращений (это может несколько дублировать то, что делает сопоставитель регулярных выражений). По мере продвижения по каждому символу в строке вы будете создавать новый указатель на корень дерева и продвигать существующие указатели к соответствующему дочернему элементу (если есть). Вы получаете совпадение, когда любой указатель достигает листа.

Answer 5

Если аббревиатура имеет фиксированный размер (как в приведенном выше примере), вы можете вычислить хеш для всех из них (можно сделать один раз в течение срока службы приложения), а затем разбить строку на такие перекрывающиеся части и рассчитать для них тоже хеш. Тогда все, что вам нужно сделать, это искать значения из одного массива в другой.

Вы, вероятно, могли бы создать дерево суффиксов / префиксов или что-то подобное из аббревиатур и искать по этой информации, в Википедии есть множество алгоритмов, чтобы сделать именно это.

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