Thuật toán frontend: Tìm node chứa content chính
Bài viết được sự cho phép của tác giả Thanh Lê
Tại sao nên đọc bài này
- Đập vào mặt những đứa nói làm Frontend thì không cần logic, thuật toán
- Xem tui khoe công việc đang làm thôi
Vấn đề
Chuyện là mình đang build một feature cho https://getnimbus.io, trong đó có một tính năng gọi là Term explain, cơ bản khi bạn đang xem một trang web nào đó mà có một vài từ về web3 thì Nimbus sẽ giải thích từ đó là gì, một cách ngắn gọn nhất.
Đó cơ bản feature là vậy, tuy nhiên có một vấn đề nhỏ: Một trang web sẽ có rất nhiều content, và thường user khi đọc một article hay news thì thường sẽ chỉ focus vào content đó thôi. Nếu vậy sẽ cực kì khó chịu nếu mình show một đống term explain mà không năm trong main content.
Vậy câu hỏi tiếp theo, làm sao mình tự động detect được node nào trong cây DOM chứa main content, để từ đó lấy ra text rồi match trong đó xem có term nào cần explain không.
Rồi cái khó ở đây là làm sao xác định được cái div nào là main content nhỉ? Trước đây thì mình hard code, mà hôm nay thấy nhiều quá, làm không nổi. Vậy là suy nghĩ có cách nào để tìm được div chứa main content không.
Solution
Ratio = (Node nào có text length / tổng sổ node bên trong) Node nào có cái ratio đó cao nhất thì khả năng cao là main content
Cùng test thử nhé
- Bạn có thể lấy được text content của một node bằng
node.innerText
- Số lượng child node của div qua
node.childElementCount
hoặc lấy list children quanode.childNodes
. (Note lànode.childElementCount = node.childNodes.length
nhé)
Children count
const getTotalChildNode = (node, total = 0) => {
if (!node.childElementCount) {
return total;
}
return total + (node.childElementCount || 0) + Array.from(node.childNodes).map(child => getTotalChildNode(child)).reduce((a, b) => a + b, 0)
}
Vì cần tìm hết cháu chắt chút chít nên hãy suy nghĩ kiểu gì cùng phải dùng đệ qui (recursive) rồi nhé!
Công thức khi nào nên nghĩ tới đệ quy: – Khi input data có structure lặp lại và kết quả lại là tổng hợp của tất cả các lần lập lại đó.
Cụ thể ở đây là node.childNodes
. Mình đang cần lấy cái childNodes
để biết có bao nhiêu child đúng không, và từng thằng child trong đó mình cũng lại phải đếm childNodes
của nó.
Cách viết đệ quy:
1. Điều kiện dừng
2. Tính kết quả và phân phối đệ quy.
Như ở trên là dk dừng là khi éo còn childElementCount
nào nữa
Tính kết quả là total + (node.childElementCount || 0)
, phân phối là Array.from(node.childNodes).map(child => getTotalChildNode(child)).reduce((a, b) => a + b, 0)
![Thuật toán frontend](https://topdev.vn/blog/wp-content/uploads/2024/01/thuat-toan-frontend-8.png)
Ratio
const textNodeRatio = (node) => {
const totalNodes = getTotalChildNode(node);
if (!node.innerText || !totalNodes) {
return 0;
}
const textLength = node.innerText.length;
return textLength / getTotalChildNode(node);
}
const checkAllNodes = (node, result = []) => {
result.push({node, ratio: textNodeRatio(node)});
if (node.childElementCount) {
Array.from(node.childNodes).forEach(child => {
checkAllNodes(child, result);
})
}
return result.sort((a, b) => b.ratio - a.ratio).slice(0, 10);
}
Như nãy đã giải thuyết, lấy số từ trong node rồi chia ra theo tổng số cháu chắt, thằng nào có ratio đó cao nhất nghĩa là main
![Thuật toán frontend](https://topdev.vn/blog/wp-content/uploads/2024/01/thuat-toan-frontend-5.jpg)
A… đuồi ròi, list kết quả chỉ là cái div chứa content (Môt div chứa đoạn văn). Uhm đúng nhỉ, éo có childrent nào cả, toàn là text bên trong thì chả có ratio cao nhất rồi
DKM, cay, giả thuyết mình sai sao?
Xem ngay các tin đăng tuyển dụng Front-end lương cao trên TopDev
Context của bài toán
Pop lên trong đầu mình , nếu mình đi check các trang về tin tức, news đồ, chả lẽ cả trang tin thì dài có mấy trăm chữ?
Vậy mình nên filter bỏ ra mấy thằng div mà text ít quá nhỉ. Đơn giản.
const textNodeRatio = (node) => {
const totalNodes = getTotalChildNode(node);
if (!node.innerText || !totalNodes) {
return 0;
}
const textLength = node.innerText.length;
if (textLength < 1000) {
// Thằng nào có text ít quá thì cho ra đê luôn
return 0;
}
return textLength / getTotalChildNode(node);
}
Test lại
![Thuật toán frontend](https://topdev.vn/blog/wp-content/uploads/2024/01/thuat-toan-frontend-4.jpg)
![Thuật toán frontend](https://topdev.vn/blog/wp-content/uploads/2024/01/thuat-toan-frontend-3.jpg)
Full script
const getTotalChildNode = (node, total = 0) => {
if (!node.childElementCount) {
return total;
}
return total + (node.childElementCount || 0) + Array.from(node.childNodes).map(child => getTotalChildNode(child)).reduce((a, b) => a + b, 0)
}
const textNodeRatio = (node) => {
const totalNodes = getTotalChildNode(node);
if (!node.innerText || !totalNodes) {
return 0;
}
const textLength = node.innerText.length;
if (textLength < 1000) {
return 0;
}
return textLength / getTotalChildNode(node);
}
const checkAllNodes = (node, result = []) => {
result.push({node, ratio: textNodeRatio(node)});
if (node.childElementCount) {
Array.from(node.childNodes).forEach(child => {
checkAllNodes(child, result);
})
}
return result.sort((a, b) => b.ratio - a.ratio).slice(0, 10);
}
Độ hoàn thiện
Nói chung là mình test một vài trang khá ok, một vài trang content rất dài nên dẫn tới cái điều kiện < 1000
có vẻ không ổn lắm.
So far so good, thôi tạm ổn để sài đã . Để suy nghĩ thêm xem có cách gì khiến nó stable hơn không đã. Bạn đọc có idea gì thì giúp mình với nhá.
Đánh giá performance
Nói chung đoạn này nên check thử xem cái thuật toán của mình có thực sự chạy được không, kiểu logic đúng mà 5p sau biến laptop của user thành cái chảo chiên trứng thì hơi… độc ác phải không nào.
![Đánh giá performance](https://topdev.vn/blog/wp-content/uploads/2024/01/thuat-toan-frontend-2.jpg)
Một số idea khác
- Tìm xem div nào chiếm nhiều viewport nhất
- Div nào chứa nhiều thẻ
p
trong đó nhất
- Coi xem thằng này làm làm sao https://github.com/mozilla/readability
Tổng kết
Đó thấy đó, đôi khi giỏi thuật toán sẽ giúp bạn giải quyết những bài toán ảo ma canada, xuka yêu chai en vậy. Vì vậy đừng coi thường thuật toán nhé!
![Thuật toán frontend](https://topdev.vn/blog/wp-content/uploads/2024/01/thuat-toan-frontend-1.jpg)
Have a good weekend!
Bài viết gốc được đăng tải tại thanhle.blog
Xem thêm:
- Frontend cần học những gì để trở nên thật giỏi!
- Virtualbox Headless Frontend là gì?
- Tổng Hợp Những Câu Hỏi Phỏng Vấn Front End Thường Xuyên Xuất Hiện Trong Các Buổi Phỏng Vấn
Tham khảo ngay việc làm IT mọi cấp độ trên TopDev!
- T Tổng hợp 50+ thuật ngữ chuyên ngành dành cho Frontend Developer
- T Top 5 thư viện Slider thông dụng cho lập trình viên Frontend
- A AngularJS Là Gì? AngularJS và Angular có khác nhau?
- 1 14 công cụ tuyệt vời dành cho lập trình viên Frontend
- 7 7 thư viện CSS Animation cực hay cho lập trình viên Frontend
- S State trong frontend là gì? Tại sao nên giỏi cái này?
- C Chia sẻ kinh nghiệm viết code Front-end hiệu quả và bảo mật
- T Tại sao Vue.js được nhiều frontend developer lựa chọn?
- F Fix lỗi Force layout, reflow ảnh hưởng tới performance Frontend
- T Thuật toán frontend: Tìm node chứa content chính