yarn install
yarn start
open https://localhost:8000
yarn run build:data
build:data generate 2 files.
{
"i":[ [0,4,1,5],[2,4,1,5], ....,
"w":["common","ostrich","somali", ...
}
That's a compressed representation of original data file. Index array has references to the Word
array in even positions and flags in odd ones. Flag can show that a word was capitalized, had hypen or space before.
A (trie)[https://en.wikipedia.org/wiki/Trie] structure. Keys are use (metaphone)[https://yomguithereal.github.io/clj-fuzzy/node.html#metaphone] to be typo agnostic. Nodes has references to the birds.json
indices.
Implemented trie algorithm has one improvement. Trie node has nodeThreshold parameter. If node has less than nodeThreshold refereces, it keep it inside that node. If it exceeded, it rebalance this node by creating subnodes, maintaining the same nodeThreshold value. This reduces size of trie.
Search algorithm split input text, then extract metaphones. Metaphones goes through trie using getRefsByPartialKey
and get a list of references to the words index using getWordsByRefs
.
Later rangeWordsWithDiceDistance
is used to extract actual words and using dice
distance metrics range words and sort it accordingly. A special heuristics is used to filter out false positive matches. Search has diceTreshold equal to 0.35. Any dice distance metric below that value becomes false positive and replaced by zero.
Mean of all dice instances is used to range entire word.