Hacker News Reader

Comment by Herring | Hacker News Reader

Did anyone get the O(document size) solution? I can't see how it would work without checking each word against the list.

View on HN

Yet another approach: Translate the regular expression for the disjunction of the search terms into a DFA. Then traverse each document with the DFA to find all matches. Traversing a string of length n with a DFA takes O(n) time regardless of the DFA's size.

The DFA turns out to be basically the same thing as the trie. Indeed, the standard DFA construction factors out common prefixes of the search terms, just like a trie. But this formulation has the advantage that anyone can implement it in a few minutes with their language's regex library. In Python you might do something like this:

    def searcher(terms):
        pattern = r"(?:^|\s)(%s)(?:$|\s|,|\.|!|\?)"
        dfa = re.compile(pattern % ('|'.join(map(re.escape, terms)),))
        return lambda string: dfa.findall(string)

This snippet also tries to deal properly (if simplistically) with search term occurrences bracketed by whitespace and punctuation.

As a side note, the problem didn't specify whether matches could overlap. Actualy, it isn't even solvable in O(n) time (plus precomputation) if overlapping matches are allowed. Let's say the search terms are "a", "aa", "aaa", etc, and the search string consists of n copies of "a". Then every substring of the string is a match and so there are O(n^2) matches, which obviously cannot be listed in O(n) time.

Most regex libraries don't do determinization (perhaps awk or grep do, but perl doesn't).

You'll want to do better than just "use a trie" - like http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_mat...

Perl will actually use Aho-Corasick string matching for regular expressions like these.

Setup a hashtable of keyword -> wikipedia link.

Check every word in the document against it. One check per word should be O(word count) ish, shouldn't it?

Hashing every word will have a cost, but will be roughly the same for each word so I'll brush it aside as a constant, setting up the hash will have a cost, but shared over the number of documents to check. Checking every word sounds expensive but so does looking every word up in any data structure or searching every dictionary word in the document keywords and links have to be stored somehow.

My biggest hesitation is it can't be that easy or all you and the interviewer would be saying it, so I must be glossing over some big cost somewhere, right?

That works if each phrase is one word. Many (most?) of the terms in the vocabulary are multi-word phrases. How would your algorithm work for multiple word phrases? What is its running time?

It would have to be altered; let's see:

Create hashtable where the key is the first word and the value is (rest of sentence, link). In the case of collisions, a list of rest of sentences and links.

Checking the document would still go word by word, if no lookup fine, if one result compare the rest of phrase with the following document words, if a list, do that repeatedly.

Runtime varies a lot with distribution of input phrases - if there are 50,000 beginning "phospholipid" that's not good.

I don't know how to estimate the runtime well, best case is no matches or single word phrases, and then as above. Worst case is every document word matches a long list of phrase endings but none of them complete, but even then the searching is only searching a fraction of the phrases in len(longest-phrase) chars of the document.

O(doc_words * num_of_phrases_by_prefix * avg_phrase_length)

I'm uncomfortable here, wishing I had more algorithm/data knowledge to draw on, and maybe wouldn't have gone down this route had I paid attention to many words from the start. Every problem doesn't need a hashtable. Maybe phrase-trees...

In the case of collisions, you need to search for a bunch of possible rest-of-sentence phrases in the text. This is exactly the problem that your algorithm tries to solve! If you apply it recursively, you get, essentially, trie matching with words instead of characters.

http://en.wikipedia.org/wiki/Trie

There is some bunch searching, but most of the document doesn't get searched, and the bits which get searched aren't searched for most of the keyphrases.

Instead of:

    For phrase in keyphrases:
        If phrase in document:
            pass

This

    For word in document:
        Some_phrases = get_keyphrases_starting[word]
        if document.next_5_words.find(some_phrases)

Instead of searching 100,000 keyphrases in the whole document, this searches 10 rest-of-sentences in the 5 words following a mention of 'phospholipid', 18 rest-of-sentences in the 3 word following 'proteomerase' and nothing in the text about the lab temperature, and never touches most of the keyphrases at all for the document.

At first glance I don't think you can achieve O(document size) without some form of preprocessing. Each word in the vocabulary has to be looked at, so a natural lower boundary seems to be O(document size + vocabulary size).

Also it is unclear what will count as an atomic operation. Although the description reads as if word comparisons were counted, this makes for another simplification, as words could be of arbitrary size.

Also: I only checked the HN comment section to see if someone got the solution and I am amazed that others stuck to that part as well.

Yes, you use pre-processing.

I framed the problem in a very real-world scenario. Use that. It's not a trick question. How would you solve my real-world problem efficiently?

Thank you! This is Hacker News! Why isn't everyone trying to solve the problem?!

Use a bloom filter?

http://en.wikipedia.org/wiki/Bloom_filter

Set up a trie containing each phrase in the vocabulary. Repeatedly match phrases starting at the current word against the trie, stopping at the longest matching phrase. Link that and reset from the first non-matching word.

The end result is O(n) in the number of characters in the document.

Reply on news.ycombinator.com