跟蹤/計數字頻率

我想獲得一些社區對良好設計的一致意見，以便能夠存儲和查詢單詞頻率計數。我正在構建一個應用程序，在該應用程序中，我必須解析文本輸入並存儲單詞出現的次數（隨着時間的推移）。因此，考慮以下輸入：跟蹤/計數字頻率

「殺死一隻小八哥」
「懲戒鋼琴玩家」

將存儲以下值：

Word Count 
------------- 
To  1 
Kill 1 
A  2 
Mocking 2 
Bird 1 
Piano 1 
Player 1

和更高版本能夠快速查詢給定任意單詞的計數值。

我目前的計劃是簡單地將單詞和計數存儲在數據庫中，並依靠緩存單詞計數值......但是我懷疑我沒有獲得足夠的緩存命中時間以使其成爲長期可行的解決方案。

任何人都可以提出算法，或數據結構，或任何其他想法，可能會使這一表現良好的解決方案？

來源

2010-05-17 Joel Martinez

我不明白你爲什麼覺得數據庫不是一個合適的解決方案。您可能只有大約100000行，表格的小尺寸意味着它可以完全存儲在內存中。讓這個詞成爲主鍵，查找速度會非常快。

來源

2010-05-17 20:54:49

字計數是MapReduce程序（僞來自維基百科的代碼）的典型的例子：

我不說這是的方式做到這一點，但它肯定的是選項，如果你需要的東西可以很好地擴展單個機器上可用內存的數量。只要你能夠保持低於內存限制，更新散列表的簡單循環應該能夠做到。

來源

2010-05-17 20:54:40

使用hash table。

來源

2010-05-17 20:56:10

您的解決方案聽起來不錯。如果緩存基於最近的使用次數，那麼它將保存最頻繁單詞的字數。（Word分佈類似於前100個單詞涵蓋了90％的詞實例），因此您不需要非常大的緩存。

如果要提高性能並刪除數據庫，可以將這些單詞編碼爲樹狀結構，並將使用計數存儲在葉節點中。在本質上，如果你在單詞文本上編制索引，數據庫就是這麼做的，所以你只能避免數據庫延遲。如果這是目標，那麼還有其他避免數據庫延遲的方法，例如使用並行查找。

來源

2010-05-17 20:57:51 mdma

如果性能是您的主要目標，那麼您只能在RAM中使用基於散列或基於樹結構的結構。假設你做了一些有用的過濾（不要用非單詞字符來統計術語），表中最大字數將在10⁶到10⁷的範圍內（即使涉及多種語言），所以這很容易適合當前PC的內存（並完全避免所有的數據庫處理）。另一方面，如果你必須自己實現散列表細節，那麼你可以做的更多的代碼是錯誤的（儘管數據庫人員希望儘可能地調整他們的代碼）。所以即使你自己實現的細節也可能導致性能再次下降。

所以這個困境清楚地向我們展示了優化的第一個和第二個規則： 1.不要過早優化。在優化之前測量。

來源

2010-05-17 21:30:51 Bananeweizen

跟蹤/計數字頻率

回答

相關問題