StringZilla 🦖

由于字符串操作的低效，每年至少浪费了1亿美元。一个典型的代码库逐字符处理字符串，导致分支和数据依赖过多，忽略了90%的现代CPU的潜力。LibC是不同的。它试图利用SIMD指令来提升一些操作，通常被高级语言、运行时和数据库使用。但它并不完美。1️⃣ 首先，即使在包括超过十亿64位ARM CPU的常见硬件上，像 strstr 和 memmem 这样的常用函数也只能达到CPU吞吐量的1/3。2️⃣ 第二，SIMD的覆盖率不一致：正向扫描的加速并不能保证反向顺序搜索的速度。3️⃣ 最后，大多数高级语言并不能总是使用LibC，因为字符串通常不是NULL终止的，或者字符串中可能包含Unicode“零”字符。这就是为什么需要StringZilla的原因。为了提供可预测的高性能，可移植到任何现代平台、操作系统和编程语言。

StringZilla是字符串库中的GodZilla，使用SIMD和SWAR来加速现代CPU上的字符串操作。它比C、C++、Python和其他语言中的默认甚至其他SIMD加速字符串库快高达10倍，同时具有广泛的功能。它能够加速精确和模糊字符串匹配、编辑距离计算、排序、延迟评估的范围以避免内存分配，甚至随机字符串生成器。

• 🐂 C : 将LibC的<string.h>升级到<stringzilla.h>在C 99中
• 🐉 C++: 将STL的<string>升级到<stringzilla.hpp>在C++ 11中
• 🐍 Python: 将你的str升级到更快的Str
• 🍎 Swift: 使用String+StringZilla扩展
• 🦀 Rust: 使用StringZilla traits crate
• 🐚 Shell: 使用sz_前缀加速常见的CLI工具
• 📚 研究者？跳转到算法 & 设计决策
• 💡 想要贡献？寻找"good first issues"
• 🤝 并查看指南以设置环境
• 想要更多的绑定或功能？让我知道！

这是为谁准备的？

• 为数据工程师解析大型数据集，如CommonCrawl、RedPajama或LAION。
• 为软件工程师优化其应用程序和服务的字符串。
• 为寻找USearch的编辑距离的生物信息学家和搜索工程师。
• 为DBMS开发者，优化LIKE、ORDER BY和GROUP BY操作。
• 为需要SWAR基准的字符串处理功能的硬件设计师。
• 为学习SIMD/SWAR应用程序到非数据并行操作的学生。

性能

StringZilla 具有大量功能，其中大部分在 C、C++、Python 和其他语言的基准测试中得到覆盖。您可以在 ./scripts 目录中找到这些功能，使用说明列在 CONTRIBUTING.md 文件中。值得注意的是，如果 CPU 支持错位加载，即使是 64 位 SWAR 后端也比标准库更快。

大多数基准测试都是在 1 GB 的英语文本语料库上进行的，平均单词长度为 6 个字符。代码使用 GCC 12 编译，使用 glibc v2.35。基准测试在基于 Arm 的 Graviton3 AWS c7g 实例和 r7iz Intel Sapphire Rapids 上进行。大多数现代 Arm-based 64 位 CPU 将具有类似的相对速度提升。x86 CPU 之间的差异将更大。 ¹ 与其他库不同，LibC 需要字符串以 NULL 结尾。 ² ASCII 集中的 6 个空格字符是： \t\n\v\f\r。Python 和其他标准库都有针对这些字符的特殊函数。 ³ 大多数 Python 字符串库也用 C 实现。 ⁴ 与 BioPython 的其余部分不同，对齐分数的计算是用 C 实现的。 ⁵ 所有模运算都使用 uint8_t 进行，以便为编译器提供更多的优化机会。C++ STL 和 StringZilla 基准测试使用 64 位 Mersenne Twister 作为生成器。对于 C、C++ 和 StringZilla，使用原地更新字符串。在 Python 中，每个字符串都必须作为新对象分配，这使其不够公平。 ⁶ 与流行观点相反，Python 的默认 sorted 函数比 C 和 C++ 标准库更快。这在大型字符串列表或元组中有效，但一旦需要更复杂的逻辑，如按字符串键对字典进行排序，或生成“排序顺序”排列，就会失败。后者在数据库引擎中非常常见，最类似于 numpy.argsort。当前的 StringZilla 解决方案至少可以快 4 倍，而不会损失一般性。

功能

StringZilla 与大多数现代 CPU 兼容，并提供广泛的功能。

• 支持小端和大端架构。
• 支持32位和64位硬件架构。
• 兼容ASCII和UTF-8编码。

并非所有功能都在所有绑定中可用。如果您需要尚未实现的功能，请考虑贡献。

🌳部分在生产中使用。🧐部分处于测试阶段。🚧部分正在积极开发中，可能在后续版本中出现问题。✅已实现。⚪在考虑中。❌未打算实现。

快速开始：Python 🐍

Python绑定可在PyPI上获得，并可以使用pip安装。您可以使用以下命令立即检查已安装的版本和使用的硬件功能：

pip install stringzilla
python -c "import stringzilla; print(stringzilla.__version__)"
python -c "import stringzilla; print(stringzilla.__capabilities__)"

基本用法

如果您曾经使用过Python的str、bytes、bytearray、memoryview类，您就会知道期待什么。StringZilla的Str类是这两个类的混合体，提供了类似于str的接口，用于字节数组。

from stringzilla import Str, File

text_from_str = Str('some-string') # no copies, just a view
text_from_file = Str(File('some-file.txt')) # memory-mapped file

File类将文件从持久性内存中映射到内存中，而不将其副本加载到RAM中。该文件的 contents 将保持不变，并且映射可以被多个Python进程同时共享。一个标准的预处理数据集用例是将大型文本数据集（如Common Crawl）映射到内存中，生成子进程，并在它们之间分配工作。

基本操作

• 长度：len(text) -> int
• 索引：text[42] -> str
• 切片：text[42:46] -> Str
• 子字符串检查：'substring' in text -> bool
• 哈希：hash(text) -> int
• 字符串转换：str(text) -> str

高级操作

import sys

x: bool = text.contains('substring', start=0, end=sys.maxsize)
x: int = text.find('substring', start=0, end=sys.maxsize)
x: int = text.count('substring', start=0, end=sys.maxsize, allowoverlap=False)
x: str = text.decode(encoding='utf-8', errors='strict')
x: Strs = text.split(separator=' ', maxsplit=sys.maxsize, keepseparator=False)
x: Strs = text.rsplit(separator=' ', maxsplit=sys.maxsize, keepseparator=False)
x: Strs = text.splitlines(keeplinebreaks=False, maxsplit=sys.maxsize)

需要注意的是，最后一个函数的行为与Python的str.splitlines略有不同。本地版本匹配\n、\r、\v或\x0b、\f或\x0c、\x1c、\x1d、\x1e、\x85、\r\n、\u2028、\u2029，包括3个双字节长度的字符。StringZilla版本仅匹配\n、\v、\f、\r、\x1c、\x1d、\x1e、\x85，避免了双字节长度的字符。

字符集操作

Python 字符串原生不支持字符集操作。这迫使人们使用正则表达式，这既慢又难以阅读。为了避免使用 re.finditer，StringZilla 提供以下接口

x: int = text.find_first_of('chars', start=0, end=sys.maxsize)
x: int = text.find_last_of('chars', start=0, end=sys.maxsize)
x: int = text.find_first_not_of('chars', start=0, end=sys.maxsize)
x: int = text.find_last_not_of('chars', start=0, end=sys.maxsize)
x: Strs = text.split_charset(separator='chars', maxsplit=sys.maxsize, keepseparator=False)
x: Strs = text.rsplit_charset(separator='chars', maxsplit=sys.maxsize, keepseparator=False)

集合级操作

一旦分割成 Strs 对象，您就可以对切片进行排序、洗牌和重新组织，而内存占用最小。如果所有块都位于连续的内存区域中，内存开销可以低至每个块 4 字节。

lines: Strs = text.split(separator='\n') # 4 bytes per line overhead for under 4 GB of text
batch: Strs = lines.sample(seed=42) # 10x faster than `random.choices`
lines.shuffle(seed=42) # or shuffle all lines in place and shard with slices
# WIP: lines.sort() # explodes to 16 bytes per line overhead for any length text
# WIP: sorted_order: tuple = lines.argsort() # similar to `numpy.argsort`

在 RedPajama 上工作，处理 200 亿个标注的英文文档，只需要 160 GB 的 RAM，而不是千兆字节。一旦加载，数据将被内存映射，可以在多个 Python 进程之间重复使用而无需复制。当然，您还可以使用切片来导航数据集并在多个工作者之间分片。

lines[::3] # every third line
lines[1::1] # every odd line
lines[:-100:-1] # last 100 lines in reverse order

迭代器和内存效率

Python 的操作，如 split() 和 readlines() 会立即创建一个复制的部分列表。对于大型数据集来说，这可能会非常低效。StringZilla 通过将现有内存区域视为子字符串来节省大量内存，但使用懒加载迭代器可以节省更多的内存。

x: SplitIterator[Str] = text.split_iter(separator=' ', keepseparator=False)
x: SplitIterator[Str] = text.rsplit_iter(separator=' ', keepseparator=False)
x: SplitIterator[Str] = text.split_charset_iter(separator='chars', keepseparator=False)
x: SplitIterator[Str] = text.rsplit_charset_iter(separator='chars', keepseparator=False)

StringZilla 的内存效率可以比原生 Python 类提高 10 倍以上，特别是在分词方面。使用懒操作，它实际上变得免费。

import stringzilla as sz
%load_ext memory_profiler

text = open("enwik9.txt", "r").read() # 1 GB, mean word length 7.73 bytes
%memit text.split() # increment: 8670.12 MiB (152 ms)
%memit sz.split(text) # increment: 530.75 MiB (25 ms)
%memit sum(1 for _ in sz.split_iter(text)) # increment: 0.00 MiB

低级 Python API

除了在 Str 和 Strs 类上调用方法外，还可以直接在 str 和 bytes 实例上调用全局函数。假设 StringZilla CPython 绑定实现 没有使用任何中间工具，如 SWIG 或 PyBind，调用延迟应与原生类相似。

import stringzilla as sz

contains: bool = sz.contains("haystack", "needle", start=0, end=sys.maxsize)
offset: int = sz.find("haystack", "needle", start=0, end=sys.maxsize)
count: int = sz.count("haystack", "needle", start=0, end=sys.maxsize, allowoverlap=False)

编辑距离

assert sz.edit_distance("apple", "aple") == 1 # skip one ASCII character
assert sz.edit_distance("αβγδ", "αγδ") == 2 # skip two bytes forming one rune
assert sz.edit_distance_unicode("αβγδ", "αγδ") == 1 # one unicode rune

一些 Python 库提供编辑距离计算。大多数都是用 C 实现的，但并不总是像 StringZilla 那么快。以大约 10,000 个字符长的 1,000 个蛋白质为例，只需计算 100 个距离

• JellyFish: 62.3s
• EditDistance: 32.9s
• StringZilla: 0.8s

此外，您还可以传递自定义替换矩阵来计算 Needleman-Wunsch 对齐得分。这项任务在生物信息学和计算生物学中非常常见。它被 BioPython 原生支持，并且其 BLOSUM 矩阵可以转换为 StringZilla 的格式。或者，您可以使用 NumPy 构建任意 256x256 的成本矩阵。根据参数的不同，结果可能等于负 Levenshtein 距离。

import numpy as np
import stringzilla as sz

costs = np.zeros((256, 256), dtype=np.int8)
costs.fill(-1)
np.fill_diagonal(costs, 0)

assert sz.alignment_score("first", "second", substitution_matrix=costs, gap_score=-1) == -sz.edit_distance(a, b)

使用与 Levenshtein 距离基准测试相同的蛋白质

• BioPython: 25.8s
• StringZilla: 7.8s

import numpy as np
from Bio import Align
from Bio.Align import substitution_matrices

aligner = Align.PairwiseAligner()
aligner.substitution_matrix = substitution_matrices.load("BLOSUM62")
aligner.open_gap_score = 1
aligner.extend_gap_score = 1

# Convert the matrix to NumPy
subs_packed = np.array(aligner.substitution_matrix).astype(np.int8)
subs_reconstructed = np.zeros((256, 256), dtype=np.int8)

# Initialize all banned characters to a the largest possible penalty
subs_reconstructed.fill(127)
for packed_row, packed_row_aminoacid in enumerate(aligner.substitution_matrix.alphabet):
    for packed_column, packed_column_aminoacid in enumerate(aligner.substitution_matrix.alphabet):
        reconstructed_row = ord(packed_row_aminoacid)
        reconstructed_column = ord(packed_column_aminoacid)
        subs_reconstructed[reconstructed_row, reconstructed_column] = subs_packed[packed_row, packed_column]

# Let's pick two examples for of tri-peptides (made of 3 aminoacids)
glutathione = "ECG" # Need to rebuild human tissue?
thyrotropin_releasing_hormone = "QHP" # Or to regulate your metabolism?

