{"_id":"@superhuman/trie-ing","_rev":"28-934a1af9a3145955c2cbf0fde97a1962","name":"@superhuman/trie-ing","dist-tags":{"latest":"0.5.6"},"versions":{"0.5.0":{"name":"@superhuman/trie-ing","version":"0.5.0","_id":"@superhuman/trie-ing@0.5.0","maintainers":[{"name":"cirwin","email":"conrad.irwin@gmail.com"}],"dist":{"shasum":"8f36480df83c9506554662ffa11934839e8953a3","tarball":"https://registry.npmjs.org/@superhuman/trie-ing/-/trie-ing-0.5.0.tgz","integrity":"sha512-ZolTthum1H55abcO1r2zFdTieTDDl/kZUqOtBMt5lB6qUSDuGL8G40g5gmD4frjeRn6Uj9rlbMR3E2PXKIpgyQ==","signatures":[{"sig":"MEQCIFzvmVfJEvcpTGfm1J6anYoz5E61PQGRFjKh6YLXlXJ3AiAnc5oVEmcCOWKTPa84LXmNpbv//gUFEPf+QbjbkQAXqA==","keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA"}]},"main":"index.js","_from":".","_shasum":"8f36480df83c9506554662ffa11934839e8953a3","gitHead":"33230f468ff050bff7c3cc766e46d42e8df12bb7","scripts":{"test":"mocha test/*_test.js"},"_npmUser":{"name":"cirwin","email":"conrad.irwin@gmail.com"},"_npmVersion":"3.10.9","description":"A fast weighted autocompleter","directories":{},"_nodeVersion":"7.2.0","devDependencies":{"karma":"^0.13.9","mocha":"^2.2.5","benchmark":"^1.0.0","karma-mocha":"^0.2.0"},"_npmOperationalInternal":{"tmp":"tmp/trie-ing-0.5.0.tgz_1508882536167_0.549082444049418","host":"s3://npm-registry-packages"}},"0.5.1":{"name":"@superhuman/trie-ing","version":"0.5.1","_id":"@superhuman/trie-ing@0.5.1","maintainers":[{"name":"gabeshahbazian","email":"gabeshahbazian@gmail.com"},{"name":"gvohra","email":"gaurav@vohra.org.uk"},{"name":"rogueg","email":"rogueg@gmail.com"},{"name":"kakadiya91","email":"kakadiya91@gmail.com"},{"name":"ibash","email":"islam.sharabash@gmail.com"},{"name":"cirwin","email":"conrad.irwin@gmail.com"},{"name":"conrad-superhuman","email":"conrad@superhuman.com"}],"dist":{"shasum":"db2a4ee37bc909b0808ed10af78ce85b9699a43d","tarball":"https://registry.npmjs.org/@superhuman/trie-ing/-/trie-ing-0.5.1.tgz","integrity":"sha512-yqkUPgj0vlp+iBNLtVGI2uU1EHC3hOBgvjvP/bC9SyegWlv/NjYE3NWhcxiQ0R5/vyuPNce23RSTwQykaOvdxg==","signatures":[{"sig":"MEQCIE8RWBlH4dQNcS8qAK82kmSme5T49qlIR+epnnkulhjoAiBGM7V05eYdIOn4LKmBs+DVHOxiEFjvl97GjYHrQdqR3A==","keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA"}]},"main":"index.js","_from":".","_shasum":"db2a4ee37bc909b0808ed10af78ce85b9699a43d","gitHead":"efb8e12bd0400f3215de2d5285541ceec80da133","scripts":{"test":"mocha test/*_test.js"},"_npmUser":{"name":"cirwin","email":"conrad.irwin@gmail.com"},"_npmVersion":"3.10.9","description":"A fast weighted autocompleter","directories":{},"_nodeVersion":"7.2.0","devDependencies":{"karma":"^0.13.9","mocha":"^2.2.5","benchmark":"^1.0.0","karma-mocha":"^0.2.0"},"_npmOperationalInternal":{"tmp":"tmp/trie-ing-0.5.1.tgz_1509405447143_0.8082350846379995","host":"s3://npm-registry-packages"}},"0.5.2":{"name":"@superhuman/trie-ing","version":"0.5.2","_id":"@superhuman/trie-ing@0.5.2","maintainers":[{"name":"gabeshahbazian","email":"gabeshahbazian@gmail.com"},{"name":"gvohra","email":"gaurav@vohra.org.uk"},{"name":"rogueg","email":"rogueg@gmail.com"},{"name":"kakadiya91","email":"kakadiya91@gmail.com"},{"name":"ibash","email":"islam.sharabash@gmail.com"},{"name":"cirwin","email":"conrad.irwin@gmail.com"},{"name":"conrad-superhuman","email":"conrad@superhuman.com"}],"dist":{"shasum":"ec70f1728b916637dc3d98942d7f8c08bd0a0afd","tarball":"https://registry.npmjs.org/@superhuman/trie-ing/-/trie-ing-0.5.2.tgz","integrity":"sha512-tvZO+FwnJDBwAaENF0NvMvA04kk61Tgzc2fPRS5BLdgftmO5Qj7FLDG+AhjKVWZta6Qr8ErnLOOw9X1aekUEtA==","signatures":[{"sig":"MEUCIC8yPOMX/4l2HOLSEPhqL+cZvP6lNDLQIPtO0ntILityAiEAl8SQbOcADdmHqHeTd79gD9qOGwUknxbc3nV/zzu7b5I=","keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA"}]},"main":"index.js","_from":".","_shasum":"ec70f1728b916637dc3d98942d7f8c08bd0a0afd","gitHead":"85dc836a874566d9f03e8d2753f73087d238f2a6","scripts":{"test":"mocha test/*_test.js"},"_npmUser":{"name":"cirwin","email":"conrad.irwin@gmail.com"},"_npmVersion":"3.10.9","description":"A fast weighted autocompleter","directories":{},"_nodeVersion":"7.2.0","devDependencies":{"karma":"^0.13.9","mocha":"^2.2.5","benchmark":"^1.0.0","karma-mocha":"^0.2.0"},"_npmOperationalInternal":{"tmp":"tmp/trie-ing-0.5.2.tgz_1509407141831_0.5180444952566177","host":"s3://npm-registry-packages"}},"0.5.3":{"name":"@superhuman/trie-ing","version":"0.5.3","_id":"@superhuman/trie-ing@0.5.3","maintainers":[{"name":"gabeshahbazian","email":"gabeshahbazian@gmail.com"},{"name":"gvohra","email":"gaurav@vohra.org.uk"},{"name":"rogueg","email":"rogueg@gmail.com"},{"name":"kakadiya91","email":"kakadiya91@gmail.com"},{"name":"ibash","email":"islam.sharabash@gmail.com"},{"name":"cirwin","email":"conrad.irwin@gmail.com"},{"name":"conrad-superhuman","email":"conrad@superhuman.com"}],"dist":{"shasum":"f9da5ba660dd0837b116ebe16ec9061fb72cbfd4","tarball":"https://registry.npmjs.org/@superhuman/trie-ing/-/trie-ing-0.5.3.tgz","integrity":"sha512-RNwBu97u0UO71wXLNkAPqFOd3AGnAi1I6ACULgU4ZuYtObTldjMWrGNMUByWjX7l5SmuRrB6cbfZVlUClohzcw==","signatures":[{"sig":"MEQCIESCryJUzeJcFYhmCpz5uI6Q6NBCtU3wHE5IxsxMW4tYAiAqhvo+Ura7i9jASxLybWuSoXem+6ME0L3R+2PK93irxA==","keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA"}]},"main":"index.js","_from":".","_shasum":"f9da5ba660dd0837b116ebe16ec9061fb72cbfd4","gitHead":"5b91b8ab5ccd3041cbb2bbac1c03f6ac0c7d30ca","scripts":{"test":"mocha test/*_test.js"},"_npmUser":{"name":"cirwin","email":"conrad.irwin@gmail.com"},"_npmVersion":"3.10.9","description":"A fast weighted autocompleter","directories":{},"_nodeVersion":"7.2.0","devDependencies":{"karma":"^0.13.9","mocha":"^2.2.5","benchmark":"^1.0.0","karma-mocha":"^0.2.0"},"_npmOperationalInternal":{"tmp":"tmp/trie-ing-0.5.3.tgz_1509579976840_0.3633418104145676","host":"s3://npm-registry-packages"}},"0.5.4":{"name":"@superhuman/trie-ing","version":"0.5.4","_id":"@superhuman/trie-ing@0.5.4","maintainers":[{"name":"gabeshahbazian","email":"gabeshahbazian@gmail.com"},{"name":"gvohra","email":"gaurav@vohra.org.uk"},{"name":"rogueg","email":"rogueg@gmail.com"},{"name":"kakadiya91","email":"kakadiya91@gmail.com"},{"name":"ibash","email":"islam.sharabash@gmail.com"},{"name":"cirwin","email":"conrad.irwin@gmail.com"},{"name":"conrad-superhuman","email":"conrad@superhuman.com"}],"dist":{"shasum":"24a3832a37e42f140bcaba5d32d4546c8c12bae1","tarball":"https://registry.npmjs.org/@superhuman/trie-ing/-/trie-ing-0.5.4.tgz","integrity":"sha512-etSIYBh5cCmZkeeapZWhlJwGFsKaQPMeCuwJeNNxEU1pP5etR05sm0Ff1/A9MOTD6vP46seVKGqX1LQzt0wReA==","signatures":[{"sig":"MEUCIQCIWaVSYpq+WasNEtb2b6WYHrWUjZuKoEStMBCG3x0RdAIgCTKgkmPCqqVFoIduwFoyJJBUSxQiXEB33gtQykeAJe0=","keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA"}],"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.13\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJh2crgCRA9TVsSAnZWagAA2qYP/i5GTjcdmiBYqGrexlgC\najJFMgHXo+lvRGq4pycvdKb5F0MbdLTHxFfmilCKj8pNeAplUEqA81NWXxxT\nPDzTz5ZLp61ewB01jCTITg7KX3OmlG5JUtG+eVIpieVDEdcHUuqrOxg+wasG\nKW0xwKfnIO1WrxtdSq3i7mJl01itwv9StuPDlH7RYUFLF1IalO4XpwbGVrfv\nwI9pwYYyS1s+dnjfi0rIds8O5QtyVoYs24FHvUpw7jmG8cht/PIOS6zqpMjq\nmdEhoMT/7omsos/vEuOlCVvBwN2Lq+PbAtW5Mi5zYEMlNo3Zkhq0BHg+VGSk\ncHfODme6+jZ4kSoWmVs6CHsi9euOhBw4AfV3UdFFZEV/pwjHp/GmABSf1oMD\njAypbKru1Al2vS/YLBxK9rmSqVNXCuGPTe8pFc8xoTQbZF7DqgbWmz7G9uuD\nMCo2JLhAtiChkeAWKTwqV5o0177AUyi9CpfLz2shLJmOmPS3E9iYnfVzQJGt\nHGmPXh/+Y8/ZvBzNvm329AWOVo5DJF8w1xkfixz59Klz3KQrn16D1IoDmDzp\nx1eFgFEsGKeWaUjnqywWAW/MoBQDW6a845apmfCah3TQ5QP9DNrI2E7F7McK\nlNhmbtU8MhKWqKBJ2CyiVT6R0sc4QFxua2v7cyYqMJNBnKQbg8JZ7ffcyPj9\npjAD\r\n=NoUz\r\n-----END PGP SIGNATURE-----\r\n"},"main":"index.js","_from":".","_shasum":"24a3832a37e42f140bcaba5d32d4546c8c12bae1","gitHead":"c714761de28d764fbde186b7dbafa0f17b053727","scripts":{"test":"mocha test/*_test.js"},"_npmUser":{"name":"cirwin","email":"conrad.irwin@gmail.com"},"_npmVersion":"3.10.9","description":"A fast weighted autocompleter","directories":{},"_nodeVersion":"7.2.0","devDependencies":{"karma":"^0.13.9","mocha":"^2.2.5","benchmark":"^1.0.0","karma-mocha":"^0.2.0"},"_npmOperationalInternal":{"tmp":"tmp/trie-ing-0.5.4.tgz_1509589348966_0.6259339160751551","host":"s3://npm-registry-packages"}},"0.5.5":{"name":"@superhuman/trie-ing","version":"0.5.5","_id":"@superhuman/trie-ing@0.5.5","maintainers":[{"name":"superhumanengineering","email":"engineering+npm@superhuman.com"},{"name":"alif","email":"me@alifaiz.com"},{"name":"patrickdbakke","email":"patrickdbakke@gmail.com"},{"name":"timsuperhuman","email":"tim@superhuman.com"},{"name":"conrad-superhuman","email":"conrad@superhuman.com"},{"name":"cirwin","email":"conrad.irwin@gmail.com"},{"name":"gvohra","email":"gaurav@vohra.org.uk"},{"name":"gabeshahbazian","email":"gabeshahbazian@gmail.com"},{"name":"mkassoff_superhuman","email":"mkassoff@superhuman.com"}],"dist":{"shasum":"7471d223be86c337d90401acc7df3b8b07f8245c","tarball":"https://registry.npmjs.org/@superhuman/trie-ing/-/trie-ing-0.5.5.tgz","fileCount":11,"integrity":"sha512-6BqK43KVXovxaC0gbwmxlv77Pg9AMcKmHq+A5+puecqIL+iKuK8rhL2FHPzkBs147SpT16bO4t2AaHUam/6slA==","signatures":[{"sig":"MEQCIADCq1wSHF2LQR/AZOvkqezAoQ/oc32nwK1iDpf3uyxSAiBdvi5AjgsWOXa+zlT4fdFGBslrGC8FV/uY/Kd0iun0VQ==","keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA"}],"unpackedSize":10828144},"main":"index.js","gitHead":"a9e42e812a2de6d023337035e1740045b82aacd4","scripts":{"test":"mocha test/*_test.js","format":"eslint \"**/*.{js,jsx,ts,tsx}\" --max-warnings=0 --fix --cache"},"_npmUser":{"name":"superhumanengineering","email":"engineering+npm@superhuman.com"},"_npmVersion":"8.5.0","description":"A fast weighted autocompleter","directories":{},"_nodeVersion":"16.14.2","_hasShrinkwrap":false,"devDependencies":{"karma":"^0.13.9","mocha":"^2.2.5","eslint":"^8.47.0","prettier":"3.0.2","benchmark":"^1.0.0","karma-mocha":"^0.2.0","eslint-config-prettier":"^9.0.0","eslint-plugin-prettier":"^5.0.0"},"_npmOperationalInternal":{"tmp":"tmp/trie-ing_0.5.5_1692990790298_0.2912616352787183","host":"s3://npm-registry-packages"}},"0.5.6":{"name":"@superhuman/trie-ing","version":"0.5.6","_id":"@superhuman/trie-ing@0.5.6","maintainers":[{"name":"superhumanengineering","email":"engineering+npm@superhuman.com"},{"name":"alif","email":"me@alifaiz.com"},{"name":"patrickdbakke","email":"patrickdbakke@gmail.com"},{"name":"timsuperhuman","email":"tim@superhuman.com"},{"name":"conrad-superhuman","email":"conrad@superhuman.com"},{"name":"cirwin","email":"conrad.irwin@gmail.com"},{"name":"gvohra","email":"gaurav@vohra.org.uk"},{"name":"gabeshahbazian","email":"gabeshahbazian@gmail.com"},{"name":"mkassoff_superhuman","email":"mkassoff@superhuman.com"}],"dist":{"shasum":"b45679a683bddfc7a3e5113b7901ec65a8be9a94","tarball":"https://registry.npmjs.org/@superhuman/trie-ing/-/trie-ing-0.5.6.tgz","fileCount":11,"integrity":"sha512-UaSq5TXjIRv243zCZxXplW1io0+jx8qUKVTtuQ5BbWir4y/kx6YLSAitVO71753Y/k9/gm0A0uf0VBfKusu/Gw==","signatures":[{"sig":"MEYCIQDxUlqeo7Cw74cLxRxu1MXut32xAU2cz+t4a3B1eU2AKQIhAMgRxPf/J8TIUfs/fZjhhJWg6nvItEGVvx17gPXNV5jE","keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA"}],"unpackedSize":10832808},"main":"index.js","gitHead":"f44b98df34333b9f70dd784763fe9de521e43acd","scripts":{"test":"mocha test/*_test.js","format":"eslint \"**/*.{js,jsx,ts,tsx}\" --max-warnings=0 --fix --cache"},"_npmUser":{"name":"patrickdbakke","email":"patrickdbakke@gmail.com"},"_npmVersion":"8.5.0","description":"A fast weighted autocompleter","directories":{},"_nodeVersion":"16.14.2","_hasShrinkwrap":false,"devDependencies":{"karma":"^0.13.9","mocha":"^2.2.5","eslint":"^8.47.0","prettier":"3.0.2","benchmark":"^1.0.0","karma-mocha":"^0.2.0","eslint-config-prettier":"^9.0.0","eslint-plugin-prettier":"^5.0.0"},"_npmOperationalInternal":{"tmp":"tmp/trie-ing_0.5.6_1695675927644_0.5935467705412003","host":"s3://npm-registry-packages"}}},"time":{"created":"2017-10-24T22:02:16.392Z","modified":"2025-09-17T23:04:01.551Z","0.5.0":"2017-10-24T22:02:16.392Z","0.5.1":"2017-10-30T23:17:27.594Z","0.5.2":"2017-10-30T23:45:41.997Z","0.5.3":"2017-11-01T23:46:17.210Z","0.5.4":"2017-11-02T02:22:29.366Z","0.5.5":"2023-08-25T19:13:10.558Z","0.5.6":"2023-09-25T21:05:27.927Z"},"description":"A fast weighted autocompleter","maintainers":[{"email":"tim@superhuman.com","name":"timsuperhuman"},{"email":"patrickdbakke@gmail.com","name":"patrickdbakke"},{"email":"engineering+npm@superhuman.com","name":"superhumanengineering"},{"email":"shivangi@superhuman.com","name":"shivangi_c"}],"readme":"The fastest weighted auto-completion trie known to me.\n\nIntroduction\n============\n\nYet another trie? \"Why?\" I hear you cry! I know, it's trie-ing...\n\nFor [Superhuman](http://superhuman.com) we're building a product focussed around speed and\nproductivity. To do this we need to run an auto-completer over your contacts, ordered by how\nrecently you contacted them.\n\nMost tries return results in alphabetical order, this trie returns them by descending score.\n\nThis trie structure can index my 285kb of contact data in ~11ms, and provide auto-completion\nresults ordered by how recently I've communicated with them in ~0.25ms. This improves over\nthe original linear search (which took ~40ms) and first stab at using a trie (~55ms index, ~20ms search).\n\nUsage\n=====\n\nFirst install. In this example I'm using npm, but browserify or copy-paste works just fine.\n\n```\nnpm install trie-ing\n```\n\nThen use it\n\n```javascript\n\nvar Trie = require('trie-ing');\n\nvar trie = new Trie();\n\ntrie.add({\n    key: \"richard\",\n    value: {name: \"Richard\", ...},\n    score: 5\n});\n\ntrie.add({\n    key: \"rachael\",\n    value: {name: \"Rachael\", ...},\n    score: 1\n});\n\ntrie.add({\n    key: \"sarah\",\n    value: {name: \"Sarah\", ...},\n    score: 3\n});\n\ntrie.add({\n    key: \"sam\",\n    value: {name: \"Sam\", ...},\n    score: 2\n});\n\n// The limit option limits the number of results.\n// The unique option returns only the first result for each key\n// (the trie can store multiple values per key)\ntrie.prefixSearch('r', {limit: 3, unique: true})\n//=> [{name: \"Richard\", ...} , {name: \"Rachael\", ...}]\n```\n\nEfficiency\n==========\n\nThe problem with building a search tree for contacts is that the order of\nresults is orthogonal from the search.\n\nIf I type \"R\", my dad (\"Richard\") should be the first auto-completion result, not\nmy friend \"Rachael\" who I haven't spoken to for a year.\n\nTo do this nodes in the trie have their highest score attached:\n\n```\n                     + (4) rachael\n           + (4) r --+ (1) richard\n  root ----+\n           + (3) s ---+ (3) a ---+ (3) sarah\n                                 + (2) sam\n```\n\nTo improve indexing time, sub-nodes are not sorted; so on the first access to\neach section of the tree you have to pay the cost of sorting the sub-nodes (\nthis is usually a very small sort, <5 entries, per node in the tree).\n\nThere's also a special case for nodes with one child, where we don't expand\nthem out letter by letter. (An exercise for the reader would be to use a\nfully compressed trie, which would give us this optimization as a side-effect)\n\nThe search algorithm maintains a queue of nodes to visit based on score, and is\ntruncated to the limit. The most expensive part of the search is merging the\ncurrent node's children into the priority queue, and so the efficiency of lookup\nis dominated by the limit parameter, with some additional cost due to having to\ntraverse many intermediate nodes (see note about implementing a compressed trie).\n\nMeta-fu\n=======\n\nThis code base started out as the trie implementation from\nhttps://github.com/marccampbell/node-autocomplete packaged in a way I can use\nit in the browser, but has been significantly alterred.\n\nSee LICENSE for original copyright holder, changes are also released under the MIT license.\n","readmeFilename":"README.md"}