Repository: mideind/Tokenizer (language: python)

Issue:
The tokenizer is slow when the input string is long.
When the input into tokenizer is very long, the time it takes to tokenise the string into sentence does not grow linearly with the input length as one might expect.

Test case to demonstrate the issue:
```
from time import time

import tokenizer
from tqdm import tqdm


def create_test_sentence(num_words, num_sentences):
    """Create a test string which contains num_words words and num_sentences sentences."""
    sentences = []
    for i in range(num_sentences):
        sentence = ["Hæ"] * num_words
        sentences.append(" ".join(sentence))
        sentences[-1] += "."
    return " ".join(sentences) + "\n"


def run_multi_sentence_test(num_words, num_sentences, num_lines):
    print(f"Running test with {num_words} words and {num_sentences} sentences in each line and {num_lines} lines.")
    start = time()
    test_data = list(create_test_sentence(num_words, num_sentences) for _ in range(num_lines))
    count = 0
    for line in tqdm(test_data):
        for sent in tokenizer.split_into_sentences(line, original=True):
            count += 1
    end = time()
    assert count == num_lines * num_sentences
    print("number of sentences encountered:", count)
    print("time taken:", end - start)
    print(f"{(end - start) / count:.6f} seconds per sentence")


num_words = 20
num_sentences = 40
num_lines = 300
run_multi_sentence_test(num_words, num_sentences, num_lines)
# Running test with 20 words and 40 sentences in each line and 300 lines.
# ...
# number of sentences encountered: 12000
# time taken: 17.760034322738647
# 0.001480 seconds per sentence

num_sentences = 1
num_lines = 300 * 40
run_multi_sentence_test(num_words, num_sentences, num_lines)
# Running test with 20 words and 1 sentences in each line and 12000 lines.
# ...
# number of sentences encountered: 12000
# time taken: 3.183797597885132
# 0.000265 seconds per sentence

num_sentences = 300 * 40
num_lines = 1
run_multi_sentence_test(num_words, num_sentences, num_lines)
# Running test with 20 words and 12000 sentences in each line and 1 lines.
# Does not return a value in 5 minutes.
```


Discussion / hints:
I ran a profiler on these test cases and the problem is in Tok.split(), see https://github.com/mideind/Tokenizer/blob/9cd18923b2a99776136ab8469ebf4bbaa1f2b91f/src/tokenizer/tokenizer.py#L208

I will submit a PR to fix this issue

Fix patch:
diff --git a/src/tokenizer/definitions.py b/src/tokenizer/definitions.py
index d0c44c3..5b2434e 100644
--- a/src/tokenizer/definitions.py
+++ b/src/tokenizer/definitions.py
@@ -139,6 +139,10 @@ class PersonNameTuple(NamedTuple):
 
 # Used for the first step of token splitting
 ROUGH_TOKEN_REGEX = re.compile(r"(\s*)([^\s]*)", re.UNICODE)
+# Constants for readability when using the ROUGH_TOKEN_REGEX
+ROUGH_TOKEN_REGEX_ENTIRE_MATCH = 0
+ROUGH_TOKEN_REGEX_WHITE_SPACE_GROUP = 1
+ROUGH_TOKEN_REGEX_TOKEN_GROUP = 2
 
 # Hyphens are normalized to '-'
 HYPHEN = "-"  # Normal hyphen
diff --git a/src/tokenizer/tokenizer.py b/src/tokenizer/tokenizer.py
index 51cf78d..5c54a12 100644
--- a/src/tokenizer/tokenizer.py
+++ b/src/tokenizer/tokenizer.py
@@ -40,30 +40,29 @@
 
 from typing import (
     Any,
+    Callable,
+    Deque,
+    FrozenSet,
+    Iterable,
+    Iterator,
     List,
     Mapping,
-    FrozenSet,
-    Callable,
+    Match,
     Optional,
-    Iterator,
-    Iterable,
     Tuple,
-    Deque,
-    Union,
-    Match,
-    TypeVar,
     Type,
+    TypeVar,
+    Union,
     cast,
 )
 
-import re
 import datetime
+import re
 import unicodedata  # type: ignore
 from collections import deque
 
-from .definitions import *
 from .abbrev import Abbreviations
-
+from .definitions import *
 
 _T = TypeVar("_T", bound="Tok")
 
@@ -72,6 +71,10 @@
 # normalized exclamation
 EXCLAMATIONS = frozenset(("!", "?"))
 
+# Global constants for readability
+SPAN_START = 0
+SPAN_END = 1
+
 
 class Tok:
 
