Repository: qurator-spk/dinglehopper (language: python)

Issue:
only call `words_normalized` once
`words_normalized` should only be called once, since it is quite slow, which has a large effect now that the string matching is faster. On my laptop this achieves the following performance improvement:
Before:
```
[max@localhost dinglehopper]$ /usr/bin/time -f '\t%E real,\t%U user,\t%S sys,\t%M mmem' dinglehopper gt.txt frak2021_0.905_1587027_9141630.txt
	0:15.89 real,	9.61 user,	7.14 sys,	92704 mmem
```
After:
```
[max@localhost dinglehopper]$ /usr/bin/time -f '\t%E real,\t%U user,\t%S sys,\t%M mmem' dinglehopper gt.txt frak2021_0.905_1587027_9141630.txt
	0:12.56 real,	7.88 user,	5.56 sys,	92836 mmem
```

---
@mikegerber's task list:

- [x] Fix tests for this PR
- [x] Review error rate calculation (might also be faulty in edge cases on master. This produced NaN in test_cli_valid_json, check if it should have been infinity - according to our definition at least)
- [x] Review comment I made about the docstring 
- [x] Review RapidFuzz dependency. The one we have may be need an update for this. (tests succeed with RapidFuzz >= 3 in a fresh venv)
- [x] Review the whole PR again
- [x] Rebase/merge into master


Discussion / hints:

Fix patch:
diff --git a/qurator/dinglehopper/align.py b/qurator/dinglehopper/align.py
index cc96891..07cbc8f 100644
--- a/qurator/dinglehopper/align.py
+++ b/qurator/dinglehopper/align.py
@@ -1,7 +1,9 @@
+import math
+from math import ceil
+
 from .edit_distance import *
 from rapidfuzz.distance import Levenshtein
 
-
 def align(t1, t2):
     """Align text."""
     s1 = list(grapheme_clusters(unicodedata.normalize("NFC", t1)))
@@ -9,11 +11,27 @@ def align(t1, t2):
     return seq_align(s1, s2)
 
 
-def seq_align(s1, s2):
+def score_hint(er: float, n: int) -> int | None:
+    """Calculate RapidFuzz score hint for a given error rate and count.
+
+    Gives the score hint for the distance functions (= expected distance) or None if
+    the error rate is inf.
+    """
+    assert not math.isnan(er)
+    try:
+        score_hint = int(ceil(er * n))
+    except (OverflowError, ValueError):
+        # ceil(er * n) can be inf or NaN (for n == 0), so int() can throw an
+        # OverflowError and a ValueError.
+        score_hint = None
+    return score_hint
+
+
+def seq_align(s1, s2, score_hint=None):
     """Align general sequences."""
     s1 = list(s1)
     s2 = list(s2)
-    ops = Levenshtein.editops(s1, s2)
+    ops = Levenshtein.editops(s1, s2, score_hint=score_hint)
     i = 0
     j = 0
 
diff --git a/qurator/dinglehopper/character_error_rate.py b/qurator/dinglehopper/character_error_rate.py
index 0c3ef7d..3b8c0cc 100644
--- a/qurator/dinglehopper/character_error_rate.py
+++ b/qurator/dinglehopper/character_error_rate.py
@@ -1,5 +1,3 @@
-from __future__ import division
-
 import unicodedata
 from typing import Tuple
 
@@ -11,7 +9,9 @@
 
 
 @multimethod
-def character_error_rate_n(reference: str, compared: str) -> Tuple[float, int]:
+def character_error_rate_n(
+    reference: list[str], compared: list[str]
+) -> Tuple[float, int]:
     """
     Compute character error rate.
 
@@ -19,7 +19,7 @@ def character_error_rate_n(reference: str, compared: str) -> Tuple[float, int]:
     """
 
     d = distance(reference, compared)
-    n = len(list(grapheme_clusters(unicodedata.normalize("NFC", reference))))
+    n = len(reference)
 
     if d == 0:
         return 0, n
