Рассчитать вхождения указанного слова в большой текстовый файл

Question

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

Answer 1

То, что вы хотите, это алгоритм Бойера-Мура . Это наиболее эффективный из известных общих методов решения этой проблемы.

Answer 2

Лучший способ идентифицировать вхождение word , в отличие от той последовательности символов, которая встречается как подстрока строки файла, возможно, с помощью регулярного выражения Pattern, скомпилированного из \bword\b - \b - это «границы слов».

Если у вас есть Pattern, то нет прямого метода для подсчета количества вхождений в строке, поэтому вам потребуется некоторый тест для определения того, что быстрее - split (принимая длину полученного массива из строк минус один), маловероятно, но возможно, или сделать Matcher с помощью метода matcher шаблона, затем зацикливаться на его методе find во время подсчета (я бы поставил на это), или еще что-то еще , Но самостоятельного определения границ слов достаточно для PITA, поэтому я обычно использую регулярные выражения для выполнения задачи; -).

Можно снизить скорость, считывая (и считая вхождения слов) более одной строки за раз - скажем, МБ за раз. Но если вы сделаете это, то вам нужно позаботиться о последней «частичной» строке в мегабайте-глотке, поскольку вхождение слова может быть разбито между концом этой частичной строки и началом следующего глотка - выполнимо , но такая оптимизация выполняется только под принуждением, так как очень легко внести ошибку; -).

Answer 3

Считать файл, используя буферный поток char-by-char в массив, пока не встретятся пробельные символы или их группы (пробелы, табуляции, новые строки, ...), сравнить содержимое этого массива с цельюword, увеличить счетчик, если соответствует, очистить массив, вернуться к чтению.

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

Кроме того, вы можете объединить чтение char и сравнение его с целью в одном цикле, устраняя необходимость в промежуточном массиве.Первый вариант легко конвертируется в этот, просто выкиньте массив и сравните на лету, вам нужно только знать текущий символ и его положение в слове.

Answer 4

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