The math and algorithms behind a search library

Re:The math and algorithms behind a search library by JamesMcMinn on Saturday November 11, 2017 @12:46PM (#15677244)

This is a an interesting way of doing text search over a collection of documents, that I suppose makes sense if you only have a small number of documents to search.

Generally, an inverted index [1] is used rather than a trie, and collection-based term weights are calculated using something like IDF [2]. You could then use something like cosine to compute length normalised rankings for documents.

There are of course many different approaches to text search, but this is the first time I've personally come across this one.

If anyone is interested in an in depth look at how text search works, an Introduction to Information Retrieval [3] is available for free and is a fantastic book.

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

[2] https://en.wikipedia.org/wiki/Tf%E2%80%93idf

[3] https://nlp.stanford.edu/IR-book/

[ Parent | on HN ]

Re:The math and algorithms behind a search library by kbr on Saturday November 11, 2017 @01:02PM (#15677315)

This is how Wade was originally going to be implemented. I actually had a local version of it using an inverted index and a deterministic acyclic finite state automaton [1]. It was using TF-IDF as well for the rankings.

I began to experiment with a couple of my own ideas and used a trie rather than a DAFSA because it could be stored and loaded rather than generated at runtime. I also created and used the various linear methods described in the post to rank the documents.

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

[ Parent | on HN ]

Re:The math and algorithms behind a search library by mooneater on Saturday November 11, 2017 @08:05PM (#15679112)

Consider BM25 as a newer substitute for tf-idf https://en.wikipedia.org/wiki/Okapi_BM25

[ Parent | on HN ]