Last active
September 18, 2019 09:07
-
-
Save vaaas/4baba50d593ee5708ef5fbccb806a0ca to your computer and use it in GitHub Desktop.
trigram search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| let trigrams = null | |
| const $$ = q => [...document.querySelectorAll(q)] | |
| const lower_case = x => x.toLowerCase() | |
| const alnum_only = x => x.replace(/[^A-Za-z0-9]/g, "") | |
| function trigram(string) | |
| { const t = new Set() | |
| const gap = 3 | |
| string.split(" ") | |
| .filter(x => x.length >= 3) | |
| .forEach(x => | |
| { for (let i = 0; i + gap <= string.length; i++) | |
| t.add(string.slice(i, i+gap)) }) | |
| return t } | |
| const process = x => trigram(lower_case(alnum_only(x))) | |
| const elem_trigram_tuple = x => [x, process(x.innerText)] | |
| function push_create(obj, key, value) | |
| { if (obj[key]) obj[key].push(value) | |
| else obj[key] = [value] } | |
| function increment_create(map, key) | |
| { if (map.has(key)) map.set(key, map.get(key)+1) | |
| else map.set(key, 1) } | |
| function merge_sets(xs) | |
| { const obj = {} | |
| xs.forEach(([node, trigrams]) => | |
| trigrams.forEach(t => push_create(obj, t, node))) | |
| return obj } | |
| const elems_to_trigrams = xs => merge_sets(xs.map(elem_trigram_tuple)) | |
| const merge_results = (map, xs) => | |
| { xs.forEach(x => increment_create(map, x)) | |
| return map } | |
| function search(string, trigrams) | |
| { const query = [...process(string)] | |
| const results = query | |
| .map(x => x in trigrams ? trigrams[x] : []) | |
| .reduce(merge_results, new Map()) | |
| return [...results.entries()].map(x => [x[0], x[1]/query.length]) } | |
| const hide = x => x.style.display="none" | |
| const show = x => x.style.display="" | |
| const show_above = n => ([node, val]) => { if (val >= n) show(node) } | |
| function on_input(e) | |
| { if (trigrams === null) trigrams = elems_to_trigrams($$("li")) | |
| if (!this.value) return $$("li").forEach(show) | |
| else | |
| { $$("li").forEach(hide) | |
| search(this.value, trigrams).forEach(show_above(0.9)) }} | |
| function main() { | |
| document.querySelector("input").addEventListener("input", on_input) } | |
| window.onload = main |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment