News for hackers. Stuff that matters.

A comment on The math and algorithms behind a search library. Parent comment

Re:The math and algorithms behind a search library by kbr on Saturday November 11, 2017 @02:31PM (#15677703)
This isn't an exact pattern searching library. Wade originally used Boyer-Moore, but has since switched to a trie [1] structure to search for _terms_ rather than the whole query.

This allows for result documents that can contain some of the terms, all of the terms, or a prefix of a term. It's also pretty fast as it doesn't need to run a linear search through the documents. I'm not sure what you mean by "classical" search algorithms, but a trie based search is a pretty standard way of doing it.

[1] https://en.wikipedia.org/wiki/Trie

[ Parent | on HN ]
Re:The math and algorithms behind a search library by stochastic_monk on Saturday November 11, 2017 @09:13PM (#15679328)
I understand, thank you. (Though a lot of inexact pattern matching is done with using exact pattern matching of substrings with the pidgeonhole principle.)

Tries led to suffix trees led to suffix arrays led to Burrows-Wheeler transform led to FM index, which is probably the best way to do an offline search.

If you haven't looked at BWT indexing, it's worth at least checking out. It preserves the advantages you speak of with linear memory cost with the search space. It's a lot more hairy to implement, unfortunately.

[ Parent | on HN ]
Re:The math and algorithms behind a search library by stochastic_monk on Sunday November 12, 2017 @12:40PM (#15681668)
A nice summary can be found here:

http://www.cs.jhu.edu/~langmea/resources/lecture_notes/bwt_a....

[ Parent | on HN ]