pagesift_frontier/focus/
harvest.rs

1//! 各部分的收成：每抓一页，记下它有没有带来新的切题内容（自适应停止判断的"有收获"），按子树
2//! 或簇分开统计收获率，用置信区间和其余部分比较（多臂老虎机的逐次淘汰）。
3//!
4//! - 某部分收获率的上界低于其余部分收获率的下界：再抓下去也追不上，枯竭（撞词的陷阱：期刊系统
5//!   一期期目录、商店商品页，每页都沾一个查询词，却从不带来新的切题内容）；
6//! - 某部分收获率的下界高于其余部分收获率的下界：产出确实好，按簇分散的上限不该把它赶走。
7//!
8//! 没有按数据调出来的门槛：样本少时区间宽，不轻易下结论；一直颗粒无收的部分，抓得越多区间越窄，
9//! 很快就会被淘汰。置信区间是 Wilson 区间（双侧 `1−δ`，见 [`wilson`]）。
10
11use std::collections::HashMap;
12
13use url::Url;
14
15/// 收获率的 Wilson 置信区间 (下界, 上界)；没有样本时是 (0, 1)。
16///
17/// Wilson 得分区间（Wilson, JASA 22, 1927），双侧水平 `1−δ`：分位数 `z = Φ⁻¹(1−δ/2)`
18/// 。
19fn wilson(hits: u32, n: u32) -> (f64, f64) {
20    pagesift_stat::beta::wilson_z(f64::from(hits), f64::from(n), *Z)
21}
22
23/// 双侧分位数 `Φ⁻¹(1−δ/2)`，进程里只算一次。
24static Z: std::sync::LazyLock<f64> = std::sync::LazyLock::new(|| {
25    pagesift_stat::special::normal_quantile(1.0 - pagesift_stat::Delta::DEFAULT.get() / 2.0)
26});
27
28/// 按某种分法（子树或簇）统计的收获。
29#[derive(Default)]
30pub struct Harvest {
31    /// 部分 → (页数, 有收获的页数)。
32    parts: HashMap<String, (u32, u32)>,
33    total: (u32, u32),
34}
35
36impl Harvest {
37    /// 记下属于 `part` 的一页，`hit` 说它有没有带来新的切题内容。
38    pub fn observe(&mut self, part: String, hit: bool) {
39        let p = self.parts.entry(part).or_default();
40        p.0 += 1;
41        p.1 += u32::from(hit);
42        self.total.0 += 1;
43        self.total.1 += u32::from(hit);
44    }
45
46    /// 这一部分和其余部分各自的 (页数, 有收获的页数)。
47    fn split(&self, part: &str) -> ((u32, u32), (u32, u32)) {
48        let mine = self.parts.get(part).copied().unwrap_or_default();
49        (mine, (self.total.0 - mine.0, self.total.1 - mine.1))
50    }
51
52    /// 枯竭：收获率的上界低于其余部分收获率的下界。
53    pub fn is_dry(&self, part: &str) -> bool {
54        let ((n, h), (rn, rh)) = self.split(part);
55        n > 0 && wilson(h, n).1 < wilson(rh, rn).0
56    }
57
58    /// 产出证明了好：收获率的下界高于其余部分收获率的下界。两边都用下界：其余部分只有一两页时
59    /// （开局时只有种子页），它的点估计是 0 或 1，拿来比没有意义，下界会把样本少的一边自然压低。
60    pub fn is_proven(&self, part: &str) -> bool {
61        let ((n, h), (rn, rh)) = self.split(part);
62        n > 0 && wilson(h, n).0 > wilson(rh, rn).0
63    }
64}
65
66/// 页面所在的子树：别的主机（子站）整个算一棵；种子主机上按页面的上级目录分，跳过开头的
67/// 语言段，最多两段（`/research-highlight/某篇` → `research-highlight`，
68/// `/en/education/programmes/x` → `education/programmes`）。只按第一段分的话，整站都在
69/// `/en/` 下的站点就成了一棵树，判它枯竭等于停掉整个爬取。`seed_host` 已去掉 `www.`、小写。
70pub fn subtree(seed_host: &str, url: &Url) -> String {
71    let host = url
72        .host_str()
73        .unwrap_or_default()
74        .trim_start_matches("www.")
75        .to_ascii_lowercase();
76    if host != seed_host {
77        return host;
78    }
79    let mut segs: Vec<&str> = url.path().split('/').filter(|s| !s.is_empty()).collect();
80    segs.pop();
81    if segs.first().is_some_and(|s| {
82        super::url_shape::is_language_code(s) || super::url_shape::is_language_name(s)
83    }) {
84        segs.remove(0);
85    }
86    segs.truncate(2);
87    format!("{host}/{}", segs.join("/"))
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    fn u(s: &str) -> Url {
95        Url::parse(s).unwrap()
96    }
97
98    #[test]
99    fn a_part_that_never_pays_off_is_dropped_once_the_evidence_is_clear() {
100        let mut h = Harvest::default();
101        // 图书馆的正经页面：一半有收获
102        for i in 0..10 {
103            h.observe("lib".into(), i % 2 == 0);
104        }
105        // 期刊系统：颗粒无收。几页的时候还说不准，多了就清楚了
106        for _ in 0..3 {
107            h.observe("journals".into(), false);
108        }
109        assert!(!h.is_dry("journals"));
110        for _ in 0..12 {
111            h.observe("journals".into(), false);
112        }
113        assert!(h.is_dry("journals"));
114        assert!(!h.is_dry("lib"));
115        assert!(h.is_proven("lib"));
116        assert!(!h.is_proven("journals"));
117        // 收获率一般、和其余部分差不多的部分不算枯竭
118        let mut h = Harvest::default();
119        for i in 0..40 {
120            h.observe("study".into(), i % 5 == 0);
121            h.observe("other".into(), i % 4 == 0);
122        }
123        assert!(!h.is_dry("study") && !h.is_dry("other"));
124    }
125
126    /// δ = 0.05 时和 0.81 的 z = 1.96 的区间在 1e-4 内一致（冷启动等于现值），没有样本时是 (0, 1)。
127    #[test]
128    fn wilson_uses_two_sided_delta() {
129        let old = |h: f64, n: f64| {
130            let z: f64 = 1.96;
131            let p = h / n;
132            let z2 = z * z;
133            let c = (p + z2 / (2.0 * n)) / (1.0 + z2 / n);
134            let half = z * (p * (1.0 - p) / n + z2 / (4.0 * n * n)).sqrt() / (1.0 + z2 / n);
135            ((c - half).max(0.0), (c + half).min(1.0))
136        };
137        for (h, n) in [(0, 1), (3, 4), (5, 40), (40, 40)] {
138            let (a, b) = wilson(h, n);
139            let (c, d) = old(f64::from(h), f64::from(n));
140            assert!((a - c).abs() < 1e-4 && (b - d).abs() < 1e-4, "{h}/{n}");
141        }
142        assert_eq!(wilson(0, 0), (0.0, 1.0));
143    }
144
145    #[test]
146    fn subtrees_follow_parent_directories() {
147        let seed = "e.edu";
148        assert_eq!(
149            subtree(seed, &u("https://journals.e.edu/j1/issue/current")),
150            "journals.e.edu"
151        );
152        assert_eq!(
153            subtree(seed, &u("https://www.e.edu/en/research-highlight/story-1")),
154            "e.edu/research-highlight"
155        );
156        assert_eq!(
157            subtree(seed, &u("https://e.edu/en/education/programmes/x/y")),
158            "e.edu/education/programmes"
159        );
160        assert_eq!(subtree(seed, &u("https://e.edu/about")), "e.edu/");
161    }
162}
pagesift_frontier/focus/harvest.rs

pagesift_frontier/focus/
harvest.rs
