Skip to content

Instantly share code, notes, and snippets.

@programaths
Created December 23, 2023 17:18
Show Gist options
  • Save programaths/d54b2b3f9ec2b298a9e1914786768483 to your computer and use it in GitHub Desktop.
Save programaths/d54b2b3f9ec2b298a9e1914786768483 to your computer and use it in GitHub Desktop.
Dumb lookups
<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport"
content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Power Search</title>
<link rel="stylesheet" href="style.css">
<script type="module" src="main.js"></script>
</head>
<body>
<div><label for="lookup">Word search (466550 entries) </label><input type="search" id="lookup"></div>
<div id="names"></div>
</body>
</html>
let txt=await fetch('words.txt').then((r)=>r.text());
let names=txt.split("\n");
let field=document.body.querySelector('#lookup');
let namesDisplay=document.body.querySelector('#names');
field.addEventListener('input',()=>{
namesDisplay.innerHTML='';
if(field.value.length>0) {
const startTime = performance.now();
let filtered = names.filter((it) => it.includes(field.value));
const timeTaken = performance.now() - startTime;
namesDisplay.innerHTML += `<div>Took: ${timeTaken} ms</div>`
let i = 0;
while (i < 10 && i < filtered.length) {
const index = filtered[i].indexOf(field.value);
let prefix = filtered[i].substring(0, index);
let suffix = filtered[i].substring(index + field.value.length);
let match = filtered[i].substring(index, index + field.value.length);
namesDisplay.innerHTML += `<div>${encodeURI(prefix)}<strong>${encodeURI(match)}</strong>${encodeURI(suffix)}</div>`;
i++;
}
}
})
let txt=await fetch('words.txt').then((r)=>r.text());
let names=txt.split("\n");
class Trie {
constructor() {
this.root={children:{}};
}
/**
*
* @param string {string}
* @param index {number}
*/
addNodes(string,index){
let cn=this.root;
string=string+'$';
for(let c of string) {
if (cn.children.hasOwnProperty(c)){
cn=cn.children[c]
}else{
cn.children[c]={children: []}
}
}
if(Array.isArray(cn.indexes)){
cn.indexes.push(index)
}else {
cn.indexes = [index];
}
}
getIndexes(string,count){
let result=[];
let cn=this.root;
for(let c of string) {
if (cn.children.hasOwnProperty(c)){
cn=cn.children[c];
}else{
return result;
}
}
let q=[cn];
while (q.length>0 && count>0){
cn=q.pop();
if(Array.isArray(cn.indexes)){
result.push.apply(result,cn.indexes);
count=count-cn.indexes.length;
}
for(let child of Object.values(cn.children)){
q.push(child);
}
}
return result;
}
}
let trie=new Trie();
for(let [index,name] of names.entries()){
for(let i=0;i<name.length;i++) {
trie.addNodes(name.slice(i), index);
}
}
let field=document.body.querySelector('#lookup');
let namesDisplay=document.body.querySelector('#names');
field.addEventListener('input',()=>{
namesDisplay.innerHTML='';
if(field.value.length>0) {
const startTime=performance.now();
let indexes = trie.getIndexes(field.value,50);
let filtered = indexes.map((it) => names[it]);
let i = 0;
const timeTaken=performance.now()-startTime;
namesDisplay.innerHTML += `<div>Took: ${timeTaken} ms</div>`
while (i < 50 && i < filtered.length) {
const index = filtered[i].indexOf(field.value);
let prefix = filtered[i].substring(0, index);
let suffix = filtered[i].substring(index + field.value.length);
let match = filtered[i].substring(index, index + field.value.length);
namesDisplay.innerHTML += `<div>${encodeURI(prefix)}<strong>${encodeURI(match)}</strong>${encodeURI(suffix)}</div>`;
i++;
}
}
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment