Thuật toán để khớp với một tệp đầu vào với số tệp nhất định

Question

Tôi đã có một cuộc phỏng vấn vào tuần trước. Tôi đã bị mắc kẹt trong một trong những câu hỏi trong vòng thuật toán. Tôi trả lời câu hỏi đó, nhưng người phỏng vấn dường như không bị thuyết phục. Đó là lý do tôi chia sẻ như vậy.

Hãy cho tôi biết mọi phương pháp được tối ưu hóa cho câu hỏi này, để nó sẽ giúp tôi trong các cuộc phỏng vấn trong tương lai.

Câu hỏi: -

Có 20 tập tin văn bản nhất định, tất cả các file là các tập tin văn bản ASCII, có kích thước ít hơn 10^9 byte. Có một đầu vào cũng được đưa ra, đây cũng là cũng là một tệp ASCII, input.txt.

Nhiệm vụ của chúng tôi là đối sánh chiến lược nội dung của tệp đầu vào này với cho 20 tệp và in tên tệp phù hợp gần nhất. Nội dung của tệp đầu vào chỉ có thể khớp một phần

Cảm ơn bạn trước. Tìm kiếm trả lời của các bạn.

Answer 1

diff họ và đi qua wc -l, hoặc thực hiện Levenshtein distance trong C++ điều trị mỗi dòng như một nhân vật duy nhất (hoặc bất kỳ đơn vị thích hợp hơn condidering lĩnh vực chủ đề)

Answer 2

Bạn có thể tạo ra một số loại chỉ mục (ví dụ: trie) để tóm tắt tệp đầu vào. Sau đó, bạn có thể kiểm tra số lượng chỉ mục khớp với các tài liệu.

Ví dụ: Tạo một trie cho tập tin đầu vào cho chiều dài 10. Đối với mỗi chuỗi chiều dài 10 (chồng chéo) trong các tập tin văn bản kiểm tra có bao nhiêu trong số họ phù hợp trong trie.

Answer 3

Là một đề xuất cho việc thiết kế các hệ thống có khả năng mở rộng, có khả năng thực hiện tương tự tài liệu, tôi khuyên bạn nên đọc Chương 3 của Mining Massive Datasets, có sẵn trực tuyến miễn phí. Một cách tiếp cận được trình bày ở đây là các bộ dữ liệu 'shingle' bằng cách vector hóa số lượng từ thành các bộ, sau đó băm các từ đó và so sánh các họ của các kết quả băm với sự tương đồng của Jaccard để có được điểm giữa tất cả các tài liệu. Điều này có thể hoạt động trên các tệp petabyte có độ chính xác cao nếu được thực hiện đúng. Các chi tiết rõ ràng có sơ đồ tốt có thể được đọc ở số CS246 Slides on Locality Sensitive Hashing của Stanford. Các phương pháp đơn giản như đếm tần số từ được mô tả trong cuốn sách.