Fast Concordance: Instant concordance on a corpus of >1,200 books

(iafisher.com)

52 points by evakhoury21 days ago

4 comments

simonw17 days ago
This is a neat brute-force search system - it uses goroutines, one for each of the 1,200 books in the corpus, and has each one do a regex search against the in-memory text for that book.Here's a neat trick I picked up from the source code:<pre><code> indices := fdr.rgx.FindAllStringSubmatchIndex(text, -1) for _, pair := range indices { start := pair[0] end := pair[1] leftStart := max(0, start-CONTEXT_LENGTH) rightEnd := min(end+CONTEXT_LENGTH, len(text)) // TODO: this doesn't work with Unicode if start > 0 && isLetter(text[start-1]) { continue } if end < len(text) && isLetter(text[end]) { continue } </code></pre> An earlier comment explains this:<pre><code> // The '\b' word boundary regex pattern is very slow. So we don't use it here and // instead filter for word boundaries inside `findConcordance`. // TODO: case-insensitive matching - (?i) flag (but it's slow) pattern := regexp.QuoteMeta(keyword) </code></pre> So instead of `\bWORD\b` it does the simplest possible match and then checks to see if the character one index before the match and or one index after the matches are also letters. If they are it skips the match.
- never_inline17 days ago
 Spinning 1K goroutines per request doesn't feel right to me for some reason.Isn't trigram search supposed to be better?<a href="https://swtch.com/~rsc/regexp/regexp4.html" rel="nofollow">https://swtch.com/~rsc/regexp/regexp4.html</a>
2b3a5117 days ago
It is, indeed, impressively fast. The results seem to be sorted by first name of author. Is that a deliberate choice?
est17 days ago
It's very fast, and the result aligning by keyword looks super cool.
drivebyhooting17 days ago
It seems to work at the word level.Why not use a precomputed posting list?
- mrkeen17 days ago
 Yeah I can't figure out if this is something the author stands by or if it's just a project to mess around with goroutines or something. And it's unfair to criticise if it isn't meant to be good.> The server reads all the documents into memory at start-up. The corpus occupies about 600 MB, so this is reasonable, though it pushes the limits of what a cloud server with 1 GB of RAM can handle. With 2 GB, it's no problem.1200 books per 1GB server? Whole-internet search engines are older than 1GB servers.> queries that take 2,000 milliseconds from disk can be done in 800 milliseconds from memory. That's still too slow, though, which is why fast-concordance uses [lots of threads]No query should ever take either of those amounts of time. And the "optimisation" is to just use more threads. Which other consumers could have used to run their searches, but now can't.<a href="https://www.pingdom.com/blog/original-google-setup-at-stanford-university/" rel="nofollow">https://www.pingdom.com/blog/original-google-setup-at-stanfo...</a>