assert sz.alignment_score(
    glutathione,
    thyrotropin_releasing_hormone, 
    substitution_matrix=subs_reconstructed, 
    gap_score=1) == aligner.score(glutathione, thyrotropin_releasing_hormone) # Equal to 6

序列化

文件系统

类似于如何使用 File 读取大文件，其他接口可以用于更快地将字符串写入磁盘。Str 类具有 write_to 方法，可以将字符串写入文件，并具有 offset_within 获取较大字符串中子字符串视图的整数偏移量以进行导航。

web_archive = Str("<html>...</html><html>...</html>")
_, end_tag, next_doc = web_archive.partition("</html>") # or use `find`
next_doc_offset = next_doc.offset_within(web_archive)
web_archive.write_to("next_doc.html") # no GIL, no copies, just a view

PyArrow

Str 很容易转换为 PyArrow 缓冲区。

from pyarrow import foreign_buffer
from stringzilla import Str

original = "hello"
view = Str(native)
arrow = foreign_buffer(view.address, view.nbytes, view)

这意味着您可以将 Str 转换为 pyarrow.Buffer，并将 Strs 转换为 pyarrow.Array 而无需额外的复制。

快速入门：C/C++ 🛠️

C库仅包含头文件，因此您只需将stringzilla.h头文件复制到您的项目中。同样的方法也适用于C++，您需要复制stringzilla.hpp头文件。或者，将其作为子模块添加，并在构建系统中包含它。

git submodule add https://github.com/ashvardanian/stringzilla.git

或者使用纯CMake方法

FetchContent_Declare(stringzilla GIT_REPOSITORY https://github.com/ashvardanian/stringzilla.git)
FetchContent_MakeAvailable(stringzilla)

最后但同样重要的是，您还可以将其作为库安装，并链接到它。这种方法在内联方面表现较差，但为最先进的CPU功能提供了动态运行时调度。

C 99及更高版本的基本用法

存在一个稳定的C 99接口，其中所有函数名都以前缀sz_开头。大多数接口都有良好的文档，并带有自解释的名称和示例。在某些情况下，还提供了硬件特定的重载，例如sz_find_avx512或sz_find_neon。这两个都是sz_find的伴侣，第一个是为支持AVX-512的x86 CPU，第二个是为支持Arm NEON的CPU。

#include <stringzilla/stringzilla.h>

// Initialize your haystack and needle
sz_string_view_t haystack = {your_text, your_text_length};
sz_string_view_t needle = {your_subtext, your_subtext_length};

// Perform string-level operations
sz_size_t substring_position = sz_find(haystack.start, haystack.length, needle.start, needle.length);
sz_size_t substring_position = sz_find_avx512(haystack.start, haystack.length, needle.start, needle.length);
sz_size_t substring_position = sz_find_neon(haystack.start, haystack.length, needle.start, needle.length);

// Hash strings
sz_u64_t hash = sz_hash(haystack.start, haystack.length);

// Perform collection level operations
sz_sequence_t array = {your_order, your_count, your_get_start, your_get_length, your_handle};
sz_sort(&array, &your_config);

C++ 11及更高版本的基本用法

在ashvardanian::stringzilla命名空间中提供了一个稳定的C++ 11接口。它包含两个类似STL的类：string_view和string。第一个是一个不拥有字符串的视图，第二个是一个可变字符串，具有小型字符串优化。

#include <stringzilla/stringzilla.hpp>

namespace sz = ashvardanian::stringzilla;

sz::string haystack = "some string";
sz::string_view needle = sz::string_view(haystack).substr(0, 4);

auto substring_position = haystack.find(needle); // Or `rfind`
auto hash = std::hash<sz::string_view>(haystack); // Compatible with STL's `std::hash`

haystack.end() - haystack.begin() == haystack.size(); // Or `rbegin`, `rend`
haystack.find_first_of(" \w\t") == 4; // Or `find_last_of`, `find_first_not_of`, `find_last_not_of`
haystack.starts_with(needle) == true; // Or `ends_with`
haystack.remove_prefix(needle.size()); // Why is this operation in-place?!
haystack.contains(needle) == true; // STL has this only from C++ 23 onwards
haystack.compare(needle) == 1; // Or `haystack <=> needle` in C++ 20 and beyond

StringZilla还提供了字符串字面量以自动进行类型解析，类似于STL

using sz::literals::operator""_sz;
using std::literals::operator""sv;

auto a = "some string"; // char const *
auto b = "some string"sv; // std::string_view
auto b = "some string"_sz; // sz::string_view

内存所有权和小型字符串优化

StringZilla 中的大多数操作都不假设任何内存所有权。除了提供类似搜索的只读操作外，StringZilla 还为拥有内存的字符串“类”提供了一种简约的 C 和 C++ 实现。与其他高效的字符串实现一样，它使用小型字符串优化（SSO）来避免为短字符串进行堆分配。

typedef union sz_string_t {
    struct internal {
        sz_ptr_t start;
        sz_u8_t length;
        char chars[SZ_STRING_INTERNAL_SPACE]; /// Ends with a null-terminator.
    } internal;

    struct external {
        sz_ptr_t start;
        sz_size_t length;        
        sz_size_t space; /// The length of the heap-allocated buffer.
        sz_size_t padding;
    } external;

} sz_string_t;

正如大家所看到的，如果短字符串能够适应 internal.chars 数组，它就可以保持在栈上。在 2015 年之前，GCC 的字符串实现只有 8 字节，只能容纳 7 个字符。如今，不同的 STL 实现对小型字符串优化有不同的阈值。类似于 GCC，StringZilla 大小为 32 字节，类似于 Clang，它可以在栈上容纳 22 个字符。如果想要避免分支，我们的布局可能更受欢迎。如果您使用的是不同的编译器，您可能想通过简单的 Gist检查其 SSO 缓冲区大小。

这种设计已经移植到许多高级编程语言中。例如，Swift 可以在 String 实例中存储 15 字节。StringZilla 在 C 级别实现 SSO，提供 sz_string_t 联合和简单的 API 用于主要操作。

sz_memory_allocator_t allocator;
sz_string_t string;

// Init and make sure we are on stack
sz_string_init(&string);
sz_string_is_on_stack(&string); // == sz_true_k

// Optionally pre-allocate space on the heap for future insertions.
sz_string_grow(&string, 100, &allocator); // == sz_true_k

// Append, erase, insert into the string.
sz_string_expand(&string, 0, "_Hello_", 7, &allocator); // == sz_true_k
sz_string_expand(&string, SZ_SIZE_MAX, "world", 5, &allocator); // == sz_true_k
sz_string_erase(&string, 0, 1);

// Unpacking & introspection.
sz_ptr_t string_start;
sz_size_t string_length;
sz_size_t string_space;
sz_bool_t string_is_external;
sz_string_unpack(string, &string_start, &string_length, &string_space, &string_is_external);
sz_equal(string_start, "Hello_world", 11); // == sz_true_k

// Reclaim some memory.
sz_string_shrink_to_fit(&string, &allocator); // == sz_true_k
sz_string_free(&string, &allocator);

与传统的 C 字符串不同，sz_string_t 允许包含空字符。为了安全打印这些字符，请将 string_length 传递给 printf。

printf("%.*s\n", (int)string_length, string_start);

C++ 标准库有什么问题？

StringZilla 被设计为 C++ 标准模板库的即插即用替代品。话虽如此，STL 字符串的一些设计决策是高度有争议的、易出错的和昂贵的。最值得注意的是

1. replace、insert、erase 和类似函数的参数顺序无法猜测。
2. 类似于 substr 的函数的边界检查异常只抛出范围的一侧。
3. 类似于 substr 的函数返回字符串副本会导致大量分配。
4. 通过类似于 push_back 的函数进行增量构建会经过太多的分支。
5. 类似于 string 和 string_view 方法的差异，例如缺少 remove_prefix 和 remove_suffix。

请检查以下断言集，以验证 std::string 规范。期望普通开发者记住 std::string::replace 的 14 种重载是不现实的。

using str = std::string;

assert(str("hello world").substr(6) == "world");
assert(str("hello world").substr(6, 100) == "world"); // 106 is beyond the length of the string, but its OK
assert_throws(str("hello world").substr(100), std::out_of_range);   // 100 is beyond the length of the string
assert_throws(str("hello world").substr(20, 5), std::out_of_range); // 20 is beyond the length of the string
assert_throws(str("hello world").substr(-1, 5), std::out_of_range); // -1 casts to unsigned without any warnings...
assert(str("hello world").substr(0, -1) == "hello world");          // -1 casts to unsigned without any warnings...

assert(str("hello").replace(1, 2, "123") == "h123lo");
assert(str("hello").replace(1, 2, str("123"), 1) == "h23lo");
assert(str("hello").replace(1, 2, "123", 1) == "h1lo");
assert(str("hello").replace(1, 2, "123", 1, 1) == "h2lo");
assert(str("hello").replace(1, 2, str("123"), 1, 1) == "h2lo");
assert(str("hello").replace(1, 2, 3, 'a') == "haaalo");
assert(str("hello").replace(1, 2, {'a', 'b'}) == "hablo");

为了避免这些问题，StringZilla提供了一种替代的统一接口。它支持有符号参数，并且每个函数不超过3个参数，或者说是标准API和我们的替代API可以通过以下代码有条件地禁用：SZ_SAFETY_OVER_COMPATIBILITY=1。启用时，标准中的主观上风险较大的重载将被禁用。

using str = sz::string;

str("a:b").front(1) == "a"; // no checks, unlike `substr`
str("a:b").front(2) == "2"; // take first 2 characters
str("a:b").back(-1) == "b"; // accepting negative indices
str("a:b").back(-2) == ":b"; // similar to Python's `"a:b"[-2:]`
str("a:b").sub(1, -1) == ":"; // similar to Python's `"a:b"[1:-1]`
str("a:b").sub(-2, -1) == ":"; // similar to Python's `"a:b"[-2:-1]`
str("a:b").sub(-2, 1) == ""; // similar to Python's `"a:b"[-2:1]`
"a:b"_sz[{-2, -1}] == ":"; // works on views and overloads `operator[]`

假设StringZilla是一个仅提供头文件的库，你可以在某些翻译单元中使用完整的API，然后逐步过渡到更安全的受限API。额外的好处是所有边界检查都是无分支的，所以它具有恒定的成本，不会伤害你的分支预测器。

超越C++标准库——从Python学习

Python可以说是数据科学中最受欢迎的编程语言。部分原因是因为它的标准接口简单。StringZilla将其中一些功能带到了C++。

• 内容检查：isalnum、isalpha、isascii、isdigit、islower、isspace、isupper。
• 修剪字符集：lstrip、rstrip、strip。
• 修剪字符串匹配：remove_prefix、remove_suffix。
• 搜索结果的范围：splitlines、split、rsplit。
• 非重叠子字符串匹配的数量：count。
• 分区：partition、rpartition。

例如，在解析文档时，通常需要将其分割成子字符串。通常，接下来会计算跳过的部分、偏移量和剩余部分的长度。这导致大量的指针运算，容易出错。StringZilla提供了一个方便的partition函数，它返回一个包含三个字符串视图的元组，使代码更简洁。

auto parts = haystack.partition(':'); // Matching a character
auto [before, match, after] = haystack.partition(':'); // Structure unpacking
auto [before, match, after] = haystack.partition(char_set(":;")); // Character-set argument
auto [before, match, after] = haystack.partition(" : "); // String argument
auto [before, match, after] = haystack.rpartition(sz::whitespaces); // Split around the last whitespace

结合split函数，可以轻松解析CSV文件或HTTP头。

for (auto line : haystack.split("\r\n")) {
    auto [key, _, value] = line.partition(':');
    headers[key.strip()] = value.strip();
}

一些其他扩展也不在Python标准库中。让我们按类别逐一介绍C++的功能。

• 分割和范围.
• 无分配连接字符串.
• 随机生成.
• 编辑距离和模糊搜索.

StringZilla的一些接口甚至不在Python的本地str类中。以下是一些最有用的接口的预览。

text.hash(); // -> 64 bit unsigned integer 
text.ssize(); // -> 64 bit signed length to avoid `static_cast<std::ssize_t>(text.size())`
text.contains_only(" \w\t"); // == text.find_first_not_of(char_set(" \w\t")) == npos;
text.contains(sz::whitespaces); // == text.find(char_set(sz::whitespaces)) != npos;

// Simpler slicing than `substr`
text.front(10); // -> sz::string_view
text.back(10); // -> sz::string_view

// Safe variants, which clamp the range into the string bounds
using sz::string::cap;
text.front(10, cap) == text.front(std::min(10, text.size()));
text.back(10, cap) == text.back(std::min(10, text.size()));

// Character set filtering
text.lstrip(sz::whitespaces).rstrip(sz::newlines); // like Python
text.front(sz::whitespaces); // all leading whitespaces
text.back(sz::digits); // all numerical symbols forming the suffix

// Incremental construction
using sz::string::unchecked;
text.push_back('x'); // no surprises here
text.push_back('x', unchecked); // no bounds checking, Rust style
text.try_push_back('x'); // returns `false` if the string is full and the allocation failed

sz::concatenate(text, "@", domain, ".", tld); // No allocations

分割和范围

最常见的用例之一是将字符串分割成一系列子字符串。这通常会导致StackOverflow查询和以下类似的片段。

std::vector<std::string> lines = split(haystack, "\r\n"); // string delimiter
std::vector<std::string> words = split(lines, ' '); // character delimiter

这些为每个字符串和临时向量分配内存。每次分配可能比简单的序列for-循环遍历字符的费用高几个数量级。为了避免这些问题，StringZilla提供了与Range-v3库兼容的延迟评估范围。

for (auto line : haystack.split("\r\n"))
    for (auto word : line.split(char_set(" \w\t.,;:!?")))
        std::cout << word << std::endl;

这些也可以以相反的顺序使用。它还允许交织匹配，如果你想在xxx中包含两次xx。调试指针偏移量不是一项愉快的任务，所以请记住以下函数。

• haystack.[r]find_all(needle,interleaving)
• haystack.[r]find_all(char_set(""))
• haystack.[r]split(needle)
• haystack.[r]split(char_set(""))

对于$N$个匹配，分割函数将报告$N+1$个匹配，可能包括空字符串。范围也有一些方便的方法

range.size(); // -> std::size_t
range.empty(); // -> bool
range.template to<std::set<std::sting>>(); 
range.template to<std::vector<std::sting_view>>(); 

无分配连接字符串

另一种常见的字符串操作是连接。STL提供了std::string::operator+和std::string::append，但如果有多次调用，这些方法并不高效。

std::string name, domain, tld;
auto email = name + "@" + domain + "." + tld; // 4 allocations

一种高效的方法是在预先分配的内存中复制字符串。

std::string email;
email.reserve(name.size() + domain.size() + tld.size() + 2);
email.append(name), email.append("@"), email.append(domain), email.append("."), email.append(tld);

这听起来很复杂，也容易出错。StringZilla提供了一个更方便的concatenate函数，它接受可变数量的参数。它还重载了operator|以懒连接字符串，而不进行任何分配。

auto email = sz::concatenate(name, "@", domain, ".", tld);   // 0 allocations
auto email = name | "@" | domain | "." | tld;                // 0 allocations
sz::string email = name | "@" | domain | "." | tld;          // 1 allocations

随机生成

软件开发者经常需要生成随机字符串以进行测试。STL提供了std::generate和std::random_device，这些可以与StringZilla一起使用。

sz::string random_string(std::size_t length, char const *alphabet, std::size_t cardinality) {
    sz::string result(length, '\0');
    static std::random_device seed_source; // Expensive to construct - due to system calls
    static std::mt19937 generator(seed_source()); // Also expensive - due to the state size
    std::uniform_int_distribution<std::size_t> distribution(0, cardinality);
    std::generate(result.begin(), result.end(), [&]() { return alphabet[distribution(generator)]; });
    return result;
}

这听起来很复杂且速度慢。StringZilla提供了一个C原生方法 - sz_generate和方便的C++包装器 - sz::generate。类似于Python，它还定义了常用的字符集。

auto protein = sz::string::random(300, "ARNDCQEGHILKMFPSTWYV"); // static method
auto dna = sz::basic_string<custom_allocator>::random(3_000_000_000, "ACGT");

dna.randomize("ACGT"); // `noexcept` pre-allocated version
dna.randomize(&std::rand, "ACGT"); // pass any generator, like `std::mt19937`

char uuid[36];
sz::randomize(sz::string_span(uuid, 36), "0123456789abcdef-"); // Overwrite any buffer

Levenshtein编辑距离和比对得分

Levenshtein和Hamming编辑距离适用于字节字符串和UTF-8字符串。后者将以Unicode代码点输出距离，而不是字节。Needleman-Wunsch比对得分仅适用于字节字符串。

// Count number of substitutions in same length strings
sz::hamming_distance(first, second[, upper_bound]) -> std::size_t;
sz::hamming_distance_utf8(first, second[, upper_bound]) -> std::size_t;

// Count number of insertions, deletions and substitutions
sz::edit_distance(first, second[, upper_bound[, allocator]]) -> std::size_t;
sz::edit_distance_utf8(first, second[, upper_bound[, allocator]]) -> std::size_t;

// Substitution-parametrized Needleman-Wunsch global alignment score
std::int8_t costs[256][256]; // Substitution costs matrix
sz::alignment_score(first, second, costs[, gap_score[, allocator]) -> std::ptrdiff_t;

C和C++中的排序

LibC提供了qsort，STL提供了std::sort。它们都有自己的问题。LibC标准无法将上下文传递给比较函数，这仅通过平台特定的扩展才可行。这些在每一个操作系统上都有不同的参数顺序。

// Linux: https://linux.die.net/man/3/qsort_r
void qsort_r(void *elements, size_t count, size_t element_width, 
    int (*compare)(void const *left, void const *right, void *context),
    void *context);
// MacOS and FreeBSD: https://developer.apple.com/library/archive/documentation/System/Conceptual/ManPages_iPhoneOS/man3/qsort_r.3.html
void qsort_r(void *elements, size_t count, size_t element_width, 
    void *context,
    int (*compare)(void *context, void const *left, void const *right));
// Windows conflicts with ISO `qsort_s`: https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/qsort-s?view=msvc-170
void qsort_s(id *elements, size_t count, size_t element_width, 
    int (*compare)(void *context, void const *left, void const *right),
    void *context);

C++泛型算法也不是完美的。标准没有保证std::sort不会分配任何内存。如果您在嵌入式系统、实时系统或每个节点有100多个CPU核心上运行，您可能希望避免这种情况。StringZilla不解决通用情况，但希望提高字符串的性能。使用sz_sort，或高级的sz::sorted_order，它可以用来对任何可转换为sz::string_view的元素集合进行排序。

std::vector<std::string> data({"c", "b", "a"});
std::vector<std::size_t> order = sz::sorted_order(data); //< Simple shortcut

// Or, taking care of memory allocation:
sz::sorted_order(data.begin(), data.end(), order.data(), [](auto const &x) -> sz::string_view { return x; });

具有字符串键的C++标准容器

C++标准模板库提供了几个关联容器，通常与字符串键一起使用。

std::map<std::string, int, std::less<std::string>> sorted_words;
std::unordered_map<std::string, int, std::hash<std::string>, std::equal_to<std::string>> words;

这些容器的性能通常受字符串键性能的限制，尤其是在读取操作中。StringZilla可以通过重载默认的比较器和哈希函数来加速具有std::string键的容器。

std::map<std::string, int, sz::string_view_less> sorted_words;
std::unordered_map<std::string, int, sz::string_view_hash, sz::string_view_equal_to> words;

或者，更好的方法是使用sz::string类作为键。合适的哈希函数和比较器会被自动选择，如果键较短，性能提升会更加明显。

std::map<sz::string, int> sorted_words;
std::unordered_map<sz::string, int> words;

编译设置和调试

SZ_DEBUG:

为了获得最佳性能，C 库在发布版本中不执行任何边界检查。在 C++ 中，边界检查仅在 STL 的 std::string 会执行边界检查的地方发生。如果您想启用更激进的边界检查，请在包含头文件之前定义 SZ_DEBUG。如果没有明确设置，它将根据构建类型推断。

SZ_USE_X86_AVX512、SZ_USE_X86_AVX2、SZ_USE_ARM_NEON:

为了兼容性，可以显式禁用某些 SIMD 指令族。默认值在编译时推断。

SZ_DYNAMIC_DISPATCH:

默认情况下，StringZilla 是一个仅包含头文件的库。但如果您在不同的设备代之间运行，一次性为所有支持的设备代预编译库并运行时调度是有意义的。此标志正是为此而设计的，用于生成 stringzilla.so 共享库以及 Python 绑定。

SZ_USE_MISALIGNED_LOADS:

默认情况下，StringZilla 避免非对齐加载。如果支持，它将许多字级操作替换为字级操作。从类似 char 的类型到类似 uint64_t 的类型可以显著加速串行（SWAR）后端。因此，如果您正在为某些嵌入式设备构建，请考虑启用它。

SZ_AVOID_LIBC 和 SZ_OVERRIDE_LIBC

当使用 C 仅包含头文件的库时，可以禁用 LibC 的使用。这可能会影响在神秘硬件平台上的类型解析系统。此外，可以让 stringzilla 覆盖像 memcpy 和 memset 这样的常见符号，使用其自己的实现。在这种情况下，您可以使用 LD_PRELOAD 技巧 来优先选择其符号而不是来自 LibC 的符号，从而加速现有字符串密集型应用程序而无需重新编译它们。

SZ_AVOID_STL 和 SZ_SAFETY_OVER_COMPATIBILITY

当使用 C++ 接口时，可以禁用从 std::string 到 sz::string 以及返回的隐式转换。如果不需要，则排除 <string> 和 <string_view> 头文件，从而减少编译时间。此外，如果 STL 兼容性优先级较低，则可以通过禁用可能导致主观错误的重载来使 API 更安全。

STRINGZILLA_BUILD_SHARED、STRINGZILLA_BUILD_TEST、STRINGZILLA_BUILD_BENCHMARK、STRINGZILLA_TARGET_ARCH 对于 CMake 用户

在编译测试和基准测试时，可以显式设置目标硬件架构。它与 GCC 的 -march 标志同义，用于启用/禁用适当的指令集。您还可以禁用共享库的构建，如果您不需要它。

快速入门：Rust 🦀

StringZilla 可作为 Rust 包提供，文档可在 docs.rs/stringzilla 上找到。要使用项目中的最新包版本，请将以下内容添加到您的 Cargo.toml

[dependencies]
stringzilla = ">=3"

或者如果您想从存储库中使用最新的预发布版本

[dependencies]
stringzilla = { git = "https://github.com/ashvardanian/stringzilla", branch = "main-dev" }

安装完成后，所有功能都可通过 stringzilla 命名空间访问。许多接口对于 memchr 库的用户来说都很熟悉。

use stringzilla::sz;

// Identical to `memchr::memmem::find` and `memchr::memmem::rfind` functions
sz::find("Hello, world!", "world") // 7
sz::rfind("Hello, world!", "world") // 7

// Generalizations of `memchr::memrchr[123]`
sz::find_char_from("Hello, world!", "world") // 2
sz::rfind_char_from("Hello, world!", "world") // 11

与 memchr 不同，stringzilla 的吞吐量在正常和逆序搜索中都很高。[查看更多](https://github.com/ashvardanian/memchr_vs_stringzilla)。它对字符集的大小也没有限制，而 memchr 只允许使用 1、2 或 3 个字符。除了全局函数外，stringzilla 还提供了一个 StringZilla 扩展特质。

use stringzilla::StringZilla;

let my_string: String = String::from("Hello, world!");
let my_str = my_string.as_str();
let my_cow_str = Cow::from(&my_string);

// Use the generic function with a String
assert_eq!(my_string.sz_find("world"), Some(7));
assert_eq!(my_string.sz_rfind("world"), Some(7));
assert_eq!(my_string.sz_find_char_from("world"), Some(2));
assert_eq!(my_string.sz_rfind_char_from("world"), Some(11));
assert_eq!(my_string.sz_find_char_not_from("world"), Some(0));
assert_eq!(my_string.sz_rfind_char_not_from("world"), Some(12));

// Same works for &str and Cow<'_, str>
assert_eq!(my_str.sz_find("world"), Some(7));
assert_eq!(my_cow_str.as_ref().sz_find("world"), Some(7));

该库还公开了 Levenshtein 和 Hamming 编辑距离，用于字节数组和 UTF-8 字符串，以及 Needleman-Wunch 对齐得分。

use stringzilla::sz;

// Handling arbitrary byte arrays:
sz::edit_distance("Hello, world!", "Hello, world?"); // 1
sz::hamming_distance("Hello, world!", "Hello, world?"); // 1
sz::alignment_score("Hello, world!", "Hello, world?", sz::unary_substitution_costs(), -1); // -1

// Handling UTF-8 strings:
sz::hamming_distance_utf8("αβγδ", "αγγδ") // 1
sz::edit_distance_utf8("façade", "facade") // 1

快速入门：Swift 🍏

您可以将 StringZilla 添加到 Swift 包管理器中。在您的 Package.swift 文件中，添加以下内容

dependencies: [
    .package(url: "https://github.com/ashvardanian/stringzilla")
]

目前该包仅覆盖最基本的功能，但计划扩展以覆盖完整的 C++ API。

var s = "Hello, world! Welcome to StringZilla. 👋"
s[s.findFirst(substring: "world")!...] // "world! Welcome to StringZilla. 👋")    
s[s.findLast(substring: "o")!...] // "o StringZilla. 👋")
s[s.findFirst(characterFrom: "aeiou")!...] // "ello, world! Welcome to StringZilla. 👋")
s[s.findLast(characterFrom: "aeiou")!...] // "a. 👋")
s[s.findFirst(characterNotFrom: "aeiou")!...] // "Hello, world! Welcome to StringZilla. 👋"
s.editDistance(from: "Hello, world!")! // 29

算法与设计决策 📚

StringZilla 旨在优化一些最慢的字符串操作。然而，一些流行的操作，如等性比较和相对顺序检查，几乎总是在前几个字节中完成。在这些操作中，向量化几乎是无用的，除非考虑非常大的非常相似字符串。StringZilla 也实现了这些操作，但不会带来显著的速度提升。

精确子字符串搜索

子字符串搜索算法通常分为：基于比较的、基于自动机的和位并行。不同的算法系列适用于不同的字母表大小和针长度。每字符需要的操作越多，SIMD 就越有效。针越长，跳转表就越有效。StringZilla 使用不同的精确子字符串搜索算法，针对不同的针长度和后端。

• 当没有 SIMD 可用的情况下，使用 SWAR（寄存器内的 SIMD）算法在 64 位字上进行。
• 对于较长的针，使用带有 Raita 启发式变体的 Boyer-Moore-Horspool (BMH) 算法。
• 对 SIMD 算法进行随机化，以查看针的不同部分。

对于非常短的针，尤其是 1-4 个字符长，使用 SIMD 的暴力搜索是最快的解决方案。对于中等长度的针，位并行算法是有效的，因为字符掩码可以放入 32 位或 64 位字中。无论如何，如果针的长度小于 64 字节，在稻草检索过程中我们仍然会检索每个 CPU 缓存行。因此，唯一提高性能的方法是减少比较次数。下面的片段显示了 StringZilla 是如何为长度为两的针完成这一点的。

https://github.com/ashvardanian/StringZilla/blob/266c01710dddf71fc44800f36c2f992ca9735f87/include/stringzilla/stringzilla.h#L1585-L1637

超出这个范围，对于较长的针，Boyer-Moore (BM) 及其变体通常是最佳选择。它有两个表：好的后缀移位和坏字符移位。常见的做法是使用简化的 BMH 算法，它只使用坏字符移位表，从而减少预处理时间。我们为 256 字节长度的中等长度针也这样做。这样，堆栈分配的移位表仍然很小。

https://github.com/ashvardanian/StringZilla/blob/46e957cd4f9ecd4945318dd3c48783dd11323f37/include/stringzilla/stringzilla.h#L1774-L1825

在 C++ 标准库中，std::string::find 函数使用带有 Raita 启发式的 BMH 算法。在比较整个字符串之前，它匹配第一个、最后一个和中间的字符。非常实用，但对于重复字符来说可能较慢。StringZilla 的 SWAR 和 SIMD 后端都有便宜的预处理步骤，其中我们定位唯一的字符。这使得库在处理非英语语料库时更加实用。

https://github.com/ashvardanian/StringZilla/blob/46e957cd4f9ecd4945318dd3c48783dd11323f37/include/stringzilla/stringzilla.h#L1398-L1431

所有这些算法在最坏情况下的复杂度都是 $O(hn)$。为了确保最坏情况下的时间复杂度为 $O(h)$，Apostolico-Giancarlo (AG) 算法增加了一个额外的跳转表。预处理阶段的时间和空间复杂度为 $O(n+\sigma)$。在遍历过程中，比较次数从 $(h/n)$ 到 $(3h/2)$ 不等。然而，在现代CPU上并不实用。一个更简单的想法，Galil规则，可能对于必须找到许多匹配的情况来说是一个更相关的优化。

之前考虑过并废弃的其他算法

• 用于更长针的Apostolico-Giancarlo算法。控制流过于复杂，难以进行有效向量化。
• 基于Shift-Or的Bitap算法用于短针。比SWAR慢。
• 在SIMD后端使用Horspool风格的坏字符检查。仅对非常长的针以及针和文本之间非常不均匀的字符分布有效。需要更快的“字符在集合中”检查以进行泛化。

§ 阅读材料。Java中的精确字符串匹配算法。适用于SIMD的子串搜索算法。

Levenshtein编辑距离

Levenshtein距离是已知的最优字符串编辑距离，它检查需要多少插入、删除和替换才能将一个字符串转换成另一个字符串。它在近似字符串匹配、拼写检查和生物信息学中得到广泛应用。

Levenshtein距离的计算成本是 $O(n * m)$，其中 $n$ 和 $m$ 是字符串参数的长度。为了计算它，朴素方法需要 $O(n * m)$ 的空间来存储“Levenshtein矩阵”，其右下角将包含Levenshtein距离。产生该矩阵的算法是由苏联数学家Vladimir Levenshtein（1965年）、Taras Vintsyuk（1968年）以及美国计算机科学家Robert Wagner、David Sankoff、Michael J. Fischer在随后的几年中同时研究/发现的。已知几种优化方法

1. 空间优化：矩阵可以在 $O(min(n,m))$ 的空间内计算，只需存储矩阵的最后两行。
2. 分而治之：Hirschberg算法可以应用于将计算分解为子任务。
3. 自动机：如果其中一个字符串不改变，并且是多次比较的对象，Levenshtein自动机可能非常有效。
4. Shift-Or：位并行算法将矩阵转换为位矩阵，并在其上执行位操作。

最后一种方法非常强大且性能出色，被伟大的RapidFuzz库所使用。它不如其他方法知名，源自Baeza-Yates-Gonnet算法，在20世纪90年代由Manber和Wu扩展到有限编辑距离搜索，并由Gene Myers（1999年）和Heikki Hyyro（2002年至2004年之间）进一步扩展。

StringZilla引入了一种不同的方法，这种方法在Unum的内部组合优化库中得到广泛应用。这种方法不会改变基本操作的数量，但会以不同的顺序执行它们，从而在计算插入成本时消除数据依赖性。这导致了更好的向量化，适用于核心内并行性和单次请求的多核评估。

下一个设计目标

• 将快速遍历推广到矩形矩阵。
• 将x86 AVX-512解决方案移植到Arm NEON。

§ 阅读材料。使用SIMD友好的遍历顺序加速Levenshtein距离。

生物信息学中的Needleman-Wunsch对齐得分

生物信息学领域研究生物结构的各种表示。通常，“主要”表示是稀疏字母表上的字符串

• DNA序列，其中字母表是 {A, C, G, T}，长度从短读的 ~100 个字符到人类基因组的 30 亿个字符不等。
• RNA序列，字母表为{A, C, G, U}，长度从tRNA的约50个字符到mRNA的数千个字符。
• 蛋白质，字母表由22种氨基酸组成，长度从双肽的2个字符到最长的蛋白质Titin的35,000个字符。

表示越短，研究人员可能越频繁地使用自定义替换矩阵。这意味着两个字符之间的替换成本可能对于所有配对来说并不相同。

StringZilla将效率较高的两行Wagner-Fisher算法作为Needleman-Wunsch得分的基准串行实现。它支持任意字母表，最多256个字符，可以使用BLOSUM、PAM或其他替换矩阵。它还使用SIMD来加速替换查找。然而，这还没有打破插入成本的依赖关系，其中80%的时间被浪费了。解决了这个问题后，SIMD实现将比串行实现快5倍。

随机生成

从不同的字母表中生成随机字符串是一个非常常见的操作。StringZilla接受任意的伪随机数生成器来产生噪声，以及一个字符数组来采样。采样被优化以避免整数除法，这是现代CPU上的一个昂贵操作。为此，使用了一个768字节的查找表来执行2次查找、1次乘法、2次移位和2次累加。

https://github.com/ashvardanian/StringZilla/blob/266c01710dddf71fc44800f36c2f992ca9735f87/include/stringzilla/stringzilla.h#L2490-L2533

排序

对于字符串的字典排序，StringZilla使用“混合-混合”方法，复杂度为$O(n * log(n))$。

1. 基数排序用于将第一个字节导出到连续缓冲区以实现局部性。
2. 在部分排序的块上使用IntroSort以平衡效率和最坏情况性能。
   1. IntroSort以QuickSort开始。
   2. 如果递归深度超过某个阈值，则切换到HeapSort。

下一个设计目标

• 推广到超过40亿个条目的数组。
• 算法改进可能会带来3倍的性能提升。
• Radix切片的SIMD加速。

哈希

[!警告] 哈希函数不是加密安全的，目前正处于积极开发中。它们可能在未来的小版本更新中发生变化。

选择适合您应用程序的正确哈希算法在性能和安全性方面都非常关键。在StringZilla中，64位滚动哈希函数被重用于字符串哈希和子串哈希，Rabin风格的指纹。滚动哈希计算不同窗口大小的哈希值所需时间相同，并且更新速度快。然而，它们并不是完美的哈希，碰撞很常见。StringZilla试图使用SIMD，但性能尚不令人满意。在Intel Sapphire Rapids上，对于N路并行变体可以期待以下数字。

• 4路AVX2吞吐量，64位整数乘法（无原生支持）：0.28 GB/s。
• 4路AVX2吞吐量，32位整数乘法：0.54 GB/s。
• 4路AVX-512DQ吞吐量，64位整数乘法：0.46 GB/s。
• 4路AVX-512吞吐量，32位整数乘法：0.58 GB/s。
• 8路AVX-512吞吐量，32位整数乘法：0.11 GB/s。

下一个设计目标

• 尝试gear-hash和其他滚动方法。

为什么不使用CRC32？

循环冗余校验32（CRC-32）是计算机科学中最常用的散列函数之一。它在x86和Arm架构上都有硬件支持，适用于8位、16位、32位和64位字。在iSCSI、Btrfs、ext4中使用的是多项式0x1EDC6F41，而在SATA、以太网、Zlib、PNG中使用的是0x04C11DB7。对于Arm架构，支持多项式超过一个。然而，它在大数据处理用例中有些限制，因为大数据处理往往需要处理超过40亿的字符串，导致碰撞难以避免。此外，现有的SIMD方法比较复杂，结合通用计算和专用指令，以在每个周期中利用更多的硅片。

§ 阅读材料。 方法的全面推导 x86上4 KB缓冲区的快速计算 比较不同的查找表 优秀的开源实现。Peter Cawley的作品 Stephan Brumme的作品

其他现代替代方案

MurmurHash是由Austin Appleby于2008年提出的，是最著名的非加密散列之一。它有很短的实现，能够生成32位和128位散列。Google于2011年提出的CityHash和xxHash在此基础上进行了改进，更好地利用了现代CPU的超标量特性，并生成64位和128位散列。

这些函数都不是加密函数，与MD5、SHA和BLAKE算法不同。大多数加密散列基于Merkle-Damgård构造，并且不受长度扩展攻击的影响。当前最先进的技术可能是BLAKE3算法。它对广泛的攻击具有抵抗力，每个CPU周期可以处理2个字节，并提供了针对C和Rust的非常优化的官方实现。它具有与BLAKE2相同的128位安全级别，通过减少混合轮数，以1 KiB数据块处理数据来实现性能提升，这对于长字符串来说非常好，但在短字符串上可能会表现不佳。

所有提到的库都经过广泛测试，被认为是生产就绪的。它们肯定可以加速您的应用程序，但下游混合器也是如此。例如，当构建哈希表时，哈希值会进一步压缩以解决表桶。如果混合器丢失熵，哈希函数的性能提升可能会丢失。一个例子是2的幂次方模运算，这是一个常见的混合器，但已知很弱。另一个替代方案是Daniel Lemire的fastrange。另一个是使用黄金比的Fibonacci散列技巧，也用于StringZilla。

Unicode，UTF-8和宽字符

StringZilla的大部分操作都是字节级别的，因此它们与ASCII和UTF8内容兼容。在某些情况下，如编辑距离计算，字节级别评估和字符级别评估的结果可能不同。因此，StringZilla提供了以下函数来处理Unicode

• sz_edit_distance_utf8 - 计算两个UTF-8字符串之间的Levenshtein距离。
• sz_hamming_distance_utf8 - 计算两个UTF-8字符串之间的Hamming距离。

Java、JavaScript、Python 2、C#和Objective-C使用宽字符（wchar）-长度为两个字节的编码，而不是更合理的固定长度UTF32或可变长度的UTF8。这导致在面临长度为四个字节的Unicode字符时出现各种偏移量计数问题。因此，如果您来自这样的环境，请考虑使用simdutf进行转码。

贡献 👾

请查看贡献指南，以获取有关如何设置开发环境并向此项目贡献的更多详细信息。如果您喜欢这个项目，您可能还会喜欢USearch、UCall、UForm和SimSIMD。🤗

如果您喜欢字符串和效率，您可能还会喜欢以下项目

• simdutf - 转换UTF8、UTF16和UTF32 LE和BE。
• hyperscan - 具有SIMD加速的正则表达式。
• pyahocorasick - Python中的Aho-Corasick算法。
• rapidfuzz - C++和Python中的快速字符串匹配。

如果您想了解更多有关这个主题的阅读材料，请考虑以下内容

• 使用SIMD和SWAR实现5倍快速字符串.
• C++ STL字符串的痛苦陷阱.

许可证 📜

您可以根据自己的喜好在Apache 2.0或三条款BSD许可证下自由使用此项目。