@@ -100,6 +103,11 @@ def __init__(
         # This is required to preserve 'original' correctly when splitting.
         self.origin_spans: Optional[List[int]] = origin_spans
 
+    @classmethod
+    def from_txt(cls: Type[_T], txt: str) -> _T:
+        """Create a token from text"""
+        return cls(TOK.RAW, txt, None, txt, list(range(len(txt))))
+
     @classmethod
     def from_token(cls: Type[_T], t: "Tok") -> _T:
         """Create a new Tok instance by copying from a previously existing one"""
@@ -190,7 +198,13 @@ def split(self, pos: int) -> Tuple["Tok", "Tok"]:
 
         if self.origin_spans is not None and self.original is not None:
             if pos >= len(self.origin_spans):
-                l = Tok(self.kind, self.txt, self.val, self.original, self.origin_spans)
+                l = Tok(
+                    self.kind,
+                    self.txt,
+                    self.val,
+                    self.original,
+                    self.origin_spans,
+                )
                 r = Tok(self.kind, "", None, "", [])
             else:
                 l = Tok(
@@ -273,7 +287,11 @@ def substitute_all(self, old_str: str, new_char: str) -> None:
             self.substitute((i, i + len(old_str)), new_char)
 
     def concatenate(
-        self, other: "Tok", *, separator: str = "", metadata_from_other: bool = False
+        self,
+        other: "Tok",
+        *,
+        separator: str = "",
+        metadata_from_other: bool = False,
     ) -> "Tok":
         """Return a new token that consists of self with other
         concatenated to the end.
@@ -815,7 +833,9 @@ def End_Paragraph() -> Tok:
 
     @staticmethod
     def Begin_Sentence(
-        t: Optional[Tok] = None, num_parses: int = 0, err_index: Optional[int] = None
+        t: Optional[Tok] = None,
+        num_parses: int = 0,
+        err_index: Optional[int] = None,
     ) -> Tok:
         if t is None:
             return Tok(TOK.S_BEGIN, None, (num_parses, err_index))
@@ -1350,6 +1370,58 @@ def html_replacement(token: Tok) -> Tok:
     return token
 
 
+def generate_rough_tokens_from_txt(text: str) -> Iterator[Tok]:
+    """Generate rough tokens from a string."""
+    # Rough tokens are tokens that are separated by white space, i.e. the regex (\\s*)."""
+    # pos tracks the index in the text we have covered so far.
+    # We want to track pos, instead of treating text as a buffer,
+    # since that would lead to a lot of unnecessary copying.
+    pos = 0
+    while pos < len(text):
+        match = ROUGH_TOKEN_REGEX.match(text, pos)
+        assert match is not None
+        match_span = match.span(ROUGH_TOKEN_REGEX_ENTIRE_MATCH)
+        tok = Tok.from_txt(text[match_span[SPAN_START] : match_span[SPAN_END]])
+        pos = match_span[SPAN_END]
+        yield tok
+
+
+def generate_rough_tokens_from_tok(tok: Tok) -> Iterator[Tok]:
+    """Generate rough tokens from a token."""
+    # Some tokens might have whitespace characters after we replace composite unicode glyphs
+    # and replace HTML escapes.
+    # This function further splits those tokens into multiple tokens.
+    # Rough tokens are tokens that are separated by white space, i.e. the regex (\\s*)."""
+
+    def shift_span(span: Tuple[int, int], pos: int):
+        """Shift a span by a given amount"""
+        return (span[SPAN_START] + pos, span[SPAN_END] + pos)
+
+    text = tok.txt
+    # pos tracks the index in the text we have covered so far.
+    # We want to track pos, instead of treating text as a buffer,
+    # since that would lead to a lot of unnecessary copying.
+    pos = 0
+    while pos < len(text):
+        match = ROUGH_TOKEN_REGEX.match(text, pos)
+        assert match is not None
+        # Since the match indexes the text of the original token,
+        # we need to shift the indices so that they match the current token.
+        shifted_all_group_span = shift_span(
+            match.span(ROUGH_TOKEN_REGEX_ENTIRE_MATCH), -pos
+        )
+        shifted_white_space_span = shift_span(
+            match.span(ROUGH_TOKEN_REGEX_WHITE_SPACE_GROUP), -pos
+        )
+        # Then we split the current token using the shifted spans
+        small_tok, tok = tok.split(shifted_all_group_span[SPAN_END])
+        # Remove whitespace characters from the start of the token
+        small_tok.substitute(shifted_white_space_span, "")
+        # The pos is not shifted
+        pos = match.span(ROUGH_TOKEN_REGEX_ENTIRE_MATCH)[SPAN_END]
+        yield small_tok
+
+
 def generate_raw_tokens(
     text_or_gen: Union[str, Iterable[str]],
     replace_composite_glyphs: bool = True,
@@ -1425,30 +1497,33 @@ def generate_raw_tokens(
                         text = text[:-2]
                         # Postpone the yield until after the raw token loop
                         paragraph_end += 1
-                tok_big = Tok(TOK.RAW, text, None, text, list(range(len(text))))
-                if replace_composite_glyphs:
-                    # Replace composite glyphs with single code points
-                    tok_big = unicode_replacement(tok_big)
-                if replace_html_escapes:
-                    # Replace HTML escapes: '&aacute;' -> 'á'
-                    tok_big = html_replacement(tok_big)
-
-                while tok_big.txt != "":
-                    res = ROUGH_TOKEN_REGEX.match(tok_big.txt)
-                    assert res is not None
-                    tok, tok_big = tok_big.split(res.span(0)[1])
-
-                    # Remove whitespace from the start of the token
-                    tok.substitute(res.span(1), "")
-                    if tok.txt == "":
-                        # We have some trailing whitespace at the end of a 'big_text'
-                        # This can only be the last item in 'splits'.
-                        # See ROUGH_TOKEN_REGEX to convince yourself this is true.
-                        # Save this bit and attach it to the front of the next 'big_text'
-                        # since we don't want to yield a word token with empty text.
-                        saved = tok
-                    else:
-                        yield tok
+                for tok in generate_rough_tokens_from_txt(text):
+                    if replace_composite_glyphs:
+                        # Replace composite glyphs with single code points
+                        tok = unicode_replacement(tok)
+                    if replace_html_escapes:
+                        # Replace HTML escapes: '&aacute;' -> 'á'
+                        tok = html_replacement(tok)
+                    # The HTML escapes and unicode possibly contain whitespace characters
+                    # e.g. Em space '&#8195;' and non-breaking space '&nbsp;'
+                    # Here we split those tokens into multiple tokens.
+                    for small_tok in generate_rough_tokens_from_tok(tok):
+                        if small_tok.txt == "":
+                            # There was whitespace at the end of the last token.
+                            # We do not want to yield a token with empty text if possible.
+                            # We want to attach it in front of the next token, if there is one.
+                            # If there is no next token, we attach it in front of the next 'big_text'.
+                            # This will happen when:
+                            # 1. When 'text' has whitespace at the end
+                            # 2. When we have replaced a composite glyph or an HTML escape with whitespace.
+                            # See ROUGH_TOKEN_REGEX to convince yourself this is true.
+                            saved = small_tok
+                        else:
+                            if saved is not None:
+                                # Attach the saved token in front of the current token
+                                small_tok = saved.concatenate(small_tok)
+                                saved = None
+                            yield small_tok
 
                 while paragraph_end:
                     # Yield the postponed TOK.P_END token
@@ -1460,7 +1535,7 @@ def generate_raw_tokens(
                 yield TOK.Begin_Paragraph()
             else:
                 # Sentence split: 'text' is the split pattern
-                tok_split = Tok(TOK.RAW, text, None, text, list(range(len(text))))
+                tok_split = Tok.from_txt(text)
                 # This token should have no output text, but we still want to preserve
                 # the original text.
                 tok_split.substitute((0, len(text)), "")
@@ -1476,7 +1551,9 @@ def generate_raw_tokens(
 
 
 def could_be_end_of_sentence(
-    next_token: Tok, test_set: FrozenSet[int] = TOK.TEXT, multiplier: bool = False
+    next_token: Tok,
+    test_set: FrozenSet[int] = TOK.TEXT,
+    multiplier: bool = False,
 ) -> bool:
     """Return True if next_token could be ending the current sentence or
     starting the next one"""
@@ -2143,7 +2220,10 @@ def lookup(abbrev: str) -> Optional[List[BIN_Tuple]]:
                         a = "{0:.2f}".format(next_token.number).split(".")
                         h, m = int(a[0]), int(a[1])
                         token = TOK.Time(
-                            token.concatenate(next_token, separator=" "), h, m, 0
+                            token.concatenate(next_token, separator=" "),
+                            h,
+                            m,
+                            0,
                         )
                     else:
                         # next_token.kind is TOK.TIME
@@ -2279,7 +2359,9 @@ def lookup(abbrev: str) -> Optional[List[BIN_Tuple]]:
                     )
                 else:
                     token = TOK.Measurement(
-                        token.concatenate(next_token, separator=" "), unit, value
+                        token.concatenate(next_token, separator=" "),
+                        unit,
+                        value,
                     )
                 next_token = next(token_stream)
 
@@ -2478,9 +2560,10 @@ def parse_sentences(token_stream: Iterator[Tok]) -> Iterator[Tok]:
                         token = tok_end_sentence
                         in_sentence = False
                 if token.punctuation in END_OF_SENTENCE and not (
-                    token.punctuation
-                    == "…"  # Excluding sentences with ellipsis in the middle
-                    and not could_be_end_of_sentence(next_token)
+                    token.punctuation == "…"
+                    and not could_be_end_of_sentence(
+                        next_token
+                    )  # Excluding sentences with ellipsis in the middle
                 ):
                     # Combining punctuation ('??!!!')
                     while (
@@ -2588,7 +2671,8 @@ def parse_phrases_1(token_stream: Iterator[Tok]) -> Iterator[Tok]:
                     # the abbreviation "gr.", we assume that the only
                     # interpretation of the abbreviation is "grein".
                     next_token = TOK.Word(
-                        next_token, [BIN_Tuple("grein", 0, "kvk", "skst", "gr.", "-")]
+                        next_token,
+                        [BIN_Tuple("grein", 0, "kvk", "skst", "gr.", "-")],
                     )
 
                 month = month_for_token(next_token, True)
@@ -2883,7 +2967,8 @@ def parse_phrases_2(
                     if percentage is not None:
                         # We have '17 prósent': coalesce into a single token
                         token = TOK.Percent(
-                            token.concatenate(next_token, separator=" "), token.number
+                            token.concatenate(next_token, separator=" "),
+                            token.number,
                         )
                         # Eat the percent word token
                         next_token = next(token_stream)


Test patch:
diff --git a/test/test_tokenizer.py b/test/test_tokenizer.py
index dd8c028..dbf9822 100755
--- a/test/test_tokenizer.py
+++ b/test/test_tokenizer.py
@@ -31,12 +31,11 @@
 
 """
 
-from typing import Any, Iterable, Iterator, List, Union, Tuple, cast
+from typing import Any, Iterable, Iterator, List, Tuple, Union, cast
 
 import tokenizer as t
 from tokenizer.definitions import BIN_Tuple, ValType
 
-
 TOK = t.TOK
 Tok = t.Tok
 
@@ -2425,12 +2424,12 @@ def test_normalization() -> None:
     assert t.text_from_tokens(toklist) == 'Hann sagði : ,, Þú ert ágæt ??!? " .'
     assert t.normalized_text_from_tokens(toklist) == "Hann sagði : „ Þú ert ágæt ? “ ."
 
-    toklist = list(t.tokenize('Jón,, farðu út.'))
-    assert t.text_from_tokens(toklist) == 'Jón ,, farðu út .'
+    toklist = list(t.tokenize("Jón,, farðu út."))
+    assert t.text_from_tokens(toklist) == "Jón ,, farðu út ."
     assert t.normalized_text_from_tokens(toklist) == "Jón , farðu út ."
 
-    toklist = list(t.tokenize('Jón ,,farðu út.'))
-    assert t.text_from_tokens(toklist) == 'Jón ,, farðu út .'
+    toklist = list(t.tokenize("Jón ,,farðu út."))
+    assert t.text_from_tokens(toklist) == "Jón ,, farðu út ."
     assert t.normalized_text_from_tokens(toklist) == "Jón „ farðu út ."
 
     toklist = list(t.tokenize('Hann sagði: ,,Þú ert ágæt.....".'))
@@ -2442,7 +2441,6 @@ def test_normalization() -> None:
     assert t.normalized_text_from_tokens(toklist) == "Hann sagði : „ Þú ert ágæt … “ ."
 
 
-
 def test_abbr_at_eos() -> None:
     """Test that 'Örn.' is not treated as an abbreviation here"""
     toklist = list(
@@ -2490,7 +2488,15 @@ def test_html_escapes() -> None:
         Tok(kind=11002, txt=None, val=None),
     ]
     assert toklist == correct
-
+    toklist = list(
+        t.tokenize(
+            # En space and Em space
+            "Ég&#8194;fór &aacute; &lt;bömmer&gt;&#8195;og bor&shy;ðaði köku.",
+            replace_html_escapes=True,
+        )
+    )
+    toklist = strip_originals(toklist)
+    assert toklist == correct
     toklist = list(
         t.tokenize(
             "Ég fór &uacute;t og &#97;fs&#x61;kaði mig", replace_html_escapes=True
diff --git a/test/test_tokenizer_tok.py b/test/test_tokenizer_tok.py
index a583021..3ee1f46 100644
--- a/test/test_tokenizer_tok.py
+++ b/test/test_tokenizer_tok.py
@@ -35,6 +35,9 @@
 
 ACCENT = chr(769)
 UMLAUT = chr(776)
+SOFT_HYPHEN = chr(173)
+ZEROWIDTH_SPACE = chr(8203)
+ZEROWIDTH_NBSP = chr(65279)
 
 
 def test_split_simple() -> None:
@@ -98,7 +101,6 @@ def test_split_at_ends() -> None:
     assert l == Tok(TOK.RAW, "ab", None, "ab", [0, 1])
     assert r == Tok(TOK.RAW, "", None, "", [])
 
-
     t = Tok(TOK.RAW, "ab", None)
     l, r = t.split(0)
     assert l == Tok(TOK.RAW, "", None)
@@ -151,27 +153,71 @@ def test_substitute_bugfix_1() -> None:
     test_string = "xya" + ACCENT + "zu" + ACCENT + "w&aacute;o" + UMLAUT + "b"
     #              012    3         45    6         7890123456    7         8
     #              0123456789012345
-    t = Tok(kind=-1, txt=test_string, val=None, original=test_string, origin_spans=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18])
+    t = Tok(
+        kind=-1,
+        txt=test_string,
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
+    )
     t.substitute((2, 4), "á")
-    assert t == Tok(kind=-1, txt='xyázu' + ACCENT + 'w&aacute;o' + UMLAUT + 'b', val=None, original=test_string, origin_spans=[0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18])
+    assert t == Tok(
+        kind=-1,
+        txt="xyázu" + ACCENT + "w&aacute;o" + UMLAUT + "b",
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
+    )
 
     t.substitute((4, 6), "ú")
-    assert t == Tok(kind=-1, txt='xyázúw&aacute;o' + UMLAUT + 'b', val=None, original=test_string, origin_spans=[0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18])
+    assert t == Tok(
+        kind=-1,
+        txt="xyázúw&aacute;o" + UMLAUT + "b",
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
+    )
 
     t.substitute((14, 16), "ö")
-    assert t == Tok(kind=-1, txt='xyázúw&aacute;öb', val=None, original=test_string, origin_spans=[0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18])
-    
+    assert t == Tok(
+        kind=-1,
+        txt="xyázúw&aacute;öb",
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18],
+    )
+
     # bug was here
     t.substitute((6, 14), "á")
-    assert t == Tok(kind=-1, txt='xyázúwáöb', val=None, original=test_string, origin_spans=[0, 1, 2, 4, 5, 7, 8, 16, 18])
+    assert t == Tok(
+        kind=-1,
+        txt="xyázúwáöb",
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 4, 5, 7, 8, 16, 18],
+    )
 
 
 def test_multiple_substitutions() -> None:
-    t = Tok(TOK.RAW, "a&123b&456&789c", None, "a&123b&456&789c", [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14])
+    t = Tok(
+        TOK.RAW,
+        "a&123b&456&789c",
+        None,
+        "a&123b&456&789c",
+        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
+    )
     t.substitute((1, 5), "x")
-    assert t == Tok(TOK.RAW, "axb&456&789c", None, "a&123b&456&789c", [0, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14])
+    assert t == Tok(
+        TOK.RAW,
+        "axb&456&789c",
+        None,
+        "a&123b&456&789c",
+        [0, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
+    )
     t.substitute((3, 7), "y")
-    assert t == Tok(TOK.RAW, "axby&789c", None, "a&123b&456&789c", [0, 1, 5, 6, 10, 11, 12, 13, 14])
+    assert t == Tok(
+        TOK.RAW, "axby&789c", None, "a&123b&456&789c", [0, 1, 5, 6, 10, 11, 12, 13, 14]
+    )
     t.substitute((4, 8), "z")
     assert t == Tok(TOK.RAW, "axbyzc", None, "a&123b&456&789c", [0, 1, 5, 6, 10, 14])
 
@@ -208,7 +254,7 @@ def test_substitute_that_removes() -> None:
     t = Tok(TOK.RAW, "ab&123", None, "ab&123", [0, 1, 2, 3, 4, 5])
     t.substitute((2, 6), "")
     assert t == Tok(TOK.RAW, "ab", None, "ab&123", [0, 1])
-    
+
 
 def test_split_without_origin_tracking() -> None:
     t = Tok(TOK.RAW, "boat", None)
@@ -256,29 +302,156 @@ def test_html_escapes_with_origin_tracking() -> None:
     test_string = "xy&#x61;z&aacute;w&#97;b"
     tokens = list(tokenizer.generate_raw_tokens(test_string, replace_html_escapes=True))
     assert len(tokens) == 1
-    assert tokens[0] == Tok(kind=TOK.RAW, txt="xyazáwab", val=None, original=test_string, origin_spans=[0, 1, 2, 8, 9, 17, 18, 23])
+    assert tokens[0] == Tok(
+        kind=TOK.RAW,
+        txt="xyazáwab",
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 8, 9, 17, 18, 23],
+    )
+    # Note the space after &nbsp;
+    test_string = "Ég&nbsp; fór út."
+    # Here we show in comments when a new token starts in the string with "|" (inclusive).
+    #              | |         |
+    # We also show the character indices for each token.
+    #              0101234567890123
+    # And where the 'txt' is.
+    #              ^^       ^^^ ^^^
+    tokens = list(tokenizer.generate_raw_tokens(test_string, replace_html_escapes=True))
+    assert len(tokens) == 3
+    assert tokens == [
+        Tok(kind=TOK.RAW, txt="Ég", val=None, original="Ég", origin_spans=[0, 1]),
+        Tok(
+            kind=TOK.RAW,
+            txt="fór",
+            val=None,
+            original="&nbsp; fór",
+            origin_spans=[7, 8, 9],
+        ),
+        Tok(kind=TOK.RAW, txt="út.", val=None, original=" út.", origin_spans=[1, 2, 3]),
+    ]
+    test_string = "Ég&nbsp;&nbsp;fór út."
+    #              | |              |
+    #              010123456789012340123
+    #              ^^            ^^^ ^^^
+    tokens = list(tokenizer.generate_raw_tokens(test_string, replace_html_escapes=True))
+    assert len(tokens) == 3
+    assert tokens == [
+        Tok(kind=TOK.RAW, txt="Ég", val=None, original="Ég", origin_spans=[0, 1]),
+        Tok(
+            kind=TOK.RAW,
+            txt="fór",
+            val=None,
+            original="&nbsp;&nbsp;fór",
+            origin_spans=[12, 13, 14],
+        ),
+        Tok(kind=TOK.RAW, txt="út.", val=None, original=" út.", origin_spans=[1, 2, 3]),
+    ]
+    test_string = "Ég&nbsp;fór&nbsp;út."
+    #              | |        |
+    #              01012345678012345678
+    #              ^^      ^^^      ^^^
+    tokens = list(tokenizer.generate_raw_tokens(test_string, replace_html_escapes=True))
+    assert len(tokens) == 3
+    assert tokens == [
+        Tok(kind=TOK.RAW, txt="Ég", val=None, original="Ég", origin_spans=[0, 1]),
+        Tok(
+            kind=TOK.RAW,
+            txt="fór",
+            val=None,
+            original="&nbsp;fór",
+            origin_spans=[6, 7, 8],
+        ),
+        Tok(
+            kind=TOK.RAW,
+            txt="út.",
+            val=None,
+            original="&nbsp;út.",
+            origin_spans=[6, 7, 8],
+        ),
+    ]
+    test_string = "Ég fór út.&nbsp;"
+    #              | |   |
+    #              0101230123012345
+    #              ^^ ^^^ ^^^
+    tokens = list(tokenizer.generate_raw_tokens(test_string, replace_html_escapes=True))
+    assert len(tokens) == 4
+    assert tokens == [
+        Tok(kind=TOK.RAW, txt="Ég", val=None, original="Ég", origin_spans=[0, 1]),
+        Tok(kind=TOK.RAW, txt="fór", val=None, original=" fór", origin_spans=[1, 2, 3]),
+        Tok(kind=TOK.RAW, txt="út.", val=None, original=" út.", origin_spans=[1, 2, 3]),
+        Tok(kind=TOK.S_SPLIT, txt="", val=None, original="&nbsp;", origin_spans=[]),
+    ]
+    test_string = "&nbsp;Ég fór út."
+    #              |       |   |
+    #              0123456701230123
+    #                    ^^ ^^^ ^^^
+    tokens = list(tokenizer.generate_raw_tokens(test_string, replace_html_escapes=True))
+    assert len(tokens) == 3
+    assert tokens == [
+        Tok(kind=TOK.RAW, txt="Ég", val=None, original="&nbsp;Ég", origin_spans=[6, 7]),
+        Tok(kind=TOK.RAW, txt="fór", val=None, original=" fór", origin_spans=[1, 2, 3]),
+        Tok(kind=TOK.RAW, txt="út.", val=None, original=" út.", origin_spans=[1, 2, 3]),
+    ]
 
 
 def test_unicode_escapes_with_origin_tracking() -> None:
     test_string = "xya" + ACCENT + "zu" + ACCENT + "wo" + UMLAUT + "b"
-    tokens = list(tokenizer.generate_raw_tokens(test_string, replace_composite_glyphs=True))
+    tokens = list(
+        tokenizer.generate_raw_tokens(test_string, replace_composite_glyphs=True)
+    )
+    assert len(tokens) == 1
+    assert tokens[0] == Tok(
+        kind=TOK.RAW,
+        txt="xyázúwöb",
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 4, 5, 7, 8, 10],
+    )
+
+    test_string = (
+        "þetta" + ZEROWIDTH_SPACE + "er" + ZEROWIDTH_NBSP + "eitt" + SOFT_HYPHEN + "orð"
+    )
+    tokens = list(
+        tokenizer.generate_raw_tokens(test_string, replace_composite_glyphs=True)
+    )
     assert len(tokens) == 1
-    assert tokens[0] == Tok(kind=TOK.RAW, txt="xyázúwöb", val=None, original=test_string, origin_spans=[0, 1, 2, 4, 5, 7, 8, 10])
+    assert tokens[0] == Tok(
+        kind=TOK.RAW,
+        txt="þettaereittorð",
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 14, 15, 16],
+    )
 
 
 def test_unicode_escapes_that_are_removed() -> None:
     test_string = "a\xadb\xadc"
-    tokens = list(tokenizer.generate_raw_tokens(test_string, replace_composite_glyphs=True))
+    tokens = list(
+        tokenizer.generate_raw_tokens(test_string, replace_composite_glyphs=True)
+    )
     assert len(tokens) == 1
-    assert tokens[0] == Tok(kind=TOK.RAW, txt="abc", val=None, original=test_string, origin_spans=[0, 2, 4])
+    assert tokens[0] == Tok(
+        kind=TOK.RAW, txt="abc", val=None, original=test_string, origin_spans=[0, 2, 4]
+    )
 
 
 def test_html_unicode_mix() -> None:
     test_string = "xya" + ACCENT + "zu" + ACCENT + "w&aacute;o" + UMLAUT + "b"
     #              012    3         45    6         7890123456    7         8
-    tokens = list(tokenizer.generate_raw_tokens(test_string, replace_composite_glyphs=True, replace_html_escapes=True))
+    tokens = list(
+        tokenizer.generate_raw_tokens(
+            test_string, replace_composite_glyphs=True, replace_html_escapes=True
+        )
+    )
     assert len(tokens) == 1
-    assert tokens[0] == Tok(kind=TOK.RAW, txt="xyázúwáöb", val=None, original=test_string, origin_spans=[0, 1, 2, 4, 5, 7, 8, 16, 18])
+    assert tokens[0] == Tok(
+        kind=TOK.RAW,
+        txt="xyázúwáöb",
+        val=None,
+        original=test_string,
+        origin_spans=[0, 1, 2, 4, 5, 7, 8, 16, 18],
+    )
 
 
 def test_tok_concatenation() -> None:
@@ -286,7 +459,9 @@ def test_tok_concatenation() -> None:
     tok1 = Tok(TOK.RAW, str1, None, str1, list(range(len(str1))))
     str2 = "jklæ"
     tok2 = Tok(TOK.RAW, str2, None, str2, list(range(len(str1))))
-    assert tok1.concatenate(tok2) == Tok(TOK.RAW, str1+str2, None, str1+str2, list(range(len(str1+str2))))
+    assert tok1.concatenate(tok2) == Tok(
+        TOK.RAW, str1 + str2, None, str1 + str2, list(range(len(str1 + str2)))
+    )
 
     str1 = "abc"
     or1 = "&123&456&789"
@@ -294,7 +469,9 @@ def test_tok_concatenation() -> None:
     or2 = "&xx&yy&zz"
     tok1 = Tok(TOK.RAW, str1, None, or1, [0, 4, 8])
     tok2 = Tok(TOK.RAW, str2, None, or2, [0, 2, 4])
-    assert tok1.concatenate(tok2) == Tok(TOK.RAW, str1+str2, None, or1+or2, [0, 4, 8, 12, 14, 16])
+    assert tok1.concatenate(tok2) == Tok(
+        TOK.RAW, str1 + str2, None, or1 + or2, [0, 4, 8, 12, 14, 16]
+    )
 
 
 def test_tok_concatenation_with_separator() -> None:
@@ -303,7 +480,13 @@ def test_tok_concatenation_with_separator() -> None:
     str2 = "jklæ"
     tok2 = Tok(TOK.RAW, str2, None, str2, list(range(len(str1))))
     sep = "WOLOLO"
-    assert tok1.concatenate(tok2, separator=sep) == Tok(TOK.RAW, str1+sep+str2, None, str1+str2, [0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 5, 6, 7])
+    assert tok1.concatenate(tok2, separator=sep) == Tok(
+        TOK.RAW,
+        str1 + sep + str2,
+        None,
+        str1 + str2,
+        [0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 5, 6, 7],
+    )
 
     str1 = "abc"
     or1 = "&123&456&789"
@@ -312,7 +495,13 @@ def test_tok_concatenation_with_separator() -> None:
     tok1 = Tok(TOK.RAW, str1, None, or1, [0, 4, 8])
     tok2 = Tok(TOK.RAW, str2, None, or2, [0, 2, 4])
     sep = "WOLOLO"
-    assert tok1.concatenate(tok2, separator=sep) == Tok(TOK.RAW, str1+sep+str2, None, or1+or2, [0, 4, 8, 12, 12, 12, 12, 12, 12, 12, 14, 16])
+    assert tok1.concatenate(tok2, separator=sep) == Tok(
+        TOK.RAW,
+        str1 + sep + str2,
+        None,
+        or1 + or2,
+        [0, 4, 8, 12, 12, 12, 12, 12, 12, 12, 14, 16],
+    )
 
 
 def test_tok_substitute_all() -> None:
@@ -335,7 +524,13 @@ def test_tok_substitute_all() -> None:
     #    01234567890123456789
     t = Tok(TOK.RAW, s, None, s, list(range(len(s))))
     t.substitute_all("r", "")
-    assert t == Tok(TOK.RAW, "Þessi veðu lengi.", None, s, [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 13, 14, 15, 16, 18, 19])
+    assert t == Tok(
+        TOK.RAW,
+        "Þessi veðu lengi.",
+        None,
+        s,
+        [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 13, 14, 15, 16, 18, 19],
+    )
 
 
 def test_tok_substitute_longer() -> None:
@@ -353,3 +548,41 @@ def test_tok_substitute_longer() -> None:
     t = Tok(TOK.RAW, s, None, s, list(range(len(s))))
     t.substitute_longer((0, 1), "xyz")
     assert t == Tok(TOK.RAW, "xyzsdf", None, s, [1, 1, 1, 1, 2, 3])
+
+
+def test_tok_from_txt() -> None:
+    s = "asdf"
+    t = Tok.from_txt(s)
+    assert t == Tok(TOK.RAW, s, None, s, list(range(len(s))))
+
+    s = " asdf"
+    t = Tok.from_txt(s)
+    assert t == Tok(TOK.RAW, s, None, s, list(range(len(s))))
+
+    s = "asdf "
+    t = Tok.from_txt(s)
+    assert t == Tok(TOK.RAW, s, None, s, list(range(len(s))))
+
+    s = " asdf "
+    t = Tok.from_txt(s)
+    assert t == Tok(TOK.RAW, s, None, s, list(range(len(s))))
+
+    s = "Tok getur alveg verið heil setning."
+    t = Tok.from_txt(s)
+    assert t == Tok(TOK.RAW, s, None, s, list(range(len(s))))
+
+    s = "HTML&nbsp;&amp; er líka óbreytt"
+    t = Tok.from_txt(s)
+    assert t == Tok(TOK.RAW, s, None, s, list(range(len(s))))
+
+    s = (
+        "unicode"
+        + ZEROWIDTH_SPACE
+        + "er"
+        + ZEROWIDTH_NBSP
+        + "líka"
+        + SOFT_HYPHEN
+        + "óbreytt"
+    )
+    t = Tok.from_txt(s)
+    assert t == Tok(TOK.RAW, s, None, s, list(range(len(s))))