FTS5 xTokenize Byte Offset Challenges in Unicode Normalization

Issue Overview: FTS5 xTokenize Callback and Unicode Byte Offset Mismatch

The core issue revolves around the FTS5 (Full-Text Search) extension in SQLite, specifically the xTokenize callback function, which is responsible for tokenizing text during indexing. The xTokenize callback provides byte offsets into the original text for each token, which is crucial for auxiliary functions like snippet and highlight. However, this mechanism faces significant challenges when dealing with Unicode text, particularly when the text undergoes preprocessing such as Unicode normalization.

Unicode normalization transforms text into a standardized form, which can alter the byte representation of characters. For example, the character "é" can be represented as a single codepoint (U+00E9) or as a combination of two codepoints (U+0065 + U+0301). When normalization is applied, the byte offsets of tokens in the original text may no longer align with the normalized text. This misalignment complicates the task of mapping tokens back to their original byte offsets, especially for tokenizer implementations in languages like Python that rely on Unicode-aware processing.

The FTS5 engine internally counts tokens rather than bytes, meaning the byte offsets are largely ignored during indexing. However, the snippet and highlight auxiliary functions rely on these byte offsets to identify sentence boundaries and highlight text accurately. This creates a dilemma: tokenizers must provide accurate byte offsets for auxiliary functions to work correctly, but achieving this is non-trivial when Unicode normalization is involved.

The discussion highlights a specific example where a Python developer uses a regular expression to tokenize text, such as re.findall("\w+", "hello world 132 曑exam.ple𣊭"). This approach works well for tokenization but fails to account for byte offsets in the original text, particularly when dealing with multi-byte Unicode characters. The proposed solution involves concatenating tokens, converting them back to UTF-8, and performing a longest sequence match between the token bytes and the original text bytes. However, this approach is imperfect and may fail under certain conditions.

Possible Causes: Unicode Normalization and Tokenizer Limitations

The root cause of the issue lies in the interaction between Unicode normalization and the FTS5 tokenizer’s requirement for accurate byte offsets. Unicode normalization is a process that transforms text into a standardized form, ensuring that equivalent sequences of characters are represented consistently. While this is beneficial for text comparison and search, it introduces complexity when mapping tokens back to their original byte offsets.

When text is normalized, the byte representation of characters may change. For example, the character "é" can be represented as a single codepoint (U+00E9) or as a combination of two codepoints (U+0065 + U+0301). Normalization ensures that these representations are treated as equivalent, but it also means that the byte offsets of tokens in the normalized text may not correspond to the original text. This misalignment is particularly problematic for tokenizers that rely on Unicode-aware processing, as they must reconcile the normalized text with the original byte offsets.

Another contributing factor is the design of the FTS5 tokenizer interface. The xTokenize callback is required to provide byte offsets for each token, even though these offsets are largely ignored during indexing. This requirement places an unnecessary burden on tokenizer implementations, especially when dealing with Unicode text. Tokenizers must go to great lengths to map Unicode offsets back to the original byte offsets, often resorting to complex and error-prone techniques.

The discussion also highlights the limitations of existing tokenizer implementations. For example, some tokenizers build a list of the start of each codepoint in the UTF-8 text, attempting to map Unicode offsets back to byte offsets. However, this approach is not foolproof and can fail under certain conditions, such as when dealing with complex scripts or combining characters. The result is that tokenizers may provide incorrect byte offsets, leading to inaccuracies in the snippet and highlight functions.

Troubleshooting Steps, Solutions & Fixes: Addressing Byte Offset Challenges in FTS5

To address the challenges associated with byte offsets in FTS5, several approaches can be considered. These range from modifying the FTS5 engine to accommodate unknown byte offsets to improving tokenizer implementations to handle Unicode normalization more effectively.

1. Modifying FTS5 to Handle Unknown Byte Offsets:
One potential solution is to update the FTS5 engine to allow tokenizers to indicate that they do not know the byte offsets for a given token. This could be achieved by introducing a convention, such as providing negative values for the offset and length parameters in the xTokenize callback. When the FTS5 engine encounters these values, it could fall back to using the token stream for auxiliary functions like snippet and highlight.

This approach would relieve tokenizers of the burden of providing accurate byte offsets, particularly when dealing with Unicode normalization. However, it would require changes to the FTS5 engine and may impact the accuracy of auxiliary functions that rely on byte offsets. For example, the snippet function uses byte offsets to identify sentence boundaries, and falling back to the token stream may result in less precise results.

2. Improving Tokenizer Implementations:
Another approach is to improve tokenizer implementations to handle Unicode normalization more effectively. This could involve developing more sophisticated techniques for mapping Unicode offsets back to byte offsets, such as using a combination of character encoding libraries and custom logic.

For example, a tokenizer could use a library like ICU (International Components for Unicode) to perform Unicode normalization and track the mapping between normalized and original text. This would allow the tokenizer to provide accurate byte offsets even when the text has been normalized. However, this approach requires significant effort and may still be prone to errors in certain edge cases.

3. Concatenating Tokens and Performing Longest Sequence Matching:
A practical workaround, as suggested in the discussion, is to concatenate the tokens, convert them back to UTF-8, and perform a longest sequence match between the token bytes and the original text bytes. This approach involves the following steps:

• Tokenize the normalized text using a Unicode-aware tokenizer.
• Concatenate the tokens into a single string.
• Convert the concatenated string back to UTF-8.
• Perform a longest sequence match between the concatenated UTF-8 bytes and the original text bytes to determine the byte offsets.

While this approach is not perfect, it provides a reasonable approximation of the byte offsets and can be implemented with relative ease. However, it may fail in cases where the normalized text contains characters that are not present in the original text or when the tokenization process introduces ambiguities.

4. Leveraging FTS5_TOKENIZE_AUX for Auxiliary Functions:
The discussion also mentions that byte offsets are primarily required for the FTS5_TOKENIZE_AUX flag, which is used by auxiliary functions like snippet and highlight. This suggests that tokenizers could optimize their implementation to focus on providing accurate byte offsets only when necessary.

For example, a tokenizer could implement a two-phase approach: during the initial tokenization phase, it could ignore byte offsets and focus on generating tokens. When the FTS5_TOKENIZE_AUX flag is set, it could perform additional processing to determine the byte offsets. This approach would reduce the overhead of calculating byte offsets for every token and improve performance in cases where auxiliary functions are not used.

5. Exploring Alternative Tokenizer Designs:
Finally, it may be worth exploring alternative tokenizer designs that are better suited to handling Unicode normalization and byte offsets. For example, a tokenizer could be designed to operate directly on the original text, avoiding the need for normalization altogether. Alternatively, a tokenizer could be designed to work with a hybrid approach, combining Unicode-aware processing with byte-level accuracy.

In conclusion, the challenges associated with byte offsets in FTS5 are primarily caused by the interaction between Unicode normalization and the tokenizer’s requirement for accurate byte offsets. Addressing these challenges requires a combination of modifications to the FTS5 engine, improvements to tokenizer implementations, and practical workarounds. By carefully considering these approaches, it is possible to achieve a balance between accurate tokenization and reliable auxiliary function performance in FTS5.