2b:null 2c:["$","title",null,{"children":"Search tree | Grégoire Geis | Observable"}] 31:T194c,SearchTree = { // The alphabet whose keys represent entries. const ALPHABET = "abcdefghijklmnopqrstuvwxyz"; // The maximum number of results for an entry. const MAX_RESULTS_COUNT = 10; // The number of bits needed to store an integer `n <= MAX_RESULTS_COUNT`. const MAX_RESULTS_COUNT_BITS = Math.ceil(Math.log2(MAX_RESULTS_COUNT + 1)); // The number of bits needed to store the alphabet bitmap and the number of results. const BITS_PER_NODE = ALPHABET.length + MAX_RESULTS_COUNT_BITS; // The number of bytes needed to store the alphabet bitmap and the number of results. const BYTES_PER_NODE = Math.ceil(BITS_PER_NODE / 8); // The number of bytes needed to store the alphabet bitmap. const BYTES_FOR_ALPHABET = Math.ceil(ALPHABET.length / 8); // The number of bytes needed to store an integer `n <= MAX_RESULTS_COUNT`. const BYTES_FOR_RESULTS_COUNT = Math.ceil(MAX_RESULTS_COUNT_BITS / 8); // The number of bits to skip (using a shift) when reading the number of results. const BITS_TO_SKIP_FOR_RESULTS_COUNT = ALPHABET.length % 8; // The number of bytes needed to store one edge, i.e. an offset to another node. const BYTES_PER_EDGE = 4; // 32 bits // The number of bytes needed to store one result, i.e. the index of an input entry. const BYTES_PER_RESULT = 4; // 32 bits function buildSearchTree(entries) { // Normalize input. entries = entries.map(([k, v]) => [k.toLowerCase(), v]).sort((a, b) => a[0] - b[0]); // Build tree. const root = { _: [] }; let nodesCount = 1; let edgesCount = 0; let resultsCount = 0; for (const [fullKey, value] of entries) { let node = root; for (let i = 0; i < fullKey.length; i++) { const char = fullKey[i]; if (char in node) { node = node[char]; } else { nodesCount++; edgesCount++; node = node[char] = { _: [] }; } } node._.push(value); resultsCount++; } // Encode tree to buffer. const treeBuffer = new Uint8Array( nodesCount * BYTES_PER_NODE + edgesCount * BYTES_PER_EDGE + resultsCount * BYTES_PER_RESULT, ); const treeBufferView = new DataView(treeBuffer.buffer); let currentOffset = 0; const encodeSearchTree = (offsetOffset, node, textSoFar) => { if (offsetOffset > 0) { // Do not write offset for root node. treeBufferView.setUint32(offsetOffset, currentOffset); } // Compute and write bits for the node. let childrenCount = 0; let nodeBits = 0n; for (let i = 0; i < ALPHABET.length; i++) { const char = ALPHABET[i]; if (char in node) { nodeBits |= 1n << BigInt(i); childrenCount++; } } const resultsCount = node._.length; if (resultsCount > MAX_RESULTS_COUNT) { throw Object.assign( new Error("number of results exceeds MAX_RESULTS_COUNT"), { resultsCount, MAX_RESULTS_COUNT, key: textSoFar }, ); } nodeBits |= BigInt(resultsCount) << BigInt(ALPHABET.length); treeBufferView.setBigUint64(currentOffset, nodeBits); currentOffset += BYTES_PER_NODE; // Make some room for children; these values will be filled later. const childrenStartOffset = currentOffset; currentOffset += childrenCount * BYTES_PER_EDGE; // Write results. for (const result of node._) { treeBufferView.setUint32(currentOffset, result); currentOffset += BYTES_PER_RESULT; } // Write children. for (let i = 0; i < ALPHABET.length; i++) { const char = ALPHABET[i]; if (char in node) { encodeSearchTree(childrenStartOffset + i * BYTES_PER_EDGE, node[char], char); } } }; encodeSearchTree(0, root, ""); return treeBuffer; } function search(tree, prefix, treeOffset, prefixOffset) { if (prefix.length === prefixOffset) { // Result found, collect results with BFS. const queue = [treeOffset]; const results = []; while (queue.length > 0) { const nodeOffset = queue.pop(); // Add results. const edgesCount = popcount(tree, nodeOffset, BYTES_FOR_ALPHABET, ALPHABET.length - BYTES_FOR_ALPHABET * 8); const resultsCount = ALPHABET.length % 8 === 0 ? getAnyUint(tree, nodeOffset + BYTES_FOR_ALPHABET, BYTES_FOR_RESULTS_COUNT) : getAnyUint(tree, nodeOffset + BYTES_FOR_ALPHABET - 1, BYTES_FOR_RESULTS_COUNT) >> (ALPHABET.length % 8); const resultsOffset = nodeOffset + edgesCount * BYTES_PER_EDGE; for (let i = 0; i < resultsCount; i++) { const resultOffset = resultsOffset + i * BYTES_PER_RESULT; const result = tree.getUint32(resultOffset); results.push(result); } // Enqueue children. let childOffset = nodeOffset + BYTES_PER_NODE; for (let i = 0; i < ALPHABET.length; i += 8) { const iters = Math.min(i + 8, ALPHABET.length) - i; const byte = tree.getUint8(nodeOffset + i / 8); for (let j = 0; j < iters; j++) { if ((1 << j) & byte) { queue.push(childOffset); childOffset += BYTES_PER_EDGE; } } } } return results; } // Compute index of character to find. const searchIndex = prefix[prefixOffset]; const searchIndexBytesToSkip = Math.floor(searchIndex / 8); const searchIndexInByte = searchIndex % 8; const hasSearchIndexChild = (tree.getUint8(treeOffset + searchIndexBytesToSkip) & (1 << searchIndexInByte)) !== 0; if (!hasSearchIndexChild) { return []; } const bitsToSkipAtEnd = ALPHABET.length - searchIndex; const searchIndexInTree = popcount(tree, treeOffset, BYTES_FOR_ALPHABET - Math.floor(bitsToSkipAtEnd / 8), bitsToSkipAtEnd % 8); return search(tree, prefix, searchIndexInTree, prefixOffset + 1); } return { build: buildSearchTree, search(tree, prefix) { const prefixIndices = []; for (const char of prefix) { const lowerChar = char.toLowerCase(); const alphabetIndex = ALPHABET.indexOf(lowerChar); if (alphabetIndex === -1) { throw new Error("input not in alphabet"); } prefixIndices.push(alphabetIndex); } return search(new DataView(tree.buffer), prefixIndices, 0, 0); }, }; }32:T56ee,words = ` a abandon ability able abortion about above abroad absence absolute absolutely absorb abuse academic accept access accident accompany accomplish according account accurate accuse achieve achievement acid acknowledge acquire across act action active activist activity actor actress actual actually ad adapt add addition additional address adequate adjust adjustment administration administrator admire admission admit adolescent adopt adult advance advanced advantage adventure advertising advice advise adviser advocate affair affect afford afraid African African-American after afternoon again against age agency agenda agent aggressive ago agree agreement agricultural ah ahead aid aide AIDS aim air aircraft airline airport album alcohol alive all alliance allow ally almost alone along already also alter alternative although always AM amazing American among amount analysis analyst analyze ancient and anger angle angry animal anniversary announce annual another answer anticipate anxiety any anybody anymore anyone anything anyway anywhere apart apartment apparent apparently appeal appear appearance apple application apply appoint appointment appreciate approach appropriate approval approve approximately Arab architect area argue argument arise arm armed army around arrange arrangement arrest arrival arrive art article artist artistic as Asian aside ask asleep aspect assault assert assess assessment asset assign assignment assist assistance assistant associate association assume assumption assure at athlete athletic atmosphere attach attack attempt attend attention attitude attorney attract attractive attribute audience author authority auto available average avoid award aware awareness away awful baby back background bad badly bag bake balance ball ban band bank bar barely barrel barrier base baseball basic basically basis basket basketball bathroom battery battle be beach bean bear beat beautiful beauty because become bed bedroom beer before begin beginning behavior behind being belief believe bell belong below belt bench bend beneath benefit beside besides best bet better between beyond Bible big bike bill billion bind biological bird birth birthday bit bite black blade blame blanket blind block blood blow blue board boat body bomb bombing bond bone book boom boot border born borrow boss both bother bottle bottom boundary bowl box boy boyfriend brain branch brand bread break breakfast breast breath breathe brick bridge brief briefly bright brilliant bring British broad broken brother brown brush buck budget build building bullet bunch burden burn bury bus business busy but butter button buy buyer by cabin cabinet cable cake calculate call camera camp campaign campus can Canadian cancer candidate cap capability capable capacity capital captain capture car carbon card care career careful carefully carrier carry case cash cast cat catch category Catholic cause ceiling celebrate celebration celebrity cell center central century CEO ceremony certain certainly chain chair chairman challenge chamber champion championship chance change changing channel chapter character characteristic characterize charge charity chart chase cheap check cheek cheese chef chemical chest chicken chief child childhood Chinese chip chocolate choice cholesterol choose Christian Christmas church cigarette circle circumstance cite citizen city civil civilian claim class classic classroom clean clear clearly client climate climb clinic clinical clock close closely closer clothes clothing cloud club clue cluster coach coal coalition coast coat code coffee cognitive cold collapse colleague collect collection collective college colonial color column combination combine come comedy comfort comfortable command commander comment commercial commission commit commitment committee common communicate communication community company compare comparison compete competition competitive competitor complain complaint complete completely complex complicated component compose composition comprehensive computer concentrate concentration concept concern concerned concert conclude conclusion concrete condition conduct conference confidence confident confirm conflict confront confusion Congress congressional connect connection consciousness consensus consequence conservative consider considerable consideration consist consistent constant constantly constitute constitutional construct construction consultant consume consumer consumption contact contain container contemporary content contest context continue continued contract contrast contribute contribution control controversial controversy convention conventional conversation convert conviction convince cook cookie cooking cool cooperation cop cope copy core corn corner corporate corporation correct correspondent cost cotton couch could council counselor count counter country county couple courage course court cousin cover coverage cow crack craft crash crazy cream create creation creative creature credit crew crime criminal crisis criteria critic critical criticism criticize crop cross crowd crucial cry cultural culture cup curious current currently curriculum custom customer cut cycle dad daily damage dance danger dangerous dare dark darkness data date daughter day dead deal dealer dear death debate debt decade decide decision deck declare decline decrease deep deeply deer defeat defend defendant defense defensive deficit define definitely definition degree delay deliver delivery demand democracy Democrat democratic demonstrate demonstration deny department depend dependent depending depict depression depth deputy derive describe description desert deserve design designer desire desk desperate despite destroy destruction detail detailed detect determine develop developing development device devote dialogue die diet differ difference different differently difficult difficulty dig digital dimension dining dinner direct direction directly director dirt dirty disability disagree disappear disaster discipline discourse discover discovery discrimination discuss discussion disease dish dismiss disorder display dispute distance distant distinct distinction distinguish distribute distribution district diverse diversity divide division divorce DNA do doctor document dog domestic dominant dominate door double doubt down downtown dozen draft drag drama dramatic dramatically draw drawing dream dress drink drive driver drop drug dry due during dust duty each eager ear early earn earnings earth ease easily east eastern easy eat economic economics economist economy edge edition editor educate education educational educator effect effective effectively efficiency efficient effort egg eight either elderly elect election electric electricity electronic element elementary eliminate elite else elsewhere e-mail embrace emerge emergency emission emotion emotional emphasis emphasize employ employee employer employment empty enable encounter encourage end enemy energy enforcement engage engine engineer engineering English enhance enjoy enormous enough ensure enter enterprise entertainment entire entirely entrance entry environment environmental episode equal equally equipment era error escape especially essay essential essentially establish establishment estate estimate etc ethics ethnic European evaluate evaluation even evening event eventually ever every everybody everyday everyone everything everywhere evidence evolution evolve exact exactly examination examine example exceed excellent except exception exchange exciting executive exercise exhibit exhibition exist existence existing expand expansion expect expectation expense expensive experience experiment expert explain explanation explode explore explosion expose exposure express expression extend extension extensive extent external extra extraordinary extreme extremely eye fabric face facility fact factor factory faculty fade fail failure fair fairly faith fall false familiar family famous fan fantasy far farm farmer fashion fast fat fate father fault favor favorite fear feature federal fee feed feel feeling fellow female fence few fewer fiber fiction field fifteen fifth fifty fight fighter fighting figure file fill film final finally finance financial find finding fine finger finish fire firm first fish fishing fit fitness five fix flag flame flat flavor flee flesh flight float floor flow flower fly focus folk follow following food foot football for force foreign forest forever forget form formal formation former formula forth fortune forward found foundation founder four fourth frame framework free freedom freeze French frequency frequent frequently fresh friend friendly friendship from front fruit frustration fuel full fully fun function fund fundamental funding funeral funny furniture furthermore future gain galaxy gallery game gang gap garage garden garlic gas gate gather gay gaze gear gender gene general generally generate generation genetic gentleman gently German gesture get ghost giant gift gifted girl girlfriend give given glad glance glass global glove go goal God gold golden golf good government governor grab grade gradually graduate grain grand grandfather grandmother grant grass grave gray great greatest green grocery ground group grow growing growth guarantee guard guess guest guide guideline guilty gun guy habit habitat hair half hall hand handful handle hang happen happy hard hardly hat hate have he head headline headquarters health healthy hear hearing heart heat heaven heavily heavy heel height helicopter hell hello help helpful her here heritage hero herself hey hi hide high highlight highly highway hill him himself hip hire his historian historic historical history hit hold hole holiday holy home homeless honest honey honor hope horizon horror horse hospital host hot hotel hour house household housing how however huge human humor hundred hungry hunter hunting hurt husband hypothesis I ice idea ideal identification identify identity ie if ignore ill illegal illness illustrate image imagination imagine immediate immediately immigrant immigration impact implement implication imply importance important impose impossible impress impression impressive improve improvement in incentive incident include including income incorporate increase increased increasing increasingly incredible indeed independence independent index Indian indicate indication individual industrial industry infant infection inflation influence inform information ingredient initial initially initiative injury inner innocent inquiry inside insight insist inspire install instance instead institution institutional instruction instructor instrument insurance intellectual intelligence intend intense intensity intention interaction interest interested interesting internal international Internet interpret interpretation intervention interview into introduce introduction invasion invest investigate investigation investigator investment investor invite involve involved involvement Iraqi Irish iron Islamic island Israeli issue it Italian item its itself jacket jail Japanese jet Jew Jewish job join joint joke journal journalist journey joy judge judgment juice jump junior jury just justice justify keep key kick kid kill killer killing kind king kiss kitchen knee knife knock know knowledge lab label labor laboratory lack lady lake land landscape language lap large largely last late later Latin latter laugh launch law lawn lawsuit lawyer lay layer lead leader leadership leading leaf league lean learn learning least leather leave left leg legacy legal legend legislation legitimate lemon length less lesson let letter level liberal library license lie life lifestyle lifetime lift light like likely limit limitation limited line link lip list listen literally literary literature little live living load loan local locate location lock long long-term look loose lose loss lost lot lots loud love lovely lover low lower luck lucky lunch lung machine mad magazine mail main mainly maintain maintenance major majority make maker makeup male mall man manage management manager manner manufacturer manufacturing many map margin mark market marketing marriage married marry mask mass massive master match material math matter may maybe mayor me meal mean meaning meanwhile measure measurement meat mechanism media medical medication medicine medium meet meeting member membership memory mental mention menu mere merely mess message metal meter method Mexican middle might military milk million mind mine minister minor minority minute miracle mirror miss missile mission mistake mix mixture mm-hmm mode model moderate modern modest mom moment money monitor month mood moon moral more moreover morning mortgage most mostly mother motion motivation motor mount mountain mouse mouth move movement movie Mr Mrs Ms much multiple murder muscle museum music musical musician Muslim must mutual my myself mystery myth naked name narrative narrow nation national native natural naturally nature near nearby nearly necessarily necessary neck need negative negotiate negotiation neighbor neighborhood neither nerve nervous net network never nevertheless new newly news newspaper next nice night nine no nobody nod noise nomination none nonetheless nor normal normally north northern nose not note nothing notice notion novel now nowhere n't nuclear number numerous nurse nut object objective obligation observation observe observer obtain obvious obviously occasion occasionally occupation occupy occur ocean odd odds of off offense offensive offer office officer official often oh oil ok okay old Olympic on once one ongoing onion online only onto open opening operate operating operation operator opinion opponent opportunity oppose opposite opposition option or orange order ordinary organic organization organize orientation origin original originally other others otherwise ought our ourselves out outcome outside oven over overall overcome overlook owe own owner pace pack package page pain painful paint painter painting pair pale Palestinian palm pan panel pant paper parent park parking part participant participate participation particular particularly partly partner partnership party pass passage passenger passion past patch path patient pattern pause pay payment PC peace peak peer penalty people pepper per perceive percentage perception perfect perfectly perform performance perhaps period permanent permission permit person personal personality personally personnel perspective persuade pet phase phenomenon philosophy phone photo photograph photographer phrase physical physically physician piano pick picture pie piece pile pilot pine pink pipe pitch place plan plane planet planning plant plastic plate platform play player please pleasure plenty plot plus PM pocket poem poet poetry point pole police policy political politically politician politics poll pollution pool poor pop popular population porch port portion portrait portray pose position positive possess possibility possible possibly post pot potato potential potentially pound pour poverty powder power powerful practical practice pray prayer precisely predict prefer preference pregnancy pregnant preparation prepare prescription presence present presentation preserve president presidential press pressure pretend pretty prevent previous previously price pride priest primarily primary prime principal principle print prior priority prison prisoner privacy private probably problem procedure proceed process produce producer product production profession professional professor profile profit program progress project prominent promise promote prompt proof proper properly property proportion proposal propose proposed prosecutor prospect protect protection protein protest proud prove provide provider province provision psychological psychologist psychology public publication publicly publish publisher pull punishment purchase pure purpose pursue push put qualify quality quarter quarterback question quick quickly quiet quietly quit quite quote race racial radical radio rail rain raise range rank rapid rapidly rare rarely rate rather rating ratio raw reach react reaction read reader reading ready real reality realize really reason reasonable recall receive recent recently recipe recognition recognize recommend recommendation record recording recover recovery recruit red reduce reduction refer reference reflect reflection reform refugee refuse regard regarding regardless regime region regional register regular regularly regulate regulation reinforce reject relate relation relationship relative relatively relax release relevant relief religion religious rely remain remaining remarkable remember remind remote remove repeat repeatedly replace reply report reporter represent representation representative Republican reputation request require requirement research researcher resemble reservation resident resist resistance resolution resolve resort resource respect respond respondent response responsibility responsible rest restaurant restore restriction result retain retire retirement return reveal revenue review revolution rhythm rice rich rid ride rifle right ring rise risk river road rock role roll romantic roof room root rope rose rough roughly round route routine row rub rule run running rural rush Russian sacred sad safe safety sake salad salary sale sales salt same sample sanction sand satellite satisfaction satisfy sauce save saving say scale scandal scared scenario scene schedule scheme scholar scholarship school science scientific scientist scope score scream screen script sea search season seat second secret secretary section sector secure security see seed seek seem segment seize select selection self sell Senate senator send senior sense sensitive sentence separate sequence series serious seriously serve service session set setting settle settlement seven several severe sex sexual shade shadow shake shall shape share sharp she sheet shelf shell shelter shift shine ship shirt shit shock shoe shoot shooting shop shopping shore short shortly shot should shoulder shout show shower shrug shut sick side sigh sight sign signal significance significant significantly silence silent silver similar similarly simple simply sin since sing singer single sink sir sister sit site situation six size ski skill skin sky slave sleep slice slide slight slightly slip slow slowly small smart smell smile smoke smooth snap snow so so-called soccer social society soft software soil solar soldier solid solution solve some somebody somehow someone something sometimes somewhat somewhere son song soon sophisticated sorry sort soul sound soup source south southern Soviet space Spanish speak speaker special specialist species specific specifically speech speed spend spending spin spirit spiritual split spokesman sport spot spread spring square squeeze stability stable staff stage stair stake stand standard standing star stare start state statement station statistics status stay steady steal steel step stick still stir stock stomach stone stop storage store storm story straight strange stranger strategic strategy stream street strength strengthen stress stretch strike string strip stroke strong strongly structure struggle student studio study stuff stupid style subject submit subsequent substance substantial succeed success successful successfully such sudden suddenly sue suffer sufficient sugar suggest suggestion suicide suit summer summit sun super supply support supporter suppose supposed Supreme sure surely surface surgery surprise surprised surprising surprisingly surround survey survival survive survivor suspect sustain swear sweep sweet swim swing switch symbol symptom system table tablespoon tactic tail take tale talent talk tall tank tap tape target task taste tax taxpayer tea teach teacher teaching team tear teaspoon technical technique technology teen teenager telephone telescope television tell temperature temporary ten tend tendency tennis tension tent term terms terrible territory terror terrorism terrorist test testify testimony testing text than thank thanks that the theater their them theme themselves then theory therapy there therefore these they thick thin thing think thinking third thirty this those though thought thousand threat threaten three throat through throughout throw thus ticket tie tight time tiny tip tire tired tissue title to tobacco today toe together tomato tomorrow tone tongue tonight too tool tooth top topic toss total totally touch tough tour tourist tournament toward towards tower town toy trace track trade tradition traditional traffic tragedy trail train training transfer transform transformation transition translate transportation travel treat treatment treaty tree tremendous trend trial tribe trick trip troop trouble truck true truly trust truth try tube tunnel turn TV twelve twenty twice twin two type typical typically ugly ultimate ultimately unable uncle under undergo understand understanding unfortunately uniform union unique unit United universal universe university unknown unless unlike unlikely until unusual up upon upper urban urge us use used useful user usual usually utility vacation valley valuable value variable variation variety various vary vast vegetable vehicle venture version versus very vessel veteran via victim victory video view viewer village violate violation violence violent virtually virtue virus visible vision visit visitor visual vital voice volume volunteer vote voter vs vulnerable wage wait wake walk wall wander want war warm warn warning wash waste watch water wave way we weak wealth wealthy weapon wear weather wedding week weekend weekly weigh weight welcome welfare well west western wet what whatever wheel when whenever where whereas whether which while whisper white who whole whom whose why wide widely widespread wife wild will willing win wind window wine wing winner winter wipe wire wisdom wise wish with withdraw within without witness woman wonder wonderful wood wooden word work worker working works workshop world worried worry worth would wound wrap write writer writing wrong yard yeah year yell yellow yes yesterday yet yield you young your yours yourself youth zone `.trim().split("\n")33:[] 2f:{"id":"6877add0b95e64de","slug":null,"title":"Search tree","thumbnail":"cf208270817b10e3497212ed25019b72661de16504936c0b4342b353b4e4cef9","access_level":"public","create_time":"$D2023-10-28T07:12:38.050Z","update_time":"$D2023-10-28T13:40:40.465Z","view_time":null,"first_public_time":"$D2023-10-28T07:12:38.050Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"6817f8df4b71afcf","login":"71","name":"Grégoire Geis","avatar_url":"https://avatars-next.observableusercontent.com/046456a6fcb599cae062b5a172a9e2c85acef403c376bdb60a4cc6d135a60aad","tier":"starter_2024"},"version":187,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"3881cfc7f3117323","login":"71","name":"Grégoire Geis","avatar_url":"https://avatars-next.observableusercontent.com/046456a6fcb599cae062b5a172a9e2c85acef403c376bdb60a4cc6d135a60aad","tier":null}],"members":[{"type":"individual","id":"3881cfc7f3117323","login":"71","name":"Grégoire Geis","avatar_url":"https://avatars-next.observableusercontent.com/046456a6fcb599cae062b5a172a9e2c85acef403c376bdb60a4cc6d135a60aad","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Search tree","cells":[{"id":0,"value":"# Search tree\n\nSearch strings starting with a given string.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":27,"value":"viewof searchInput = Inputs.text({ label: \"Search\", value: \"hel\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"{\n const toSearch = searchInput.toLowerCase();\n\n const startTime = performance.now();\n const results = SearchTree.search(searchTree, toSearch);\n const endTime = performance.now();\n\n const naiveStartTime = endTime;\n const naiveResults = words.filter(w => w.startsWith(toSearch));\n const naiveEndTime = performance.now();\n\n return md`\n### Tree-based search\n${results.length} result${results.length === 1 ? \"\" : \"s\"} found in ${(endTime - startTime).toPrecision(3)} ms:\n${results.map((r) => `\\n- ${r}`)}\n\n### Naive search\n${naiveResults.length} result${naiveResults.length === 1 ? \"\" : \"s\"} found in ${(naiveEndTime - naiveStartTime).toPrecision(3)} ms:\n${naiveResults.map((r) => `\\n- ${r}`)}\n `;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"searchTree = SearchTree.build(words.map((w, i) => [w, i]))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"function getAnyUint(dataView, offset, bytes) {\n switch (bytes) {\n case 0:\n return 0;\n case 1:\n return dataView.getUint8(offset);\n case 2:\n return dataView.getUint16(offset);\n case 3:\n return dataView.getUint32(offset) & 0x00ffffff;\n case 4:\n return dataView.getUint32(offset);\n default:\n throw new Error(\"can only read up to uint32\");\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"function popcount(dataView, offset, bytes, excludedBits) {\n const bitExclusionMask = (1 << excludedBits) - 1;\n\n let sum = 0;\n let i = 0;\n\n // `popcount()` per blocks of 4 bytes.\n while (i < bytes) {\n sum += popcount32(dataView.getUint32(offset + i));\n i += 4; // bytes in uint32\n }\n\n return sum + popcount32(getAnyUint(dataView, offset + i, bytes % 4) & bitExclusionMask);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"function popcount32(n) {\n // https://stackoverflow.com/a/43122214\n n = n - ((n >> 1) & 0x55555555);\n n = (n & 0x33333333) + ((n >> 2) & 0x33333333);\n return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"