@@ -30,11 +30,20 @@ def character_error_rate_n(reference: str, compared: str) -> Tuple[float, int]:
     # XXX Should we really count newlines here?
 
 
+@multimethod
+def character_error_rate_n(reference: str, compared: str) -> Tuple[float, int]:
+    seq1 = list(grapheme_clusters(unicodedata.normalize("NFC", reference)))
+    seq2 = list(grapheme_clusters(unicodedata.normalize("NFC", compared)))
+    return character_error_rate_n(seq1, seq2)
+
+
 @multimethod
 def character_error_rate_n(
     reference: ExtractedText, compared: ExtractedText
 ) -> Tuple[float, int]:
-    return character_error_rate_n(reference.text, compared.text)
+    return character_error_rate_n(
+        reference.grapheme_clusters, compared.grapheme_clusters
+    )
 
 
 def character_error_rate(reference, compared) -> float:
diff --git a/qurator/dinglehopper/cli.py b/qurator/dinglehopper/cli.py
index 72d428d..4d4349c 100644
--- a/qurator/dinglehopper/cli.py
+++ b/qurator/dinglehopper/cli.py
@@ -3,18 +3,18 @@
 import click
 from jinja2 import Environment, FileSystemLoader
 from markupsafe import escape
-from uniseg.graphemecluster import grapheme_clusters
 from ocrd_utils import initLogging
+from math import ceil
 
 from .character_error_rate import character_error_rate_n
 from .word_error_rate import word_error_rate_n, words_normalized
-from .align import seq_align
+from .align import seq_align, score_hint
 from .extracted_text import ExtractedText
 from .ocr_files import extract
 from .config import Config
 
 
-def gen_diff_report(gt_in, ocr_in, css_prefix, joiner, none):
+def gen_diff_report(gt_in, ocr_in, css_prefix, joiner, none, score_hint=None):
     gtx = ""
     ocrx = ""
 
@@ -45,16 +45,15 @@ def format_thing(t, css_classes=None, id_=None):
     if isinstance(gt_in, ExtractedText):
         if not isinstance(ocr_in, ExtractedText):
             raise TypeError()
-        # XXX splitting should be done in ExtractedText
-        gt_things = list(grapheme_clusters(gt_in.text))
-        ocr_things = list(grapheme_clusters(ocr_in.text))
+        gt_things = gt_in.grapheme_clusters
+        ocr_things = ocr_in.grapheme_clusters
     else:
         gt_things = gt_in
         ocr_things = ocr_in
 
     g_pos = 0
     o_pos = 0
-    for k, (g, o) in enumerate(seq_align(gt_things, ocr_things)):
+    for k, (g, o) in enumerate(seq_align(gt_things, ocr_things, score_hint)):
         css_classes = None
         gt_id = None
         ocr_id = None
@@ -106,18 +105,19 @@ def process(gt, ocr, report_prefix, *, metrics=True, textequiv_level="region"):
 
     gt_text = extract(gt, textequiv_level=textequiv_level)
     ocr_text = extract(ocr, textequiv_level=textequiv_level)
+    gt_words = words_normalized(gt_text)
+    ocr_words = words_normalized(ocr_text)
 
     cer, n_characters = character_error_rate_n(gt_text, ocr_text)
-    wer, n_words = word_error_rate_n(gt_text, ocr_text)
-
     char_diff_report = gen_diff_report(
-        gt_text, ocr_text, css_prefix="c", joiner="", none="·"
+        gt_text, ocr_text, css_prefix="c", joiner="", none="·",
+        score_hint=score_hint(cer, n_characters)
     )
 
-    gt_words = words_normalized(gt_text)
-    ocr_words = words_normalized(ocr_text)
+    wer, n_words = word_error_rate_n(gt_words, ocr_words)
     word_diff_report = gen_diff_report(
-        gt_words, ocr_words, css_prefix="w", joiner=" ", none="⋯"
+        gt_words, ocr_words, css_prefix="w", joiner=" ", none="⋯",
+        score_hint=score_hint(wer, n_words)
     )
 
     env = Environment(
diff --git a/qurator/dinglehopper/cli_extract.py b/qurator/dinglehopper/cli_extract.py
index 0d4f713..9c51d34 100644
--- a/qurator/dinglehopper/cli_extract.py
+++ b/qurator/dinglehopper/cli_extract.py
@@ -1,9 +1,6 @@
-import os
-
 import click
 from ocrd_utils import initLogging
 
-from .extracted_text import ExtractedText
 from .ocr_files import extract
 
 
diff --git a/qurator/dinglehopper/cli_line_dirs.py b/qurator/dinglehopper/cli_line_dirs.py
index 4c07ce5..00478cb 100644
--- a/qurator/dinglehopper/cli_line_dirs.py
+++ b/qurator/dinglehopper/cli_line_dirs.py
@@ -1,19 +1,14 @@
 import os
-import sys
 import itertools
 
 import click
 from jinja2 import Environment, FileSystemLoader
-from markupsafe import escape
-from uniseg.graphemecluster import grapheme_clusters
 from ocrd_utils import initLogging
+from math import ceil
 
 from .character_error_rate import character_error_rate_n
 from .word_error_rate import word_error_rate_n, words_normalized
-from .align import seq_align
-from .extracted_text import ExtractedText
 from .ocr_files import plain_extract
-from .config import Config
 from .cli import gen_diff_report, json_float
 
 
@@ -32,7 +27,7 @@ def common_suffix(its):
 
 def removesuffix(text, suffix):
     if suffix and text.endswith(suffix):
-        return text[:-len(suffix)]
+        return text[: -len(suffix)]
     return text
 
 
@@ -52,7 +47,11 @@ def process(gt_dir, ocr_dir, report_prefix, *, metrics=True):
         ocr = removesuffix(gt, gt_suffix) + ocr_suffix
 
         gt_text = plain_extract(os.path.join(gt_dir, gt), include_filename_in_id=True)
-        ocr_text = plain_extract(os.path.join(ocr_dir, ocr), include_filename_in_id=True)
+        ocr_text = plain_extract(
+            os.path.join(ocr_dir, ocr), include_filename_in_id=True
+        )
+        gt_words = words_normalized(gt_text)
+        ocr_words = words_normalized(ocr_text)
 
         # Compute CER
         l_cer, l_n_characters = character_error_rate_n(gt_text, ocr_text)
@@ -60,11 +59,13 @@ def process(gt_dir, ocr_dir, report_prefix, *, metrics=True):
             cer, n_characters = l_cer, l_n_characters
         else:
             # Rolling update
-            cer = (cer * n_characters + l_cer * l_n_characters) / (n_characters + l_n_characters)
+            cer = (cer * n_characters + l_cer * l_n_characters) / (
+                n_characters + l_n_characters
+            )
             n_characters = n_characters + l_n_characters
 
         # Compute WER
-        l_wer, l_n_words = word_error_rate_n(gt_text, ocr_text)
+        l_wer, l_n_words = word_error_rate_n(gt_words, ocr_words)
         if wer is None:
             wer, n_words = l_wer, l_n_words
         else:
@@ -74,12 +75,12 @@ def process(gt_dir, ocr_dir, report_prefix, *, metrics=True):
 
         # Generate diff reports
         char_diff_report += gen_diff_report(
-            gt_text, ocr_text, css_prefix="l{0}-c".format(k), joiner="", none="·"
+            gt_text, ocr_text, css_prefix="l{0}-c".format(k), joiner="", none="·",
+            score_hint=score_hint(l_cer, l_n_characters)
         )
-        gt_words = words_normalized(gt_text)
-        ocr_words = words_normalized(ocr_text)
         word_diff_report += gen_diff_report(
-            gt_words, ocr_words, css_prefix="l{0}-w".format(k), joiner=" ", none="⋯"
+            gt_words, ocr_words, css_prefix="l{0}-w".format(k), joiner=" ", none="⋯",
+            score_hint=score_hint(l_wer, l_n_words)
         )
 
     env = Environment(
diff --git a/qurator/dinglehopper/edit_distance.py b/qurator/dinglehopper/edit_distance.py
index 24f6928..32ef354 100644
--- a/qurator/dinglehopper/edit_distance.py
+++ b/qurator/dinglehopper/edit_distance.py
@@ -1,17 +1,21 @@
-from __future__ import division, print_function
-
 import unicodedata
-from functools import partial, lru_cache
-from typing import Sequence, Tuple
 
-import numpy as np
 from multimethod import multimethod
 from uniseg.graphemecluster import grapheme_clusters
-from tqdm import tqdm
 from rapidfuzz.distance import Levenshtein
 
 from .extracted_text import ExtractedText
-from .config import Config
+
+
+@multimethod
+def distance(seq1: list[str], seq2: list[str]):
+    """Compute the Levenshtein edit distance between two lists of grapheme clusters.
+
+    This assumes that the grapheme clusters are already normalized.
+
+    Use distance(str, str) instead if you need to compare two Unicode strings.
+    """
+    return Levenshtein.distance(seq1, seq2)
 
 
 @multimethod
@@ -29,7 +33,7 @@ def distance(s1: str, s2: str):
 
 @multimethod
 def distance(s1: ExtractedText, s2: ExtractedText):
-    return distance(s1.text, s2.text)
+    return Levenshtein.distance(s1.grapheme_clusters, s2.grapheme_clusters)
 
 
 def editops(word1, word2):
diff --git a/qurator/dinglehopper/extracted_text.py b/qurator/dinglehopper/extracted_text.py
index 9703b6b..28678e4 100644
--- a/qurator/dinglehopper/extracted_text.py
+++ b/qurator/dinglehopper/extracted_text.py
@@ -1,4 +1,5 @@
 import enum
+import functools
 import re
 import unicodedata
 from contextlib import suppress
@@ -9,6 +10,7 @@
 import numpy as np
 from lxml import etree as ET
 from ocrd_utils import getLogger
+from uniseg.graphemecluster import grapheme_clusters
 
 
 class Normalization(enum.Enum):
@@ -133,20 +135,40 @@ def check(self, _, value):
     segments = attr.ib(type=Optional[list], converter=attr.converters.optional(list))
     joiner = attr.ib(type=Optional[str])
     _text = attr.ib(type=Optional[str])
+    _grapheme_clusters = attr.ib(type=Optional[list[str]])
 
     @segments.validator
     def check(self, _, value):
         if value is not None and self._text is not None:
             raise ValueError("Can't have both segments and text")
 
+    @joiner.validator
+    def check(self, _, value):
+        if self.segments is None:
+            if value is not None:
+                raise ValueError("Can't have joiner without segments to join")
+        if self.segments is not None:
+            if value not in ("", " ", "\n"):
+                raise ValueError(f"Unexcepted segment joiner value {repr(value)}")
+
     @_text.validator
     def check(self, _, value):
-        if value is not None and self.segments is not None:
+        if value is None:
+            return
+
+        if self.segments is not None:
             raise ValueError("Can't have both segments and text")
-        if value is not None and unicodedata.normalize("NFC", value) != value:
+        if unicodedata.normalize("NFC", value) != value:
             raise ValueError('String "{}" is not in NFC.'.format(value))
-        if value is not None and normalize(value, self.normalization) != value:
+        if normalize(value, self.normalization) != value:
             raise ValueError('String "{}" is not normalized.'.format(value))
+        if self._grapheme_clusters is None:
+            raise ValueError("Requires both text and grapheme clusters to be set")
+
+    @_grapheme_clusters.validator
+    def check(self, _, value):
+        if value is not None and self._text is None:
+            raise ValueError("Requires both text and grapheme clusters to be set")
 
     normalization = attr.ib(converter=Normalization, default=Normalization.NFC_SBB)
 
@@ -157,6 +179,35 @@ def text(self):
         else:
             return self.joiner.join(s.text for s in self.segments)
 
+    @functools.cached_property
+    def _joiner_grapheme_cluster(self):
+        """We need the joiner as a list of 0 or 1 grapheme clusters.
+
+        This property is cached.
+        """
+
+        if len(self.joiner) > 0:
+            joiner_grapheme_cluster = list(grapheme_clusters(self.joiner))
+            assert len(joiner_grapheme_cluster) == 1  # see joiner's check above
+        elif len(self.joiner) == 0:
+            joiner_grapheme_cluster = []
+        else:
+            joiner_grapheme_cluster = None
+
+        return joiner_grapheme_cluster
+
+    @property
+    def grapheme_clusters(self):
+        if self._text is not None:
+            return self._grapheme_clusters
+        else:
+            # TODO Test with text extracted at glyph level (joiner == "")
+            clusters = []
+            for seg in self.segments:
+                clusters += seg.grapheme_clusters + self._joiner_grapheme_cluster
+            clusters = clusters[:-1]
+            return clusters
+
     _segment_id_for_pos = None
 
     def segment_id_for_pos(self, pos):
@@ -197,7 +248,8 @@ def from_text_segment(cls, text_segment, nsmap, textequiv_level="region"):
                 # FIXME hardcoded SBB normalization
                 segment_text = normalize_sbb(segment_text)
             segment_text = segment_text or ""
-            return cls(segment_id, None, None, segment_text)
+            clusters = list(grapheme_clusters(segment_text))
+            return cls(segment_id, None, None, segment_text, clusters)
         else:
             # Recurse
             sub_localname = children_for_localname[localname]
@@ -212,12 +264,15 @@ def from_text_segment(cls, text_segment, nsmap, textequiv_level="region"):
                     )
                 )
             joiner = joiner_for_textequiv_level[sub_textequiv_level]
-            return cls(segment_id, segments, joiner, None)
+            return cls(segment_id, segments, joiner, None, None)
 
     @classmethod
     def from_str(cls, text, normalization=Normalization.NFC_SBB):
         normalized_text = normalize(text, normalization)
-        return cls(None, None, None, normalized_text, normalization=normalization)
+        clusters = list(grapheme_clusters(normalized_text))
+        return cls(
+            None, None, None, normalized_text, clusters, normalization=normalization
+        )
 
 
 def invert_dict(d):
diff --git a/qurator/dinglehopper/ocr_files.py b/qurator/dinglehopper/ocr_files.py
index 69f4df7..6384dfa 100644
--- a/qurator/dinglehopper/ocr_files.py
+++ b/qurator/dinglehopper/ocr_files.py
@@ -1,12 +1,10 @@
-from __future__ import division, print_function
-
 import os
 import sys
 from typing import Iterator
-from warnings import warn
 
 from lxml import etree as ET
 from lxml.etree import XMLSyntaxError
+from uniseg.graphemecluster import grapheme_clusters
 
 from .extracted_text import ExtractedText, normalize_sbb
 
@@ -32,13 +30,15 @@ def alto_extract_lines(tree: ET.ElementTree) -> Iterator[ExtractedText]:
             string.attrib.get("CONTENT")
             for string in line.iterfind("alto:String", namespaces=nsmap)
         )
