A search engine that favors text-heavy sites and punishes modern web design

Re:A search engine that favors text-heavy sites and punishes... by marginalia_nu on Friday September 17, 2021 @03:20AM (#28562269)

The trick is that the list of URLs for each word already is in the URLs file.

The URLs in a range are sorted. A sorted list (or list-range) forms an implicit set-like data structure, where you can do binary searches to test for existence.

Consider a words file with two words, "hello" and "world", corresponding to the ranges (0,3), (3,6). The URLs file contains URLs 1, 5, 7, 2, 5, 8.

The first range corresponds to the URLs 1, 5, 7; and the second 2, 5, 8.

If you search for hello world, it will first pick a range, the range for "hello", let's say (1,5,7); and then do binary searches in the second range -- the range corresponding to "world" -- (2,5,8) to find the overlap.

This seems like it would be very slow, but since you can trivially find the size of the ranges, it's possible to always do them in an order of increasing range-sizes. 10 x log(100000) is a lot smaller than 100000 x log(10)

[ Parent | on HN ]

Re:A search engine that favors text-heavy sites and punishes... by bullen on Sunday September 19, 2021 @06:24AM (#28583166)

Hm, ok I understand more but how do you perform the "binary search", just loop over the URL ids?

Funny I also selected "hello" and "world" above! Xo

My system is also written in Java btw!

Here are example results of my word search:

http://root.rupy.se/node/data/word/four

http://root.rupy.se/node/data/word/only

etc.

[ Parent | on HN ]

Re:A search engine that favors text-heavy sites and punishes... by marginalia_nu on Sunday September 19, 2021 @10:42AM (#28584703)

I'll get back to your email in a while, I've got a ton of messages I'm working through.

But yeah, in short pseudocode:

  for url in range-for-"hello":
    if binary-search (range-for-"world", url):
      yield url

I do use streams, but that is the bare essence of it.

[ Parent | on HN ]

Re:A search engine that favors text-heavy sites and punishes... by soheil on Tuesday September 21, 2021 @01:44AM (#28602340)

So every time you insert a new URL for a word you have to update the range for every other single word since the URL file will be shifted?

[ Parent | on HN ]

Re:A search engine that favors text-heavy sites and punishes... by soheil on Tuesday September 21, 2021 @01:00PM (#28607092)

Are the n-grams always at most n=2 bigrams?

[ Parent | on HN ]

Re:A search engine that favors text-heavy sites and punishes... by marginalia_nu on Tuesday September 21, 2021 @03:36PM (#28608954)

No, I actually count the n-grams as distinct words (up to 4-grams). The main limiter is for that is space, so I only extract "canned" n-grams from some tags.

I would first search for the bigram hello_world, that's an O(1) array lookup; as then documents merely containing the words hello and world (usually not a good search result), that's the algorithm I'm describing in the parent comment.

[ Parent | on HN ]

Re:A search engine that favors text-heavy sites and punishes... by soheil on Tuesday September 21, 2021 @04:09PM (#28609325)

Makes sense. Every time you insert a new URL for a word you have to update the ranges for every other word since the URL file will be shifted?

[ Parent | on HN ]