Как найти количество вхождений строки в огромную строку, как в большой книге

Question

Мне недавно задали этот вопрос во время интервью C #:

Как бы вы эффективно нашли количество вхождений слова в огромный текст, такой как большая книга (Библия, словарь и т. Д.).

Мне интересно, какова была бы наиболее эффективная структура данных для хранения содержимого книги. Самой грязной мыслью, о которой я мог подумать, было хранение ее в StringBuilder и поиск количества подстрок, ноЯ уверен, что должен быть намного лучший способ сделать это.

И для строки разумного размера есть несколько способов сделать это, используя подстроку, регулярные выражения и т. Д., Но для огромной строки, которая является наиболееэффективный способ.

Обновление: я ищу следующее:

Предполагая, что есть текстовый файл, давайте снова скажем Библию размером 20 МБ, и я хочу найти числораз слово «Иисус» встречается в тексте, за исключением загрузки всего 20 МБ в строку или StringBuilder и использования подстроки или регулярного выражения длянайти количество совпадений, есть ли другая структура данных, которая может быть использована для хранения всего текстового содержимого.Фактический поиск может быть выполнен несколькими способами, и я ищу наиболее эффективную «структуру данных» для временного хранилища.

Answer 1

Предполагая, что вам не нужны подстроки, а только полные слова, я бы использовал хеш-таблицу. Может быть построен за линейное время, а размер пропорционален количеству отдельных слов. Dictionary<string,int> конкретно. На моей машине потребовалось около 450 мс, чтобы загрузить всю библию в хеш-таблицу и найти все записи слова «Бог».

Answer 2

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

Создайте три из Библии с информацией о количестве.

Если вам нужно запроситьслово, пройдитесь по дереву, получите счет.

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

Предполагается, что слова для запроса изменяются, Библия остается неизменной ...

Answer 3

Что-то размер библии не настолько велик, чтобы предотвратить кэширование всей строки в памяти, так что с предположением, что вы можете ... Я использовал этот метод раньше, но он, очевидно, не будет молниеносным.Строго говоря, с точки зрения эффективности с вычислительной точки зрения, это не самая быстрая скорость, но, учитывая скорость кодирования и разумную скорость, я думаю, что это работает до подсчета наносекунд.

        string text = "a set of text to search in. fast to implement.";
        string key = "to";
        MessageBox.Show(text.Split(" ',.".ToCharArray()).Where(a => a == key).Count().ToString());

Редактировать: не решает окончательную версию вопроса и, возможно, неверно истолковал исходный вопрос.Отбой.

Answer 4

В Википедии есть интересная статья о поиске строк: http://en.wikipedia.org/wiki/String_searching_algorithm, и согласно этой статье этот алгоритм является своего рода эталоном: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm