C#: эффективно искать большую строку для вхождений других строк

Question

Я использую C# для непрерывного поиска нескольких «ключевых слов» строк в больших строках, которые составляют = = 4kb. Этот код постоянно зацикливается, и сон не снижает производительность процессора, сохраняя при этом разумную скорость. Bog-down - это метод сопоставления ключевых слов.

Я нашел несколько возможностей, и все они дают схожую эффективность.

1) http://tomasp.net/articles/ahocorasick.aspx -У меня недостаточно ключевых слов для этого, чтобы быть наиболее эффективным алгоритмом.

2) Регулярное выражение. Используя уровень экземпляра, скомпилированное регулярное выражение. -Проставляет больше функциональности, чем я требую, и не достаточно эффективности.

3) String.IndexOf. - Мне нужно сделать «умную» версию этого, чтобы обеспечить достаточную эффективность. Пересечение каждого ключевого слова и вызов IndexOf не разрезают его.

Кто-нибудь знает какие-либо алгоритмы или методы, которые я могу использовать для достижения своей цели?

Answer 1

Вы всегда искали одни и те же ключевые слова? Код товара: Boyer-Moore. Для этого требуется некоторая предварительная обработка ключевых слов, но впоследствии она получает скорость.

Answer 2

Я не пробовал, но посмотрели ли вы на Rabin-Karp? По-видимому, это имеет плохую худшую сложность, но обычно неплохо.

Как выглядят ваши ключевые слова? В частности, они всегда ограничены пробелами (или чем-то подобным)? Если это так, вы можете в основном просмотреть строку после поиска «слов», а затем либо создать карту из слова в список индексов этого слова, либо, возможно, сделать это только для интересующих вас ключевых слов.

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

Answer 3

Я разработал эффективное использование IndexOf на этот вопрос:

A better way to replace many strings - obfuscation in C#

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

Answer 4

На самом деле я должен был решить это раньше, это было весело. У меня было 20k html-страниц, каждый с заголовком, и хотел, чтобы все остальные записи названия на других страницах ссылались на страницу с этим заголовком. Звучит очень похоже на то, что вы пытаетесь выполнить.

подход:

1. Процесс текст файла, превратив его в связанный список {Word, Whitespace}, где Слово было идентифицировано как непрерывный буквенно-цифровой последовательности с несколькими специальными символами, и пробелом было все, что привело к следующему слову.
2. Повторите процесс на шаге 1 для каждого «заголовка» страниц, на которые я хотел ссылаться.
3. Каждое слово из узла в связанном списке на шаге 1 затем было добавлено в список, отсортированный по двоичным параметрам.
4. Теперь вам нужно всего лишь пройти первое слово из каждого титульного смежного списка с шага 2 и искать в двоичном отсортированном списке с шага 3. Вы можете найти несколько ударов или даже мягких ударов, когда слово является множественным, чтобы вы могли иметь несколько стартовых узлов из двоичного списка, который вам нужно проверить.
5. После обработки документа в форме, описанной в шаге 1, на самом деле его очень легко изменить, вставив новые узлы и/или изменив значение Whitespace. После завершения вы просто переходите весь список и выгружаете все это в поток.

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

Однако вы ее решить, весело с ним :)

Answer 5

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

Я выполняю аналогичный поиск, в основном ищут ключевые слова длиной около 10-50 байтов в тексте размером около 45 тыс. Байт. Я ищу около 1900 ключевых слов более девяти миллионов текстов, поэтому получение этого как можно быстрее также является аналогичным приоритетом.

Итак, самый быстрый метод, который я нашел с помощью .NET 4, является параллельным Regex IsMatch.

Вот пример получать полные матчи -

needles.AsParallel ().Sum (l => Regex.IsMatch (haystack , Regex.Escape (l)) ? 1 : 0); 

Это работает для моего сценария (выше), это 55% быстрее, чем порядковые параллельные сравнения IndexOf в моих тестах, по крайней мере для сортировки размера I данных использую. Я также думаю, что улучшение скорости происходит только в том случае, если вы используете многоядерные машины.

Было бы интересно, если кто-нибудь сможет найти более быстрый метод?