Theo dõi/đếm tần số từ

Question

Tôi muốn nhận được sự đồng thuận của cộng đồng về thiết kế tốt để có thể lưu trữ và truy vấn số lượng tần số từ. Tôi đang xây dựng một ứng dụng mà trong đó tôi phải phân tích các đầu vào văn bản và lưu trữ số lần một từ đã xuất hiện (theo thời gian). Vì vậy, cho các đầu vào sau:

• "To Kill a Mocking Bird"
• "Mocking một người chơi đàn piano"

sẽ lưu trữ các giá trị sau:

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

Và sau đó được có thể nhanh chóng truy vấn giá trị đếm của một từ tùy ý nhất định.

Kế hoạch hiện tại của tôi là lưu trữ các từ và số lượng trong cơ sở dữ liệu, và dựa vào các giá trị đếm từ bộ nhớ ... Nhưng tôi nghi ngờ rằng tôi sẽ không nhận được đủ số lần truy cập bộ nhớ cache.

Ai đó có thể đề xuất thuật toán hoặc cấu trúc dữ liệu hoặc bất kỳ ý tưởng nào khác có thể làm cho giải pháp này hoạt động tốt không?

Answer 1

Tôi không hiểu tại sao bạn cảm thấy cơ sở dữ liệu không phải là giải pháp phù hợp. Bạn có thể sẽ chỉ có khoảng 100000 hàng và kích thước nhỏ của bảng sẽ có nghĩa là nó có thể được lưu trữ hoàn toàn trong bộ nhớ. Làm cho từ khóa chính và tra cứu sẽ rất nhanh.

Answer 2

Lời đếm là ví dụ kinh điển của một chương trình MapReduce (pseudo code từ Wikipedia):

Tôi không nói rằng đây là các cách để làm điều đó, nhưng nó chắc chắn là một là tùy chọn nếu bạn cần một cái gì đó mà quy mô tốt khi số lượng từ riêng biệt vượt ra ngoài bộ nhớ có sẵn trên một máy tính duy nhất. Miễn là bạn có thể ở lại dưới giới hạn bộ nhớ, một vòng lặp đơn giản cập nhật một bảng băm nên làm các trick.

Answer 3

Sử dụng hash table.

Answer 4

Giải pháp của bạn nghe có vẻ ổn. Nếu bộ nhớ cache dựa trên số lượng sử dụng gần đây, thì nó sẽ giữ số từ cho các từ thường xuyên nhất. (Phân phối từ là một cái gì đó giống như 100 từ đầu tiên bao gồm 90% trường hợp từ), do đó bạn không cần một bộ nhớ cache rất lớn.

Nếu bạn muốn cải thiện hiệu suất và thả db, bạn có thể mã hóa các từ như một trie, và lưu trữ số lượng sử dụng trong các nút lá. Trong essense, đó là những gì cơ sở dữ liệu đang làm nếu bạn chỉ mục trên văn bản từ, vì vậy bạn thực sự chỉ tránh độ trễ db. Nếu đó là mục tiêu, thì có nhiều cách khác để tránh độ trễ của db, chẳng hạn như sử dụng tra cứu song song.

Answer 5

Nếu hiệu suất là mục tiêu chính của bạn, bạn có thể sử dụng cấu trúc dựa trên băm hoặc dựa trên bộ nhớ RAM chỉ trong RAM. Giả sử rằng bạn thực hiện một số tính năng lọc hữu ích (để không tính các thuật ngữ với các ký tự không phải từ), số từ tối đa trong bảng của bạn sẽ nằm trong khoảng từ 10⁶ đến 10⁷ (ngay cả khi có nhiều ngôn ngữ), vì vậy việc này sẽ dễ dàng phù hợp với bộ nhớ của máy tính hiện tại (và hoàn toàn tránh tất cả việc xử lý cơ sở dữ liệu).

Mặt khác, nếu bạn phải tự mình triển khai chi tiết bảng băm, chỉ có nhiều mã mà bạn có thể làm sai (trong khi các cơ sở dữ liệu hy vọng đã chỉnh sửa mã của chúng tối đa). Vì vậy, ngay cả chi tiết nhỏ trong việc thực hiện của riêng bạn có thể dẫn đến mất hiệu suất một lần nữa.

Do đó tình trạng khó xử này cho thấy rõ ràng quy tắc tối ưu hóa đầu tiên và thứ hai: 1. Không tối ưu hóa sớm. 2. Đo lường, trước khi bạn tối ưu hóa.

:)