MapReduce - Thuật toán
Thuật toán MapReduce chứa hai nhiệm vụ quan trọng, đó là Bản đồ và Giảm.
- Nhiệm vụ bản đồ được thực hiện bởi Mapper Class
- Nhiệm vụ giảm thiểu được thực hiện bằng Lớp giảm tốc.
Lớp Mapper lấy đầu vào, mã hóa nó, ánh xạ và sắp xếp nó. Đầu ra của lớp Mapper được sử dụng làm đầu vào bởi lớp Reducer, từ đó tìm kiếm các cặp phù hợp và giảm chúng.
MapReduce thực hiện các thuật toán toán học khác nhau để chia một nhiệm vụ thành các phần nhỏ và gán chúng cho nhiều hệ thống. Về mặt kỹ thuật, thuật toán MapReduce giúp gửi các tác vụ Bản đồ & Rút gọn đến các máy chủ thích hợp trong một cụm.
Các thuật toán toán học này có thể bao gồm:
- Sorting
- Searching
- Indexing
- TF-IDF
Sắp xếp
Sắp xếp là một trong những thuật toán MapReduce cơ bản để xử lý và phân tích dữ liệu. MapReduce triển khai thuật toán sắp xếp để tự động sắp xếp các cặp khóa-giá trị đầu ra từ trình ánh xạ theo khóa của chúng.
Các phương thức sắp xếp được thực hiện trong chính lớp ánh xạ.
Trong giai đoạn trộn và sắp xếp, sau khi mã hóa các giá trị trong lớp ánh xạ, Context lớp (lớp do người dùng định nghĩa) thu thập các khóa có giá trị phù hợp như một tập hợp.
Để thu thập các cặp khóa-giá trị tương tự (khóa trung gian), lớp Mapper có sự trợ giúp của RawComparator lớp để sắp xếp các cặp khóa-giá trị.
Tập hợp các cặp khóa-giá trị trung gian cho một Bộ giảm tốc nhất định được Hadoop tự động sắp xếp để tạo thành các khóa-giá trị (K2, {V2, V2,…}) trước khi chúng được hiển thị cho Bộ giảm tốc.
Đang tìm kiếm
Tìm kiếm đóng một vai trò quan trọng trong thuật toán MapReduce. Nó giúp ích trong giai đoạn kết hợp (tùy chọn) và trong giai đoạn Bộ giảm tốc. Hãy để chúng tôi cố gắng hiểu cách Tìm kiếm hoạt động với sự trợ giúp của một ví dụ.
Thí dụ
Ví dụ sau đây cho thấy cách MapReduce sử dụng thuật toán Tìm kiếm để tìm ra chi tiết của nhân viên có mức lương cao nhất trong một tập dữ liệu nhân viên nhất định.
Giả sử chúng ta có dữ liệu nhân viên trong bốn tệp khác nhau - A, B, C và D. Hãy giả sử rằng có các bản ghi nhân viên trùng lặp trong cả bốn tệp do nhập dữ liệu nhân viên từ tất cả các bảng cơ sở dữ liệu nhiều lần. Xem hình minh họa sau đây.
The Map phasexử lý từng tệp đầu vào và cung cấp dữ liệu nhân viên theo cặp khóa-giá trị (<k, v>: <tên tôi, tiền lương>). Xem hình minh họa sau đây.
The combiner phase(kỹ thuật tìm kiếm) sẽ chấp nhận đầu vào từ giai đoạn Bản đồ dưới dạng một cặp khóa-giá trị với tên nhân viên và tiền lương. Sử dụng kỹ thuật tìm kiếm, bộ kết hợp sẽ kiểm tra tất cả mức lương của nhân viên để tìm ra nhân viên có mức lương cao nhất trong mỗi tệp. Xem đoạn mã sau.
<k: employee name, v: salary>
Max= the salary of an first employee. Treated as max salary
if(v(second employee).salary > Max){
Max = v(salary);
}
else{
Continue checking;
}Kết quả mong đợi như sau:
|
Reducer phase- Lập từng hồ sơ, bạn sẽ tìm được nhân viên có mức lương cao nhất. Để tránh dư thừa, hãy kiểm tra tất cả các cặp <k, v> và loại bỏ các mục trùng lặp, nếu có. Thuật toán tương tự được sử dụng giữa bốn cặp <k, v>, đến từ bốn tệp đầu vào. Kết quả cuối cùng sẽ như sau:
<gopal, 50000>Lập chỉ mục
Thông thường, lập chỉ mục được sử dụng để trỏ đến một dữ liệu cụ thể và địa chỉ của nó. Nó thực hiện lập chỉ mục hàng loạt trên các tệp đầu vào cho một Mapper cụ thể.
Kỹ thuật lập chỉ mục thường được sử dụng trong MapReduce được gọi là inverted index.Các công cụ tìm kiếm như Google và Bing sử dụng kỹ thuật lập chỉ mục ngược. Hãy để chúng tôi cố gắng hiểu cách hoạt động của Lập chỉ mục với sự trợ giúp của một ví dụ đơn giản.
Thí dụ
Văn bản sau đây là đầu vào để lập chỉ mục ngược. Ở đây T [0], T [1] và t [2] là tên tệp và nội dung của chúng được đặt trong dấu ngoặc kép.
T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"Sau khi áp dụng thuật toán Lập chỉ mục, chúng tôi nhận được kết quả sau:
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}Ở đây "a": {2} ngụ ý thuật ngữ "a" xuất hiện trong tệp T [2]. Tương tự, "là": {0, 1, 2} ngụ ý thuật ngữ "là" xuất hiện trong các tệp T [0], T [1] và T [2].
TF-IDF
TF-IDF là một thuật toán xử lý văn bản, viết tắt của Cụm từ Tần số kỳ hạn - Tần suất Tài liệu Nghịch đảo. Nó là một trong những thuật toán phân tích web phổ biến. Ở đây, thuật ngữ 'tần suất' đề cập đến số lần một thuật ngữ xuất hiện trong tài liệu.
Tần suất kỳ hạn (TF)
Nó đo lường tần suất một thuật ngữ cụ thể xuất hiện trong tài liệu. Nó được tính bằng số lần một từ xuất hiện trong tài liệu chia cho tổng số từ trong tài liệu đó.
TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)Tần suất tài liệu nghịch đảo (IDF)
Nó đo lường tầm quan trọng của một thuật ngữ. Nó được tính bằng số lượng tài liệu trong cơ sở dữ liệu văn bản chia cho số lượng tài liệu mà một thuật ngữ cụ thể xuất hiện.
Trong khi tính toán TF, tất cả các thuật ngữ đều được coi là quan trọng như nhau. Điều đó có nghĩa là, TF đếm tần suất thuật ngữ cho các từ thông thường như “là”, “a”, “cái gì”, v.v. Vì vậy, chúng ta cần biết các thuật ngữ thường gặp trong khi mở rộng các thuật ngữ hiếm, bằng cách tính toán sau:
IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).Thuật toán được giải thích dưới đây với sự trợ giúp của một ví dụ nhỏ.
Thí dụ
Hãy xem xét một tài liệu chứa 1000 từ, trong đó từ hivexuất hiện 50 lần. TF chohive sau đó là (50/1000) = 0,05.
Bây giờ, giả sử chúng ta có 10 triệu tài liệu và từ hivexuất hiện trong 1000 trong số này. Sau đó, IDF được tính là log (10.000.000 / 1.000) = 4.
Trọng lượng TF-IDF là tích của các đại lượng này - 0,05 × 4 = 0,20.