rusty_alto/
parseval.rs

1//! Fast EVALB-style Parseval scoring for constituency trees.
2
3use crate::{FxHashMap, FxHashSet};
4use packed_term_arena::tree::{Tree, TreeArena};
5use smallvec::SmallVec;
6use std::{error::Error, fmt};
7
8/// The conventional Collins/PTB EVALB profile used when no parameter file is supplied.
9const COLLINS_PTB_PARAMS: &str = r#"
10CUTOFF_LEN 40
11DELETE_LABEL TOP
12DELETE_LABEL S1
13DELETE_LABEL ROOT
14DELETE_LABEL -NONE-
15DELETE_LABEL ,
16DELETE_LABEL :
17DELETE_LABEL ``
18DELETE_LABEL ''
19DELETE_LABEL .
20DELETE_LABEL ?
21DELETE_LABEL !
22DELETE_LABEL -LRB-
23DELETE_LABEL -RRB-
24DELETE_LABEL $
25DELETE_LABEL #
26DELETE_LABEL AUX
27DELETE_LABEL AUXG
28EQ_LABEL ADVP PRT
29"#;
30
31/// EVALB normalization parameters relevant to constituent scoring.
32#[derive(Clone, Debug, Default)]
33pub struct EvalbParams {
34    delete_labels: FxHashSet<String>,
35    delete_words: FxHashSet<String>,
36    equivalent_labels: FxHashMap<String, String>,
37    cutoff_len: Option<usize>,
38}
39
40impl EvalbParams {
41    /// Parse an EVALB parameter file.
42    pub fn parse(input: &str) -> Result<Self, EvalbParamError> {
43        let mut params = Self::default();
44        for (line_index, raw_line) in input.lines().enumerate() {
45            let line_no = line_index + 1;
46            let line = raw_line.trim();
47            if line.is_empty() || line.starts_with('#') {
48                continue;
49            }
50
51            let fields: Vec<&str> = line.split_whitespace().collect();
52            match fields.as_slice() {
53                ["DELETE_LABEL", labels @ ..] if !labels.is_empty() => {
54                    params
55                        .delete_labels
56                        .extend(labels.iter().map(|label| (*label).to_owned()));
57                }
58                ["DELETE_WORD", words @ ..] if !words.is_empty() => {
59                    params
60                        .delete_words
61                        .extend(words.iter().map(|word| (*word).to_owned()));
62                }
63                ["EQ_LABEL", left, right] => {
64                    params.add_label_equivalence(left, right);
65                }
66                ["CUTOFF_LEN", value] => {
67                    params.cutoff_len = Some(value.parse().map_err(|_| {
68                        EvalbParamError::new(line_no, format!("invalid CUTOFF_LEN value {value:?}"))
69                    })?);
70                }
71                // These standard EVALB controls do not affect the bracket inventory.
72                ["DEBUG", _]
73                | ["MAX_ERROR", _]
74                | ["LABELED", _]
75                | ["DISC_ONLY", _]
76                | ["TREE_PAIR", _] => {}
77                [directive, ..] => {
78                    return Err(EvalbParamError::new(
79                        line_no,
80                        format!("unsupported or malformed directive {directive:?}"),
81                    ));
82                }
83                [] => unreachable!(),
84            }
85        }
86        Ok(params)
87    }
88
89    /// Return the built-in Collins/PTB normalization profile.
90    pub fn collins_ptb() -> Self {
91        Self::parse(COLLINS_PTB_PARAMS).expect("embedded EVALB parameters are valid")
92    }
93
94    /// Maximum normalized sentence length to score, if configured.
95    pub fn cutoff_len(&self) -> Option<usize> {
96        self.cutoff_len
97    }
98
99    fn add_label_equivalence(&mut self, left: &str, right: &str) {
100        let left_canonical = self
101            .equivalent_labels
102            .get(left)
103            .cloned()
104            .unwrap_or_else(|| left.to_owned());
105        let right_canonical = self
106            .equivalent_labels
107            .get(right)
108            .cloned()
109            .unwrap_or_else(|| right.to_owned());
110        let canonical = left_canonical.clone();
111        for mapped in self.equivalent_labels.values_mut() {
112            if *mapped == right_canonical {
113                *mapped = canonical.clone();
114            }
115        }
116        self.equivalent_labels
117            .insert(left.to_owned(), canonical.clone());
118        self.equivalent_labels.insert(right.to_owned(), canonical);
119    }
120
121    fn canonical_label<'a>(&'a self, label: &'a str) -> &'a str {
122        self.equivalent_labels
123            .get(label)
124            .map_or(label, String::as_str)
125    }
126}
127
128/// A line-numbered EVALB parameter error.
129#[derive(Clone, Debug, PartialEq, Eq)]
130pub struct EvalbParamError {
131    line: usize,
132    message: String,
133}
134
135impl EvalbParamError {
136    fn new(line: usize, message: String) -> Self {
137        Self { line, message }
138    }
139}
140
141impl fmt::Display for EvalbParamError {
142    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
143        write!(f, "line {}: {}", self.line, self.message)
144    }
145}
146
147impl Error for EvalbParamError {}
148
149/// Sufficient statistics for labeled and unlabeled Parseval.
150#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
151pub struct ParsevalCounts {
152    /// Number of scored constituents in the predicted tree.
153    pub predicted: usize,
154    /// Number of scored constituents in the gold tree.
155    pub gold: usize,
156    /// Number of matching labeled constituents.
157    pub matched_labeled: usize,
158    /// Number of matching unlabeled constituents.
159    pub matched_unlabeled: usize,
160}
161
162impl ParsevalCounts {
163    /// Add another sentence's counts.
164    pub fn add_assign(&mut self, other: Self) {
165        self.predicted += other.predicted;
166        self.gold += other.gold;
167        self.matched_labeled += other.matched_labeled;
168        self.matched_unlabeled += other.matched_unlabeled;
169    }
170
171    /// Labeled precision.
172    pub fn labeled_precision(self) -> f64 {
173        ratio(self.matched_labeled, self.predicted)
174    }
175
176    /// Labeled recall.
177    pub fn labeled_recall(self) -> f64 {
178        ratio(self.matched_labeled, self.gold)
179    }
180
181    /// Labeled F1.
182    pub fn labeled_f1(self) -> f64 {
183        f1(self.labeled_precision(), self.labeled_recall())
184    }
185
186    /// Unlabeled precision.
187    pub fn unlabeled_precision(self) -> f64 {
188        ratio(self.matched_unlabeled, self.predicted)
189    }
190
191    /// Unlabeled recall.
192    pub fn unlabeled_recall(self) -> f64 {
193        ratio(self.matched_unlabeled, self.gold)
194    }
195
196    /// Unlabeled F1.
197    pub fn unlabeled_f1(self) -> f64 {
198        f1(self.unlabeled_precision(), self.unlabeled_recall())
199    }
200}
201
202fn ratio(numerator: usize, denominator: usize) -> f64 {
203    if denominator == 0 {
204        1.0
205    } else {
206        numerator as f64 / denominator as f64
207    }
208}
209
210fn f1(precision: f64, recall: f64) -> f64 {
211    if precision + recall == 0.0 {
212        0.0
213    } else {
214        2.0 * precision * recall / (precision + recall)
215    }
216}
217
218/// Why a sentence was not scored.
219#[derive(Clone, Copy, Debug, PartialEq, Eq)]
220pub enum ParsevalSkip {
221    /// Gold and predicted trees have different normalized terminal counts.
222    LengthMismatch {
223        /// Predicted normalized terminal count.
224        predicted: usize,
225        /// Gold normalized terminal count.
226        gold: usize,
227    },
228    /// The normalized gold sentence exceeds `CUTOFF_LEN`.
229    Cutoff {
230        /// Gold normalized terminal count.
231        length: usize,
232        /// Configured cutoff.
233        cutoff: usize,
234    },
235}
236
237/// Compare two constituency trees after EVALB normalization.
238///
239/// Both trees are traversed and merged lazily in left-to-right postorder. Expected running time
240/// is linear in the two tree sizes; auxiliary memory is proportional to tree depth plus the
241/// largest group of constituents sharing one span.
242pub fn compare_trees(
243    predicted_arena: &TreeArena<String>,
244    predicted_root: Tree,
245    gold_arena: &TreeArena<String>,
246    gold_root: Tree,
247    params: &EvalbParams,
248) -> Result<ParsevalCounts, ParsevalSkip> {
249    let mut predicted = ConstituentIter::new(predicted_arena, predicted_root, params);
250    let mut gold = ConstituentIter::new(gold_arena, gold_root, params);
251    let counts = match_constituents(&mut predicted, &mut gold);
252
253    if predicted.words != gold.words {
254        return Err(ParsevalSkip::LengthMismatch {
255            predicted: predicted.words,
256            gold: gold.words,
257        });
258    }
259    if let Some(cutoff) = params.cutoff_len
260        && gold.words > cutoff
261    {
262        return Err(ParsevalSkip::Cutoff {
263            length: gold.words,
264            cutoff,
265        });
266    }
267
268    Ok(counts)
269}
270
271/// Count gold constituents for a failed parse, applying the cutoff if configured.
272pub fn count_gold(
273    gold_arena: &TreeArena<String>,
274    gold_root: Tree,
275    params: &EvalbParams,
276) -> Result<ParsevalCounts, ParsevalSkip> {
277    let mut gold = ConstituentIter::new(gold_arena, gold_root, params);
278    let gold_count = gold.by_ref().count();
279    if let Some(cutoff) = params.cutoff_len
280        && gold.words > cutoff
281    {
282        return Err(ParsevalSkip::Cutoff {
283            length: gold.words,
284            cutoff,
285        });
286    }
287    Ok(ParsevalCounts {
288        gold: gold_count,
289        ..ParsevalCounts::default()
290    })
291}
292
293#[derive(Clone, Copy, Debug)]
294struct Constituent<'a> {
295    start: usize,
296    end: usize,
297    label: &'a str,
298}
299
300struct ConstituentIter<'a> {
301    arena: &'a TreeArena<String>,
302    params: &'a EvalbParams,
303    stack: Vec<Frame>,
304    words: usize,
305}
306
307#[derive(Clone, Copy)]
308struct Frame {
309    node: Tree,
310    next_child: usize,
311    start: usize,
312}
313
314impl<'a> ConstituentIter<'a> {
315    fn new(arena: &'a TreeArena<String>, root: Tree, params: &'a EvalbParams) -> Self {
316        Self {
317            arena,
318            params,
319            stack: vec![Frame {
320                node: root,
321                next_child: 0,
322                start: 0,
323            }],
324            words: 0,
325        }
326    }
327}
328
329impl<'a> Iterator for ConstituentIter<'a> {
330    type Item = Constituent<'a>;
331
332    fn next(&mut self) -> Option<Self::Item> {
333        while let Some(frame) = self.stack.last_mut() {
334            let children = self.arena.get_children(frame.node);
335            if frame.next_child < children.len() {
336                let child = children[frame.next_child];
337                frame.next_child += 1;
338                self.stack.push(Frame {
339                    node: child,
340                    next_child: 0,
341                    start: self.words,
342                });
343                continue;
344            }
345
346            let frame = self.stack.pop().expect("stack is nonempty");
347            let children = self.arena.get_children(frame.node);
348            let label = self.arena.get_label(frame.node).as_str();
349            if children.is_empty() {
350                let parent_deletes_terminal = self.stack.last().is_some_and(|parent| {
351                    self.params
352                        .delete_labels
353                        .contains(self.arena.get_label(parent.node).as_str())
354                });
355                // Ordinary PTB trees represent terminals as words below a POS preterminal, so
356                // DELETE_LABEL applies to the parent. Alto's TreeWithArities PTB corpora omit
357                // words and use the POS tag itself as the leaf, so the same directive must also
358                // apply to the leaf label. Supporting both shapes keeps normalization invariant
359                // under omission of the word layer.
360                let leaf_label_deletes_terminal = self.params.delete_labels.contains(label);
361                if !parent_deletes_terminal
362                    && !leaf_label_deletes_terminal
363                    && !self.params.delete_words.contains(label)
364                {
365                    self.words += 1;
366                }
367            } else if !is_preterminal(self.arena, frame.node)
368                && self.words > frame.start
369                && !self.params.delete_labels.contains(label)
370            {
371                return Some(Constituent {
372                    start: frame.start,
373                    end: self.words,
374                    label: self.params.canonical_label(label),
375                });
376            }
377        }
378        None
379    }
380}
381
382fn is_preterminal(arena: &TreeArena<String>, node: Tree) -> bool {
383    let children = arena.get_children(node);
384    children.len() == 1 && arena.get_children(children[0]).is_empty()
385}
386
387fn match_constituents(
388    predicted: &mut ConstituentIter<'_>,
389    gold: &mut ConstituentIter<'_>,
390) -> ParsevalCounts {
391    let mut counts = ParsevalCounts::default();
392    let (mut predicted_item, mut gold_item) = (predicted.next(), gold.next());
393    let mut predicted_group: SmallVec<[Constituent<'_>; 8]> = SmallVec::new();
394    let mut gold_group: SmallVec<[Constituent<'_>; 8]> = SmallVec::new();
395
396    while let (Some(p), Some(g)) = (predicted_item, gold_item) {
397        match span_key(p).cmp(&span_key(g)) {
398            std::cmp::Ordering::Less => {
399                counts.predicted += 1;
400                predicted_item = predicted.next();
401                gold_item = Some(g);
402            }
403            std::cmp::Ordering::Greater => {
404                counts.gold += 1;
405                gold_item = gold.next();
406                predicted_item = Some(p);
407            }
408            std::cmp::Ordering::Equal => {
409                let span = (p.start, p.end);
410                predicted_group.clear();
411                gold_group.clear();
412                predicted_group.push(p);
413                gold_group.push(g);
414
415                predicted_item = predicted.next();
416                while predicted_item.is_some_and(|item| (item.start, item.end) == span) {
417                    predicted_group.push(predicted_item.take().expect("checked Some"));
418                    predicted_item = predicted.next();
419                }
420                gold_item = gold.next();
421                while gold_item.is_some_and(|item| (item.start, item.end) == span) {
422                    gold_group.push(gold_item.take().expect("checked Some"));
423                    gold_item = gold.next();
424                }
425
426                counts.predicted += predicted_group.len();
427                counts.gold += gold_group.len();
428                counts.matched_unlabeled += predicted_group.len().min(gold_group.len());
429                counts.matched_labeled +=
430                    match_label_multisets(predicted_group.as_slice(), gold_group.as_slice());
431            }
432        }
433    }
434
435    if predicted_item.is_some() {
436        counts.predicted += 1;
437    }
438    if gold_item.is_some() {
439        counts.gold += 1;
440    }
441    counts.predicted += predicted.count();
442    counts.gold += gold.count();
443    counts
444}
445
446fn span_key(item: Constituent<'_>) -> (usize, std::cmp::Reverse<usize>) {
447    (item.end, std::cmp::Reverse(item.start))
448}
449
450fn match_label_multisets(predicted: &[Constituent<'_>], gold: &[Constituent<'_>]) -> usize {
451    if predicted.len().max(gold.len()) <= 8 {
452        let mut used = [false; 8];
453        let mut matched = 0;
454        for p in predicted {
455            if let Some(index) = gold
456                .iter()
457                .enumerate()
458                .find_map(|(i, g)| (!used[i] && p.label == g.label).then_some(i))
459            {
460                used[index] = true;
461                matched += 1;
462            }
463        }
464        return matched;
465    }
466
467    let mut inventory: FxHashMap<&str, usize> = FxHashMap::default();
468    for item in predicted {
469        *inventory.entry(item.label).or_default() += 1;
470    }
471    let mut matched = 0;
472    for item in gold {
473        if let Some(remaining) = inventory.get_mut(item.label)
474            && *remaining > 0
475        {
476            *remaining -= 1;
477            matched += 1;
478        }
479    }
480    matched
481}
482
483#[cfg(test)]
484mod tests {
485    use super::*;
486    use packed_term_arena::parser::parse_tree;
487
488    fn tree(text: &str) -> (TreeArena<String>, Tree) {
489        let mut arena = TreeArena::new();
490        let root = parse_tree(&mut arena, text).unwrap();
491        (arena, root)
492    }
493
494    fn bare() -> EvalbParams {
495        EvalbParams::default()
496    }
497
498    #[test]
499    fn exact_match_scores_all_constituents() {
500        let (a1, r1) = tree("S(NP(DT(the), NN(cat)), VP(VBD(slept)))");
501        let (a2, r2) = tree("S(NP(DT(the), NN(cat)), VP(VBD(slept)))");
502        let counts = compare_trees(&a1, r1, &a2, r2, &bare()).unwrap();
503        assert_eq!(
504            counts,
505            ParsevalCounts {
506                predicted: 3,
507                gold: 3,
508                matched_labeled: 3,
509                matched_unlabeled: 3,
510            }
511        );
512    }
513
514    #[test]
515    fn labeled_and_unlabeled_matches_differ() {
516        let (pred, pr) = tree("S(X(NN(a), NN(b)))");
517        let (gold, gr) = tree("S(NP(NN(a), NN(b)))");
518        let counts = compare_trees(&pred, pr, &gold, gr, &bare()).unwrap();
519        assert_eq!(counts.matched_unlabeled, 2);
520        assert_eq!(counts.matched_labeled, 1);
521    }
522
523    #[test]
524    fn duplicate_unary_brackets_are_multisets() {
525        let (pred, pr) = tree("A(A(A(NN(x))))");
526        let (gold, gr) = tree("A(A(NN(x)))");
527        let counts = compare_trees(&pred, pr, &gold, gr, &bare()).unwrap();
528        assert_eq!(counts.predicted, 3);
529        assert_eq!(counts.gold, 2);
530        assert_eq!(counts.matched_labeled, 2);
531        assert_eq!(counts.matched_unlabeled, 2);
532    }
533
534    #[test]
535    fn deletion_and_equivalence_normalize_trees() {
536        let params =
537            EvalbParams::parse("DELETE_LABEL TOP -NONE-\nDELETE_WORD ,\nEQ_LABEL PRT ADVP\n")
538                .unwrap();
539        let (pred, pr) = tree("TOP(S(PRT(RP(up)), PUNC(',')))");
540        let (gold, gr) = tree("S(ADVP(RP(up)))");
541        let counts = compare_trees(&pred, pr, &gold, gr, &params).unwrap();
542        assert_eq!(counts.matched_labeled, 2);
543        assert_eq!(counts.matched_unlabeled, 2);
544    }
545
546    #[test]
547    fn collins_defaults_delete_root_and_punctuation() {
548        let params = EvalbParams::collins_ptb();
549        let (pred, pr) = tree("ROOT(S(NP(NN(a)), ','(','), VP(VB(b)), '.'('.')))");
550        let (gold, gr) = tree("S(NP(NN(a)), VP(VB(b)))");
551        assert_eq!(
552            compare_trees(&pred, pr, &gold, gr, &params).unwrap(),
553            ParsevalCounts {
554                predicted: 3,
555                gold: 3,
556                matched_labeled: 3,
557                matched_unlabeled: 3,
558            }
559        );
560    }
561
562    #[test]
563    fn deleted_preterminal_removes_its_terminal_from_spans() {
564        let params = EvalbParams::parse("DELETE_LABEL PUNC\n").unwrap();
565        let (pred, pr) = tree("S(NP(NN(a)), PUNC(','), VP(VB(b)))");
566        let (gold, gr) = tree("S(NP(NN(a)), VP(VB(b)))");
567        assert_eq!(
568            compare_trees(&pred, pr, &gold, gr, &params).unwrap(),
569            ParsevalCounts {
570                predicted: 3,
571                gold: 3,
572                matched_labeled: 3,
573                matched_unlabeled: 3,
574            }
575        );
576    }
577
578    #[test]
579    fn deleted_pos_leaf_is_removed_in_alto_tree_shape() {
580        let params = EvalbParams::collins_ptb();
581        let (pred, pr) = tree("S(NP(DT, NN), '.', VP(VB, RB))");
582        let (gold, gr) = tree("S(NP(DT, NN), VP(VB, RB))");
583        assert_eq!(
584            compare_trees(&pred, pr, &gold, gr, &params).unwrap(),
585            ParsevalCounts {
586                predicted: 3,
587                gold: 3,
588                matched_labeled: 3,
589                matched_unlabeled: 3,
590            }
591        );
592    }
593
594    #[test]
595    fn detects_length_mismatch_and_cutoff() {
596        let (short, sr) = tree("S(NN(a))");
597        let (long, lr) = tree("S(NN(a), NN(b))");
598        assert_eq!(
599            compare_trees(&short, sr, &long, lr, &bare()),
600            Err(ParsevalSkip::LengthMismatch {
601                predicted: 1,
602                gold: 2
603            })
604        );
605
606        let params = EvalbParams::parse("CUTOFF_LEN 1").unwrap();
607        assert_eq!(
608            count_gold(&long, lr, &params),
609            Err(ParsevalSkip::Cutoff {
610                length: 2,
611                cutoff: 1
612            })
613        );
614    }
615
616    #[test]
617    fn parameter_errors_include_line_numbers() {
618        let error = EvalbParams::parse("DELETE_LABEL TOP\nMYSTERY 1\n").unwrap_err();
619        assert_eq!(
620            error.to_string(),
621            "line 2: unsupported or malformed directive \"MYSTERY\""
622        );
623    }
624
625    #[test]
626    fn empty_denominators_follow_parseval_conventions() {
627        let counts = ParsevalCounts::default();
628        assert_eq!(counts.labeled_precision(), 1.0);
629        assert_eq!(counts.labeled_recall(), 1.0);
630        assert_eq!(counts.labeled_f1(), 1.0);
631    }
632}
rusty_alto/parseval.rs

rusty_alto/
parseval.rs
