String Models, Encoding & Core Operations

What Is a String? Alphabets, Languages, and Core Relations

Formally, an alphabet $\Sigma$ is a non-empty finite set of symbols (for example, $\Sigma = \{0,1\}$ or $\Sigma = \{a,b,c\}$). A string $S$ over $\Sigma$ is a finite sequence of symbols drawn from $\Sigma$. The length of $S$, denoted $\lvert S\rvert$, is the number of symbol positions in the sequence.

The unique string containing no symbols is the empty string, denoted $\varepsilon$ (or sometimes $\lambda$), and $\lvert\varepsilon\rvert = 0$. The set of all finite strings over $\Sigma$, including the empty string, is denoted $\Sigma^*$. The set of all non-empty finite strings is

$$ \Sigma^+ = \Sigma^* \setminus \{\varepsilon\}. $$

A language over $\Sigma$ is any set of strings over that alphabet; formally, $L \subseteq \Sigma^*$.

The fundamental binary operation on strings is concatenation. Given two strings $U = u_1 u_2 \dots u_m$ and $V = v_1 v_2 \dots v_n$, their concatenation $UV$ (or $U \cdot V$) is the string $u_1 \dots u_m v_1 \dots v_n$ of length $m + n$. Concatenation is associative—$(UV)W = U(VW)$—and has $\varepsilon$ as its identity element ($S\varepsilon = \varepsilon S = S$), making $\Sigma^*$ a free monoid under concatenation.

Structural relationships between strings form the foundation of pattern matching and text indexing:

• Prefix: A string $P$ is a prefix of $S$ if there exists a string $X \in \Sigma^*$ such that $S = PX$. If $X \neq \varepsilon$, then $P$ is a proper prefix.

• Suffix: A string $F$ is a suffix of $S$ if there exists a string $Y \in \Sigma^*$ such that $S = YF$. If $Y \neq \varepsilon$, then $F$ is a proper suffix.

• Border: A string $B$ is a border of $S$ if it is both a proper prefix and a proper suffix of $S$. Under the convention that empty borders are allowed, $\varepsilon$ is a trivial border of every non-empty string. For $S = \text{"abracadabra"}$, the borders are $\varepsilon$, $\text{"a"}$, and $\text{"abra"}$.

• Substring: A string $T$ is a substring (or factor) of $S$ if there exist strings $X,Y \in \Sigma^*$ such that $S = XTY$. Thus, a substring consists of contiguous positions in $S$. An occurrence of $T$ in $S$ is specified by a starting index $i$ such that $$ S[i \dots i+\lvert T\rvert-1] = T. $$ Two occurrences occupying the inclusive ranges $[i_1,j_1]$ and $[i_2,j_2]$ overlap if $$ \max(i_1,i_2) \leq \min(j_1,j_2). $$

• Subsequence: A string $W$ is a subsequence of $S$ if it can be obtained by deleting zero or more symbols from $S$ without changing the relative order of the remaining symbols. Substrings are contiguous; subsequences need not be.

• Reversal: If $S = s_1s_2\dots s_n$, its reversal is $$ S^R = s_ns_{n-1}\dots s_1. $$

• Rotation and cyclic equivalence: A string $R$ is a rotation (or cyclic shift) of $S$ if there exist strings $U,V \in \Sigma^*$ such that $S = UV$ and $R = VU$. Two strings are cyclically equivalent if one is a rotation of the other.

Ordering Strings: Lexicographic, Shortlex, and Colexicographic

Ordering strings requires total order relations built from a total order on the underlying alphabet $\Sigma$. Different orderings yield distinct topological properties and are suited for different computational tasks:

1. Lexicographic Order ($\le_{\text{lex}}$): The standard dictionary order. $U \le_{\text{lex}} V$ if $U$ is a prefix of $V$, or if at the first position $i$ where $U[i] \neq V[i]$, we have $U[i] \lt V[i]$ in $\Sigma$. Under lexicographic order, a shorter string is not necessarily smaller than a longer string (e.g., $\text{"b"} \gt_{\text{lex}} \text{"aaaa"}$). As a result, $\Sigma^*$ under lexicographic order is not well-founded over non-singleton alphabets because infinite descending chains like $\text{"b"} \gt \text{"ab"} \gt \text{"aab"} \gt \text{"aaab"} \dots$ can exist.
2. Shortlex (Radix / Length-Lexicographic) Order ($\le_{\text{shortlex}}$): Strings are compared first by length, and ties are broken lexicographically. $U \lt_{\text{shortlex}} V$ if $\lvert U\rvert \lt \lvert V\rvert$, or if $\lvert U\rvert = \lvert V\rvert$ and $U \lt_{\text{lex}} V$. Shortlex produces a well-ordering of $\Sigma^*$ where every string has a finite index in the enumeration.
3. Colexicographic Order ($\le_{\text{colex}}$): Strings are compared from right to left (i.e., comparing their reversals under lexicographic order). $U \le_{\text{colex}} V$ if $U^R \le_{\text{lex}} V^R$. Colexicographic ordering clusters strings sharing common suffixes, making it useful in combinatorics and backward string matching algorithms.

Bytes, Code Units, Code Points, and Grapheme Clusters

Modern text processing operates across four distinct abstraction layers. Conflating these layers leads to index out-of-bounds errors, corrupted multi-byte sequences, and broken user interfaces.

1. Bytes (8-bit Octets): The physical unit of storage and transmission. A single character may span 1 to 4 bytes depending on the encoding format.
2. Code Units: The fundamental storage unit of a specific character encoding scheme. For UTF-8, a code unit is an 8-bit byte; for UTF-16, a 16-bit word; for UTF-32, a 32-bit dword.
3. Unicode Code Points: Abstract numerical values assigned by the Unicode Standard, written as U+XXXX (ranging from U+0000 to U+10FFFF). UTF-32 represents each code point directly in one 32-bit code unit, whereas UTF-16 uses 1 or 2 code units (surrogate pairs) and UTF-8 uses 1 to 4 code units.
4. Extended Grapheme Clusters: What a human user perceives as a single "character" (e.g., e + ◌́ = é, or a base emoji combined with zero-width joiners and skin-tone modifiers). A single grapheme cluster may consist of multiple code points, code units, and bytes.

flowchart TD
SubGraph1["Layer 4: Extended Grapheme Cluster"] --> G1["'é' (User-Perceived Character)"]
G1 --> SubGraph2["Layer 3: Unicode Code Points"]
SubGraph2 --> CP1["U+0065 (LATIN SMALL LETTER E)"]
SubGraph2 --> CP2["U+0301 (COMBINING ACUTE ACCENT)"]
CP1 --> SubGraph3["Layer 2: UTF-16 Code Units"]
CP2 --> SubGraph3
SubGraph3 --> CU1["0x0065 (16-bit)"]
SubGraph3 --> CU2["0x0301 (16-bit)"]
CU1 --> SubGraph4["Layer 1: UTF-8 Bytes"]
CU2 --> SubGraph4
SubGraph4 --> B1["0x65"]
SubGraph4 --> B2["0xCC"]
SubGraph4 --> B3["0x81"]

Encodings and Unicode Normalization

Character encodings map sequence structures to abstract values. ASCII maps 0–127 to single bytes. UTF-8 uses variable-length encoding (1 to 4 bytes per code point), maintaining backward compatibility with ASCII. UTF-16 uses 2 or 4 bytes (1 or 2 16-bit code units, using surrogate pairs U+D800–U+DFFF for code points above U+FFFF). UTF-32 uses a fixed 4 bytes per code point.

Validation ensures byte streams obey structural invariants (e.g., UTF-8 continuation bytes matching 10xxxxxx). Overlong UTF-8 encodings (such as encoding U+0000 as 0xC0 0x80) are illegal for security reasons and must be rejected during validation.

Because Unicode permits equivalent text to be represented via different code point sequences, equivalence forms and normalization algorithms are necessary:

