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

Question

Я использую C # для постоянного поиска нескольких строковых «ключевых слов» в больших строках, которые> 4 КБ. Этот код постоянно зацикливается, и спящий режим недостаточно сокращает загрузку процессора при сохранении разумной скорости. Замедленная съемка - это метод сопоставления ключевых слов.

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

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

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

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

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

Answer 1

Вы всегда ищете одни и те же ключевые слова? Попробуйте Бойер-Мур . Требуется некоторая предварительная обработка ключевых слов, но впоследствии она набирает скорость.

Answer 2

Я не пробовал, но вы смотрели на Рабин-Карп ? Очевидно, он имеет плохую сложность в худшем случае, но обычно довольно хорош.

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

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

Answer 3

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

Подход:

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

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

Как бы вы не решили, развлекайтесь:)

Answer 4

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

Лучший способ заменить множество строк - запутывание в C #

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

Answer 5

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

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

Итак, самый быстрый метод, который я нашел, используя .NET 4 - это параллельное Regex IsMatch.

Вот пример получения общего количества совпадений -

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

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

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