search

jnu / tiny-trie

JS Trie / DAWG classes
31 stars 4 forks source link

Fuzzy-matching / Prefix search #1

Closed thangngoc89 closed 6 years ago

thangngoc89 commented 7 years ago

Hi,

First of all, thank you very much for publishing such an awesome library. This is the best JS DAWG I could find on npm. Do you have any plan to implementing fuzzy-matching / prefix search? If you don't have the time, could you tell me the idea so I can implementing it?

Thanks in advance

jnu commented 6 years ago

hey @thangngoc89, I totally missed this. I implemented wildcard matching on these tries in a hacky way for a different project: https://github.com/jnu/crucible/blob/master/src/lib/readcross/FixedLengthWordIndex.js#L63

it's straightforward to implement: just rewrite the #test methods to use a BFS. When you see a wildcard instead of a literal, add all the children of a node to the search queue (otherwise just add the literal child, if it exists). #test returns a boolean indicating membership, in which case you can short-circuit when something is found; probably also want to add a new method #search that returns an array of matched words.

I can probably add this soon.