{"author":"Ash Vardanian","author_email":"1983160+ashvardanian@users.noreply.github.com","bugtrack_url":null,"classifiers":["Development Status :: 5 - Production/Stable","Intended Audience :: Developers","Intended Audience :: Information Technology","License :: OSI Approved :: Apache Software License","Natural Language :: English","Operating System :: OS Independent","Programming Language :: C++","Programming Language :: Python :: 3 :: Only","Programming Language :: Python :: 3.10","Programming Language :: Python :: 3.11","Programming Language :: Python :: 3.12","Programming Language :: Python :: 3.13","Programming Language :: Python :: 3.6","Programming Language :: Python :: 3.7","Programming Language :: Python :: 3.8","Programming Language :: Python :: 3.9","Programming Language :: Python :: Implementation :: CPython","Programming Language :: Python :: Implementation :: PyPy","Topic :: File Formats","Topic :: Internet :: Log Analysis","Topic :: Scientific/Engineering :: Information Analysis","Topic :: System :: Logging","Topic :: Text Processing :: General","Topic :: Text Processing :: Indexing"],"description":"# StringZilla 🦖\n\n![StringZilla banner](https://github.com/ashvardanian/ashvardanian/blob/master/repositories/StringZilla.png?raw=true)\n\nThe world wastes a minimum of $100M annually due to inefficient string operations.\nA typical codebase processes strings character by character, resulting in too many branches and data-dependencies, neglecting 90% of modern CPU's potential.\nLibC is different.\nIt attempts to leverage SIMD instructions to boost some operations, and is often used by higher-level languages, runtimes, and databases.\nBut it isn't perfect.\n1️⃣ First, even on common hardware, including over a billion 64-bit ARM CPUs, common functions like `strstr` and `memmem` only achieve 1/3 of the CPU's throughput.\n2️⃣ Second, SIMD coverage is inconsistent: acceleration in forward scans does not guarantee speed in the reverse-order search.\n3️⃣ At last, most high-level languages can't always use LibC, as the strings are often not NULL-terminated or may contain the Unicode \"Zero\" character in the middle of the string.\nThat's why StringZilla was created.\nTo provide predictably high performance, portable to any modern platform, operating system, and programming language.\n\n[![StringZilla Python installs](https://static.pepy.tech/personalized-badge/stringzilla?period=total&units=abbreviation&left_color=black&right_color=blue&left_text=StringZilla%20Python%20installs)](https://github.com/ashvardanian/stringzilla)\n[![StringZilla Rust installs](https://img.shields.io/crates/d/stringzilla?logo=rust&label=Rust%20installs)](https://crates.io/crates/stringzilla)\n[![GitHub Actions Workflow Status](https://img.shields.io/github/actions/workflow/status/ashvardanian/StringZilla/release.yml?branch=main&label=Ubuntu)](https://github.com/ashvardanian/StringZilla/actions/workflows/release.yml)\n[![GitHub Actions Workflow Status](https://img.shields.io/github/actions/workflow/status/ashvardanian/StringZilla/release.yml?branch=main&label=Windows)](https://github.com/ashvardanian/StringZilla/actions/workflows/release.yml)\n[![GitHub Actions Workflow Status](https://img.shields.io/github/actions/workflow/status/ashvardanian/StringZilla/release.yml?branch=main&label=MacOS)](https://github.com/ashvardanian/StringZilla/actions/workflows/release.yml)\n[![GitHub Actions Workflow Status](https://img.shields.io/github/actions/workflow/status/ashvardanian/StringZilla/release.yml?branch=main&label=Alpine%20Linux)](https://github.com/ashvardanian/StringZilla/actions/workflows/release.yml)\n![StringZilla code size](https://img.shields.io/github/languages/code-size/ashvardanian/stringzilla)\n\nStringZilla is the GodZilla of string libraries, using [SIMD][faq-simd] and [SWAR][faq-swar] to accelerate string operations on modern CPUs.\nIt is up to __10x faster than the default and even other SIMD-accelerated string libraries__ in C, C++, Python, and other languages, while covering broad functionality.\nIt __accelerates exact and fuzzy string matching, edit distance computations, sorting, lazily-evaluated ranges to avoid memory allocations, and even random-string generators__.\n\n[faq-simd]: https://en.wikipedia.org/wiki/Single_instruction,_multiple_data\n[faq-swar]: https://en.wikipedia.org/wiki/SWAR\n\n- 🐂 __[C](#Basic-Usage-with-C-99-and-Newer) :__ Upgrade LibC's `` to `` in C 99\n- 🐉 __[C++](#basic-usage-with-c-11-and-newer):__ Upgrade STL's `` to `` in C++ 11\n- 🐍 __[Python](#quick-start-python-🐍):__ Upgrade your `str` to faster `Str`\n- 🍎 __[Swift](#quick-start-swift-🍏):__ Use the `String+StringZilla` extension\n- 🦀 __[Rust](#quick-start-rust-🦀):__ Use the `StringZilla` traits crate\n- 🐚 __[Shell][faq-shell]__: Accelerate common CLI tools with `sz_` prefix\n- 📚 Researcher? Jump to [Algorithms & Design Decisions](#algorithms--design-decisions-📚)\n- 💡 Thinking to contribute? Look for [\"good first issues\"][first-issues]\n- 🤝 And check the [guide](https://github.com/ashvardanian/StringZilla/blob/main/CONTRIBUTING.md) to setup the environment\n- Want more bindings or features? Let [me](https://github.com/ashvardanian) know!\n\n[faq-shell]: https://github.com/ashvardanian/StringZilla/blob/main/cli/README.md\n[first-issues]: https://github.com/ashvardanian/StringZilla/issues\n\n__Who is this for?__\n\n- For data-engineers parsing large datasets, like the [CommonCrawl](https://commoncrawl.org/), [RedPajama](https://github.com/togethercomputer/RedPajama-Data), or [LAION](https://laion.ai/blog/laion-5b/).\n- For software engineers optimizing strings in their apps and services.\n- For bioinformaticians and search engineers looking for edit-distances for [USearch](https://github.com/unum-cloud/usearch).\n- For [DBMS][faq-dbms] devs, optimizing `LIKE`, `ORDER BY`, and `GROUP BY` operations.\n- For hardware designers, needing a SWAR baseline for strings-processing functionality.\n- For students studying SIMD/SWAR applications to non-data-parallel operations.\n\n[faq-dbms]: https://en.wikipedia.org/wiki/Database\n\n## Performance\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n

C	C++	Python	StringZilla
find the first occurrence of a random word from text, ≅ 5 bytes long
\n `strstr` ¹ \n x86: 7.4 ·\n arm: 2.0 GB/s\n	\n `.find` \n x86: 2.9 ·\n arm: 1.6 GB/s\n	\n `.find` \n x86: 1.1 ·\n arm: 0.6 GB/s\n	\n `sz_find` \n x86: 10.6 ·\n arm: 7.1 GB/s\n
find the last occurrence of a random word from text, ≅ 5 bytes long
⚪	\n `.rfind` \n x86: 0.5 ·\n arm: 0.4 GB/s\n	\n `.rfind` \n x86: 0.9 ·\n arm: 0.5 GB/s\n	\n `sz_rfind` \n x86: 10.8 ·\n arm: 6.7 GB/s\n
split lines separated by `\\n` or `\\r` ²
\n `strcspn` ¹ \n x86: 5.42 ·\n arm: 2.19 GB/s\n	\n `.find_first_of` \n x86: 0.59 ·\n arm: 0.46 GB/s\n	\n `re.finditer` \n x86: 0.06 ·\n arm: 0.02 GB/s\n	\n `sz_find_charset` \n x86: 4.08 ·\n arm: 3.22 GB/s\n
find the last occurrence of any of 6 whitespaces ²
⚪	\n `.find_last_of` \n x86: 0.25 ·\n arm: 0.25 GB/s\n	⚪	\n `sz_rfind_charset` \n x86: 0.43 ·\n arm: 0.23 GB/s\n
Random string from a given alphabet, 20 bytes long ⁵
\n `rand() % n` \n x86: 18.0 ·\n arm: 9.4 MB/s\n	\n `std::uniform_int_distribution` \n x86: 47.2 ·\n arm: 20.4 MB/s\n	\n `join(random.choices(...))` \n x86: 13.3 ·\n arm: 5.9 MB/s\n	\n `sz_generate` \n x86: 56.2 ·\n arm: 25.8 MB/s\n
Mapping Characters with Look-Up Table Transforms
⚪	\n `std::transform` \n x86: 3.81 ·\n arm: 2.65 GB/s\n	\n `str.translate` \n x86: 260.0 ·\n arm: 140.0 MB/s\n	\n `sz_look_up_transform` \n x86: 21.2 ·\n arm: 8.5 GB/s\n
Get sorted order, ≅ 8 million English words ⁶
\n `qsort_r` \n x86: 3.55 ·\n arm: 5.77 s\n	\n `std::sort` \n x86: 2.79 ·\n arm: 4.02 s\n	\n `numpy.argsort` \n x86: 7.58 ·\n arm: 13.00 s\n	\n `sz_sort` \n x86: 1.91 ·\n arm: 2.37 s\n
Levenshtein edit distance, ≅ 5 bytes long
⚪	⚪	\n via `jellyfish` ³ \n x86: 1,550 ·\n arm: 2,220 ns\n	\n `sz_edit_distance` \n x86: 99 ·\n arm: 180 ns\n
Needleman-Wunsch alignment scores, ≅ 10 K aminoacids long
⚪	⚪	\n via `biopython` ⁴ \n x86: 257 ·\n arm: 367 ms\n	\n `sz_alignment_score` \n x86: 73 ·\n arm: 177 ms\n

\n\nStringZilla has a lot of functionality, most of which is covered by benchmarks across C, C++, Python and other languages.\nYou can find those in the `./scripts` directory, with usage notes listed in the [`CONTRIBUTING.md`](CONTRIBUTING.md) file.\nNotably, if the CPU supports misaligned loads, even the 64-bit SWAR backends are faster than either standard library.\n\n> Most benchmarks were conducted on a 1 GB English text corpus, with an average word length of 6 characters.\n> The code was compiled with GCC 12, using `glibc` v2.35.\n> The benchmarks performed on Arm-based Graviton3 AWS `c7g` instances and `r7iz` Intel Sapphire Rapids.\n> Most modern Arm-based 64-bit CPUs will have similar relative speedups.\n> Variance withing x86 CPUs will be larger.\n> ¹ Unlike other libraries, LibC requires strings to be NULL-terminated.\n> ² Six whitespaces in the ASCII set are: ` \\t\\n\\v\\f\\r`. Python's and other standard libraries have specialized functions for those.\n> ³ Most Python libraries for strings are also implemented in C.\n> ⁴ Unlike the rest of BioPython, the alignment score computation is [implemented in C](https://github.com/biopython/biopython/blob/master/Bio/Align/_pairwisealigner.c).\n> ⁵ All modulo operations were conducted with `uint8_t` to allow compilers more optimization opportunities.\n> The C++ STL and StringZilla benchmarks used a 64-bit [Mersenne Twister][faq-mersenne-twister] as the generator.\n> For C, C++, and StringZilla, an in-place update of the string was used.\n> In Python every string had to be allocated as a new object, which makes it less fair.\n> ⁶ Contrary to the popular opinion, Python's default `sorted` function works faster than the C and C++ standard libraries.\n> That holds for large lists or tuples of strings, but fails as soon as you need more complex logic, like sorting dictionaries by a string key, or producing the \"sorted order\" permutation.\n> The latter is very common in database engines and is most similar to `numpy.argsort`.\n> Current StringZilla solution can be at least 4x faster without loss of generality.\n\n[faq-mersenne-twister]: https://en.wikipedia.org/wiki/Mersenne_Twister\n\n## Functionality\n\nStringZilla is compatible with most modern CPUs, and provides a broad range of functionality.\n\n- [x] works on both Little-Endian and Big-Endian architectures.\n- [x] works on 32-bit and 64-bit hardware architectures.\n- [x] compatible with ASCII and UTF-8 encoding.\n\nNot all features are available across all bindings.\nConsider contributing, if you need a feature that's not yet implemented.\n\n| | Maturity | C 99 | C++ 11 | Python | Swift | Rust |\n| :----------------------------- | :------: | :---: | :----: | :----: | :---: | :---: |\n| Substring Search | 🌳 | ✅ | ✅ | ✅ | ✅ | ✅ |\n| Character Set Search | 🌳 | ✅ | ✅ | ✅ | ✅ | ✅ |\n| Edit Distances | 🧐 | ✅ | ✅ | ✅ | ✅ | ⚪ |\n| Small String Class | 🧐 | ✅ | ✅ | ❌ | ❌ | ⚪ |\n| Sorting & Sequence Operations | 🚧 | ✅ | ✅ | ✅ | ⚪ | ⚪ |\n| Lazy Ranges, Compressed Arrays | 🧐 | ⚪ | ✅ | ✅ | ⚪ | ⚪ |\n| Hashes & Fingerprints | 🚧 | ✅ | ✅ | ⚪ | ⚪ | ⚪ |\n\n> 🌳 parts are used in production.\n> 🧐 parts are in beta.\n> 🚧 parts are under active development, and are likely to break in subsequent releases.\n> ✅ are implemented.\n> ⚪ are considered.\n> ❌ are not intended.\n\n## Quick Start: Python 🐍\n\nPython bindings are available on PyPI, and can be installed with `pip`.\nYou can immediately check the installed version and the used hardware capabilities with following commands:\n\n```bash\npip install stringzilla\npython -c \"import stringzilla; print(stringzilla.__version__)\"\npython -c \"import stringzilla; print(stringzilla.__capabilities__)\"\n```\n\n### Basic Usage\n\nIf you've ever used the Python `str`, `bytes`, `bytearray`, `memoryview` class, you'll know what to expect.\nStringZilla's `Str` class is a hybrid of those two, providing `str`-like interface to byte-arrays.\n\n```python\nfrom stringzilla import Str, File\n\ntext_from_str = Str('some-string') # no copies, just a view\ntext_from_bytes = Str(b'some-array') # no copies, just a view\ntext_from_file = Str(File('some-file.txt')) # memory-mapped file\n\nimport numpy as np\nalphabet_array = np.arange(ord(\"a\"), ord(\"z\"), dtype=np.uint8)\ntext_from_array = Str(memoryview(alphabet_array))\n```\n\nThe `File` class memory-maps a file from persistent memory without loading its copy into RAM.\nThe contents of that file would remain immutable, and the mapping can be shared by multiple Python processes simultaneously.\nA standard dataset pre-processing use case would be to map a sizeable textual dataset like Common Crawl into memory, spawn child processes, and split the job between them.\n\n### Basic Operations\n\n- Length: `len(text) -> int`\n- Indexing: `text[42] -> str`\n- Slicing: `text[42:46] -> Str`\n- Substring check: `'substring' in text -> bool`\n- Hashing: `hash(text) -> int`\n- String conversion: `str(text) -> str`\n\n### Advanced Operations\n\n```py\nimport sys\n\nx: bool = text.contains('substring', start=0, end=sys.maxsize)\nx: int = text.find('substring', start=0, end=sys.maxsize)\nx: int = text.count('substring', start=0, end=sys.maxsize, allowoverlap=False)\nx: str = text.decode(encoding='utf-8', errors='strict')\nx: Strs = text.split(separator=' ', maxsplit=sys.maxsize, keepseparator=False)\nx: Strs = text.rsplit(separator=' ', maxsplit=sys.maxsize, keepseparator=False)\nx: Strs = text.splitlines(keeplinebreaks=False, maxsplit=sys.maxsize)\n```\n\nIt's important to note, that the last function behavior is slightly different from Python's `str.splitlines`.\nThe [native version][faq-splitlines] matches `\\n`, `\\r`, `\\v` or `\\x0b`, `\\f` or `\\x0c`, `\\x1c`, `\\x1d`, `\\x1e`, `\\x85`, `\\r\\n`, `\\u2028`, `\\u2029`, including 3x two-bytes-long runes.\nThe StringZilla version matches only `\\n`, `\\v`, `\\f`, `\\r`, `\\x1c`, `\\x1d`, `\\x1e`, `\\x85`, avoiding two-byte-long runes.\n\n[faq-splitlines]: https://docs.python.org/3/library/stdtypes.html#str.splitlines\n\n### Character Set Operations\n\nPython strings don't natively support character set operations.\nThis forces people to use regular expressions, which are slow and hard to read.\nTo avoid the need for `re.finditer`, StringZilla provides the following interfaces:\n\n```py\nx: int = text.find_first_of('chars', start=0, end=sys.maxsize)\nx: int = text.find_last_of('chars', start=0, end=sys.maxsize)\nx: int = text.find_first_not_of('chars', start=0, end=sys.maxsize)\nx: int = text.find_last_not_of('chars', start=0, end=sys.maxsize)\nx: Strs = text.split_charset(separator='chars', maxsplit=sys.maxsize, keepseparator=False)\nx: Strs = text.rsplit_charset(separator='chars', maxsplit=sys.maxsize, keepseparator=False)\n```\n\nYou can also transform the string using Look-Up Tables (LUTs), mapping it to a different character set.\nThis would result in a copy - `str` for `str` inputs and `bytes` for other types.\n\n```py\nx: str = text.translate('chars', {}, start=0, end=sys.maxsize, inplace=False)\nx: bytes = text.translate(b'chars', {}, start=0, end=sys.maxsize, inplace=False)\n```\n\nFor efficiency reasons, pass the LUT as a string or bytes object, not as a dictionary.\nThis can be useful in high-throughput applications dealing with binary data, including bioinformatics and image processing.\nHere is an example:\n\n```py\nimport stringzilla as sz\nlook_up_table = bytes(range(256)) # Identity LUT\nimage = open(\"/image/path.jpeg\", \"rb\").read()\nsz.translate(image, look_up_table, inplace=True)\n```\n\n### Collection-Level Operations\n\nOnce split into a `Strs` object, you can sort, shuffle, and reorganize the slices, with minimum memory footprint.\nIf all the chunks are located in consecutive memory regions, the memory overhead can be as low as 4 bytes per chunk.\n\n```python\nlines: Strs = text.split(separator='\\n') # 4 bytes per line overhead for under 4 GB of text\nbatch: Strs = lines.sample(seed=42) # 10x faster than `random.choices`\nlines.shuffle(seed=42) # or shuffle all lines in place and shard with slices\n# WIP: lines.sort() # explodes to 16 bytes per line overhead for any length text\n# WIP: sorted_order: tuple = lines.argsort() # similar to `numpy.argsort`\n```\n\nWorking on [RedPajama][redpajama], addressing 20 Billion annotated english documents, one will need only 160 GB of RAM instead of Terabytes.\nOnce loaded, the data will be memory-mapped, and can be reused between multiple Python processes without copies.\nAnd of course, you can use slices to navigate the dataset and shard it between multiple workers.\n\n```python\nlines[::3] # every third line\nlines[1::1] # every odd line\nlines[:-100:-1] # last 100 lines in reverse order\n```\n\n[redpajama]: https://github.com/togethercomputer/RedPajama-Data\n\n### Iterators and Memory Efficiency\n\nPython's operations like `split()` and `readlines()` immediately materialize a `list` of copied parts.\nThis can be very memory-inefficient for large datasets.\nStringZilla saves a lot of memory by viewing existing memory regions as substrings, but even more memory can be saved by using lazily evaluated iterators.\n\n```py\nx: SplitIterator[Str] = text.split_iter(separator=' ', keepseparator=False)\nx: SplitIterator[Str] = text.rsplit_iter(separator=' ', keepseparator=False)\nx: SplitIterator[Str] = text.split_charset_iter(separator='chars', keepseparator=False)\nx: SplitIterator[Str] = text.rsplit_charset_iter(separator='chars', keepseparator=False)\n```\n\nStringZilla can easily be 10x more memory efficient than native Python classes for tokenization.\nWith lazy operations, it practically becomes free.\n\n```py\nimport stringzilla as sz\n%load_ext memory_profiler\n\ntext = open(\"enwik9.txt\", \"r\").read() # 1 GB, mean word length 7.73 bytes\n%memit text.split() # increment: 8670.12 MiB (152 ms)\n%memit sz.split(text) # increment: 530.75 MiB (25 ms)\n%memit sum(1 for _ in sz.split_iter(text)) # increment: 0.00 MiB\n```\n\n### Low-Level Python API\n\nAside from calling the methods on the `Str` and `Strs` classes, you can also call the global functions directly on `str` and `bytes` instances.\nAssuming StringZilla CPython bindings are implemented [without any intermediate tools like SWIG or PyBind](https://ashvardanian.com/posts/pybind11-cpython-tutorial/), the call latency should be similar to native classes.\n\n```py\nimport stringzilla as sz\n\ncontains: bool = sz.contains(\"haystack\", \"needle\", start=0, end=sys.maxsize)\noffset: int = sz.find(\"haystack\", \"needle\", start=0, end=sys.maxsize)\ncount: int = sz.count(\"haystack\", \"needle\", start=0, end=sys.maxsize, allowoverlap=False)\n```\n\n### Edit Distances\n\n```py\nassert sz.edit_distance(\"apple\", \"aple\") == 1 # skip one ASCII character\nassert sz.edit_distance(\"αβγδ\", \"αγδ\") == 2 # skip two bytes forming one rune\nassert sz.edit_distance_unicode(\"αβγδ\", \"αγδ\") == 1 # one unicode rune\n```\n\nSeveral Python libraries provide edit distance computation.\nMost of them are implemented in C, but are not always as fast as StringZilla.\nTaking a 1'000 long proteins around 10'000 characters long, computing just a 100 distances:\n\n- [JellyFish](https://github.com/jamesturk/jellyfish): 62.3s\n- [EditDistance](https://github.com/roy-ht/editdistance): 32.9s\n- StringZilla: __0.8s__\n\nMoreover, you can pass custom substitution matrices to compute the Needleman-Wunsch alignment scores.\nThat task is very common in bioinformatics and computational biology.\nIt's natively supported in BioPython, and its BLOSUM matrices can be converted to StringZilla's format.\nAlternatively, you can construct an arbitrary 256 by 256 cost matrix using NumPy.\nDepending on arguments, the result may be equal to the negative Levenshtein distance.\n\n```py\nimport numpy as np\nimport stringzilla as sz\n\ncosts = np.zeros((256, 256), dtype=np.int8)\ncosts.fill(-1)\nnp.fill_diagonal(costs, 0)\n\nassert sz.alignment_score(\"first\", \"second\", substitution_matrix=costs, gap_score=-1) == -sz.edit_distance(a, b)\n```\n\nUsing the same proteins as for Levenshtein distance benchmarks:\n\n- [BioPython](https://github.com/biopython/biopython): 25.8s\n- StringZilla: __7.8s__\n\n

§ Example converting from BioPython to StringZilla.

\n\n```py\nimport numpy as np\nfrom Bio import Align\nfrom Bio.Align import substitution_matrices\n\naligner = Align.PairwiseAligner()\naligner.substitution_matrix = substitution_matrices.load(\"BLOSUM62\")\naligner.open_gap_score = 1\naligner.extend_gap_score = 1\n\n# Convert the matrix to NumPy\nsubs_packed = np.array(aligner.substitution_matrix).astype(np.int8)\nsubs_reconstructed = np.zeros((256, 256), dtype=np.int8)\n\n# Initialize all banned characters to a the largest possible penalty\nsubs_reconstructed.fill(127)\nfor packed_row, packed_row_aminoacid in enumerate(aligner.substitution_matrix.alphabet):\n for packed_column, packed_column_aminoacid in enumerate(aligner.substitution_matrix.alphabet):\n reconstructed_row = ord(packed_row_aminoacid)\n reconstructed_column = ord(packed_column_aminoacid)\n subs_reconstructed[reconstructed_row, reconstructed_column] = subs_packed[packed_row, packed_column]\n\n# Let's pick two examples for of tri-peptides (made of 3 aminoacids)\nglutathione = \"ECG\" # Need to rebuild human tissue?\nthyrotropin_releasing_hormone = \"QHP\" # Or to regulate your metabolism?\n\nassert sz.alignment_score(\n glutathione,\n thyrotropin_releasing_hormone, \n substitution_matrix=subs_reconstructed, \n gap_score=1) == aligner.score(glutathione, thyrotropin_releasing_hormone) # Equal to 6\n```\n\n

\n\n### Serialization\n\n#### Filesystem\n\nSimilar to how `File` can be used to read a large file, other interfaces can be used to dump strings to disk faster.\nThe `Str` class has `write_to` to write the string to a file, and `offset_within` to obtain integer offsets of substring view in larger string for navigation.\n\n```py\nweb_archive = Str(\"......\")\n_, end_tag, next_doc = web_archive.partition(\"\") # or use `find`\nnext_doc_offset = next_doc.offset_within(web_archive)\nweb_archive.write_to(\"next_doc.html\") # no GIL, no copies, just a view\n```\n\n#### PyArrow\n\nA `Str` is easy to cast to [PyArrow](https://arrow.apache.org/docs/python/arrays.html#string-and-binary-types) buffers.\n\n```py\nfrom pyarrow import foreign_buffer\nfrom stringzilla import Str\n\noriginal = \"hello\"\nview = Str(native)\narrow = foreign_buffer(view.address, view.nbytes, view)\n```\n\nThat means you can convert `Str` to `pyarrow.Buffer` and `Strs` to `pyarrow.Array` without extra copies.\n\n## Quick Start: C/C++ 🛠️\n\nThe C library is header-only, so you can just copy the `stringzilla.h` header into your project.\nSame applies to C++, where you would copy the `stringzilla.hpp` header.\nAlternatively, add it as a submodule, and include it in your build system.\n\n```sh\ngit submodule add https://github.com/ashvardanian/stringzilla.git\n```\n\nOr using a pure CMake approach:\n\n```cmake\nFetchContent_Declare(stringzilla GIT_REPOSITORY https://github.com/ashvardanian/stringzilla.git)\nFetchContent_MakeAvailable(stringzilla)\n```\n\nLast, but not the least, you can also install it as a library, and link against it.\nThis approach is worse for inlining, but brings dynamic runtime dispatch for the most advanced CPU features.\n\n### Basic Usage with C 99 and Newer\n\nThere is a stable C 99 interface, where all function names are prefixed with `sz_`.\nMost interfaces are well documented, and come with self-explanatory names and examples.\nIn some cases, hardware specific overloads are available, like `sz_find_avx512` or `sz_find_neon`.\nBoth are companions of the `sz_find`, first for x86 CPUs with AVX-512 support, and second for Arm NEON-capable CPUs.\n\n```c\n#include \n\n// Initialize your haystack and needle\nsz_string_view_t haystack = {your_text, your_text_length};\nsz_string_view_t needle = {your_subtext, your_subtext_length};\n\n// Perform string-level operations\nsz_size_t substring_position = sz_find(haystack.start, haystack.length, needle.start, needle.length);\nsz_size_t substring_position = sz_find_avx512(haystack.start, haystack.length, needle.start, needle.length);\nsz_size_t substring_position = sz_find_neon(haystack.start, haystack.length, needle.start, needle.length);\n\n// Hash strings\nsz_u64_t hash = sz_hash(haystack.start, haystack.length);\n\n// Perform collection level operations\nsz_sequence_t array = {your_order, your_count, your_get_start, your_get_length, your_handle};\nsz_sort(&array, &your_config);\n```\n\n

§ Mapping from LibC to StringZilla.

\n\nBy design, StringZilla has a couple of notable differences from LibC:\n\n1. all strings are expected to have a length, and are not necessarily null-terminated.\n2. every operations has a reverse order counterpart.\n\nThat way `sz_find` and `sz_rfind` are similar to `strstr` and `strrstr` in LibC.\nSimilarly, `sz_find_byte` and `sz_rfind_byte` replace `memchr` and `memrchr`.\nThe `sz_find_charset` maps to `strspn` and `strcspn`, while `sz_rfind_charset` has no sibling in LibC.\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n

LibC Functionality	StringZilla Equivalents
`memchr(haystack, needle, haystack_length)`, `strchr`	`sz_find_byte(haystack, haystack_length, needle)`
`memrchr(haystack, needle, haystack_length)`	`sz_rfind_byte(haystack, haystack_length, needle)`
`memcmp`, `strcmp`	`sz_order`, `sz_equal`
`strlen(haystack)`	`sz_find_byte(haystack, haystack_length, needle)`
`strcspn(haystack, needles)`	`sz_rfind_charset(haystack, haystack_length, needles_bitset)`
`strspn(haystack, needles)`	`sz_find_charset(haystack, haystack_length, needles_bitset)`
`memmem(haystack, haystack_length, needle, needle_length)`, `strstr`	`sz_find(haystack, haystack_length, needle, needle_length)`
`memcpy(destination, source, destination_length)`	`sz_copy(destination, source, destination_length)`
`memmove(destination, source, destination_length)`	`sz_move(destination, source, destination_length)`
`memset(destination, value, destination_length)`	`sz_fill(destination, destination_length, value)`

\n\n

\n\n### Basic Usage with C++ 11 and Newer\n\nThere is a stable C++ 11 interface available in the `ashvardanian::stringzilla` namespace.\nIt comes with two STL-like classes: `string_view` and `string`.\nThe first is a non-owning view of a string, and the second is a mutable string with a [Small String Optimization][faq-sso].\n\n```cpp\n#include \n\nnamespace sz = ashvardanian::stringzilla;\n\nsz::string haystack = \"some string\";\nsz::string_view needle = sz::string_view(haystack).substr(0, 4);\n\nauto substring_position = haystack.find(needle); // Or `rfind`\nauto hash = std::hash{}(haystack); // Compatible with STL's `std::hash`\n\nhaystack.end() - haystack.begin() == haystack.size(); // Or `rbegin`, `rend`\nhaystack.find_first_of(\" \\v\\t\") == 4; // Or `find_last_of`, `find_first_not_of`, `find_last_not_of`\nhaystack.starts_with(needle) == true; // Or `ends_with`\nhaystack.remove_prefix(needle.size()); // Why is this operation in-place?!\nhaystack.contains(needle) == true; // STL has this only from C++ 23 onwards\nhaystack.compare(needle) == 1; // Or `haystack <=> needle` in C++ 20 and beyond\n```\n\nStringZilla also provides string literals for automatic type resolution, [similar to STL][stl-literal]:\n\n```cpp\nusing sz::literals::operator\"\"_sz;\nusing std::literals::operator\"\"sv;\n\nauto a = \"some string\"; // char const *\nauto b = \"some string\"sv; // std::string_view\nauto b = \"some string\"_sz; // sz::string_view\n```\n\n[stl-literal]: https://en.cppreference.com/w/cpp/string/basic_string_view/operator%22%22sv\n\n### Memory Ownership and Small String Optimization\n\nMost operations in StringZilla don't assume any memory ownership.\nBut in addition to the read-only search-like operations StringZilla provides a minimalistic C and C++ implementations for a memory owning string \"class\".\nLike other efficient string implementations, it uses the [Small String Optimization][faq-sso] (SSO) to avoid heap allocations for short strings.\n\n[faq-sso]: https://cpp-optimizations.netlify.app/small_strings/\n\n```c\ntypedef union sz_string_t {\n struct internal {\n sz_ptr_t start;\n sz_u8_t length;\n char chars[SZ_STRING_INTERNAL_SPACE]; /// Ends with a null-terminator.\n } internal;\n\n struct external {\n sz_ptr_t start;\n sz_size_t length; \n sz_size_t space; /// The length of the heap-allocated buffer.\n sz_size_t padding;\n } external;\n\n} sz_string_t;\n```\n\nAs one can see, a short string can be kept on the stack, if it fits within `internal.chars` array.\nBefore 2015 GCC string implementation was just 8 bytes, and could only fit 7 characters.\nDifferent STL implementations today have different thresholds for the Small String Optimization.\nSimilar to GCC, StringZilla is 32 bytes in size, and similar to Clang it can fit 22 characters on stack.\nOur layout might be preferential, if you want to avoid branches.\nIf you use a different compiler, you may want to check it's SSO buffer size with a [simple Gist](https://gist.github.com/ashvardanian/c197f15732d9855c4e070797adf17b21).\n\n| | `libstdc++` in GCC 13 | `libc++` in Clang 17 | StringZilla |\n| :-------------------- | ---------------------: | -------------------: | ----------: |\n| `sizeof(std::string)` | 32 | 24 | 32 |\n| Small String Capacity | 15 | __22__ | __22__ |\n\nThis design has been since ported to many high-level programming languages.\nSwift, for example, [can store 15 bytes](https://developer.apple.com/documentation/swift/substring/withutf8(_:)#discussion) in the `String` instance itself.\nStringZilla implements SSO at the C level, providing the `sz_string_t` union and a simple API for primary operations.\n\n```c\nsz_memory_allocator_t allocator;\nsz_string_t string;\n\n// Init and make sure we are on stack\nsz_string_init(&string);\nsz_string_is_on_stack(&string); // == sz_true_k\n\n// Optionally pre-allocate space on the heap for future insertions.\nsz_string_grow(&string, 100, &allocator); // == sz_true_k\n\n// Append, erase, insert into the string.\nsz_string_expand(&string, 0, \"_Hello_\", 7, &allocator); // == sz_true_k\nsz_string_expand(&string, SZ_SIZE_MAX, \"world\", 5, &allocator); // == sz_true_k\nsz_string_erase(&string, 0, 1);\n\n// Unpacking & introspection.\nsz_ptr_t string_start;\nsz_size_t string_length;\nsz_size_t string_space;\nsz_bool_t string_is_external;\nsz_string_unpack(string, &string_start, &string_length, &string_space, &string_is_external);\nsz_equal(string_start, \"Hello_world\", 11); // == sz_true_k\n\n// Reclaim some memory.\nsz_string_shrink_to_fit(&string, &allocator); // == sz_true_k\nsz_string_free(&string, &allocator);\n```\n\nUnlike the conventional C strings, the `sz_string_t` is allowed to contain null characters.\nTo safely print those, pass the `string_length` to `printf` as well.\n\n```c\nprintf(\"%.*s\\n\", (int)string_length, string_start);\n```\n\n### What's Wrong with the C Standard Library?\n\nStringZilla is not a drop-in replacement for the C Standard Library.\nIt's designed to be a safer and more modern alternative.\nConceptually:\n\n1. LibC strings are expected to be null-terminated, so to use the efficient LibC implementations on slices of larger strings, you'd have to copy them, which is more expensive than the original string operation.\n2. LibC functionality is asymmetric - you can find the first and the last occurrence of a character within a string, but you can't find the last occurrence of a substring.\n3. LibC function names are typically very short and cryptic.\n4. LibC lacks crucial functionality like hashing and doesn't provide primitives for less critical but relevant operations like fuzzy matching.\n\nSomething has to be said about its support for UTF8.\nAside from a single-byte `char` type, LibC provides `wchar_t`:\n\n- The size of `wchar_t` is not consistent across platforms. On Windows, it's typically 16 bits (suitable for UTF-16), while on Unix-like systems, it's usually 32 bits (suitable for UTF-32). This inconsistency can lead to portability issues when writing cross-platform code.\n- `wchar_t` is designed to represent wide characters in a fixed-width format (UTF-16 or UTF-32). In contrast, UTF-8 is a variable-length encoding, where each character can take from 1 to 4 bytes. This fundamental difference means that `wchar_t` and UTF-8 are incompatible.\n\nStringZilla [partially addresses those issues](#unicode-utf-8-and-wide-characters).\n\n### What's Wrong with the C++ Standard Library?\n\n| C++ Code | Evaluation Result | Invoked Signature |\n| :----------------------------------- | :---------------- | :----------------------------- |\n| `\"Loose\"s.replace(2, 2, \"vath\"s, 1)` | `\"Loathe\"` 🤢 | `(pos1, count1, str2, pos2)` |\n| `\"Loose\"s.replace(2, 2, \"vath\", 1)` | `\"Love\"` 🥰 | `(pos1, count1, str2, count2)` |\n\nStringZilla is designed to be a drop-in replacement for the C++ Standard Templates Library.\nThat said, some of the design decisions of STL strings are highly controversial, error-prone, and expensive.\nMost notably:\n\n1. Argument order for `replace`, `insert`, `erase` and similar functions is impossible to guess.\n2. Bounds-checking exceptions for `substr`-like functions are only thrown for one side of the range.\n3. Returning string copies in `substr`-like functions results in absurd volume of allocations.\n4. Incremental construction via `push_back`-like functions goes through too many branches.\n5. Inconsistency between `string` and `string_view` methods, like the lack of `remove_prefix` and `remove_suffix`.\n\nCheck the following set of asserts validating the `std::string` specification.\nIt's not realistic to expect the average developer to remember the [14 overloads of `std::string::replace`][stl-replace].\n\n[stl-replace]: https://en.cppreference.com/w/cpp/string/basic_string/replace\n\n```cpp\nusing str = std::string;\n\nassert(str(\"hello world\").substr(6) == \"world\");\nassert(str(\"hello world\").substr(6, 100) == \"world\"); // 106 is beyond the length of the string, but its OK\nassert_throws(str(\"hello world\").substr(100), std::out_of_range); // 100 is beyond the length of the string\nassert_throws(str(\"hello world\").substr(20, 5), std::out_of_range); // 20 is beyond the length of the string\nassert_throws(str(\"hello world\").substr(-1, 5), std::out_of_range); // -1 casts to unsigned without any warnings...\nassert(str(\"hello world\").substr(0, -1) == \"hello world\"); // -1 casts to unsigned without any warnings...\n\nassert(str(\"hello\").replace(1, 2, \"123\") == \"h123lo\");\nassert(str(\"hello\").replace(1, 2, str(\"123\"), 1) == \"h23lo\");\nassert(str(\"hello\").replace(1, 2, \"123\", 1) == \"h1lo\");\nassert(str(\"hello\").replace(1, 2, \"123\", 1, 1) == \"h2lo\");\nassert(str(\"hello\").replace(1, 2, str(\"123\"), 1, 1) == \"h2lo\");\nassert(str(\"hello\").replace(1, 2, 3, 'a') == \"haaalo\");\nassert(str(\"hello\").replace(1, 2, {'a', 'b'}) == \"hablo\");\n```\n\nTo avoid those issues, StringZilla provides an alternative consistent interface.\nIt supports signed arguments, and doesn't have more than 3 arguments per function or\nThe standard API and our alternative can be conditionally disabled with `SZ_SAFETY_OVER_COMPATIBILITY=1`.\nWhen it's enabled, the _~~subjectively~~_ risky overloads from the Standard will be disabled.\n\n```cpp\nusing str = sz::string;\n\nstr(\"a:b\").front(1) == \"a\"; // no checks, unlike `substr`\nstr(\"a:b\").front(2) == \"2\"; // take first 2 characters\nstr(\"a:b\").back(-1) == \"b\"; // accepting negative indices\nstr(\"a:b\").back(-2) == \":b\"; // similar to Python's `\"a:b\"[-2:]`\nstr(\"a:b\").sub(1, -1) == \":\"; // similar to Python's `\"a:b\"[1:-1]`\nstr(\"a:b\").sub(-2, -1) == \":\"; // similar to Python's `\"a:b\"[-2:-1]`\nstr(\"a:b\").sub(-2, 1) == \"\"; // similar to Python's `\"a:b\"[-2:1]`\n\"a:b\"_sz[{-2, -1}] == \":\"; // works on views and overloads `operator[]`\n```\n\nAssuming StringZilla is a header-only library you can use the full API in some translation units and gradually transition to safer restricted API in others.\nBonus - all the bound checking is branchless, so it has a constant cost and won't hurt your branch predictor.\n\n### Beyond the C++ Standard Library - Learning from Python\n\nPython is arguably the most popular programming language for data science.\nIn part, that's due to the simplicity of its standard interfaces.\nStringZilla brings some of that functionality to C++.\n\n- Content checks: `isalnum`, `isalpha`, `isascii`, `isdigit`, `islower`, `isspace`, `isupper`.\n- Trimming character sets: `lstrip`, `rstrip`, `strip`.\n- Trimming string matches: `remove_prefix`, `remove_suffix`.\n- Ranges of search results: `splitlines`, `split`, `rsplit`.\n- Number of non-overlapping substring matches: `count`.\n- Partitioning: `partition`, `rpartition`.\n\nFor example, when parsing documents, it is often useful to split it into substrings.\nMost often, after that, you would compute the length of the skipped part, the offset and the length of the remaining part.\nThis results in a lot of pointer arithmetic and is error-prone.\nStringZilla provides a convenient `partition` function, which returns a tuple of three string views, making the code cleaner.\n\n```cpp\nauto parts = haystack.partition(':'); // Matching a character\nauto [before, match, after] = haystack.partition(':'); // Structure unpacking\nauto [before, match, after] = haystack.partition(sz::char_set(\":;\")); // Character-set argument\nauto [before, match, after] = haystack.partition(\" : \"); // String argument\nauto [before, match, after] = haystack.rpartition(sz::whitespaces_set()); // Split around the last whitespace\n```\n\nCombining those with the `split` function, one can easily parse a CSV file or HTTP headers.\n\n```cpp\nfor (auto line : haystack.split(\"\\r\\n\")) {\n auto [key, _, value] = line.partition(':');\n headers[key.strip()] = value.strip();\n}\n```\n\nSome other extensions are not present in the Python standard library either.\nLet's go through the C++ functionality category by category.\n\n- [Splits and Ranges](#splits-and-ranges).\n- [Concatenating Strings without Allocations](#concatenating-strings-without-allocations).\n- [Random Generation](#random-generation).\n- [Edit Distances and Fuzzy Search](#levenshtein-edit-distance-and-alignment-scores).\n\nSome of the StringZilla interfaces are not available even Python's native `str` class.\nHere is a sneak peek of the most useful ones.\n\n```cpp\ntext.hash(); // -> 64 bit unsigned integer \ntext.ssize(); // -> 64 bit signed length to avoid `static_cast(text.size())`\ntext.contains_only(\" \\w\\t\"); // == text.find_first_not_of(sz::char_set(\" \\w\\t\")) == npos;\ntext.contains(sz::whitespaces_set()); // == text.find(sz::char_set(sz::whitespaces_set())) != npos;\n\n// Simpler slicing than `substr`\ntext.front(10); // -> sz::string_view\ntext.back(10); // -> sz::string_view\n\n// Safe variants, which clamp the range into the string bounds\nusing sz::string::cap;\ntext.front(10, cap) == text.front(std::min(10, text.size()));\ntext.back(10, cap) == text.back(std::min(10, text.size()));\n\n// Character set filtering\ntext.lstrip(sz::whitespaces_set()).rstrip(sz::newlines_set()); // like Python\ntext.front(sz::whitespaces_set()); // all leading whitespaces\ntext.back(sz::digits_set()); // all numerical symbols forming the suffix\n\n// Incremental construction\nusing sz::string::unchecked;\ntext.push_back('x'); // no surprises here\ntext.push_back('x', unchecked); // no bounds checking, Rust style\ntext.try_push_back('x'); // returns `false` if the string is full and the allocation failed\n\nsz::concatenate(text, \"@\", domain, \".\", tld); // No allocations\n```\n\n### Splits and Ranges\n\nOne of the most common use cases is to split a string into a collection of substrings.\nWhich would often result in [StackOverflow lookups][so-split] and snippets like the one below.\n\n[so-split]: https://stackoverflow.com/questions/14265581/parse-split-a-string-in-c-using-string-delimiter-standard-c\n\n```cpp\nstd::vector lines = split(haystack, \"\\r\\n\"); // string delimiter\nstd::vector words = split(lines, ' '); // character delimiter\n```\n\nThose allocate memory for each string and the temporary vectors.\nEach allocation can be orders of magnitude more expensive, than even serial `for`-loop over characters.\nTo avoid those, StringZilla provides lazily-evaluated ranges, compatible with the [Range-v3][range-v3] library.\n\n[range-v3]: https://github.com/ericniebler/range-v3\n\n```cpp\nfor (auto line : haystack.split(\"\\r\\n\"))\n for (auto word : line.split(sz::char_set(\" \\w\\t.,;:!?\")))\n std::cout << word << std::endl;\n```\n\nEach of those is available in reverse order as well.\nIt also allows interleaving matches, if you want both inclusions of `xx` in `xxx`.\nDebugging pointer offsets is not a pleasant exercise, so keep the following functions in mind.\n\n- `haystack.[r]find_all(needle, interleaving)`\n- `haystack.[r]find_all(sz::char_set(\"\"))`\n- `haystack.[r]split(needle)`\n- `haystack.[r]split(sz::char_set(\"\"))`\n\nFor $N$ matches the split functions will report $N+1$ matches, potentially including empty strings.\nRanges have a few convenience methods as well:\n\n```cpp\nrange.size(); // -> std::size_t\nrange.empty(); // -> bool\nrange.template to>(); \nrange.template to>(); \n```\n\n### Concatenating Strings without Allocations\n\nAnother common string operation is concatenation.\nThe STL provides `std::string::operator+` and `std::string::append`, but those are not very efficient, if multiple invocations are performed.\n\n```cpp\nstd::string name, domain, tld;\nauto email = name + \"@\" + domain + \".\" + tld; // 4 allocations\n```\n\nThe efficient approach would be to pre-allocate the memory and copy the strings into it.\n\n```cpp\nstd::string email;\nemail.reserve(name.size() + domain.size() + tld.size() + 2);\nemail.append(name), email.append(\"@\"), email.append(domain), email.append(\".\"), email.append(tld);\n```\n\nThat's mouthful and error-prone.\nStringZilla provides a more convenient `concatenate` function, which takes a variadic number of arguments.\nIt also overrides the `operator|` to concatenate strings lazily, without any allocations.\n\n```cpp\nauto email = sz::concatenate(name, \"@\", domain, \".\", tld); // 0 allocations\nauto email = name | \"@\" | domain | \".\" | tld; // 0 allocations\nsz::string email = name | \"@\" | domain | \".\" | tld; // 1 allocations\n```\n\n### Random Generation\n\nSoftware developers often need to generate random strings for testing purposes.\nThe STL provides `std::generate` and `std::random_device`, that can be used with StringZilla.\n\n```cpp\nsz::string random_string(std::size_t length, char const *alphabet, std::size_t cardinality) {\n sz::string result(length, '\\0');\n static std::random_device seed_source; // Expensive to construct - due to system calls\n static std::mt19937 generator(seed_source()); // Also expensive - due to the state size\n std::uniform_int_distribution distribution(0, cardinality);\n std::generate(result.begin(), result.end(), [&]() { return alphabet[distribution(generator)]; });\n return result;\n}\n```\n\nMouthful and slow.\nStringZilla provides a C native method - `sz_generate` and a convenient C++ wrapper - `sz::generate`.\nSimilar to Python it also defines the commonly used character sets.\n\n```cpp\nauto protein = sz::string::random(300, \"ARNDCQEGHILKMFPSTWYV\"); // static method\nauto dna = sz::basic_string::random(3_000_000_000, \"ACGT\");\n\ndna.randomize(\"ACGT\"); // `noexcept` pre-allocated version\ndna.randomize(&std::rand, \"ACGT\"); // pass any generator, like `std::mt19937`\n\nchar uuid[36];\nsz::randomize(sz::string_span(uuid, 36), \"0123456789abcdef-\"); // Overwrite any buffer\n```\n\n### Bulk Replacements\n\nIn text processing, it's often necessary to replace all occurrences of a specific substring or set of characters within a string.\nStandard library functions may not offer the most efficient or convenient methods for performing bulk replacements, especially when dealing with large strings or performance-critical applications.\n\n- `haystack.replace_all(needle_string, replacement_string)`\n- `haystack.replace_all(sz::char_set(\"\"), replacement_string)`\n- `haystack.try_replace_all(needle_string, replacement_string)`\n- `haystack.try_replace_all(sz::char_set(\"\"), replacement_string)`\n- `haystack.transform(sz::look_up_table::identity())`\n- `haystack.transform(sz::look_up_table::identity(), haystack.data())`\n\n### Levenshtein Edit Distance and Alignment Scores\n\nLevenshtein and Hamming edit distance are provided for both byte-strings and UTF-8 strings.\nThe latter will output the distance in Unicode code points, not bytes.\nNeedleman-Wunsch alignment scores are only defined for byte-strings.\n\n```cpp\n// Count number of substitutions in same length strings\nsz::hamming_distance(first, second[, upper_bound]) -> std::size_t;\nsz::hamming_distance_utf8(first, second[, upper_bound]) -> std::size_t;\n\n// Count number of insertions, deletions and substitutions\nsz::edit_distance(first, second[, upper_bound[, allocator]]) -> std::size_t;\nsz::edit_distance_utf8(first, second[, upper_bound[, allocator]]) -> std::size_t;\n\n// Substitution-parametrized Needleman-Wunsch global alignment score\nstd::int8_t costs[256][256]; // Substitution costs matrix\nsz::alignment_score(first, second, costs[, gap_score[, allocator]) -> std::ptrdiff_t;\n```\n\n### Sorting in C and C++\n\nLibC provides `qsort` and STL provides `std::sort`.\nBoth have their quarks.\nThe LibC standard has no way to pass a context to the comparison function, that's only possible with platform-specific extensions.\nThose have [different arguments order](https://stackoverflow.com/a/39561369) on every OS.\n\n```c\n// Linux: https://linux.die.net/man/3/qsort_r\nvoid qsort_r(void *elements, size_t count, size_t element_width, \n int (*compare)(void const *left, void const *right, void *context),\n void *context);\n// MacOS and FreeBSD: https://developer.apple.com/library/archive/documentation/System/Conceptual/ManPages_iPhoneOS/man3/qsort_r.3.html\nvoid qsort_r(void *elements, size_t count, size_t element_width, \n void *context,\n int (*compare)(void *context, void const *left, void const *right));\n// Windows conflicts with ISO `qsort_s`: https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/qsort-s?view=msvc-170\nvoid qsort_s(id *elements, size_t count, size_t element_width, \n int (*compare)(void *context, void const *left, void const *right),\n void *context);\n```\n\nC++ generic algorithm is not perfect either.\nThere is no guarantee in the standard that `std::sort` won't allocate any memory.\nIf you are running on embedded, in real-time or on 100+ CPU cores per node, you may want to avoid that.\nStringZilla doesn't solve the general case, but hopes to improve the performance for strings.\nUse `sz_sort`, or the high-level `sz::sorted_order`, which can be used sort any collection of elements convertible to `sz::string_view`.\n\n```cpp\nstd::vector data({\"c\", \"b\", \"a\"});\nstd::vector order = sz::sorted_order(data); //< Simple shortcut\n\n// Or, taking care of memory allocation:\nsz::sorted_order(data.begin(), data.end(), order.data(), [](auto const &x) -> sz::string_view { return x; });\n```\n\n### Standard C++ Containers with String Keys\n\nThe C++ Standard Templates Library provides several associative containers, often used with string keys.\n\n```cpp\nstd::map> sorted_words;\nstd::unordered_map, std::equal_to> words;\n```\n\nThe performance of those containers is often limited by the performance of the string keys, especially on reads.\nStringZilla can be used to accelerate containers with `std::string` keys, by overriding the default comparator and hash functions.\n\n```cpp\nstd::map sorted_words;\nstd::unordered_map words;\n```\n\nAlternatively, a better approach would be to use the `sz::string` class as a key.\nThe right hash function and comparator would be automatically selected and the performance gains would be more noticeable if the keys are short.\n\n```cpp\nstd::map sorted_words;\nstd::unordered_map words;\n```\n\n### Compilation Settings and Debugging\n\n__`SZ_DEBUG`__:\n\n> For maximal performance, the C library does not perform any bounds checking in Release builds.\n> In C++, bounds checking happens only in places where the STL `std::string` would do it.\n> If you want to enable more aggressive bounds-checking, define `SZ_DEBUG` before including the header.\n> If not explicitly set, it will be inferred from the build type.\n\n__`SZ_USE_X86_AVX512`, `SZ_USE_X86_AVX2`, `SZ_USE_ARM_NEON`__:\n\n> One can explicitly disable certain families of SIMD instructions for compatibility purposes.\n> Default values are inferred at compile time.\n\n__`SZ_DYNAMIC_DISPATCH`__:\n\n> By default, StringZilla is a header-only library.\n> But if you are running on different generations of devices, it makes sense to pre-compile the library for all supported generations at once, and dispatch at runtime.\n> This flag does just that and is used to produce the `stringzilla.so` shared library, as well as the Python bindings.\n\n__`SZ_USE_MISALIGNED_LOADS`__:\n\n> By default, StringZilla avoids misaligned loads.\n> If supported, it replaces many byte-level operations with word-level ones.\n> Going from `char`-like types to `uint64_t`-like ones can significantly accelerate the serial (SWAR) backend.\n> So consider enabling it if you are building for some embedded device.\n\n__`SZ_AVOID_LIBC`__ and __`SZ_OVERRIDE_LIBC`__:\n\n> When using the C header-only library one can disable the use of LibC.\n> This may affect the type resolution system on obscure hardware platforms. \n> Moreover, one may let `stringzilla` override the common symbols like the `memcpy` and `memset` with its own implementations.\n> In that case you can use the [`LD_PRELOAD` trick][ld-preload-trick] to prioritize it's symbols over the ones from the LibC and accelerate existing string-heavy applications without recompiling them.\n> It also adds a layer of security, as the `stringzilla` isn't [undefined for NULL inputs][redhat-memcpy-ub] like `memcpy(NULL, NULL, 0)`.\n\n[ld-preload-trick]: https://ashvardanian.com/posts/ld-preload-libsee\n[redhat-memcpy-ub]: https://developers.redhat.com/articles/2024/12/11/making-memcpynull-null-0-well-defined\n\n__`SZ_AVOID_STL`__ and __`SZ_SAFETY_OVER_COMPATIBILITY`__:\n\n> When using the C++ interface one can disable implicit conversions from `std::string` to `sz::string` and back.\n> If not needed, the `` and `` headers will be excluded, reducing compilation time.\n> Moreover, if STL compatibility is a low priority, one can make the API safer by disabling the overloads, which are subjectively error prone.\n\n__`STRINGZILLA_BUILD_SHARED`, `STRINGZILLA_BUILD_TEST`, `STRINGZILLA_BUILD_BENCHMARK`, `STRINGZILLA_TARGET_ARCH`__ for CMake users:\n\n> When compiling the tests and benchmarks, you can explicitly set the target hardware architecture.\n> It's synonymous to GCC's `-march` flag and is used to enable/disable the appropriate instruction sets.\n> You can also disable the shared library build, if you don't need it.\n\n## Quick Start: Rust 🦀\n\nStringZilla is available as a Rust crate, with documentation available on [docs.rs/stringzilla](https://docs.rs/stringzilla).\nTo use the latest crate release in your project, add the following to your `Cargo.toml`:\n\n```toml\n[dependencies]\nstringzilla = \">=3\"\n```\n\nOr if you want to use the latest pre-release version from the repository:\n\n```toml\n[dependencies]\nstringzilla = { git = \"https://github.com/ashvardanian/stringzilla\", branch = \"main-dev\" }\n```\n\nOnce installed, all of the functionality is available through the `stringzilla` namespace.\nMany interfaces will look familiar to the users of the `memchr` crate.\n\n```rust\nuse stringzilla::sz;\n\n// Identical to `memchr::memmem::find` and `memchr::memmem::rfind` functions\nsz::find(\"Hello, world!\", \"world\") // 7\nsz::rfind(\"Hello, world!\", \"world\") // 7\n\n// Generalizations of `memchr::memrchr[123]`\nsz::find_char_from(\"Hello, world!\", \"world\") // 2\nsz::rfind_char_from(\"Hello, world!\", \"world\") // 11\n```\n\nUnlike `memchr`, the throughput of `stringzilla` is [high in both normal and reverse-order searches][memchr-benchmarks].\nIt also provides no constraints on the size of the character set, while `memchr` allows only 1, 2, or 3 characters.\nIn addition to global functions, `stringzilla` provides a `StringZilla` extension trait:\n\n```rust\nuse stringzilla::StringZilla;\n\nlet my_string: String = String::from(\"Hello, world!\");\nlet my_str = my_string.as_str();\nlet my_cow_str = Cow::from(&my_string);\n\n// Use the generic function with a String\nassert_eq!(my_string.sz_find(\"world\"), Some(7));\nassert_eq!(my_string.sz_rfind(\"world\"), Some(7));\nassert_eq!(my_string.sz_find_char_from(\"world\"), Some(2));\nassert_eq!(my_string.sz_rfind_char_from(\"world\"), Some(11));\nassert_eq!(my_string.sz_find_char_not_from(\"world\"), Some(0));\nassert_eq!(my_string.sz_rfind_char_not_from(\"world\"), Some(12));\n\n// Same works for &str and Cow<'_, str>\nassert_eq!(my_str.sz_find(\"world\"), Some(7));\nassert_eq!(my_cow_str.as_ref().sz_find(\"world\"), Some(7));\n```\n\nThe library also exposes Levenshtein and Hamming edit-distances for byte-arrays and UTF-8 strings, as well as Needleman-Wunch alignment scores.\n\n```rust\nuse stringzilla::sz;\n\n// Handling arbitrary byte arrays:\nsz::edit_distance(\"Hello, world!\", \"Hello, world?\"); // 1\nsz::hamming_distance(\"Hello, world!\", \"Hello, world?\"); // 1\nsz::alignment_score(\"Hello, world!\", \"Hello, world?\", sz::unary_substitution_costs(), -1); // -1\n\n// Handling UTF-8 strings:\nsz::hamming_distance_utf8(\"αβγδ\", \"αγγδ\") // 1\nsz::edit_distance_utf8(\"façade\", \"facade\") // 1\n```\n\n[memchr-benchmarks]: https://github.com/ashvardanian/memchr_vs_stringzilla\n\n## Quick Start: Swift 🍏\n\nStringZilla can be added as a dependency in the Swift Package Manager.\nIn your `Package.swift` file, add the following:\n\n```swift\ndependencies: [\n .package(url: \"https://github.com/ashvardanian/stringzilla\")\n]\n```\n\nThe package currently covers only the most basic functionality, but is planned to be extended to cover the full C++ API.\n\n```swift\nvar s = \"Hello, world! Welcome to StringZilla. 👋\"\ns[s.findFirst(substring: \"world\")!...] // \"world! Welcome to StringZilla. 👋\") \ns[s.findLast(substring: \"o\")!...] // \"o StringZilla. 👋\")\ns[s.findFirst(characterFrom: \"aeiou\")!...] // \"ello, world! Welcome to StringZilla. 👋\")\ns[s.findLast(characterFrom: \"aeiou\")!...] // \"a. 👋\")\ns[s.findFirst(characterNotFrom: \"aeiou\")!...] // \"Hello, world! Welcome to StringZilla. 👋\"\ns.editDistance(from: \"Hello, world!\")! // 29\n```\n\n## Algorithms & Design Decisions 📚\n\nStringZilla aims to optimize some of the slowest string operations.\nSome popular operations, however, like equality comparisons and relative order checking, almost always complete on some of the very first bytes in either string.\nIn such operations vectorization is almost useless, unless huge and very similar strings are considered.\nStringZilla implements those operations as well, but won't result in substantial speedups.\n\n### Exact Substring Search\n\nSubstring search algorithms are generally divided into: comparison-based, automaton-based, and bit-parallel.\nDifferent families are effective for different alphabet sizes and needle lengths.\nThe more operations are needed per-character - the more effective SIMD would be.\nThe longer the needle - the more effective the skip-tables are.\nStringZilla uses different exact substring search algorithms for different needle lengths and backends:\n\n- When no SIMD is available - SWAR (SIMD Within A Register) algorithms are used on 64-bit words.\n- Boyer-Moore-Horspool (BMH) algorithm with Raita heuristic variation for longer needles.\n- SIMD algorithms are randomized to look at different parts of the needle.\n\nOn very short needles, especially 1-4 characters long, brute force with SIMD is the fastest solution.\nOn mid-length needles, bit-parallel algorithms are effective, as the character masks fit into 32-bit or 64-bit words.\nEither way, if the needle is under 64-bytes long, on haystack traversal we will still fetch every CPU cache line.\nSo the only way to improve performance is to reduce the number of comparisons.\nThe snippet below shows how StringZilla accomplishes that for needles of length two.\n\nhttps://github.com/ashvardanian/StringZilla/blob/266c01710dddf71fc44800f36c2f992ca9735f87/include/stringzilla/stringzilla.h#L1585-L1637\n\nGoing beyond that, to long needles, Boyer-Moore (BM) and its variants are often the best choice.\nIt has two tables: the good-suffix shift and the bad-character shift.\nCommon choice is to use the simplified BMH algorithm, which only uses the bad-character shift table, reducing the pre-processing time.\nWe do the same for mid-length needles up to 256 bytes long.\nThat way the stack-allocated shift table remains small.\n\nhttps://github.com/ashvardanian/StringZilla/blob/46e957cd4f9ecd4945318dd3c48783dd11323f37/include/stringzilla/stringzilla.h#L1774-L1825\n\nIn the C++ Standards Library, the `std::string::find` function uses the BMH algorithm with Raita's heuristic.\nBefore comparing the entire string, it matches the first, last, and the middle character.\nVery practical, but can be slow for repetitive characters.\nBoth SWAR and SIMD backends of StringZilla have a cheap pre-processing step, where we locate unique characters.\nThis makes the library a lot more practical when dealing with non-English corpora.\n\nhttps://github.com/ashvardanian/StringZilla/blob/46e957cd4f9ecd4945318dd3c48783dd11323f37/include/stringzilla/stringzilla.h#L1398-L1431\n\nAll those, still, have $O(hn)$ worst case complexity.\nTo guarantee $O(h)$ worst case time complexity, the Apostolico-Giancarlo (AG) algorithm adds an additional skip-table.\nPreprocessing phase is $O(n+sigma)$ in time and space.\nOn traversal, performs from $(h/n)$ to $(3h/2)$ comparisons.\nIt however, isn't practical on modern CPUs.\nA simpler idea, the Galil-rule might be a more relevant optimizations, if many matches must be found.\n\nOther algorithms previously considered and deprecated:\n\n- Apostolico-Giancarlo algorithm for longer needles. _Control-flow is too complex for efficient vectorization._\n- Shift-Or-based Bitap algorithm for short needles. _Slower than SWAR._\n- Horspool-style bad-character check in SIMD backends. _Effective only for very long needles, and very uneven character distributions between the needle and the haystack. Faster \"character-in-set\" check needed to generalize._\n\n> § Reading materials.\n> [Exact String Matching Algorithms in Java](https://www-igm.univ-mlv.fr/~lecroq/string).\n> [SIMD-friendly algorithms for substring searching](http://0x80.pl/articles/simd-strfind.html).\n\n### Levenshtein Edit Distance\n\nLevenshtein distance is the best known edit-distance for strings, that checks, how many insertions, deletions, and substitutions are needed to transform one string to another.\nIt's extensively used in approximate string-matching, spell-checking, and bioinformatics.\n\nThe computational cost of the Levenshtein distance is $O(n * m)$, where $n$ and $m$ are the lengths of the string arguments.\nTo compute that, the naive approach requires $O(n * m)$ space to store the \"Levenshtein matrix\", the bottom-right corner of which will contain the Levenshtein distance.\nThe algorithm producing the matrix has been simultaneously studied/discovered by the Soviet mathematicians Vladimir Levenshtein in 1965, Taras Vintsyuk in 1968, and American computer scientists - Robert Wagner, David Sankoff, Michael J. Fischer in the following years.\nSeveral optimizations are known:\n\n1. __Space Optimization__: The matrix can be computed in $O(min(n,m))$ space, by only storing the last two rows of the matrix.\n2. __Divide and Conquer__: Hirschberg's algorithm can be applied to decompose the computation into subtasks.\n3. __Automata__: Levenshtein automata can be effective, if one of the strings doesn't change, and is a subject to many comparisons.\n4. __Shift-Or__: Bit-parallel algorithms transpose the matrix into a bit-matrix, and perform bitwise operations on it.\n\nThe last approach is quite powerful and performant, and is used by the great [RapidFuzz][rapidfuzz] library.\nIt's less known, than the others, derived from the Baeza-Yates-Gonnet algorithm, extended to bounded edit-distance search by Manber and Wu in 1990s, and further extended by Gene Myers in 1999 and Heikki Hyyro between 2002 and 2004.\n\nStringZilla introduces a different approach, extensively used in Unum's internal combinatorial optimization libraries.\nThe approach doesn't change the number of trivial operations, but performs them in a different order, removing the data dependency, that occurs when computing the insertion costs.\nThis results in much better vectorization for intra-core parallelism and potentially multi-core evaluation of a single request.\n\nNext design goals:\n\n- [ ] Generalize fast traversals to rectangular matrices.\n- [ ] Port x86 AVX-512 solution to Arm NEON.\n\n> § Reading materials.\n> [Faster Levenshtein Distances with a SIMD-friendly Traversal Order](https://ashvardanian.com/posts/levenshtein-diagonal).\n\n[rapidfuzz]: https://github.com/rapidfuzz/RapidFuzz\n\n### Needleman-Wunsch Alignment Score for Bioinformatics\n\nThe field of bioinformatics studies various representations of biological structures.\nThe \"primary\" representations are generally strings over sparse alphabets:\n\n- [DNA][faq-dna] sequences, where the alphabet is {A, C, G, T}, ranging from ~100 characters for short reads to 3 billion for the human genome.\n- [RNA][faq-rna] sequences, where the alphabet is {A, C, G, U}, ranging from ~50 characters for tRNA to thousands for mRNA.\n- [Proteins][faq-protein], where the alphabet is made of 22 amino acids, ranging from 2 characters for [dipeptide][faq-dipeptide] to 35,000 for [Titin][faq-titin], the longest protein.\n\nThe shorter the representation, the more often researchers may want to use custom substitution matrices.\nMeaning that the cost of a substitution between two characters may not be the same for all pairs.\n\nStringZilla adapts the fairly efficient two-row Wagner-Fisher algorithm as a baseline serial implementation of the Needleman-Wunsch score.\nIt supports arbitrary alphabets up to 256 characters, and can be used with either [BLOSUM][faq-blosum], [PAM][faq-pam], or other substitution matrices.\nIt also uses SIMD for hardware acceleration of the substitution lookups.\nThis however, does not __yet__ break the data-dependency for insertion costs, where 80% of the time is wasted.\nWith that solved, the SIMD implementation will become 5x faster than the serial one.\n\n[faq-dna]: https://en.wikipedia.org/wiki/DNA\n[faq-rna]: https://en.wikipedia.org/wiki/RNA\n[faq-protein]: https://en.wikipedia.org/wiki/Protein\n[faq-blosum]: https://en.wikipedia.org/wiki/BLOSUM\n[faq-pam]: https://en.wikipedia.org/wiki/Point_accepted_mutation\n[faq-dipeptide]: https://en.wikipedia.org/wiki/Dipeptide\n[faq-titin]: https://en.wikipedia.org/wiki/Titin\n\n### Memory Copying, Fills, and Moves\n\nA lot has been written about the time computers spend copying memory and how that operation is implemented in LibC.\nInterestingly, the operation can still be improved, as most Assembly implementations use outdated instructions.\nEven performance-oriented STL replacements, like Meta's [Folly v2024.09.23 focus on AVX2](https://github.com/facebook/folly/blob/main/folly/memset.S), and don't take advantage of the new masked instructions in AVX-512 or SVE.\n\nIn AVX-512, StringZilla uses non-temporal stores to avoid cache pollution, when dealing with very large strings.\nMoreover, it handles the unaligned head and the tails of the `target` buffer separately, ensuring that writes in big copies are always aligned to cache-line boundaries.\nThat's true for both AVX2 and AVX-512 backends.\n\nStringZilla also contains \"drafts\" of smarter, but less efficient algorithms, that minimize the number of unaligned loads, perfoming shuffles and permutations.\nThat's a topic for future research, as the performance gains are not yet satisfactory.\n\n> § Reading materials.\n> [`memset` benchmarks](https://github.com/nadavrot/memset_benchmark?tab=readme-ov-file) by Nadav Rotem.\n> [Cache Associativity](https://en.algorithmica.org/hpc/cpu-cache/associativity/) by Sergey Slotin.\n\n### Random Generation\n\nGenerating random strings from different alphabets is a very common operation.\nStringZilla accepts an arbitrary [Pseudorandom Number Generator][faq-prng] to produce noise, and an array of characters to sample from.\nSampling is optimized to avoid integer division, a costly operation on modern CPUs.\nFor that a 768-byte long lookup table is used to perform 2 lookups, 1 multiplication, 2 shifts, and 2 accumulations.\n\nhttps://github.com/ashvardanian/StringZilla/blob/266c01710dddf71fc44800f36c2f992ca9735f87/include/stringzilla/stringzilla.h#L2490-L2533\n\n[faq-prng]: https://en.wikipedia.org/wiki/Pseudorandom_number_generator\n\n### Sorting\n\nFor lexicographic sorting of strings, StringZilla uses a \"hybrid-hybrid\" approach with $O(n * log(n))$ and.\n\n1. Radix sort for first bytes exported into a continuous buffer for locality.\n2. IntroSort on partially ordered chunks to balance efficiency and worst-case performance.\n 1. IntroSort begins with a QuickSort.\n 2. If the recursion depth exceeds a certain threshold, it switches to a HeapSort.\n\nA better algorithm is in development.\nCheck #173 for design goals and progress updates.\n\n### Hashing\n\n> [!WARNING]\n> Hash functions are not cryptographically safe and are currently under active development.\n> They may change in future __minor__ releases.\n\nChoosing the right hashing algorithm for your application can be crucial from both performance and security standpoint.\nIn StringZilla a 64-bit rolling hash function is reused for both string hashes and substring hashes, Rabin-style fingerprints.\nRolling hashes take the same amount of time to compute hashes with different window sizes, and are fast to update.\nThose are not however perfect hashes, and collisions are frequent.\nStringZilla attempts to use SIMD, but the performance is not __yet__ satisfactory.\nOn Intel Sapphire Rapids, the following numbers can be expected for N-way parallel variants.\n\n- 4-way AVX2 throughput with 64-bit integer multiplication (no native support): 0.28 GB/s.\n- 4-way AVX2 throughput with 32-bit integer multiplication: 0.54 GB/s.\n- 4-way AVX-512DQ throughput with 64-bit integer multiplication: 0.46 GB/s.\n- 4-way AVX-512 throughput with 32-bit integer multiplication: 0.58 GB/s.\n- 8-way AVX-512 throughput with 32-bit integer multiplication: 0.11 GB/s.\n\nNext design goals:\n\n- [ ] Try gear-hash and other rolling approaches.\n\n#### Why not CRC32?\n\nCyclic Redundancy Check 32 is one of the most commonly used hash functions in Computer Science.\nIt has in-hardware support on both x86 and Arm, for both 8-bit, 16-bit, 32-bit, and 64-bit words.\nThe `0x1EDC6F41` polynomial is used in iSCSI, Btrfs, ext4, and the `0x04C11DB7` in SATA, Ethernet, Zlib, PNG.\nIn case of Arm more than one polynomial is supported.\nIt is, however, somewhat limiting for Big Data usecases, which often have to deal with more than 4 Billion strings, making collisions unavoidable.\nMoreover, the existing SIMD approaches are tricky, combining general purpose computations with specialized instructions, to utilize more silicon in every cycle.\n\n> § Reading materials.\n> [Comprehensive derivation of approaches](https://github.com/komrad36/CRC)\n> [Faster computation for 4 KB buffers on x86](https://www.corsix.org/content/fast-crc32c-4k)\n> [Comparing different lookup tables](https://create.stephan-brumme.com/crc32)\n> Great open-source implementations.\n> [By Peter Cawley](https://github.com/corsix/fast-crc32)\n> [By Stephan Brumme](https://github.com/stbrumme/crc32)\n\n#### Other Modern Alternatives\n\n[MurmurHash](https://github.com/aappleby/smhasher/blob/master/README.md) from 2008 by Austin Appleby is one of the best known non-cryptographic hashes.\nIt has a very short implementation and is capable of producing 32-bit and 128-bit hashes.\nThe [CityHash](https://opensource.googleblog.com/2011/04/introducing-cityhash) from 2011 by Google and the [xxHash](https://github.com/Cyan4973/xxHash) improve on that, better leveraging the super-scalar nature of modern CPUs and producing 64-bit and 128-bit hashes.\n\nNeither of those functions are cryptographic, unlike MD5, SHA, and BLAKE algorithms.\nMost of cryptographic hashes are based on the Merkle-Damgård construction, and aren't resistant to the length-extension attacks.\nCurrent state of the Art, might be the [BLAKE3](https://github.com/BLAKE3-team/BLAKE3) algorithm.\nIt's resistant to a broad range of attacks, can process 2 bytes per CPU cycle, and comes with a very optimized official implementation for C and Rust.\nIt has the same 128-bit security level as the BLAKE2, and achieves its performance gains by reducing the number of mixing rounds, and processing data in 1 KiB chunks, which is great for longer strings, but may result in poor performance on short ones.\n\nAll mentioned libraries have undergone extensive testing and are considered production-ready.\nThey can definitely accelerate your application, but so may the downstream mixer.\nFor instance, when a hash-table is constructed, the hashes are further shrunk to address table buckets.\nIf the mixer looses entropy, the performance gains from the hash function may be lost.\nAn example would be power-of-two modulo, which is a common mixer, but is known to be weak.\nOne alternative would be the [fastrange](https://github.com/lemire/fastrange) by Daniel Lemire.\nAnother one is the [Fibonacci hash trick](https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/) using the Golden Ratio, also used in StringZilla.\n\n### Unicode, UTF-8, and Wide Characters\n\nMost StringZilla operations are byte-level, so they work well with ASCII and UTF8 content out of the box.\nIn some cases, like edit-distance computation, the result of byte-level evaluation and character-level evaluation may differ.\nSo StringZilla provides following functions to work with Unicode:\n\n- `sz_edit_distance_utf8` - computes the Levenshtein distance between two UTF-8 strings.\n- `sz_hamming_distance_utf8` - computes the Hamming distance between two UTF-8 strings.\n\nJava, JavaScript, Python 2, C#, and Objective-C, however, use wide characters (`wchar`) - two byte long codes, instead of the more reasonable fixed-length UTF32 or variable-length UTF8.\nThis leads [to all kinds of offset-counting issues][wide-char-offsets] when facing four-byte long Unicode characters.\nSo consider transcoding with [simdutf](https://github.com/simdutf/simdutf), if you are coming from such environments.\n\n[wide-char-offsets]: https://josephg.com/blog/string-length-lies/\n\n## Contributing 👾\n\nPlease check out the [contributing guide](https://github.com/ashvardanian/StringZilla/blob/main/CONTRIBUTING.md) for more details on how to setup the development environment and contribute to this project.\nIf you like this project, you may also enjoy [USearch][usearch], [UCall][ucall], [UForm][uform], and [SimSIMD][simsimd]. 🤗\n\n[usearch]: https://github.com/unum-cloud/usearch\n[ucall]: https://github.com/unum-cloud/ucall\n[uform]: https://github.com/unum-cloud/uform\n[simsimd]: https://github.com/ashvardanian/simsimd\n\nIf you like strings and value efficiency, you may also enjoy the following projects:\n\n- [simdutf](https://github.com/simdutf/simdutf) - transcoding UTF8, UTF16, and UTF32 LE and BE.\n- [hyperscan](https://github.com/intel/hyperscan) - regular expressions with SIMD acceleration.\n- [pyahocorasick](https://github.com/WojciechMula/pyahocorasick) - Aho-Corasick algorithm in Python.\n- [rapidfuzz](https://github.com/rapidfuzz/RapidFuzz) - fast string matching in C++ and Python.\n\nIf you are looking for more reading materials on this topic, consider the following:\n\n- [5x faster strings with SIMD & SWAR](https://ashvardanian.com/posts/stringzilla/).\n- [The Painful Pitfalls of C++ STL Strings](https://ashvardanian.com/posts/painful-strings/).\n\n## License 📜\n\nFeel free to use the project under Apache 2.0 or the Three-clause BSD license at your preference.\n","description_content_type":"text/markdown","docs_url":null,"download_url":null,"downloads":{"last_day":-1,"last_month":-1,"last_week":-1},"dynamic":["Author","Author-Email","Classifier","Description","Description-Content-Type","Home-Page","License","License-File","Summary"],"home_page":"https://github.com/ashvardanian/stringzilla","keywords":null,"license":"Apache-2.0","license_expression":null,"license_files":["LICENSE"],"maintainer":null,"maintainer_email":null,"name":"stringzilla","package_url":"https://pypi.org/project/stringzilla/","platform":null,"project_url":"https://pypi.org/project/stringzilla/","project_urls":{"Homepage":"https://github.com/ashvardanian/stringzilla"},"provides_extra":null,"release_url":"https://pypi.org/project/stringzilla/3.12.5/","requires_dist":null,"requires_python":null,"summary":"SIMD-accelerated string search, sort, hashes, fingerprints, & edit distances","version":"3.12.5","yanked":false,"yanked_reason":null}

Package search

stringzilla

project_urls

Dependencies

All package metadata

Releases