diff options
Diffstat (limited to '_log/site-search.md')
| -rw-r--r-- | _log/site-search.md | 17 |
1 files changed, 7 insertions, 10 deletions
diff --git a/_log/site-search.md b/_log/site-search.md index 25c0c2c..c767381 100644 --- a/_log/site-search.md +++ b/_log/site-search.md @@ -1,13 +1,9 @@ --- -title: Static site search with suffix arrays +title: Suffix-array site search date: 2026-01-03 layout: post --- -Developed a suffix-array-based search engine. While a simple regex search -would've been sufficient, couldn't resist the technical elegance of a proper -index. - Indexer crawls the HTML, lowercases the text, and encodes it into UTF-8 bytes. Null byte sentinels mark document boundaries; sa.bin stores lexicographically sorted 32-bit unsigned integer offsets: @@ -25,8 +21,8 @@ my @sa = 0 .. (length($corpus) - 1); } ``` -32-bit offsets provide a 4 GB ceiling—overkill for a personal site with 12 -articles, but comforting to have. +32-bit offsets provide a 4 GB ceiling—overkill for 12 articles, but comforting +to have. O(L⋅N log N) sort is the bottleneck. 100 4.1 KB articles took 97.9s to index. L=64 fast path reduces that to 1.31s. Experimented with 16, 32, 128, and 256 @@ -97,10 +93,11 @@ Index size | 103557.18 KB | N/A ------------------------------------------------------------------------ </pre> -Search scales well—0.9 ms at 100 files, 8.8 ms at 5000. Indexing doesn't. 4.5s -at 300 files is tolerable; 138s at 5000 is impractical. +Search scales well—0.9ms at 100 files, 8.8ms at 5000. Indexing doesn’t: 4.5s +at 300 files is tolerable; 138s at 5000 is impractical. At six articles a year, +the indexer should remain viable for ~100 years. -Warranty: 300 / 6 → 50 years. +Next release: SA-IS O(n), Anno Domini 2126. Commit: <a href="https://git.asciimx.com/www/commit/?h=term&id=6da102d6e0494a3eac3f05fa3b2cdcc25ba2754e" |