3 ms·
The articles also discusses that it makes more complicated queries much easier to process. For instance, allowing regular expressions, or special character awar
by foota 10y ago
The articles also discusses that it makes more complicated queries much easier to process. For instance, allowing regular expressions, or special character aware searches.
- rakoo 10y agoIt is possible to index content and then retrieve it with (simple) regular expressions, see (https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html). The trick is that each regular expressions can be seen as a tree where leaves are n-grams to be searched for, and nodes are AND and OR logical operations of n-grams and intermediate nodes. So, a regexp like /banana/ can be seen as a search for the trigrams "ban" and "ana" and "nan" and "ana", all in that order. A regexp like /ca[tp]/ can be seen as a search for "cat" or "cap". Once you have simple n-grams like that it's trivial to index content on the way in (note that what you index doesn't actually need to interpret content, all you need is to split every n characters) and use that index to restrict potential matches.
- Retric 10y agoThis quickly falls down for searches like: /a[0-9][0-9][0-9]k[0-9][0-9][0-9]c