已發布·持續改進
字串演算法 指南 · 6/6
本章目前僅提供英文版。
Most string algorithms you rely on live inside libraries and tools. This chapter shows where, and which traps to avoid when writing your own.
str.find and in are built on a simplified Boyer-Moore-Horspool scheme, and since Python 3.10 long needles use the Crochemore-Perrin Two-Way algorithm. glibc's memmem and strstr also use Two-Way for long needles. Two-Way guarantees linear worst-case time with only constant extra memory.aho-corasick and memchr, which provide multi-pattern search and SIMD acceleration.Languages count string length and positions in different units.
| Environment | Index unit | Length of "😀" |
|---|---|---|
Python str | code point | 1 |
Java String, JavaScript | UTF-16 code unit | 2 |
C++ std::string, Rust str::len | UTF-8 byte | 4 |
Pass a position computed in Java or JavaScript to a Python service and it will be off as soon as the text contains an emoji. When positions cross an API boundary, state the unit explicitly.
const s = "a😀b";
console.log(s.length); // 4 (UTF-16 code units)
console.log([...s].length); // 3 (code points)
const seg = new Intl.Segmenter("en", { granularity: "grapheme" });
console.log([...seg.segment("👍🏽")].length); // 1 (user-perceived character)The same character can also be encoded in more than one way. é may be a single precomposed code point (U+00E9) or e followed by a combining accent. Text stored in NFD, as macOS file names often are, will not match an NFC query. For case-insensitive comparison, casefold() is more correct than lower().
import unicodedata
nfd = unicodedata.normalize("NFD", "café")
print(len("café"), len(nfd)) # 4 5
print("café" in nfd) # False
print("café" in unicodedata.normalize("NFC", nfd)) # True
print("Straße".lower() == "STRASSE".lower()) # False
print("Straße".casefold() == "STRASSE".casefold()) # TrueA search pipeline should apply the same normalization and case folding when indexing and when querying.
If Rabin-Karp skips the confirmation step on a hash hit, it can report wrong answers. With a fixed base and modulus an attacker can build colliding inputs, so pick a random base on each run and use a large prime modulus such as 2^61 - 1, or combine two independent hashes.
import random
MOD = (1 << 61) - 1
BASE = random.randrange(256, MOD - 1) # different base on every run
def poly_hash(s: str) -> int:
h = 0
for ch in s:
h = (h * BASE + ord(ch)) % MOD
return h
print(poly_hash("abc") == poly_hash("abc"), poly_hash("abc") == poly_hash("acb"))
# True False (a collision is very unlikely, but never impossible)(a+)+ can take exponential time (ReDoS). Escape user input with re.escape before using it as a pattern.| Situation | Recommendation |
|---|---|
| One simple search | The language's built-ins (in, find, indexOf) |
| Need borders, periods or prefix data | Prefix function (KMP) or Z-array |
| Many patterns of equal length, substring comparison | Rolling hash |
| Thousands of patterns of varying length | An Aho-Corasick library |
| Prefix lookup in a dictionary, autocomplete | Trie, or sorted list plus binary search |
| Many queries over one large text | Suffix array, FM-index, a search engine |
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。