-        yield ExtractedText(line_id, None, None, normalize_sbb(line_text))
+        normalized_text = normalize_sbb(line_text)
+        clusters = list(grapheme_clusters(normalized_text))
+        yield ExtractedText(line_id, None, None, normalized_text, clusters)
         # FIXME hardcoded SBB normalization
 
 
 def alto_extract(tree: ET.ElementTree) -> ExtractedText:
     """Extract text from the given ALTO ElementTree."""
-    return ExtractedText(None, list(alto_extract_lines(tree)), "\n", None)
+    return ExtractedText(None, list(alto_extract_lines(tree)), "\n", None, None)
 
 
 def alto_text(tree):
@@ -86,7 +86,7 @@ def page_extract(tree, *, textequiv_level="region"):
     # Filter empty region texts
     regions = [r for r in regions if r.text != ""]
 
-    return ExtractedText(None, regions, "\n", None)
+    return ExtractedText(None, regions, "\n", None, None)
 
 
 def extract_texts_from_reading_order_group(group, tree, nsmap, textequiv_level):
@@ -98,14 +98,18 @@ def extract_texts_from_reading_order_group(group, tree, nsmap, textequiv_level):
 
         ro_children = filter(lambda child: "index" in child.attrib.keys(), ro_children)
         ro_children = sorted(ro_children, key=lambda child: int(child.attrib["index"]))
-    elif ET.QName(group.tag).localname in ["UnorderedGroup","UnorderedGroupIndexed"]:
+    elif ET.QName(group.tag).localname in ["UnorderedGroup", "UnorderedGroupIndexed"]:
         ro_children = list(group)
     else:
         raise NotImplementedError
 
-
     for ro_child in ro_children:
-        if ET.QName(ro_child.tag).localname in ["OrderedGroup", "OrderedGroupIndexed", "UnorderedGroup", "UnorderedGroupIndexed"]:
+        if ET.QName(ro_child.tag).localname in [
+            "OrderedGroup",
+            "OrderedGroupIndexed",
+            "UnorderedGroup",
+            "UnorderedGroupIndexed",
+        ]:
             regions.extend(
                 extract_texts_from_reading_order_group(
                     ro_child, tree, nsmap, textequiv_level
@@ -133,17 +137,25 @@ def page_text(tree, *, textequiv_level="region"):
 
 def plain_extract(filename, include_filename_in_id=False):
     id_template = "{filename} - line {no}" if include_filename_in_id else "line {no}"
+
+    def make_segment(no, line):
+        normalized_text = normalize_sbb(line)
+        clusters = list(grapheme_clusters(normalized_text))
+        return ExtractedText(
+            id_template.format(filename=os.path.basename(filename), no=no),
+            None,
+            None,
+            normalized_text,
+            clusters,
+        )
+
     with open(filename, "r") as f:
         return ExtractedText(
             None,
-            [
-                ExtractedText(
-                    id_template.format(filename=os.path.basename(filename), no=no),
-                    None, None, normalize_sbb(line))
-                for no, line in enumerate(f.readlines())
-            ],
+            [make_segment(no, line) for no, line in enumerate(f.readlines())],
             "\n",
             None,
+            None,
         )
     # XXX hardcoded SBB normalization
 
diff --git a/qurator/dinglehopper/ocrd_cli.py b/qurator/dinglehopper/ocrd_cli.py
index 7c513e6..c5f79cd 100644
--- a/qurator/dinglehopper/ocrd_cli.py
+++ b/qurator/dinglehopper/ocrd_cli.py
@@ -33,7 +33,7 @@ def process(self):
         textequiv_level = self.parameter["textequiv_level"]
         gt_grp, ocr_grp = self.input_file_grp.split(",")
 
-        input_file_tuples = self.zip_input_files(on_error='abort')
+        input_file_tuples = self.zip_input_files(on_error="abort")
         for n, (gt_file, ocr_file) in enumerate(input_file_tuples):
             if not gt_file or not ocr_file:
                 # file/page was not found in this group
@@ -66,9 +66,9 @@ def process(self):
                 [".json", "application/json"],
             ]:
                 self.workspace.add_file(
-                    ID=file_id + report_suffix,
+                    file_id=file_id + report_suffix,
                     file_grp=self.output_file_grp,
-                    pageId=page_id,
+                    page_id=page_id,
                     mimetype=mimetype,
                     local_filename=report_prefix + report_suffix,
                 )
diff --git a/qurator/dinglehopper/word_error_rate.py b/qurator/dinglehopper/word_error_rate.py
index 8f0cc96..3b9ff5e 100644
--- a/qurator/dinglehopper/word_error_rate.py
+++ b/qurator/dinglehopper/word_error_rate.py
@@ -1,5 +1,3 @@
-from __future__ import division
-
 import unicodedata
 from typing import Tuple, Iterable
 from multimethod import multimethod
@@ -42,7 +40,6 @@ def words(s: str):
     if not word_break_patched:
         patch_word_break()
 
-
     # Check if c is an unwanted character, i.e. whitespace, punctuation, or similar
     def unwanted(c):
 
diff --git a/requirements.txt b/requirements.txt
index daf2b0f..9bce7c4 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -1,13 +1,13 @@
 click
 jinja2
 lxml
-uniseg
+uniseg >= 0.7.2
 numpy
 colorama
 MarkupSafe
 ocrd >= 2.20.1
 attrs
-multimethod == 1.3  # latest version to officially support Python 3.5
+multimethod >= 1.3
 tqdm
-rapidfuzz >= 2.4.2
+rapidfuzz >= 2.7.0
 six  # XXX workaround OCR-D/core#730


Test patch:
diff --git a/qurator/dinglehopper/tests/data/actevedef_718448162/mets.xml b/qurator/dinglehopper/tests/data/actevedef_718448162/mets.xml
index a6804ca..ed7c4f4 100644
--- a/qurator/dinglehopper/tests/data/actevedef_718448162/mets.xml
+++ b/qurator/dinglehopper/tests/data/actevedef_718448162/mets.xml
@@ -138,17 +138,17 @@
   <mets:fileSec>
     <mets:fileGrp USE="OCR-D-GT-PAGE">
       <mets:file MIMETYPE="application/xml" ID="OCR-D-GT-PAGE_00000024">
-        <mets:FLocat xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="OCR-D-GT-PAGE/00000024.page.xml"/>
+        <mets:FLocat xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="OCR-D-GT-PAGE/00000024.page.xml" LOCTYPE="OTHER" OTHERLOCTYPE="FILE"/>
       </mets:file>
     </mets:fileGrp>
     <mets:fileGrp USE="OCR-D-OCR-CALAMARI">
       <mets:file MIMETYPE="application/vnd.prima.page+xml" ID="OCR-D-OCR-CALAMARI_0001">
-        <mets:FLocat xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="OCR-D-OCR-CALAMARI/OCR-D-OCR-CALAMARI_0001.xml"/>
+        <mets:FLocat xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="OCR-D-OCR-CALAMARI/OCR-D-OCR-CALAMARI_0001.xml" LOCTYPE="OTHER" OTHERLOCTYPE="FILE"/>
       </mets:file>
     </mets:fileGrp>
     <mets:fileGrp USE="OCR-D-OCR-TESS">
       <mets:file MIMETYPE="application/vnd.prima.page+xml" ID="OCR-D-OCR-TESS_0001">
-        <mets:FLocat xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="OCR-D-OCR-TESS/OCR-D-OCR-TESS_0001.xml"/>
+        <mets:FLocat xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="OCR-D-OCR-TESS/OCR-D-OCR-TESS_0001.xml" LOCTYPE="OTHER" OTHERLOCTYPE="FILE"/>
       </mets:file>
     </mets:fileGrp>
   </mets:fileSec>
diff --git a/qurator/dinglehopper/tests/extracted_text_test.py b/qurator/dinglehopper/tests/extracted_text_test.py
index 8a81587..bc230d6 100644
--- a/qurator/dinglehopper/tests/extracted_text_test.py
+++ b/qurator/dinglehopper/tests/extracted_text_test.py
@@ -13,12 +13,13 @@ def test_text():
     test1 = ExtractedText(
         None,
         [
-            ExtractedText("s0", None, None, "foo"),
-            ExtractedText("s1", None, None, "bar"),
-            ExtractedText("s2", None, None, "bazinga"),
+            ExtractedText("s0", None, None, "foo", grapheme_clusters("foo")),
+            ExtractedText("s1", None, None, "bar", grapheme_clusters("bar")),
+            ExtractedText("s2", None, None, "bazinga", grapheme_clusters("bazinga")),
         ],
         " ",
         None,
+        None,
     )
 
     assert test1.text == "foo bar bazinga"
@@ -29,8 +30,12 @@ def test_text():
 
 def test_normalization_check():
     with pytest.raises(ValueError, match=r".*is not in NFC.*"):
-        ExtractedText("foo", None, None, unicodedata.normalize("NFD", "Schlyñ"))
-    assert ExtractedText("foo", None, None, unicodedata.normalize("NFC", "Schlyñ"))
+        ExtractedText("foo", None, None,
+                      unicodedata.normalize("NFD", "Schlyñ"),
+                      grapheme_clusters(unicodedata.normalize("NFD", "Schlyñ")))
+    assert ExtractedText("foo", None, None,
+                         unicodedata.normalize("NFC", "Schlyñ"),
+                         grapheme_clusters(unicodedata.normalize("NFC", "Schlyñ")))
 
 
 AlignmentElement = namedtuple("AlignmentElement", "left right left_id right_id")
@@ -47,25 +52,27 @@ def test_align():
     test1 = ExtractedText(
         None,
         [
-            ExtractedText("s0", None, None, "foo"),
-            ExtractedText("s1", None, None, "bar"),
-            ExtractedText("s2", None, None, "batzinga"),
+            ExtractedText("s0", None, None, "foo", grapheme_clusters("foo")),
+            ExtractedText("s1", None, None, "bar", grapheme_clusters("bar")),
+            ExtractedText("s2", None, None, "batzinga", grapheme_clusters("batzinga")),
         ],
         " ",
         None,
+        None,
     )
     test2 = ExtractedText(
         None,
         [
-            ExtractedText("x0", None, None, "foo"),
-            ExtractedText("x1", None, None, "bar"),
+            ExtractedText("x0", None, None, "foo", grapheme_clusters("foo")),
+            ExtractedText("x1", None, None, "bar", grapheme_clusters("bar")),
             # extra .
-            ExtractedText("x2", None, None, "."),
+            ExtractedText("x2", None, None, ".", grapheme_clusters(".")),
             # deletion + different grapheme cluster, m̃ also is two Python characters
-            ExtractedText("x3", None, None, "bazim̃ga"),
+            ExtractedText("x3", None, None, "bazim̃ga", grapheme_clusters("bazim̃ga")),
         ],
         " ",
         None,
+        None,
     )
 
     left_pos = 0
diff --git a/qurator/dinglehopper/tests/test_align.py b/qurator/dinglehopper/tests/test_align.py
index 96fc3c2..8e254e6 100644
--- a/qurator/dinglehopper/tests/test_align.py
+++ b/qurator/dinglehopper/tests/test_align.py
@@ -1,6 +1,7 @@
+import math
 import pytest
 from .util import unzip
-from .. import align, seq_align, distance
+from .. import align, seq_align, distance, score_hint
 
 
 def test_left_empty():
@@ -181,3 +182,7 @@ def __hash__(self):
 
     # Test __eq__ (i.e. is it a substitution or a similar string?)
     assert list(left)[0] == list(right)[0]
+
+def test_score_hint():
+    assert score_hint(0.5, 23) == 12  # int(ceil())
+    assert score_hint(math.inf, 12345) is None