3 ms·

I took letter combinations aa ab ac ... zx zy zz z0 z1 z2 ... Created a file for each letter combination aa.dat ... zz.dat ... (26 letters + 10 digits) * (26 l

by 6510 6y ago

I took letter combinations aa ab ac ... zx zy zz z0 z1 z2 ... Created a file for each letter combination aa.dat ... zz.dat ... (26 letters + 10 digits) * (26 letters + 10 digits + space/wildcard) = 1369 Peanuts for Apache. Each of my 10 000ish articles got a single bit in those files where the offset is the article number. A search query like foo bar would involve the files " f", "fo", "oo", "o ", " b", "ba", "ar", "r " These are only 8 files! for a whooping 8 kb-ish of data. We then perform the AND operation. 0000000 01000000 00000000 Remaining articles are pulled [in reverse order] and checked for the presence of the exact phrase or the presence of keywords. The php then flushes '<br><a href="'.$articleNum.'.html">'.$title.'</a>' to the page. (I also did a version with a file with url's in it. Then the first url is article 1 or bit 1. Fun for stuff linked to from the blog) For longer articles one could make 3 digit files. 37x37x37 is little over 50 000 files. Each query only involves a few of those. Sadly one cant push bits to files but for a new article bits are to be appended to each data file eventually. I just add the new articles as false positives until I have a bunch of them. The advantage of the disadvantage in that each page has to be checked for the keywords is that if it is gone it wont show up in the results. Even a highly accurate search solution shall have false positives. http://blog.go-here.nl/search-blog.php?q=aliens http://blog.go-here.nl/search-blog.php?q=aliens view source for laughs

6510 6y ago
I forget to mention: All the articles are static html and the static data files can be parsed by js too.
compressedgas 6y ago
You have 2008 script tags on that page. I know why but you could have at least had them remove themselves from the DOM after they were done adding their content. > Sadly one cant push bits to files but for a new article bits are to be appended to each data file eventually. You can it is just that each of the files has to be padded out to a multiple of full bytes. Just read the last byte and OR in the new bit at its offset. The method you are using is called q-gram filtration. The main optimization you could do is to use the specificities of the grams to prioritize the ANDing so that the most specific grams are chosen first. This can allow early stopping for misses. You can also use multiple threads to read and AND in parallel after a AND tree order has been decided from the specificities. I would also remark that it is possible to implement approximate matching or error tolerant search with q-grams. That is to rank results according to edit distance or Levenshtein distance from the query. It is also possible to do regular expression search over them as Russ Cox explains how he implement the Google Code Search: Regular Expression Matching with a Trigram Index or How Google Code Search Worked https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html This is not specific to 3-grams. It can be made to work with any gram size or even indexes consisting of variable size grams.
- 6510 6y ago
  thanks! I had lots of ideas but chose to keep it simple enough to un-break brute force. Ideas: where letters are merged into one. Ones that appear to frequently (a,o,e are one letter) and/or rare ones (q is just a k). Ones that sit side by side on the keyboard (dootbell). Discard the order of the characters (so that "becuase" might just work) Typos that dont look like typos (1 is equal to l) and find ways to scale the solution to fit the texts or chunks thereof.
- 6510 6y ago
  > You have 2008 script tags on that page. I know why but you could have at least had them remove themselves from the DOM after they were done adding their content. Unless I've missed something I don't think it works like that. It is just a html document, it comes as is. If you modify the dom the source stays the same? Also, the html parser does a wonderful job ignoring things like comments and display:none nodes / script nodes. It just doesn't do anything with them. After the innerHTML is modified there is nothing further to do with each script. It is just ignored. I've tried things like adding a 5 mb comment to the end of a page to see the behavior.

by 6510 6y ago

6510 6y ago

I forget to mention: All the articles are static html and the static data files can be parsed by js too.

compressedgas 6y ago

You have 2008 script tags on that page. I know why but you could have at least had them remove themselves from the DOM after they were done adding their content. > Sadly one cant push bits to files but for a new article bits are to be appended to each data file eventually. You can it is just that each of the files has to be padded out to a multiple of full bytes. Just read the last byte and OR in the new bit at its offset. The method you are using is called q-gram filtration. The main optimization you could do is to use the specificities of the grams to prioritize the ANDing so that the most specific grams are chosen first. This can allow early stopping for misses. You can also use multiple threads to read and AND in parallel after a AND tree order has been decided from the specificities. I would also remark that it is possible to implement approximate matching or error tolerant search with q-grams. That is to rank results according to edit distance or Levenshtein distance from the query. It is also possible to do regular expression search over them as Russ Cox explains how he implement the Google Code Search: Regular Expression Matching with a Trigram Index or How Google Code Search Worked https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html This is not specific to 3-grams. It can be made to work with any gram size or even indexes consisting of variable size grams.

6510 6y ago
thanks! I had lots of ideas but chose to keep it simple enough to un-break brute force. Ideas: where letters are merged into one. Ones that appear to frequently (a,o,e are one letter) and/or rare ones (q is just a k). Ones that sit side by side on the keyboard (dootbell). Discard the order of the characters (so that "becuase" might just work) Typos that dont look like typos (1 is equal to l) and find ways to scale the solution to fit the texts or chunks thereof.
6510 6y ago
> You have 2008 script tags on that page. I know why but you could have at least had them remove themselves from the DOM after they were done adding their content. Unless I've missed something I don't think it works like that. It is just a html document, it comes as is. If you modify the dom the source stays the same? Also, the html parser does a wonderful job ignoring things like comments and display:none nodes / script nodes. It just doesn't do anything with them. After the innerHTML is modified there is nothing further to do with each script. It is just ignored. I've tried things like adding a 5 mb comment to the end of a page to see the behavior.