• Canonical Equivalence: Visual and functional identity (e.g., U+00E9 [é] vs U+0065 U+0301 [e + ◌́]).
• Compatibility Equivalence: Visual variation preserving semantic meaning (e.g., superscript 5 U+2075 vs standard 5 U+0035, or ligatures like fi U+FB01 vs f i).
• NFC (Normalization Form C): Canonical Decomposition followed by Canonical Composition. Replaces combining sequences with precomposed characters where available.
• NFD (Normalization Form D): Canonical Decomposition. Fully decomposes precomposed characters into base characters and combining marks, sorted by Canonical Combining Class (CCC).
• NFKC (Normalization Form KC): Compatibility Decomposition followed by Canonical Composition.
• NFKD (Normalization Form KD): Compatibility Decomposition.

Case folding removes case distinctions for case-insensitive matching (e.g., mapping German ß to ss), which differs from locale-aware uppercase/lowercase conversion (such as Turkish i $\to$ İ).

String Representations: Arrays, Builders, Ropes, and Piece Tables

Choosing an internal string representation involves trade-offs between contiguous memory layout, immutability, cache locality, and edit operation performance.

Core Operations, Complexity, and Correctness Hazards

Implementing string operations requires attention to encoding boundaries, non-copying views, and edge cases.

import unicodedata
from typing import List, Generator

class StringView:
    """A non-copying slice view over a underlying sequence."""
    __slots__ = ('_data', '_start', '_end')

    def __init__(self, data: str, start: int = 0, end: int = None):
        self._data = data
        self._start = max(0, start)
        self._end = len(data) if end is None else min(len(data), end)
        if self._start > self._end:
            self._start = self._end

    def __len__(self) -> int:
        return self._end - self._start

    def __getitem__(self, idx: int) -> str:
        if isinstance(idx, slice):
            s = self._start + (idx.start or 0)
            e = self._start + (idx.stop if idx.stop is not None else len(self))
            return StringView(self._data, max(self._start, s), min(self._end, e))
        if idx < 0:
            idx += len(self)
        if idx < 0 or idx >= len(self):
            raise IndexError("StringView index out of range")
        return self._data[self._start + idx]

    def __str__(self) -> str:
        return self._data[self._start:self._end]

def get_grapheme_clusters(text: str) -> List[str]:
    """
    Primitive grapheme cluster splitter handling basic combining character sequences.
    For production environments, use standard regex (\\X) or the unicodedata library.
    """
    normalized = unicodedata.normalize('NFD', text)
    clusters = []
    for char in normalized:
        # Check if character is a combining mark (General Category 'M*')
        if unicodedata.category(char).startswith('M') and clusters:
            clusters[-1] += char
        else:
            clusters.append(char)
    # Re-normalize individual clusters back to NFC
    return [unicodedata.normalize('NFC', c) for c in clusters]

def safe_grapheme_reversal(text: str) -> str:
    """Reverses a string while preserving grapheme clusters and combining marks."""
    clusters = get_grapheme_clusters(text)
    return "".join(reversed(clusters))

def safe_rotation(text: str, k: int) -> str:
    """Rotates grapheme clusters by k positions to the left in O(N) time and O(N) space."""
    clusters = get_grapheme_clusters(text)
    n = len(clusters)
    if n == 0:
        return ""
    k = k % n
    return "".join(clusters[k:] + clusters[:k])

def normalization_equal(s1: str, s2: str, form: str = 'NFC') -> bool:
    """Performs Unicode normalization-aware equality check."""
    return unicodedata.normalize(form, s1) == unicodedata.normalize(form, s2)

#Verification / Demonstration execution
if __name__ == "__main__":
    sample = "Café ☕️"

    # Non-copying view demo
    view = StringView(sample, 0, 4)
    print(f"View slice: '{view}' (Length: {len(view)})")

    # Safe grapheme reversal demo
    combined_str = "e\u0301" # 'e' + combining acute accent = é
    reversed_str = safe_grapheme_reversal(combined_str)
    print(f"Reversed '{combined_str}' -> '{reversed_str}' (Equal code units: {combined_str == reversed_str})")

    # Rotation demo
    rot = safe_rotation("abcde", 2)
    print(f"Rotated 'abcde' by 2: '{rot}'")

    # Normalization check demo
    norm_a = "Café"
    norm_b = "Cafe\u0301"
    print(f"Naive Equal: {norm_a == norm_b}")
    print(f"NFC Equal:   {normalization_equal(norm_a, norm_b)}")