計算大文本文件中特定詞的出現次數

Question

這是一個面試問題，應該關注效率。如何計算大文本文件中指定詞的出現？我只能想到大多數編程語言中的indexOf（）方法，但我不認爲這是正確的答案。

Answer 1

你想要的是Boyer-Moore algorithm。這是解決這個問題的最有效的已知通用方法。

Answer 2

識別字發生的最好辦法，而不是僅僅出現一個行的文件中的子串字符該序列，可能是從\bword\b編譯正則表達式Pattern - 的\b是「字邊界」。

一旦你有了這個Pattern沒有直接的方法來計算一行中出現的次數，所以你需要一些基準來找出更快的 - split（將結果數組的長度減去一個），但不可能，但可能，或者使用該模式的matcher方法制作一個方法，然後在計數（我賭這個）或其他東西時循環其find方法。但是單獨檢測字邊界就足夠了PITA，我傾向於總是使用正則表達式來處理任務;-)。

可以通過一次讀取多條線（並計算單詞出現次數）來擠壓某些速度 - 比如一次一個MB。但是，如果你這樣做，那麼你必須關注兆字節中的最後一條「部分」線，因爲這個詞的出現可能會在該部分行的結尾與下一個吞嚥的開始之間分裂 - 可行，但是這種優化只是在脅迫下進行的，因爲它很容易引入錯誤;-)。

Answer 3

如果文本文件非常大，indexOf（）可能不是一個好主意，因爲您需要將整個文件加載到一個字符串中並因此咀嚼內存。給定足夠的數據，你會崩潰的程序。我認爲你需要查看流讀取API來讀取塊的文件，這些文件比indexOf（）更實用。

Answer 4

使用buffered stream字符逐字符到數組讀取文件，直到空白字符遇到或它們的組（空格，製表符，新的生產線，...），比較數組與目標詞的內容，如果比賽增加計數器，清除數組，返回閱讀。

預先分配足夠大小的數組，然後重新使用它進行讀取，如果需要的話進行擴展，不要在每次迭代時分配它。不要每次都清除數組，只需將其讀取計數器設置爲零即可。另外，您可以將字符的讀取和將其與目標進行比較，並將其轉換爲單個循環，從而不再需要中間數組。第一個變體很容易轉換成這個，只是拋出數組並且即時比較，您只需要知道當前字符及其在單詞中的位置。